Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings

We thank the reviewer for their thoughtful and constructive feedback. We address each point below.

Weaknesses

1) We agree that practical clarity is important, even in a theory-focused paper. In response, we have included several synthetic experiments that demonstrate the practical benefits of our approach (see the response to reviewer 1 (6kyE) for details). These include:

• a 2D toy example (Example 1, Appendix A),
• a high-dimensional linear problem with ill-conditioned structure, and
• a high-dimensional nonlinear experiment using a $\tanh$-based mapping.

These experiments empirically validate the iteration complexity improvements predicted by our framework. Additionally, we highlight that our framework connects with real-world settings such as neural collapse and ETF parametrisation, as explored in prior work [46]. We plan to apply our framework and cover more complex settings and real data applications in future work.

2) Indeed, the limitations mentioned—local analysis, assumption of exact mappings, deterministic setting—are important and we fully agree that they offer meaningful avenues for future research. Our current focus was to establish a rigorous foundation, but we view extending the theory to stochastic and approximate regimes as a natural and promising next step.

Questions:

1) Yes, faster convergence of neural collapse due to reduction mappings has already been observed in stochastic settings in prior work [46]. In particular, the empirical results in that paper show significant gains under SGD when using ETF-reparametrisation mappings. Extending our theoretical framework to analyse convergence in such stochastic regimes is a key future direction.

2) We agree that exact application of the pullback metric can be computationally expensive in general. However, in many structured applications, the metric admits efficient forms: Linear or affine mappings yield a constant $R$ that is easy to compute and invert. Structured nonlinear mappings (e.g. arising from normalisation layers or architectural constraints) often produce diagonal, block-diagonal, or low-rank $R$, enabling efficient approximations. For more general nonlinear cases, approximate preconditioning techniques (e.g. diagonal approximation, conjugate gradients, or low-rank updates) can be used to trade off computational cost with fidelity to the pullback geometry. These situations are common in practice, and we believe they offer a rich space for practical extensions of our theory, which we intend to explore further in future work.

We thank the reviewer for their thoughtful and constructive feedback. We address each point below.

Weaknesses:

1) We agree that numerical experiments can enhance intuition for the theory. In response, we conducted synthetic experiments illustrating the predicted iteration complexity improvements. These build upon Example 1 (Appendix A) and will appear in the final version with visualisations and analysis. All experiments were repeated with varied seeds/initialisations and results averaged.

• Example 1: Quadratic Toy Problem (Figure 1)
  Canonical function:
  $f(x_1,x_2) = x_1^2 + 10(x_2 − x_1)^2$
  with reduction mapping $x_2^\star(x_1) = x_1$, yielding reduced problem $F(x_1)=x_1^2$. GD is used with maximal step sizes.
• Example 2: High-Dimensional Quadratic
  Ill-conditioned problem ($K \in \mathbb{R}^{d\times d}, d=40$):
  $G(x, y) = \tfrac{1}{2}||x||^2 + \tfrac{1}{2}||y||^2 + \tfrac{\lambda}{2} ||y - Kx||^2$
  Reduction via $y = Kx$ gives:
  $F(x) = \tfrac{1}{2} x^\top (I + K^\top K) x,\quad R = I + K^\top K$
• Example 3: Nonlinear Mapping (Tanh)
  Reduction $\Phi(x) = [x; \alpha \tanh(Kx)]$, full objective:
  $G(x, y) = \tfrac{1}{2}||x||^2 + \tfrac{1}{2}||y||^2 + \tfrac{\lambda}{2} ||y - \alpha \tanh(Kx)||^2$
  Reduced:
  $F(x) = \tfrac{1}{2} ||x||^2 + \tfrac{1}{2} \alpha^2 ||\tanh(Kx)||^2$
  with pullback metric:
  $R(x) = I + \alpha^2 K^\top \mathrm{diag}(\mathrm{sech}^4(Kx)) K$

These results confirm that reduction significantly reduces iteration counts and preconditioning further enhances this—even for high-dimensional or nonlinear problems.

