Research map / Optimization / Optimizers
Improving Computational Complexity in Statistical Models with Local Curvature Information
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 normalized gradient descent (NormGD), with step size scaled by the maximum Hessian eigenvalue of the empirical loss, and proves it reaches the statistical radius in logarithmically many iterations for homogeneous singular statistical models, improving computational complexity over fixed-step GD.
Problem
Fixed step-size gradient descent in singular statistical models (degenerate Fisher information at the true parameter) needs polynomially many iterations in n to reach the statistical radius, which is computationally costly.
Approach
Scale the GD step size by the maximum eigenvalue of the sample Hessian (NormGD), computed cheaply via power iteration, and analyze it with a population-to-sample argument under homogeneity assumptions; this yields logarithmic iteration counts and total cost O((nd+d^2) log(n/d)) for fixed d.
Key results
- In the low SNR GLM setting, NormGD reaches statistical radius (d/n)^{1/(2p)} in logarithmic iterations, giving total cost O((nd+d^2)log(n/d)) versus O(n^{(2p-1)/(2p)} d^{1/p}) for GD.
- Empirically, the statistical error scales roughly as n^{-0.5} in high SNR and n^{-0.25} in low SNR GLM experiments (d=2, n from 100 to 10000), matching theory.
- For the low SNR two-component Gaussian mixture, NormGD reaches radius (d/n)^{1/4} after log(n) iterations, versus O((n/d)^{1/2}) for EM.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use NormGD instead of fixed step-size Gradient Descent | GLM, low SNR · Low SNR GLM, g(r)=r^p | iterations for convergence: (n/d)^{p-1 er p} -> log(n/d) | Helped |
| use NormGD instead of BFGS | GLM, low SNR · Low SNR GLM, g(r)=r^p | statistical error: (d/n)^{1/(2p+2)} -> (d/n)^{1/(2p)} | Helped |
| use NormGD instead of Newton’s Method | GLM, low SNR · Low SNR GLM, g(r)=r^p | computational complexity: (nd + d^3) log(n/d) -> (nd + d^2) log(n/d) | Helped |
| use NormGD instead of EM | symmetric two-component location GMM, low SNR · Low SNR GMM | iterations to reach statistical radius: O((n/d)^{1/2}) -> log(n) | Helped |
| use NormGD instead of fixed step-size Gradient Descent | GLM, high SNR · GLM, high SNR, d=2 | statistical error vs sample size slope: -0.4968 -> -0.5133 | No clear effect |
| use NormGD instead of fixed step-size Gradient Descent | GLM, low SNR · GLM, low SNR, d=2 | statistical error vs sample size slope: -0.2387 -> -0.2843 | No clear effect |
Surprising findings
- Newton's method and BFGS do not have established statistical optimality in the multivariate singular setting, and BFGS attains only (d/n)^{1/(2p+2)} in the low SNR GLM case.
Limitations
- Theory restricted to homogeneous population loss (Assumption W.1); inhomogeneous settings left to future work.
- Power iteration convergence requires lambda_2/lambda_max bounded away from 1, or randomization; the paper only partially addresses this.
- Experiments are limited to synthetic low-dimensional (d=2) GLM settings.
Experimental setup
Datasets: synthetic Gaussian GLM data synthetic symmetric two-component Gaussian mixture data
Benchmarks: synthetic GLM synthetic Gaussian mixture
Metrics: parameter estimation error convergence iterations log-log slope of statistical error vs sample size
Baselines: Gradient Descent Newton's method BFGS
Builds on: Ho et al. 2020 (fixed step-size GD in singular models) Balakrishnan et al. 2017 (EM / population-to-sample) Ren et al. 2022 (homogeneous assumption) BFGS (Jin et al. 2024)
Closest papers by meaning
- Local Curvature Descent: Squeezing More Curvature out of Standard and Polyak Gradient Descent (NeurIPS 2025 · similarity 0.87)
- Calibrated Target Noise Recovers Curvature from the Gradients (NeurIPS 2026 · similarity 0.87)
- Tractable structured natural-gradient descent using local parameterizations (ICML 2021 · similarity 0.86)
- Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescaling (ICML 2024 · similarity 0.85)
- Global curvature for second-order optimization of neural networks (ICML 2025 · similarity 0.85)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.85)
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.