Research map / Optimization / Nonconvex and smooth optimization
Advancing the Lower Bounds: an Accelerated, Stochastic, Second-order Method with Optimal Adaptation to Inexactness
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an accelerated stochastic cubic-Newton method with inexact gradient/Hessian oracles and a verifiable subproblem-gradient tolerance, plus a tensor generalization, and proves matching lower bounds for stochastic second-order methods.
Problem
Global convergence of second-order convex optimization when gradients and Hessians are stochastic or inexact, including the optimal trade-off between gradient and Hessian inexactness and inexact subproblem solutions.
Approach
Combines estimating-sequence acceleration with cubic regularization and an extra quadratic regularizer whose coefficient grows with iteration count, so stochastic gradient noise decays as 1/sqrt(T) while Hessian noise enters at 1/T^2; subproblems are solved to a verifiable gradient-norm tolerance tau.
Key results
- The proposed method achieves O(sigma1 R/sqrt(T) + sigma2 R^2/T^2 + L2 R^3/T^3) under stochastic Hessian, improving the T^{3/2} Hessian term of Extra-Newton.
- Lower bounds Omega(sigma1 R/sqrt(T)), Omega(sigma2 R^2/T^2) and Omega(L2 R^3/T^{7/2}) are established for stochastic second-order methods, matching the upper bounds in gradient and Hessian variance terms.
- On logistic regression (a9a), the method consistently outperforms Extra-Newton and SGD in deterministic and stochastic settings, with fewer stochastic Hessian than gradient computations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Accelerated Stochastic Cubic Newton instead of Extra-Newton | Convex minimization with stochastic gradient and Hessian · Stochastic gradient and Hessian feedback | Hessian convergence rate: O\ls \frac{\sigma_2 R^2}{T^{3/2}} \rs -> O\ls \frac{\sigma_2 R^2}{T^2} \rs | Helped |
| Use Accelerated Stochastic Cubic Newton instead of Extra-Newton | Convex minimization with stochastic gradient and Hessian · Stochastic gradient and Hessian feedback | gradient convergence rate: O\ls\frac{\sigma_1 R}{\sqrt{T}}\rs -> O\ls\frac{\sigma_1 R}{\sqrt{T}}\rs | No clear effect |
| Use Accelerated Stochastic Cubic Newton instead of Extra-Newton | Convex minimization with stochastic gradient and Hessian · Exact-oracle convergence term | exact convergence rate: O\ls \frac{L_2 R^3}{T^3} \rs -> O\ls \frac{L_2 R^3}{T^3} \rs | No clear effect |
| Replace Extra-Newton with Accelerated Stochastic Cubic Newton | Logistic regression on a9a · a9a train and test loss | loss | Helped |
| Use smaller Hessian batches relative to gradient batches | Accelerated Stochastic Cubic Newton · Logistic regression on a9a with stochastic oracles | loss | Mixed |
| Improve stochastic-gradient computation complexity over Accelerated Inexact Tensor Method | Stochastic second-order optimization with p=2 · Stochastic gradient computations | computation complexity: O(\e^{-7/3}) -> O(\e^{-2}) | Helped |
Surprising findings
- Hessian stochasticity can be handled with a much smaller batch than gradients, since the Hessian noise term decays as 1/T^2 versus 1/sqrt(T) for gradients.
Limitations
- Lower bound does not cover randomized methods.
- Subproblem requires an additional inner solver; method is not adaptive to unknown constants (sigma, L2, R).
- Experiments limited to a single logistic regression dataset (a9a).
Experimental setup
Datasets: a9a
Benchmarks: a9a
Metrics: train loss test loss
Baselines: SGD Extra-Newton Accelerated Inexact Tensor Method
Builds on: Accelerated Cubic Newton Extra-Newton Accelerated Tensor Method Inexact Cubic Newton
Closest papers by meaning
- Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations (NeurIPS 2024 · similarity 0.90)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.88)
- Stochastic Newton Proximal Extragradient Method (NeurIPS 2024 · similarity 0.88)
- Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits (NeurIPS 2025 · similarity 0.88)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.87)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.