2) While our theory assumes exact reduction mappings $\Psi$ for clarity, many practical cases admit explicit forms. Examples include BatchNorm, WeightNorm, or projections onto structured manifolds (sphere, Stiefel), often implemented via QR/polar decompositions. These are exact (not iterative) and fit our framework. Mappings derived as a solution of inner optimisation problems (e.g., balanced factorisations or ETF projections) are indeed approximate. We acknowledged this in Section 4.1, and handling such mappings is a key future direction.

3) Inverting the pullback metric $R = D\Phi^\top D\Phi$ adds some overhead, but is tractable in many settings:

• Linear $\Phi$: $R$ is constant with closed-form inverse or low-rank structure; cost is negligible.
• Structured nonlinear $\Phi$: $R(x)$ often has favourable algebraic form (e.g. diagonal dominance, low-rank perturbation of identity). Efficient inversion via Woodbury or matrix identities is possible.
• Stable conditioning: Well-behaved $\Phi$ (such as nonlinear projection on manifolds) keeps $R(x)$ stable, enabling iterative solvers (e.g. conjugate gradient) with only a few steps, hence they are not substantially increasing the wall-time performance as we see in Example 3.

Thus, while efficient large-scale implementation is indeed an important direction beyond the current scope, we see no fundamental barrier to scalability in many settings. We have updated the discussion in the paper to better reflect these considerations.

---

Questions:

1) Neural Collapse: In the context of Neural Collapse, the reduction mapping $\Psi$ can be viewed as fixing classifier weights (equivalent mappings can be formulated for hidden layers via Deep NC characterisations) to a canonical or random ETF form, eliminating orthogonal symmetry. This constant mapping fits our framework. A richer formulation defines $\Psi$ implicitly via the nearest-ETF projection, as in [46]:
$U^\star \in \arg\min_{U\in St(d,C)} ||\bar{H} - UM||^2_F + \tfrac{\delta}{2} ||U - U_{\text{prox}}||^2_F$
This defines $\Psi(\bar{H}) = U^\star M$. Empirical validation in [46, Figs. 3,4] shows faster convergence and improved conditioning, matching our theoretical predictions.

Low-rank Factorisation: Here, the solution is non-unique due to $\mathrm{GL}(r)$ symmetry: $(U, V) \mapsto (UR, V(R^{-\top}))$. Quotient manifold methods handle this via equivalence classes, but do not favour specific representatives.

Our framework allows explicit representative selection—fixing a gauge—which is crucial when structure or regularity is needed (e.g., in generalisation).

For example, an interesting choice is balanced factorisation: $U^\top U = V^\top V$. Let $A:=U^\top U, B:=V^\top V$. For any feasible $(U,V)$, compute the matrix geometric mean $X: = A^{-1/2}(A^{1/2}BA^{1/2})A^{-1/2}$
and choose the principal symmetric PD square root: $R(U, V) := X(U,V)^{1/2}$
so that $U^\top U = V^\top V$. This defines a reduction $\Psi(U,V) = (UR(U,V), V(R(U,V)^{-\top}))$. Unlike quotient optimisation, which simply eliminates symmetry, our mapping selects a preferred/specific representative from the equivalence class with desirable properties. Balancedness improves stability and generalisation in tasks like matrix completion and low-rank deep models.

With this framework, we give practitioners the ability to act with principled control over the solution structure, enabling them to design problem-specific mappings that not only resolve symmetries but also accelerate convergence toward desirable and application-relevant solutions. More broadly, many important applications motivate the need for structure-aware optimisation. In this paper, we have chosen to focus on developing the general theoretical framework. In upcoming work, we will provide a detailed treatment of key applications—illustrating how reduction mappings and the associated geometry can be leveraged in practical settings across machine learning and general nonconvex problems.

