Research map / Optimization / Nonconvex and smooth optimization
Stochastic Newton Proximal Extragradient Method
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 Stochastic Newton Proximal Extragradient (SNPE), extending the HPE framework to strongly convex problems with a noisy Hessian oracle, using averaged Hessian estimates and line search to get faster global linear and superlinear convergence than stochastic Newton (Na et al.).
Problem
Stochastic second-order methods achieve superlinear convergence only when Hessian noise diminishes, which requires growing per-iteration cost; the prior Hessian-averaging stochastic Newton method has slow global convergence (up to O~(kappa^2) or kappa^3 iterations).
Approach
Replace Newton's step with a Hybrid Proximal Extragradient step using a linearized proximal update with an averaged stochastic Hessian, a backtracking line search with step-size warm start sigma_{t+1}=eta_t/beta that lets step sizes grow, and a relaxed inexactness condition to get faster linear and superlinear rates.
Key results
- Theory: SNPE with uniform averaging has linear rate 1-O(1/kappa) versus 1-O(1/kappa^2) for stochastic Newton, and reduces the first transition point T1 by a factor of kappa^2.
- With non-uniform averaging, the second transition point to superlinear phase drops from O~(kappa^2) to O~(Upsilon^2+kappa).
- Experiments on log-sum-exp (d=500) show SNPE outperforms stochastic Newton and AGD in iterations and runtime, though exact-Hessian methods converge in fewer iterations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace stochastic Newton with SNPE | Strongly convex optimization · Strongly convex optimization | iteration complexity: \mathcal{O}(\Upsilon^2\! +\! \kappa^2 \!+\! {\frac{\log(1/\epsilon)}{\log\log(1/\epsilon)}}) -> \mathcal{O}(\Upsilon^2 \ | Helped |
| use SNPE instead of stochastic Newton with uniform Hessian averaging | Uniform Hessian averaging · Uniform Hessian averaging | warm-up iterations: {\Upsilon^2} -> \frac{\Upsilon^2}{\green{\kappa^2}} | Helped |
| use SNPE instead of stochastic Newton | Uniform Hessian averaging · Uniform Hessian averaging | linear convergence rate: 1-{\kappa^{-2}} -> 1-\green{\kappa^{-1}} | Helped |
| use SNPE instead of stochastic Newton with uniform Hessian averaging | Uniform Hessian averaging · Uniform Hessian averaging | initial superlinear transition iterations: \kappa^3 -> \green{\kappa^2} | Helped |
| use SNPE instead of stochastic Newton with uniform Hessian averaging | Uniform Hessian averaging · Uniform Hessian averaging | final superlinear transition iterations: \frac{\kappa^6}{\Upsilon^2} -> \frac{\green{\kappa^4}}{ \Upsilon^2} | Helped |
| use SNPE instead of stochastic Newton with non-uniform Hessian averaging | Non-uniform Hessian averaging · Non-uniform Hessian averaging | initial superlinear transition iterations: \kappa^2 -> \Upsilon^2+\green{\kappa} | Helped |
| use SNPE instead of stochastic Newton with non-uniform Hessian averaging | Non-uniform Hessian averaging · Non-uniform Hessian averaging | final superlinear transition iterations: \kappa^2 -> \Upsilon^2 +\green{\kappa} | Helped |
| use non-uniform instead of uniform Hessian averaging | SNPE · Strongly convex optimization | final superlinear transition iterations: \tilde{\mathcal{O}}(\frac{\kappa^4}{\Upsilon^2}) -> \tilde{\mathcal{O}}(\Upsilon^2+\kappa) | Helped |
| remove the extragradient step (ablation) | SNPE · Synthetic regularized log-sum-exp | convergence speed | Helped |
| use SNPE instead of AGD | Synthetic regularized log-sum-exp · Synthetic regularized log-sum-exp | iterations to converge | Helped |
| use SNPE instead of AGD | Synthetic regularized log-sum-exp · Synthetic regularized log-sum-exp | runtime | Helped |
| use SNPE instead of stochastic Newton | Synthetic regularized log-sum-exp · Synthetic regularized log-sum-exp | iterations to converge | Helped |
Surprising findings
- The extragradient step tends to slow convergence in experiments, so the authors use a variant without it.
Limitations
- Analysis assumes strong convexity; extension to convex setting left for future work.
- Theory requires Upsilon = O(sqrt(kappa)) for the claimed improvements in some regimes.
- Experiments are small synthetic problems on a single machine.
Experimental setup
Datasets: synthetic regularized log-sum-exp data
Benchmarks: regularized log-sum-exp synthetic minimization
Metrics: iterations to convergence runtime
Baselines: Stochastic Newton (uniform averaging) Stochastic Newton (non-uniform averaging) accelerated gradient descent damped Newton Newton Proximal Extragradient
Builds on: Hybrid Proximal Extragradient Stochastic Newton with Hessian averaging (Na et al. 2022) Newton proximal extragradient
Closest papers by meaning
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.88)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.88)
- A Bregman Proximal Stochastic Gradient Method with Extrapolation for Nonconvex Nonsmooth Problems (AAAI 2024 · similarity 0.88)
- Advancing the Lower Bounds: an Accelerated, Stochastic, Second-order Method with Optimal Adaptation to Inexactness (ICLR 2024 · similarity 0.88)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.88)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 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.