Yau's Affine Normal Descent: Algorithmic Framework and Convergence Analysis

Yi-Shuai Niu; Artan Sheshmani; Shing-Tung Yau

math.OCMar 30, 2026

Yau's Affine Normal Descent: Algorithmic Framework and Convergence Analysis

Authors: Yi-Shuai Niu, Artan Sheshmani, Shing-Tung Yau

Abstract

We propose Yau's Affine Normal Descent (YAND), a geometric framework for smooth unconstrained optimization in which search directions are defined by the equi-affine normal of level-set hypersurfaces. The resulting directions are invariant under volume-preserving affine transformations and intrinsically adapt to anisotropic curvature. Using the analytic representation of the affine normal from affine differential geometry, we establish its equivalence with the classical slice-centroid construction under convexity. For strictly convex quadratic objectives, affine-normal directions are collinear with Newton directions, implying one-step convergence under exact line search. For general smooth (possibly nonconvex) objectives, we characterize precisely when affine-normal directions yield strict descent and develop a line-search-based YAND. We establish global convergence under standard smoothness assumptions, linear convergence under strong convexity and Polyak-Lojasiewicz conditions, and quadratic local convergence near nondegenerate minimizers. We further show that affine-normal directions are robust under affine scalings, remaining insensitive to arbitrarily ill-conditioned transformations. Numerical experiments illustrate the geometric behavior of the method and its robustness under strong anisotropic scaling.

Figures & tables

Panel of Figure 1 — Figure 1. Geometric comparison between the Euclidean and affine normals

Figure 2. Disconnected inward slices for $f(x,y)=x^{2}(x^{2}-1)(x^{2}-4)(x^{2}-9)-y$ at $z=(0,0)$ . The red curve is the zero level set $f(x,y)=f(z)$ , and the green set is a representative slice $S_{C}$ for some $C<0$ . Under the inward convention, the centroid direction remains inward/descent, but the slice is disconnected and thus ceases to be a faithful local geometric proxy for the analytic affine normal.

Panel of Figure 3 — Figure 3. Normal–aligned frame at $x_{k}$ illustrating three typical constructions of $d_{k}$ . The analytic affine normal $d_{\mathrm{AN}}(x_{k})$ is represented in the frame $\{e_{1},\dots,e_{n},e_{n+1}\}$ with its $(n+1)$ -st component normalized to $-1$ . Case 1: the affine normal is already a descent direction ( $\langle\nabla f(x_{k}),d_{\mathrm{AN}}(x_{k})\rangle<0$ ), hence $d_{k}=d_{\mathrm{AN}}(x_{k})$ . Case 2: the affine normal points uphill ( $\langle\nabla f(x_{k}),d_{\mathrm{AN}}(x_{k})\rangle>0$ ), so we flip the sign and set $d_{k}=-d_{\mathrm{AN}}(x_{k})$ . Case 3: the affine normal is orthogonal to the gradient ( $\langle\nabla f(x_{k}),d_{\mathrm{AN}}(x_{k})\rangle=0$ ); in this degenerate case we revert to the steepest–descent direction $d_{k}=-\nabla f(x_{k})/\|\nabla f(x_{k})\|$ .

Panel of Figure 4 — Figure 4. YAND on the well-conditioned quadratic ( 10.1 ) with three different line-search strategies. Each panel shows (from left to right) the YAND trajectory on level sets, the function value $f(x_{k})-f^{\star}$ (log scale), and the gradient norm $\|\nabla f(x_{k})\|_{2}$ (log scale).

Figure 5. Optimization trajectories in the original

x

-coordinates for

f_{\gamma}(x)=\tfrac{1}{2}(x_{1}^{2}+\gamma^{2}x_{2}^{2})

with

\gamma=1,10^{2},10^{4}

. As

\gamma

increases, the level sets become increasingly elongated. YAND-Exact and Newton remain essentially one-step methods, while the behavior of gradient descent depends more strongly on the step-size rule. In particular, GD-Fixed becomes substantially slower as the anisotropy increases, whereas GD-Exact remains convergent on this diagonal quadratic.

Figure 6. YAND trajectories after normalization

y=B_{\gamma}x

for

\gamma=1,10^{2},10^{4}

. After mapping to the intrinsic coordinates of