2) Τhe assumptions made in our framework are both plausible and robust in real-world machine learning settings. For the spectral gap $\Delta_{\max}$​, the assumption is satisfied in any anisotropic Hessian, which is virtually always the case in modern deep networks. The only exception is the isotropic case (all eigenvalues equal), which is highly non-generic and mostly of theoretical interest. In this degenerate scenario, our reduction framework does not improve convergence over classical training—precisely as our theory predicts. More generally, as shown in Section E.4, symmetric matrices with non-simple spectra form a measure-zero subset, and our analysis explicitly accommodates eigenvalue multiplicities in the top eigenspace as long as there is a gap below. For the non-alignment assumption $\varepsilon > 0$, geometrically this requires that the tangent space of the reduced manifold does not contain the top curvature directions we aim to eliminate. Such near-perfect alignment is also non-generic and would require adversarially structured mappings or objectives. Moreover, even if alignment does occur, small, structure-preserving perturbations to the reduction mapping (e.g., reparameterisations, gauge fixes) are sufficient to break it—without altering the semantics of the model or predictor. Regarding the connection to deep learning Hessian spectra, we note that the goal is not merely to argue that $\Delta_{\max} > 0$—this is almost always true in nontrivial problems—but to emphasise that the magnitude of the spectral gap in practice can be very large, as shown empirically in [66–70]. This has two key implications: (i) our theoretical gains via reduction and preconditioning become more pronounced in such settings, and (ii) even in the purely Euclidean reduced case, the large $\Delta_{\max}$ leads to a strictly smaller smoothness constant, and hence faster convergence. This explains the accelerated behaviour observed in real-world examples like neural collapse and ETF-aligned features [46], even without preconditioning.

3) In practice, spectral gaps $⁡\Delta_{\min}$ and $\Delta_{\max}$​ are typically positive and well-separated, as confirmed in our experiments and supported by prior work on deep learning Hessians. These studies consistently observe a bulk–spike structure, where a few large outlier eigenvalues are separated from the bulk of smaller ones. This directly implies a large $\Delta_{\max}$, while $\Delta_{\min}$, though smaller, remains non-negligible. Such structure provides a natural setting where our assumptions hold and the benefits of reduction and preconditioning are most pronounced. For completeness, we include the spectral gaps for the three synthetic examples from above.

• Example 1: $\Delta_{\max} = \Delta_{\min} = 40$ (2D case)

• Example 2: $\Delta_{\max} = 3540, \Delta_{\min} = 20$

• Example 3: $\Delta_{\max} = 3.465 \times 10^5, \Delta_{\min} = 1.646 \times 10^{-6}$

We thank the reviewer for the thoughtful and constructive feedback. We address each point below.

Weaknesses:

In response, we have added two new synthetic high-dimensional examples (see the response to reviewer 1 (6kyE) for details) illustrating the utility of reduction mappings and their associated preconditioning, with a detailed analysis of the iteration complexity for each method. Moreover, our framework applies directly to prior work such as [46], where the authors employed a nonlinear reduction mapping—derived from an argmin formulation—to optimise towards the nearest ETF in the neural collapse setting. Their results, on both synthetic and real-world data, demonstrate accelerated convergence compared to standard training, further validating the benefits of this approach. Batch normalisation can also be formulated as a reduction mapping. However, due to its reliance on batch statistics, the more interesting and practical mappings are inherently stochastic. The analysis of such stochastic reduction mappings is an interesting direction and is left for future work. In contrast, a particularly instructive and tractable case is weight normalisation (WN). Consider a single neuron with weight vector $w \in \mathbb{R}^d$. WN adopts a scale–direction parametrisation:

$$w = \Phi(\theta) := g \frac{v}{\|v\|}, \quad \theta = (v, g) \in \mathbb{R}^d \times \mathbb{R}.$$

This defines a (chart) representation of the sphere bundle $S^{d-1} \times \mathbb{R} \to \mathbb{R}^d$. In the reduction view, the unit-norm direction serves as a fixed gauge, and the known scale–direction structure is captured via $\Phi$. Performing steepest descent in the pullback metric induced by $\Phi$ yields exactly the preconditioned update recommended by our framework. Letting $n = v/\|v\|$, the pullback metric is

