Research map / Optimization / Nonconvex and smooth optimization
Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions
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.
Introduces graded non-convexity (Hessian top-τ eigenvalues nonnegative) and a gradient method with spectral preconditioning using inexact top-τ Hessian eigenvectors, proving rates that improve with τ.
Problem
Gradient methods converge slowly on ill-conditioned non-convex problems whose Hessian has a few very large top eigenvalues; standard smoothness and convexity assumptions give too coarse complexity bounds.
Approach
Define a nested hierarchy of non-convex function classes by requiring the top-τ Hessian eigen-part to be PSD (graded non-convexity), and precondition gradient steps with a low-rank approximation of the top-τ Hessian plus regularization, so the complexity depends on λ_{τ+1} rather than λ_1.
Key results
- Theorem gives non-convex complexity O(λ_{τ+1}/ε^2 + L^{1/2}/ε^{3/2}) outer steps, versus gradient method's λ_1/ε^2, with improvement as τ grows.
- For convex quadratics with τ=1, the total complexity Õ((λ_2/λ_n)·λ_1/(λ_1-λ_2)) can be much better than the gradient method's Õ(λ_1/λ_n) when λ_1 ≫ λ_2.
- Experiments on matrix factorization (n=400) and logistic regression on LIBSVM show spectral preconditioning beats gradient descent and is comparable to BFGS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use spectral preconditioning of order τ instead of plain gradient descent | Gradient methods on graded non-convex functions · Non-convex problems | iteration complexity: \cO\bigl( \frac{\lambda_1}{\varepsilon^{2}} \bigr) -> \cO\bigl( \frac{ \lambda_{\tau + 1} }{\varepsilon^{2}} + \frac{L^{ | Helped |
| Use spectral preconditioning of order τ instead of plain gradient descent | Gradient methods on strongly convex problems · Strongly convex problems | iteration complexity: \tilde{\cO}\bigl( \frac{\lambda_1}{\lambda_n} \bigr) -> \tilde{\cO}\bigl( \frac{ \lambda_{\tau + 1} }{\lambda_n} + MD \b | Helped |
| Increase the spectral preconditioning order τ | Spectral Preconditioning · Non-convex problems | iteration complexity | Helped |
| Use the negative-spectrum-cutting step-size rule and auxiliary test points | Spectral Preconditioning · Non-convex problems with large negative Hessian eigenvalues | iteration complexity | Helped |
| Use spectral preconditioning with τ=1 or τ=3 instead of basic gradient descent (ablation) | Logistic regression · Several machine learning datasets | convergence | Helped |
| Use spectral preconditioning with τ=1 or τ=3 instead of BFGS (ablation) | Logistic regression · Several machine learning datasets | convergence | No clear effect |
| Use spectral preconditioning with τ=20 or τ=80 (ablation) | Spectral Preconditioning · Matrix factorization, n = 400 | convergence | Mixed |
Limitations
- Theory assumes a uniform bound on the (τ+1)-th eigenvalue and Lipschitz Hessian, which may be hard to verify in practice
- Full efficiency relies on power-method approximation of top eigenvectors with an accuracy parameter δ
- Experiments are limited to small-scale problems (matrix factorization n=400, logistic regression)
Experimental setup
Datasets: MNIST LIBSVM datasets
Metrics: gradient norm vs iterations function value convergence
Baselines: gradient descent BFGS cubic regularized Newton method gradient regularization
Builds on: gradient regularization cubic regularization of Newton method quasi-self-concordance power method
Closest papers by meaning
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning (NeurIPS 2025 · similarity 0.89)
- Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis (NeurIPS 2025 · similarity 0.89)
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness (ICML 2025 · similarity 0.88)
- A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (NeurIPS 2025 · similarity 0.88)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.87)
- Learning to Discover Iterative Spectral Algorithms (NeurIPS 2026 · 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.