Source-linked AI summary
Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information
Majid Jahani, Sergey Rusakov, Zheng Shi, Peter Richtárik, Michael W. Mahoney, Martin Takáč
TL;DR
Large-scale empirical risk minimization is difficult when sample counts and dimensions are large and the loss may be nonconvex. OASIS scales gradient information using an estimated Hessian diagonal and automatically updates its learning rate. The paper reports competitive or superior performance against many state-of-the-art first- and second-order methods.
Problem
Empirical risk minimization can be difficult when the number of training samples and the model dimension are large and the loss is potentially nonconvex.
Source: §1 · p. 1Method
OASIS uses a well-scaled Hessian-diagonal approximation to precondition gradient information and updates the learning rate automatically from a local Lipschitz-smoothness approximation.
Source: §1 · p. 2Results
OASIS consistently shows competitive or superior performance compared with many state-of-the-art first- and second-order methods on standard machine-learning tasks.
Source: §1 · p. 3Takeaways & Limitations
OASIS offers a fully adaptive approach to empirical risk minimization, with theoretical results covering convex, strongly convex, and nonconvex settings.
Source: §6 · p. 10The paper leaves convergence theory for the stochastic regime with adaptive learning rates to future work.
Source: §6 · p. 10
Abstract
from arXiv · showhide
We present a novel adaptive optimization algorithm for large-scale machine learning problems. Equipped with a low-cost estimate of local curvature and Lipschitz smoothness, our method dynamically adapts the search direction and step-size. The search direction contains gradient information preconditioned by a well-scaled diagonal preconditioning matrix that captures the local curvature information. Our methodology does not require the tedious task of learning rate tuning, as the learning rate is updated automatically without adding an extra hyperparameter. We provide convergence guarantees on a comprehensive collection of optimization problems, including convex, strongly convex, and nonconvex problems, in both deterministic and stochastic regimes. We also conduct an extensive empirical evaluation on standard machine learning problems, justifying our algorithm's versatility and demonstrating its strong performance compared to other start-of-the-art first-order and second-order methods.
1 Introduction
Large-scale empirical risk minimization can be difficult when the sample count and dimension are large and the loss is potentially nonconvex. OASIS combines a curvature-scaled gradient direction with an automatically updated learning rate.
1 Introduction
- First-order methods are prevalent but sensitive to learning-rate choices, affected by ill-conditioning, and potentially communication-limited in distributed settings.The paper relates these drawbacks to first-order updates using gradient information alone.Source: §1 · p. 1
- Newton-type and quasi-Newton methods use curvature to scale gradients, but Newton methods can require up to O(d^2) memory and O(d^3) computation.Stochastic curvature estimates can be noisy, and AdaHessian's diagonal preconditioner may poorly approximate the true Hessian-diagonal scale.Source: §1 · pp. 1–2
- OASIS estimates the Hessian diagonal so its scale more closely matches the true diagonal, then uses that curvature estimate to scale gradient components.Figure 1 compares diagonal-estimation relative error and estimated-versus-true scale for OASIS and AdaHessian.Source: §1 · p. 2, Figure 1 · p. 2
- OASIS updates its learning rate automatically from a local approximation of Lipschitz smoothness, avoiding learning-rate tuning.The adaptive rate and preconditioner together form a fully adaptive parameter-update step.Source: §1 · p. 2
- The paper reports convergence guarantees for several convexity and learning-rate settings, alongside competitive or superior results on standard machine-learning tasks.The introduction lists logistic regression, nonlinear least squares, and image classification among the evaluation tasks.Source: §1 · pp. 2–3
2 Related Work
Related work moves from gradient-based adaptive preconditioning toward methods that use curvature to scale the search direction. OASIS addresses two remaining challenges: AdaHessian’s Hessian-diagonal scale and manual learning-rate tuning, including under weighted Euclidean norms.
Gradient-based adaptive methods
- Adagrad scales gradients using accumulated squared gradients, while its growing preconditioner can rapidly shrink the learning rate.RMSProp uses an exponentially decaying average to prevent that rapid increase; Adam [21] also tracks a first-moment estimate.Source: §2 · pp. 3–4
Generic preconditioned updates
- The generic update rotates and scales gradient information using the inverse preconditioning matrix; SGD uses the identity matrix.Momentum smooths gradient estimates over past iterations and can be useful in noisy settings.Source: §2 · p. 3
Curvature-based methods
OASIS motivation
- AdaHessian’s preconditioner does not closely approximate the scale of the true Hessian diagonal, motivating a better-scaled curvature estimate.The passage also notes that learning rates remain manually tuned for curvature-based methods, while extending an adaptive rule to weighted Euclidean norms is nontrivial.Source: §2 · pp. 4–5
3 OASIS
OASIS uses a Hessian-diagonal estimate to precondition gradient information and updates the learning rate adaptively. Its deterministic and stochastic variants share this approach, with stochastic updates using mini-batches and initialization using sampled curvature estimates.
3.1 Deterministic OASIS
- OASIS uses curvature information to precondition gradients and updates its learning rate automatically; its deterministic algorithm forms curvature estimates with Hutchinson’s method.The Hessian-diagonal estimate is exponentially averaged and truncated by a positive value α to define the preconditioning matrix; the adaptive learning-rate rule uses gradient and curvature information.Source: §3.1 · p. 5
- The deterministic OASIS update can recover the algorithm in [26] by setting β2 = 1, α = 1, and D0 = Id.The adaptive-learning-rate analysis with weighted Euclidean norms is described as non-trivial.Source: §3.1 · p. 5
3.2 Stochastic OASIS
- The stochastic variant uses small training-data mini-batches to compute gradient and Hessian-diagonal information for each update.Its curvature estimate uses the Hessian on a mini-batch, and the preconditioning matrix is a truncated variant of that estimate.Source: §3.2 · p. 6
3.3 Warmstarting and Complexity of OASIS
- Both variants initialize the Hessian-diagonal estimate by sampling Hutchinson estimates before training.This initialization matters because the adaptive learning-rate rule depends on the curvature estimate; Hessian-vector products are the method’s main overhead and can be calculated with two back-propagation rounds.Source: §3.3 · p. 6
4 Theoretical Analysis
The analysis establishes OASIS convergence guarantees for adaptive and fixed learning rates across deterministic and stochastic settings. The results include linear convergence for smooth strongly convex objectives and convergence to stationary-point neighborhoods in stochastic settings.
4 Theoretical Analysis
- The analysis covers adaptive, fixed, and line-search learning-rate settings, with proofs and auxiliary lemmas provided in Appendix A.The results rely on stated smoothness, differentiability, and strong-convexity assumptions where applicable.Source: §4 · p. 6
4.1 Adaptive Learning Rate
- Under the adaptive learning-rate rule, OASIS has a convergence guarantee, with a linear contraction bound for smooth strongly convex objectives under stated conditions.The theorem’s contraction applies when β2 satisfies the stated lower bound.Source: §4.1 · pp. 6–7
4.2 Fixed Learning Rate
- The fixed-learning-rate analysis bounds the diagonal preconditioner between αI and ΓI and covers deterministic and stochastic regimes.The stated bound is αI ⪯ D̂k ⪯ ΓI, with 0 < α ≤ Γ.Source: §4.2 · p. 7
4.2.1 Deterministic Regime
- In the deterministic regime, the theorems give linear convergence for smooth strongly convex losses and convergence to stationary points for nonconvex losses.The nonconvex result assumes the objective is bounded below.Source: §4.2.1 · p. 7
4.2.2 Stochastic Regime
- In the stochastic regime, smooth strongly convex losses converge to a neighborhood of the optimum, while nonconvex results converge to stationary-point neighborhoods.Variance-reduced gradients or a decaying learning rate can establish convergence to stationary points in expectation.Source: §4.2.2 · pp. 7–8
5 Empirical Results
OASIS is evaluated against first- and second-order methods across logistic regression, nonlinear least squares, and image classification. The reported results range from performance on par with or better than competitors to CIFAR100 results surpassing them.
5 Empirical Results
- The evaluation covers strongly convex logistic regression, nonconvex nonlinear least squares on rcv1 and ijcnn16, and image classification on MNIST, CIFAR10, and CIFAR100.The experiments compare OASIS with diagonal-preconditioner methods; stochastic comparisons include SGD, Adam, AdamW, and AdaHessian.Source: §5 · pp. 8–9
5.1 Logistic Regression
- For logistic regression, OASIS with adaptive learning rate and no hyperparameter tuning performs on par with or better than the other methods.Source: §5.1 · p. 9
5.2 Non-linear Least Square
- On nonlinear least squares, OASIS outperforms the other methods in training loss and test accuracy, and its behavior is robust across initial points.Source: §5.2 · p. 9
5.3 Image Classification
- On CIFAR100/ResNet-18, fully adaptive OASIS without hyperparameter tuning surpasses the compared state-of-the-art methods; CIFAR10 OASIS variants finish on par with or better than competitors.On CIFAR10, fixed-rate OASIS performs better than Adam and comparably to SGD; momentum improves early training, and all three variants achieve satisfactory final results.Source: §5.3 · pp. 9–10, Figure 5 · p. 10, Table 2 · p. 10
6 Final Remarks
OASIS combines a Hessian-diagonal-scaled search direction with an automatically updated learning rate. The paper reports theoretical results across standard optimization settings and identifies further stochastic-theory and empirical work as future directions.
6 Final Remarks
- OASIS uses a Hessian diagonal approximation to scale gradient information and updates its learning rate automatically using a low-cost approximation of Lipschitz smoothness.The paper describes the Hessian diagonal estimate as efficiently calculable and storable.Source: §6 · p. 10
A.1 Assumptions
- The listed analysis assumptions include Lipschitz-continuous gradients, twice continuous differentiability, strong convexity, a lower bound on the objective, and unbiased stochastic gradients.Source: §A.1 · p. 14
A.2 Proof of Lemma 4.5
- Lemma 4.5 addresses a bound on the change of Dk under the smoothness assumption.Source: §A.2 · p. 14
A.3 Lemma Regarding Smoothness with Weighted Norm
- The weighted-norm smoothness lemma sets the smoothness constant to ˜L = L λmin(D) for positive definite D.Source: §A.3 · pp. 14–15
A.4 Proof of Theorem 4.6
- The proof of Theorem 4.6 uses a telescoping inequality and the adaptive learning-rate rule to establish its stated result for the generated iterates.Source: §A.4 · pp. 17–18
A.5 Proof of Lemma 4.8
- Lemma 4.8 bounds ηk under the stated smoothness, differentiability, and strong-convexity assumptions.Source: §A.1 · p. 14, §A.5 · p. 18
A.6 Proof of Theorem 4.9
Theorem 4.9 concerns iterates under smoothness and strong convexity, with a unique minimizer. Its proof tightens a condition to obtain a linear-convergence recursion.
A.6 Proof of Theorem 4.9
- Theorem 4.9 assumes smoothness and strong convexity and considers iterates converging toward a unique solution.Source: §A.6 · p. 21
- A stricter inequality on β2 is introduced to obtain a recursion that permits a linear convergence rate.Source: §A.6 · p. 22
- The proof describes contraction across terms, including function-value differences.Source: §A.6 · p. 22
A.7 Proof of Theorem 4.11
Theorem 4.11 states a result for iterates on a strongly convex, smooth objective with a unique minimizer, using a fixed learning rate bounded by α2/(LΓ).
A.7 Proof of Theorem 4.11
- Under smoothness and strong convexity, Theorem 4.11 considers a unique minimizer and fixed η satisfying 0 < η ≤ α2/(LΓ).Source: §A.7 · p. 23
A.8 Proof of Theorem 4.13
The proof invokes Theorem 4.13 under its stated assumptions and establishes a bound for every T > 1. Its displayed inequality relates the learning-rate bound to accumulated gradient norms and the initial objective gap.
A.8 Proof of Theorem 4.13
- Theorem 4.13 applies when Assumptions 4.3, 4.12, and 4.2 hold, for iterates generated by the algorithm and every T > 1.The theorem's conclusion is not fully present in the supplied passages.Source: §A.8 · p. 23
- The proof starts from (47), sums the inequality over k = 0 to T −1, and simplifies the left-hand side using ˆF ≤ F(wT).The passages describe these proof steps but do not include the full intermediate inequalities.Source: §A.8 · p. 23
A.9 Proof of Theorem 4.17
The appendix gives convergence results for OASIS under stated assumptions, describes line-search and stochastic variants, and outlines efficient Hessian-vector computations. It also specifies evaluation conventions and reports that the method can operate on high-dimensional ResNet problems.
A.9 Proof of Theorem 4.17
- Theorem 4.17 and Theorem A.5 both assume Assumptions 4.2, 4.3, 4.4, 4.15, and 4.16 and concern Algorithm 1 iterates; A.5 also imposes parameter conditions.Source: §A.9 · pp. 24–25
A.11 Proofs with Line Search
- Armijo backtracking accepts a trial step when it meets the sufficient-decrease condition and otherwise reduces the step length by a factor τ.The step uses p_k = −ˆD_k⁻¹∇F(w_k), with c1 and τ in (0, 1).Source: §A.11 · p. 27
A.11.1 Determinitic Regime - Strongly Convex
- Theorem A.7 considers iterates generated by Algorithm 1, with ηk the maximum τ−j for j = 0, 1, … satisfying (61), where 0 < c1 < 1, from starting point w0.It assumes Assumptions 4.3, 4.2, and 4.4.Source: §A.11.1 · p. 27
A.11.2 Deterministic Regime - Nonconvex
- Under Assumptions 4.3, 4.12, and 4.2, Theorem A.8 considers Algorithm 1 iterates with ηk selected as the maximum qualifying τ−j, where 0 < c1 < 1, and signals a further statement for any T > 1.Source: §A.11.2 · p. 28
B.1 Related Work
- The appendix points to Table 3 as a summary of the methodologies discussed in Section 2.The supplied passages identify the table's purpose but do not provide its entries.Source: §B.1 · p. 29, Table 3 · p. 29
B.2 Stochastic OASIS
- Stochastic OASIS uses mini-batches; its experiments reuse the sampled batch for gradient and Hessian-vector calculations to reduce overhead.The description also offers warmstarting or a bias-corrected rule to obtain the initial Hessian-diagonal estimate.Source: §B.2 · p. 30
B.3 Efficient Hessian-vector Computation
- For deep learning, the Hessian-vector product needs one additional back-propagation round beyond the gradient calculation, at almost one gradient-evaluation cost.For logistic regression, the calculation avoids explicitly constructing the Hessian.Source: §B.3 · p. 31
C.1 Table of Algorithms
- The appendix defines the logistic-regression optimality gap using a solution found by TR Newton-CG and notes OASIS operates on high-dimensional ResNets.The cited problem-details passage frames this as contrary to a widespread belief about second-order methods and dimensionality.Source: §C.1 · p. 32, §C.2 · p. 32
C.3.1 Problem and Data
The experiments use five LIBSVM binary-class datasets to study strongly convex regularized logistic regression and nonconvex nonlinear least squares. The algorithm comparisons vary method-specific parameters and use ten initializations per configuration.
C.3.1 Problem and Data
- The experiments use ijcnn1, rcv1, news20, covtype, and real-sim, with default or randomly split train/test samples.The datasets are described as popular LIBSVM binary-class datasets.Source: §C.3.1 · pp. 32–33, Table 6 · p. 33
- The study compares regularized logistic regression, which is strongly convex for λ > 0, with nonlinear least squares, which is nonconvex.The logistic-regression experiment uses λ ∈ {0.1/n, 1/n, 10/n}.Source: §C.3.1 · p. 33
C.3.2 Configuration of Algorithm
- OASIS, AdGD, and AdaHessian were tested across multiple parameter choices, and each method, dataset, and problem used ten random initializations.OASIS varied β2 and α and used a warm-start Hessian-diagonal estimate; AdGD and AdaHessian used multiple learning rates.Source: §C.3.2 · p. 33
C.3.3 Extended Experimental Results
The extended experiments track optimization and test-accuracy metrics across binary-classification datasets and image-classification tasks. CIFAR10 table results describe OASIS variants as competitive, while CIFAR100 and MNIST passages report robustness and training or test-accuracy patterns.
C.3.3 Extended Experimental Results
- The logistic-regression plots show optimality-gap evolution and ending gaps, alongside testing-accuracy evolution and maximum testing accuracy.The experiments are described as repeated from ten different initial points.Source: §C.3.3 · p. 33
- The nonlinear least-squares plots show objective evolution and ending values, as well as testing-accuracy evolution and maximum testing accuracy.Figure 10 covers objective values and Figure 11 covers testing accuracy across the stated datasets.Source: §C.3.3 · p. 33, Figure 10 · p. 36, Figure 11 · p. 36
C.4.1 CIFAR10
- OASIS with fixed learning rate beats or matches other methods with weight decay, while its adaptive variant is a consistent close second without weight decay.Table 7 covers ResNet20 and ResNet32 on CIFAR10 under both weight-decay settings.Source: Table 7 · p. 38
C.4.3 MNIST
- On MNIST, OASIS with momentum has the lowest training loss and test accuracy comparable to the best, with and without weight decay.The adaptive OASIS variant also obtained satisfactory results with fewer parameters requiring tuning.Source: §C.4.3 · pp. 39, 41, Table 9 · p. 41
C.4.2 CIFAR100
- For CIFAR100, transferring CIFAR10 ResNet20 settings without further tuning damages optimizer performance, while adaptive OASIS is robust to random-seed choice without weight decay.The comparison is reported in Table 8 for ResNet18 on CIFAR100.Source: Table 8 · p. 40
C.5 Sensitivity Analysis of OASIS
Sensitivity analyses show that OASIS is robust to tested hyperparameter settings in both deterministic and stochastic settings, although some stochastic hyperparameters require tuning. On image-classification tasks, its results remain comparable to other state-of-the-art first- and second-order approaches with less tuning effort.
C.5 Sensitivity Analysis of OASIS
- In the deterministic setting, OASIS requires no sensitive tuning and remains robust when its other hyperparameters are not perfectly hand-tuned.Figures 16 and 17 show sensitivity analyses for deterministic logistic regression and nonlinear least squares.Source: §C.5 · p. 41, Figure 16 · p. 42, Figure 17 · p. 43
- Across stochastic image-classification settings, OASIS remains robust to tested hyperparameter choices, with a narrow performance range and results comparable to state-of-the-art first- and second-order approaches.Some hyperparameters still require tuning, but the reported results remain acceptable when settings are not properly tuned.Source: §C.5 · p. 41
- For CIFAR10 on ResNet20, OASIS is robust to learning-rate choices while SGD is highly sensitive, possibly because OASIS scales gradient components by local curvature.Figure 18 compares learning-rate sensitivity; the authors offer well-scaled preconditioning as a possible explanation for the contrast.Source: §C.5 · pp. 41–42, Figure 18 · p. 43
- OASIS remains robust across γ values on CIFAR10 with ResNet20, unlike the behavior reported in.The authors report similar behavior for other network architectures.Source: §C.5 · p. 42, Figure 19 · p. 44
- OASIS is robust across the tested β2 values on CIFAR100 with ResNet18.Figure 20 presents this sensitivity analysis.Source: §C.5 · p. 42, Figure 20 · p. 44