Source-linked AI summary
Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
Peng Xu, Farbod Roosta-Khorasani, Michael W. Mahoney
TL;DR
First-order methods face convergence, tuning, stagnation, and saddle-point difficulties in non-convex ML. The paper empirically evaluates sub-sampled TR and ARC methods using curvature approximations and finds them computationally competitive, robust to hyper-parameters, and able to escape saddle regions. The study also reports an implementation limitation for Algorithm 2 and characterizes the evidence as an initial empirical glimpse.
Problem
First-order ML optimizers can converge slowly, depend on hyper-parameters, stagnate, and struggle to escape flat regions and saddle points in highly non-convex problems.
Method
The paper empirically evaluates sub-sampled trust-region and adaptive cubic-regularization methods with approximate curvature on non-convex ML problems.
Results
Sub-sampled Newton-type methods can be computationally competitive with hand-tuned SGD with momentum, robust to hyper-parameter tuning, and able to escape regions near saddle points.
Takeaways & Limitations
Curvature information provides practical advantages over first-order alternatives in the evaluated non-convex ML settings, particularly for computational cost, tuning robustness, and saddle-region escape.
Takeaways & Limitations
Algorithm 2 was excluded from Section 3.2 because the authors could not obtain its expected performance and could not identify whether the sub-problem solver caused the issue.
Abstract
from arXiv · showhide
While first-order optimization methods such as stochastic gradient descent (SGD) are popular in machine learning (ML), they come with well-known deficiencies, including relatively-slow convergence, sensitivity to the settings of hyper-parameters such as learning rate, stagnation at high training errors, and difficulty in escaping flat regions and saddle points. These issues are particularly acute in highly non-convex settings such as those arising in neural networks. Motivated by this, there has been recent interest in second-order methods that aim to alleviate these shortcomings by capturing curvature information. In this paper, we report detailed empirical evaluations of a class of Newton-type methods, namely sub-sampled variants of trust region (TR) and adaptive regularization with cubics (ARC) algorithms, for non-convex ML problems. In doing so, we demonstrate that these methods not only can be computationally competitive with hand-tuned SGD with momentum, obtaining comparable or better generalization performance, but also they are highly robust to hyper-parameter settings. Further, in contrast to SGD with momentum, we show that the manner in which these Newton-type methods employ curvature information allows them to seamlessly escape flat regions and saddle points.
1 Introduction
The paper evaluates whether sub-sampled Newton-type methods can address first-order methods’ convergence, tuning, stagnation, and saddle-point challenges in non-convex ML while remaining computationally competitive. Experiments use MLPs and NLS problems to compare these methods with first- and second-order alternatives.
- First-order methods are widely used for ML but can converge slowly, depend sensitively on hyper-parameters, stagnate at high training error, and struggle near saddle points.
- The study evaluates sub-sampled trust-region and adaptive cubic-regularization methods that approximate curvature in non-convex ML problems.
- The experiments focus on MLP networks for comparisons with first-order methods and on NLS problems for studying sub-sampling and second-order-method comparisons.
- Computational efficiency is assessed through convergence speed over total computational cost, while hyper-parameter robustness is tested across multiple choices of each method’s main parameter.
- The study also examines saddle-point behavior through varied initializations and evaluates generalization using test performance across experiments.
2 Background
The paper formulates non-convex ML as finite-sum optimization and develops sub-sampled trust-region and ARC methods using approximate Hessians. Randomized sampling reduces computational cost, while informative sampling and inexact subproblem solutions further support large-scale use.
- The optimization objective is a finite sum of smooth, possibly non-convex per-observation loss functions, with empirical risk serving as the ML objective.
- Near saddle points, line search can be ineffective because small gradients may produce iterates that remain stuck, motivating trust-region and cubic-regularization alternatives.
- Sub-sampled TR and ARC use an approximate Hessian and approximately solve their trust-region or cubic-regularized subproblems.
- Randomly sampling a subset of indices can provide significant computational savings when the sample is much smaller than the full dataset.
- For suitable finite-sum problems, informative nonuniform sampling can use smaller sample sizes than oblivious uniform sampling, while inexact subproblem solves avoid a large-scale computational bottleneck.
3 Numerical Experiments
The experiments compare sub-sampled trust-region and related second-order methods with Gauss-Newton and momentum SGD across neural-network and non-linear least-squares problems. Sub-sampled trust-region methods are competitive in computational efficiency and generalization, more robust to key hyper-parameters, and better able to escape flat or saddle regions in several settings.
- Experimental setup: The experiments evaluate sub-sampled trust-region, Gauss-Newton, and momentum-SGD methods on one-hidden-layer classifiers, deep autoencoders, and non-linear least-squares problems.The study measures convergence using total propagations and also examines initialization, hyper-parameter robustness, generalization, and sub-sampling strategies.
- Hyper-parameter robustness: Trust-region performance remains comparable across substantially different initial trust-region radii, whereas SGD is highly dependent on its learning rate.For SGD, overly small step sizes slow convergence, while overly large step sizes can cause divergence or poor generalization.
- Escaping flat and saddle regions: From zero initialization, sub-sampled trust-region methods continue progressing through flat or saddle regions where SGD and Gauss-Newton can become trapped.The reported explanation is that trust-region methods effectively use Hessian information to escape regions with extremely small gradients.
- Generalization: Sub-sampled trust-region methods obtain competitive or better generalization performance across the neural-network initialization schemes.They achieve similar test errors to other methods in some autoencoder experiments and clearly outperform them in others.
- Computational efficiency: Sub-sampled trust-region methods achieve computational performance comparable to or better than momentum SGD across the neural-network experiments.On CIFAR10, trust-region training can be slightly slower than appropriately tuned SGD, while on deep autoencoders it converges comparably fast or faster in propagations.
- Non-linear least squares: For non-linear least-squares classification, sub-sampling can improve efficiency, but overly small samples can hurt performance.Non-uniform sampling benefits Algorithm 2 more strongly than Algorithm 1, partly because their subproblem solvers require different numbers of Hessian-vector products.
- Comparison among second-order methods: L-BFGS performs poorly across the tested datasets, while Gauss-Newton works well with random initialization but poorly from all-ones initialization.The paper attributes these differences to whether methods capture negative-curvature information needed to escape regions with small gradients; ARC is consistently no better than TR.
4 Conclusion
The study finds that sub-sampled Newton-type methods can be computationally competitive, robust to hyper-parameters, effective for escaping saddle points, and beneficial for generalization. These advantages depend on empirical evidence that remains limited in scope and includes an unresolved performance issue for Algorithm 2.
- Computational Efficiency: Randomized sub-sampling combines low per-iteration cost with fewer curvature-informed iterations, making Newton-type methods competitive with SGD with momentum.The paper attributes this efficiency to the amortized combination of randomized sampling and curvature information.
- Robustness to Hyper-parameters: The proposed Newton-type methods exhibit strong robustness to hyper-parameter tuning compared with first-order algorithms.The paper identifies step-size as a particularly influential first-order hyper-parameter.
- Escaping Saddle Point: Hessian information allows Newton-type algorithms to escape regions near saddle points, unlike many first-order alternatives.The paper describes this as a seamless escape from saddle-point regions.
- Generalization Performance: Second-order methods can achieve very good prediction accuracy after only a few iterations, benefiting generalization and communication-limited distributed settings.The stated distributed benefit follows from reducing communication across the network.
- Benefits of Sub-sampling: On several real datasets, sub-sampled Newton-type methods speed computation relative to classical versions, while non-uniform sampling outperforms uniform sampling.The study also reports advantages of sub-sampled trust-region and ARC methods over L-BFGS and GN in exploiting curvature.
- Limitations: The empirical conclusions are bounded by an unresolved performance problem for Algorithm 2 and by the study’s proof-of-concept scope.The authors could not identify the source of Algorithm 2’s underperformance and characterize the experiments as only a glimpse of the methods’ properties.
A Image Classification with Cifar10
The Cifar10 experiments evaluate sensitivity to random initialization by comparing repeated runs of Algorithm 1 and SGD with momentum under fixed configurations. Across these runs, the algorithms showed little sensitivity to the random seed.
- Experimental Setup: Ten runs of Algorithm 1 and SGD with momentum used different random seeds while keeping the configuration fixed.The runs began from normalized random initialization in the associated figures.
- Sensitivity to Random Seeds: The algorithms showed little sensitivity to random seed across the repeated experiments.The reported evaluation varied initialization seeds rather than the algorithmic configuration.
- Sensitivity to Random Seeds: The figures compare multiple runs of SGD and Algorithm 1 under random initialization to assess run-to-run variation.The figure descriptions specify different random seeds for both methods.
B Non-Linear Least Squares
The non-linear least-squares experiments examine sub-sampling strategies for TR and ARC methods on binary-classification datasets. The figures show that sampling effects depend on the method and dataset, with non-uniform sampling often reducing convergence time or sensitivity to sample size.
- Experimental Setup: The experiments compare 1% and 5% training-data subsampling ratios across additional datasets.The setup applies these ratios to all sub-sampling methods.
- Datasets: mnist2 labels even digits as 1 and odd digits as 0, while mnist-28 contains only digits 2 and 8.These dataset definitions specify the binary-classification tasks used in the figures.
- a9a: On a9a, sub-sampled TR and ARC methods converge faster than their full-data counterparts, while increasing the sample size does not appear helpful.TR Uniform and TR Non-Uniform perform similarly, as do ARC Uniform and ARC NonUniform.
- mnist-28: On mnist-28, non-uniform sampling is at least as fast as uniform sampling for the sub-sampled methods.Increasing the sample size from 1% to 5% substantially affects uniform-sampling performance, particularly for ARC variants.
- mnist2: On mnist2, ARC Full outperforms ARC Uniform at 1%, whereas ARC Non-Uniform converges faster than ARC-Full at 5%.The figure suggests that 1% may be too small for uniform sampling, while non-uniform sampling appears less affected by sample-size changes.
- ijcnn1: The ijcnn1 comparison varies initialization between all-ones and random settings and reports propagation count on a logarithmic x-axis.The figure uses the number of propagations as its horizontal measure.