Research map / Optimization / Nonconvex and smooth optimization
Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings
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.
Shows that reduction mappings obtained by eliminating solution-manifold-aligned variables (affine, nonlinear, or inner argmin) strictly reduce the smoothness and increase the Morse–Bott/PL sharpness constant of the reduced objective, giving a better condition number and faster preconditioned gradient descent.
Problem
Gradient-based optimisation of over-parametrised or symmetric nonconvex objectives whose minimisers form manifolds; the question is when reparametrising onto the solution structure (reduction mappings, often from inner argmin problems) provably improves conditioning and convergence.
Approach
Treats a reduction mapping Psi(x1) that encodes known solution-manifold structure as defining a pullback metric; under non-tangency of the dominant Hessian directions and a spectral gap, the reduced objective has strictly smaller smoothness constant and strictly larger Morse–Bott/PL constant, so preconditioned gradient descent with R = DPhi^T DPhi converges faster.
Key results
- For affine reductions, the Riemannian smoothness constant satisfies beta_F <= beta_f - Delta_max(2eps - eps^2) < beta_f under non-tangency and a spectral gap.
- The Morse-Bott constant of the reduced function satisfies mu_F >= mu_f + Delta_min(2eps - eps^2) > mu_f.
- Hence the reduced condition number kappa_F < kappa_f, giving faster local linear convergence of preconditioned gradient descent.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an affine reduction mapping that avoids the dominant curvature directions | The original objective f · Local neighbourhood | smoothness constant: \beta_F \le \beta_f - \Delta_{\max}(2\varepsilon - \varepsilon^2) < \beta_f | Helped |
| Use a nonlinear reduction mapping whose curvature correction is smaller than the curvature gap | The original objective f · Local neighbourhood | smoothness constant: \beta_F \le \beta_f - \Delta_{\max}(2\varepsilon - \varepsilon^2) + \frac{Q\, Z}{m^{(\Phi)}} < \beta_f | Helped |
| Use a smooth reduction mapping | The original objective f · Solution manifold | Morse–Bott constant: \mu_F \ge \mu_f + \Delta_{\min}(2\varepsilon - \varepsilon^2) > \mu_f | Helped |
| Use pullback-metric preconditioning for gradient descent on the reduced objective | Reduction-mapped objective · Local convergence under the PL condition | condition number: \kappa_F < \kappa_f | Helped |
| Replace the optimal inner mapping x_2^*(x_1)=x_1 with the constant mapping that fixes x_2 (ablation) | Example 1: f(x_1,x_2)=x_1^2+M(x_2-x_1)^2 · Illustrative quadratic example | smoothness constant: null | Hurt |
| Use the optimal inner mapping x_2^*(x_1)=x_1 (ablation) | Example 1: f(x_1,x_2)=x_1^2+M(x_2-x_1)^2 · Illustrative quadratic example | smoothness constant: null | Helped |
| Replace the optimal inner mapping with x_2(x_1)=x_1-2\sin(x_1) (ablation) | Example 1: f(x_1,x_2)=x_1^2+M(x_2-x_1)^2 · Illustrative quadratic example | curvature: null | Hurt |
| Use the fixed mapping \Psi_2(x_1)=0 instead of the optimal mapping \Psi_1(x_1)=\sin(x_1) (ablation) | Example 2: f(x_1,x_2)=\varphi(x_1)+(x_2-\sin(x_1))^2 · Flat region [\alpha,\beta] | curvature: null | Hurt |
| Use the linear mapping \Psi_3(x_1)=x_1 instead of the fixed mapping \Psi_2(x_1)=0 (ablation) | Example 2: f(x_1,x_2)=\varphi(x_1)+(x_2-\sin(x_1))^2 · Flat region [\alpha,\beta] | curvature: null | Helped |
| Use the exact inner mapping \Psi_1(x_1)=\sin(x_1) instead of the fixed or linear mappings (ablation) | Example 2: f(x_1,x_2)=\varphi(x_1)+(x_2-\sin(x_1))^2 · Flat region [\alpha,\beta] | curvature: null | Helped |
Surprising findings
- Under the Euclidean metric, the reduced smoothness constant can degrade (scaled by the metric distortion factor M), so the gains rely on the pullback-metric preconditioner.
Limitations
- Analysis assumes the reduction mapping is evaluated exactly; approximation errors in implicit mappings are not handled.
- Results are local and deterministic; no global or stochastic convergence analysis.
- Computational cost of evaluating the mapping is not captured in iteration complexity.
Experimental setup
Metrics: smoothness constant Morse-Bott/PL constant condition number
Baselines: gradient descent on full objective
Builds on: Polyak-Łojasiewicz condition Morse-Bott property Gauss-Newton method natural gradient descent
Closest papers by meaning
- Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets (NeurIPS 2026 · similarity 0.86)
- Convergence Rates for Gradient Descent on the Edge of Stability for Overparametrised Least Squares (NeurIPS 2025 · similarity 0.86)
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning (NeurIPS 2025 · similarity 0.85)
- Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds (NeurIPS 2025 · similarity 0.85)
- An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2025 · similarity 0.85)
- Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method (ICML 2025 · 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.