Modified Gauss-Newton Algorithms under Noise
This work addresses algorithm selection for noisy optimization problems in machine learning, but it is incremental as it builds on existing methods with theoretical and experimental comparisons.
The paper investigates the performance of modified Gauss-Newton algorithms compared to gradient descent in noisy, large-scale statistical settings, finding that modified Gauss-Newton achieves quadratic convergence under specific noise regimes, while stochastic gradient descent is more versatile for nonsmooth composite objectives.
Gauss-Newton methods and their stochastic version have been widely used in machine learning and signal processing. Their nonsmooth counterparts, modified Gauss-Newton or prox-linear algorithms, can lead to contrasting outcomes when compared to gradient descent in large-scale statistical settings. We explore the contrasting performance of these two classes of algorithms in theory on a stylized statistical example, and experimentally on learning problems including structured prediction. In theory, we delineate the regime where the quadratic convergence of the modified Gauss-Newton method is active under statistical noise. In the experiments, we underline the versatility of stochastic (sub)-gradient descent to minimize nonsmooth composite objectives.