Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings

Evan Markou, Thalaiyasingam Ajanthan, Stephen Gould

Abstract

Modern machine learning models often feature high-dimensional, non-convex loss landscapes with continuous manifolds of optimal solutions due to over-parameterization and inherent symmetries. This paper introduces a geometric framework centered on "reduction mappings"—reparameterizations that explicitly restrict variables to these solution manifolds. We demonstrate that well-chosen reduction mappings fundamentally improve the loss landscape's curvature, resulting in strictly better condition numbers and provably faster convergence for gradient-based optimization.

Introduction

In high-dimensional non-convex optimization, such as training deep neural networks or performing matrix factorization, the loss landscape is notoriously complex. However, optimal solutions in these models rarely exist as isolated points; instead, they often form continuous, smooth "valleys" or manifolds. While practitioners frequently exploit this structure through techniques like batch normalization or "neural collapse," a rigorous theoretical understanding of how these reparameterizations accelerate convergence has been lacking.

This research addresses this gap by asking: if the geometric structure of optimal solutions is known, how does a mapping that reduces dimensionality by locking variables onto this structure alter the landscape's curvature?

Geometric Framework of Reduction Mappings

The authors propose a framework based on reduction mappings. Consider an objective function $f(x_1, x_2)$. If the optimal configuration of $x_2$ is known to depend on $x_1$ via a mapping $\Psi(x_1)$, we can optimize a reduced objective: $$F(x_1) = f(x_1, \Psi(x_1))$$

Visualization of an ambient surface $f$ and three different reduction mappings $\Psi_i$ defining restricted manifolds $\mathcal{M}_{F_i}$.

To analyze the impact of these mappings, the authors utilize several differential geometric tools:

  • Hessian Analysis: Examining how the reduction mapping restricts the second-derivative matrix of the original function.
  • Pullback Metrics: Equipping the reduced space with a metric that respects the intrinsic geometry of the curved manifold, preventing Euclidean distortion.
  • Geometrically Preconditioned Gradient Descent (GeoPrecGD): An algorithm that uses the Jacobian of the reduction mapping as a preconditioner to align descent directions with the manifold's intrinsic geometry.

Key Theoretical Insights

The core contribution lies in quantifying how reduction mappings reshape the optimization landscape:

  1. "Ironing Out" Curvature: A well-designed mapping effectively ignores the steepest, worst-case curvature directions of the original problem. This strictly decreases the "smoothness" constant ($\beta$), which represents the upper bound on curvature.
  2. Sharper Minima: Simultaneously, the mapping can increase the "sharpness" constant ($\mu$), ensuring the landscape does not flatten excessively near the minimum.
  3. Condition Number Improvement: By decreasing $\beta$ and increasing $\mu$, the condition number $\kappa = \beta/\mu$ is strictly improved. This reduces iteration complexity from $\mathcal{O}(\kappa_{original} \log(1/\epsilon))$ to $\mathcal{O}(\kappa_{reduced} \log(1/\epsilon))$.
  4. The Risk of "Bending": Not all mappings are beneficial. Highly nonlinear mappings can introduce artificial curvature (a "bending" effect). The paper provides mathematical bounds on acceptable nonlinearity before these benefits are negated.

Empirical Validation and Results

The authors validated their theory using synthetic 2D and 40D mathematical functions, including quadratic and nonlinear least-squares problems.

  • Algorithmic Equivalence: For specific classes, GeoPrecGD recovers powerful second-order methods: it is equivalent to the Newton method for quadratic objectives and the Gauss-Newton method for nonlinear least-squares.
  • Performance: On a 40-dimensional nonlinear least-squares problem, the geometrically preconditioned method achieved a 100x speedup in wall-clock time compared to standard gradient descent on the full unconstrained problem.

Limitations and Future Work

While promising, the framework has several limitations. It assumes the reduction mapping $\Psi(x_1)$ can be evaluated perfectly, whereas in practice (e.g., bilevel optimization), it is often approximated. Additionally, the computational cost of inverting the preconditioner matrix must be balanced against the reduction in iteration count.

Future research directions include extending the framework to Stochastic Gradient Descent (SGD) for large-scale applications and investigating whether reduction mappings can globally reshape landscapes to eliminate saddle points or spurious local minima.

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