\phi(y)=\tfrac{1}{2}\|y\|^{2}

, the trajectories collapse onto nearly identical paths, illustrating the affine invariance predicted by the theory.

Panel of Figure 7 — Figure 7. YAND on the smooth convex polynomial ( 10.2 ). Each panel shows the optimization trajectory together with the semilog plots of $f(x_{k})-f^{\star}$ and $\|\nabla f(x_{k})\|_{2}$ .

Panel of Figure 8 — Figure 8. YAND on the ill-conditioned convex inverse barrier problem ( 10.3 ). The initial point $x_{0}=(0.01,0.98)^{\top}$ lies extremely close to the affine boundary $x_{1}+x_{2}=1$ .

Panel of Figure 9 — Figure 9. YAND on the Rosenbrock function ( 10.4 ) starting from $x_{0}=(-1.2,1.0)^{\top}$ .

Figure 10. Gradient descent on the Rosenbrock function ( 10.4 ) with strong Wolfe line search.

Figure 11. Damped Newton on the Rosenbrock function ( 10.4 ) with strong Wolfe line search.

Panel of Figure 12 — Figure 12. YAND on the tilted ring-shaped valley ( 10.5 ).

Panel of Figure 13 — Figure 13. YAND on the saddle-type polynomial ( 10.6 ).

Panel of Figure 14 — Figure 14. YAND on the four-well quartic ( 10.7 ).

Nonconvex Optimization

Nonconvex optimization develops methods for problems whose objectives or constraints can have multiple local optima, saddle points, or nonsmooth structure.

See all 145 papers

Apr 4, 2026

An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent

We analyze the last-iterate convergence of the Anchored Gradient Descent Ascent algorithm for smooth convex-concave min-max problems. While previous work established a last-iterate rate of

\mathcal{O}(1/t^{2-2p})

for the squared gradient norm, where

p \in (1/2, 1)

, it remained an open problem whether the improved exact

\mathcal{O}(1/t)

rate is achievable. In this work, we resolve this question in the affirmative. This result was discovered autonomously by an AI system capable of writing formal proofs in Lean. The Lean proof can be accessed at https://github.com/google-deepmind/formal-conjectures/pull/3675/commits/a13226b49fd3b897f4c409194f3bcbeb96a08515

Anja Surina, Arun Suggala, George Tsoukalas +5

Google DeepMind

Last-Iterate Convergence Min-Max Optimization

Ask PDF

Apr 19, 2026

A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad, Shampoo and Muo

A unified framework for first-order optimization algorithms fornonconvex unconstrained optimization is proposed that uses adaptivelypreconditioned gradients and includes popular methods such as full anddiagonal AdaGrad, AdaNorm, as well as adpative variants of Shampoo andMuon. This framework also allows combining heterogeneous geometriesacross different groups of variables while preserving a unifiedconvergence analysis. A fully stochastic global rate-of-convergenceanalysis is conducted for all methods in the framework, with andwithout two types of momentum, using reasonable assumptions on thevariance of the gradient oracle and without assuming boundedstochastic gradients or small enough stepsize.

S. Gratton, Ph. L. Toint

Université de Toulouse, INP, IRIT, Toulouse, France. · Université de Toulouse, INP, IRIT, Toulouse, France, and NAXYS, University of Namur, Namur, Belgium.

Momentum Methods Nonconvex Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods

Ask PDF

Apr 15, 2026

A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity

Davis, Drusvyatskiy, and Jiang showed that gradient descent with an adaptive stepsize converges locally at a nearly-linear rate for smooth functions that grow at least quartically away from their minimizers. The argument is intricate, relying on monitoring the performance of the algorithm relative to a certain manifold of slow growth -- called the ravine. In this work, we provide a direct Lyapunov-based argument that bypasses these difficulties when the objective is in addition convex and a has a unique minimizer. As a byproduct of the argument, we obtain a more adaptive variant than the original algorithm with encouraging numerical performance.

Damek Davis, Dmitriy Drusvyatskiy

Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, Philadelphia, PA 19104

Gradient Descent Adaptive Gradient Methods

Ask PDF

Abstract

Nonconvex Optimization

Explore similar work

An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent

A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad, Shampoo and Muo

A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity