Research map / Optimization / Distributed and compressed
Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing
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 adaptive i.i.d. Hessian-sketching scheme for massively parallel Newton steps, choosing the sketch size and regularization via Marchenko-Pastur-based debiasing, with non-asymptotic Gaussian guarantees and an inexact self-concordant Newton convergence analysis.
Problem
Minimizing a twice-differentiable convex objective with L2 penalty in a massively parallel serverless setting where workers cannot communicate, making exact Newton inverse-Hessian computation costly (O(d^3)) and sketch size/regularization selection unaddressed.
Approach
Workers compute low-bias sketched inverse-Hessian estimates whose modified regularization is set by the Marchenko-Pastur deterministic equivalent; the sketch dimension is chosen adaptively by doubling with a test on the empirical Stieltjes transform of the sketched Hessian, and the server averages worker directions.
Key results
- Adaptive procedure found sketch dimension within 1.5 d_H(lambda) to 4 d_H(lambda) with success rate 1.0 across 20 Monte-Carlo trials for power-decay spectra (alpha = 1, 2/3, 1/2).
- Bias correction lowers the inverse-Hessian bias proxy relative to uncorrected estimator, roughly decaying at rate 1/sqrt(m).
- Experiments on ridge and logistic regression show bias correction accelerates convergence versus uncorrected sketched Newton, often substantially.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Rademacher or sparse Rademacher sketches instead of Gaussian sketches | Adaptive sketching procedure · Synthetic H with α=1, α=2/3, and α=1/2 | success rate: 1.0 | No clear effect |
| Apply bias correction rather than using the uncorrected estimator (λ̃=λ) | Parallel sketched Newton method · Ridge and logistic regression optimization tasks | convergence speed | Helped |
| Increase the number of workers | Parallel sketched Newton method · UCI optimization tasks | convergence speed | Helped |
Surprising findings
- The sketch-dimension selection procedure was robust across Gaussian, Rademacher, and sparse Rademacher sketches, making the sketch-type table largely uninformative.
Limitations
- Non-asymptotic guarantees are proved only for Gaussian sketches; asymptotic results cover i.i.d. sketches.
- Analysis of the approximate Newton method is restricted to self-concordant objectives.
- Certain theorem proofs are omitted or deferred, and the Rademacher/sparse results are empirical only.
Experimental setup
Datasets: UCI datasets synthetic ridge and logistic regression designs
Benchmarks: UCI ridge and logistic regression synthetic ridge and logistic regression
Metrics: optimality gap normalized Frobenius error of inverse Hessian estimate sketch-dimension success rate
Baselines: uncorrected sketched Newton (lambda tilde = lambda)
Builds on: GIANT Determinantal Averaging Surrogate sketching DiSCO
Closest papers by meaning
- Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality (ICML 2021 · similarity 0.89)
- Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update (NeurIPS 2021 · similarity 0.89)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.86)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.85)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.84)
- Communication Efficient Distributed Newton Method over Unreliable Networks (AAAI 2024 · similarity 0.84)
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.