$$R = \mathrm{diag}\left( \frac{g^2}{\|v\|^2}(I - nn^\top), 1 \right).$$

Because $R$ is singular (due to redundancy in $v$), the correct preconditioner is its Moore–Penrose pseudoinverse,

$$R^\dagger = \mathrm{diag}\left( \frac{\|v\|^2}{g^2}(I - nn^\top), 1 \right),$$

or alternatively, in a minimal coordinate chart, the full inverse is

$$R^{-1} = \mathrm{diag}\left( g^{-2} I_{d-1}, 1 \right).$$

In both cases, the inverse is closed-form and computationally efficient. At the layer level, the Jacobian becomes block-diagonal (one block per row), so preconditioning reduces to a per-row projection onto the tangent space followed by a scalar rescaling. The full metric remains block-diagonal with a cost of $\mathcal{O}(md)$ for a layer with $m$ neurons, which is negligible in practice. Future work will address the stochastic extension of reduction mappings and explore more real-world applications. Our theory suggests that while normalisation layers are already known to improve training speed in standard Euclidean settings, performing geometry-aware preconditioning through the pullback metric can yield further improvements in convergence—without additional wall-time overhead—since the metric inverses are inexpensive to compute.

Clarity: Thank you for the suggestion. Due to space constraints, we couldn’t fit the whole motivation in the main text. In the final version of the paper, we will provide additional motivation in the main text.

Questions:

1) For the case of batch normalisation bounds, our results are tight in the sense that we can move between the two results in a straightforward manner. Specifically, when the batch normalisation transformation is interpreted as a reduction mapping $\Phi_{\text{BN}}$​, the pullback metric becomes a projector–rescale operator, and our framework recovers the same structural improvements in smoothness and gradient norms observed in prior BN analyses [44]. The multiplicative factor $\gamma^2/\sigma^2$ and the projection onto the orthogonal complement of the mean and normalised input directions emerge naturally from the geometry of the mapping and match the scaling and projection terms in the BN gradients. The difference lies in how the second-order effects are handled. In our general setting, when $\Phi$ is nonlinear, the curvature correction term involving $D^2\Phi$ is upper-bounded generically by the abstract quantity $QZ/m(\Phi)$, which captures the interaction between the curvature of the mapping and the gradient of the loss. In contrast, the BN analysis computes these same curvature terms explicitly using the algebraic structure of the batch statistics, leading to closed-form expressions for the full Jacobian and its effect on the gradient and Hessian. In this sense, the BN bounds can be seen as a concrete instance of our general result, where the curvature term is evaluated exactly rather than bounded. Therefore, up to this difference in treatment of curvature, the two sets of results are equivalent in spirit and mechanism. Our bounds can be viewed as a generalisation of the BN case, and when applied to the BN setting, they yield bounds that are tight up to the curvature correction. In particular, when the reduction mapping is affine—as in frozen BN—the curvature term vanishes, and our bounds match exactly. For nonlinear cases (e.g., batch-dependent BN), the tightness of our bound depends on how well the curvature correction is controlled, but the mechanism of improvement remains the same. For a general setting, our results are minimax-tight.

2) The curvature and spectral gap conditions we impose are sufficient but not necessary for achieving improved smoothness and sharpness constants. In particular, they are not required to guarantee a qualitative improvement — that is, an improvement may still occur in their absence. In fact, the necessary and sufficient condition for a strict reduction in curvature appears in the Courant–Fisher formulation used in Lemma 4: the improvement occurs if and only if the feasible tangent space avoids the top eigenspace of the Hessian. What the curvature and spectral gap conditions provide is a quantitative strengthening of this principle. They turn the abstract variational condition into a concrete, verifiable, and practically useful bound. In that sense, our assumptions are best viewed as sufficient conditions for controlled and predictable improvement, which can guide algorithmic design and offer explicit guarantees in real-world applications.