Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings

Evan Markou, Thalaiyasingam Ajanthan, Stephen Gould

TL;DR

High-dimensional nonconvex optimization problems often suffer from poor conditioning due to over-parametrization and inherent symmetries. This paper introduces a unified geometric framework proving that "reduction mappings"—which reparameterize the problem to lie on a lower-dimensional solution manifold—strictly improve both smoothness and sharpness constants. This results in a significantly better condition number and provably faster local convergence for gradient-based methods.

What Problem Does This Paper Address?

Modern machine learning models (like deep neural networks) and matrix factorization problems are notoriously over-parameterized. This over-parametrization creates "loss landscapes" where minimizers are not isolated points, but instead form continuous, smooth manifolds.

While gradient descent works surprisingly well in practice, these landscapes often exhibit highly anisotropic curvature—meaning they are incredibly steep in some directions and completely flat in others. This poor conditioning slows down theoretical convergence rates. While practitioners frequently use reparameterization or variable elimination to simplify these problems, we have lacked a rigorous, unified mathematical framework to explain when and how these reduction techniques actually improve the optimization landscape.

Methods

The authors formalize the concept of reduction mappings. If a problem's variables can be split into two components, $(x_1, x_2)$, where $x_2$ has a known geometric structure at optimality, they define a mapping $\Psi(x_1) = x_2$. This allows them to eliminate $x_2$ and optimize a lower-dimensional reduced objective: $F(x_1) = f(x_1, \Psi(x_1))$.

To optimize this reduced objective, they introduce Geometrically Preconditioned Gradient Descent (GeoPrecGD). This method performs steepest descent under a pullback metric induced by the reduction mapping, aligning the descent directions with the intrinsic geometry of the manifold.

The paper provides a rigorous sensitivity analysis for:

  1. Affine reduction mappings: Showing they eliminate alignment with the worst-case curvature directions of the original problem.
  2. Nonlinear reduction mappings: Where they bound the extra curvature introduced by the physical "bending" of the feasible manifold.
  3. Sharpness constants: Proving that the Morse-Bott (and by extension, Polyak-Łojasiewicz) constant strictly increases near the minimizers.

Datasets

As a primarily theoretical paper, no standard real-world datasets were used. Instead, the authors validated their framework using three synthetic optimization problems:

  1. A simple 2D quadratic problem (used for visualization).
  2. A high-dimensional quadratic problem ($n = 40$).
  3. A high-dimensional nonlinear problem ($n = 40$) utilizing hyperbolic tangent functions.

Key Insights and Ideas

  • Ironing out curvature: A well-designed reduction mapping acts as an intrinsic preconditioner, flattening out the steepest, worst-case directions of the loss landscape.
  • Not all reductions are beneficial: If a reduction mapping is poorly designed or misaligned with the solution manifold, it can actually introduce more curvature (such as unwanted oscillations) and hinder convergence. Alignment with the underlying geometry is critical.
Illustration of how well-designed reduction mappings iron out worst-case curvature.
  • The Best of Both Worlds: The reduction mapping simultaneously decreases the smoothness constant ($\beta$) and increases the sharpness constant ($\mu$). Because the condition number is defined as $\kappa = \beta / \mu$, improving both constants simultaneously leads to a massive boost in optimization efficiency.
  • Unifying Classical Algorithms: The authors demonstrate that their geometric framework naturally recovers classical algorithms as special cases. For quadratic objectives, GeoPrecGD is exactly equivalent to Newton's method; for nonlinear least-squares, it recovers the Gauss-Newton method.

Key Results

  • Improved Condition Number: The authors prove that the condition number of the reduced problem is strictly better than the original ($\kappa_F < \kappa_f$).
  • Faster Convergence Rates: Under the Polyak-Łojasiewicz (PŁ) condition, GeoPrecGD accelerates the local linear convergence rate from $O(\exp(-t/\kappa_f))$ to $O(\exp(-t/\kappa_F))$. It also reduces the iteration complexity to achieve an accuracy $\epsilon$ from $O(\kappa_f \log(1/\epsilon))$ to $O(\kappa_F \log(1/\epsilon))$.
  • Empirical Speedups: In high-dimensional synthetic experiments, the reduced preconditioned method achieved dramatic wall-clock speedups—converging up to thousands of times faster than optimizing the full, unconstrained objective function.

Limitations and Future Work

  • Exact Evaluation Assumption: The framework assumes that the reduction mapping $\Psi$ can be evaluated perfectly. In many practical bilevel optimization scenarios, $\Psi$ is defined implicitly via an inner argmin problem and must be approximated, which introduces gradient bias not accounted for in this theory.
  • Computational Overhead: Inverting the pullback metric tensor ($R^{-1}$) introduces additional computational cost per iteration, though the authors note this can be mitigated using structured or approximate linear solvers.
  • Local vs. Global: The current analysis is strictly local (confined to a neighborhood around a minimizer) and deterministic. Extending this geometric framework to global convergence landscapes and stochastic settings (like SGD) remains an open challenge for future research.

Summary updated

Abstract

Many high-dimensional optimisation problems exhibit rich geometric structures in their set of minimisers, often forming smooth manifolds due to over-parametrisation or symmetries. When this structure is known, at least locally, it can be exploited through reduction mappings that reparametrise part of the parameter space to lie on the solution manifold. These reductions naturally arise from inner optimisation problems and effectively remove redundant directions, yielding a lower-dimensional objective. In this work, we introduce a general framework to understand how such reductions influence the optimisation landscape. We show that well-designed reduction mappings improve curvature properties of the objective, leading to better-conditioned problems and theoretically faster convergence for gradient-based methods. Our analysis unifies a range of scenarios where structural information at optimality is leveraged to accelerate convergence, offering a principled explanation for the empirical gains observed in such optimisation algorithms.
BibTeX
@inproceedings{markou2025sharper,
  author = {Evan Markou and Thalaiyasingam Ajanthan and Stephen Gould},
  title = {{Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=ZvqbNFWQkh},
}
Figure