Coordinate Independent and Affine Invariant Optimization

191 concepts110 papers2 proposals

Imagine you are optimizing a machine learning model where one parameter represents distance in meters and another represents weight in kilograms. If you suddenly change the distance units to millimeters, the numerical values of your parameters stretch by a factor of 1,000. To standard gradient descent, the loss landscape has transformed from a gentle, round bowl into an incredibly steep, elongated canyon. The algorithm will begin to oscillate wildly along the steep walls, slowing progress to a crawl.

This vulnerability highlights a fundamental flaw in standard optimization: the trajectory depends entirely on the arbitrary coordinate system chosen to represent the problem. Affine invariance is the property that fixes this. An affine-invariant optimization algorithm takes the exact same physical path toward the optimum regardless of whether the space is scaled, rotated, or linearly shifted.

Why Standard Methods Fail the Invariance Test

Standard gradient descent relies heavily on the Euclidean norm to determine step sizes and directions. When we say a function is smooth, traditional analysis assumes its gradient does not change faster than a global Lipschitz constant $L$ relative to the Euclidean distance:

$$\|\nabla f(x) - \nabla f(y)\| \le L \|x - y\|$$

However, as Martin Jaggi notes in Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, this Lipschitz constant $L$ is highly sensitive to coordinate scaling. If you stretch the input space, $L$ explodes, and your theoretical convergence guarantees collapse—even though the underlying geometric problem remains identical. To build algorithms that are truly robust to ill-conditioned or poorly scaled data, we must decouple the optimization process from the coordinate system.

Intrinsic Geometry and Directional Smoothness

How do we design algorithms that ignore coordinate transformations? One powerful approach, exemplified by projection-free methods like the Frank-Wolfe algorithm, replaces global, norm-dependent constants with metrics derived directly from the problem's intrinsic geometry.

Instead of relying on a global Lipschitz constant, Martin Jaggi characterizes convergence using a curvature constant. This constant measures how much the objective function deviates from its linear approximation across the feasible region. Because it considers the function's behavior relative to the boundaries of the constraint set rather than an arbitrary Euclidean metric, it remains perfectly invariant under any affine transformation.

Expanding on this geometric perspective, Thomas Kerdreux et al. introduced the concept of directional smoothness in Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets. Rather than demanding that the gradient behave well in every possible direction across the entire domain, directional smoothness measures the rate of change of the gradient specifically along the trajectory of the optimization steps. By analyzing the problem through these scalar-based, path-dependent metrics, Elias Samuel Wirth and Sebastian Pokutta demonstrated in Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes that one can prove accelerated convergence rates using a norm derived directly from the geometry of the feasible set, completely removing artificial dependencies on coordinate systems.

Self-Concordance and Local Hessian Norms

For second-order methods like Newton's method or quasi-Newton methods (such as BFGS), affine invariance is achieved by changing how we measure distance at every single step. Instead of using a fixed global norm, these methods use the local curvature of the function itself—represented by the Hessian matrix—as a metric tensor.

This approach is formalized through the framework of self-concordant functions. As Yurii E. Nesterov explains in Greedy Quasi-Newton Methods with Explicit Superlinear Convergence, a function is self-concordant if its third derivative is bounded by its second derivative. This relationship allows researchers to analyze optimization algorithms without relying on coordinate-dependent Lipschitz constants.

When you regulate step sizes using the local Hessian norm, the optimization step automatically scales itself to match the local geometry. Qiujiang Jin and Aryan Mokhtari leveraged this in Affine-Invariant Global Non-Asymptotic Convergence Analysis of BFGS under Self-Concordance to provide the first truly affine-invariant global convergence analysis for BFGS. By conceptually transforming the optimization space at each step so that the Hessian at the optimum behaves like the identity matrix, the authors proved that the algorithm's trajectory remains identical under any linear transformation. Similarly, Slavomir Hanzely et al. showed in Newton Method Revisited: Global Convergence Rates up to $O(1/k^3)$ for Stepsize Schedules and Linesearch Procedures that applying higher-order regularization penalties defined by these local Hessian norms guarantees fast, coordinate-independent convergence rates.

Dynamic Preconditioning as Automatic Whitening

What if you do not have access to exact gradients or Hessians? Derivative-free methods, online learning algorithms, and particle-based sampling methods achieve affine invariance by dynamically estimating the shape of the data and "undoing" any coordinate warping on the fly.

Consider an ensemble of particles exploring a loss landscape. By computing the empirical covariance matrix of these particles, an algorithm can figure out which directions are stretched out and which are compressed. Simon Weissmann et al. demonstrated this mechanism in The Ensemble Kalman Filter for Dynamic Inverse Problems, where the sample covariance acts as a dynamic preconditioner. This allows the solver to maintain consistent performance regardless of how parameters are scaled or rotated, effectively mimicking second-order curvature awareness without ever calculating a derivative.

In the context of online optimization, Tomer Koren and Roi Livni showed in Affine-Invariant Online Optimization and the Low-rank Experts Problem that using zero-initialized preconditioners and lazy projections allows an algorithm to mathematically treat highly skewed data as if it were perfectly "whitened" (spherical). This automated preconditioning ensures that the algorithm performs identically on raw, poorly scaled data and its perfectly normalized counterpart. This same principle underpins the rotational invariance of classic black-box methods like CMA-ES, as detailed by Anne Auger et al. in Experimental Comparisons of Derivative Free Optimization Algorithms, which continuously evolves a Gaussian distribution to match the local topology of the objective function.

Invariance in Deep Learning and Complex Representations

The quest for coordinate independence extends deep into modern neural network architectures and structured parameter spaces. In deep networks, simple changes like shifting or scaling activations can destabilize training. To combat this, second-order frameworks like Kronecker-factored Approximate Curvature (K-FAC), introduced by James Martens et al. in Optimizing Neural Networks with Kronecker-factored Approximate Curvature, and its convolutional counterpart KFC, developed by Roger B. Grosse et al. in A Kronecker-factored approximate Fisher matrix for convolution layers, provide updates that are invariant to pointwise affine transformations. This gives the optimizer an inherent stability similar to Batch Normalization, built directly into the optimization step itself.

Furthermore, when optimizing over matrix parameters or low-rank adapters, algorithms can become trapped by the mathematical symmetries of their own representations. Andrey Veprikov et al. addressed this in Preconditioned Norms: A Unified Framework for Steepest Descent, Quasi-Newton and Adaptive Methods by introducing preconditioned norms that satisfy both left-sided input and right-sided output transformations, ensuring scale invariance across neural network layers.

By decoupling learning rules from their specific parameterizations—a concept generalized by Philip S. Thomas in Decoupling Gradient-Like Learning Rules from Representations—and computing gradients directly within the intrinsic tangent spaces of geometric manifolds, as shown by Zachary Teed et al. in Tangent Space Backpropagation for 3D Transformation Groups, modern optimization is shifting away from arbitrary coordinate representations and moving toward the true, underlying geometry of the problem space.

Key Foundational Work

Towards Gauge Invariant Bundle Adjustment: A Solution Based on Gauge Dependent Damping (2003) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 110 papers
  2. Version 1 · 2026-10-04 · 138 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_affine_invariant_optimization_2d24592b,
  title = {affine-invariant optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/affine-invariant-optimization/rdr_2d24592b86eb44799ddc3ac80e40cf94},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_affine_invariant_optimization_2d24592b_v2,
  title = {affine-invariant optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/affine-invariant-optimization/rdr_2d24592b86eb44799ddc3ac80e40cf94/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake