Overview

Gradient descent is a family of methods that repeatedly adjusts parameters in the direction that lowers an objective, making it a basic tool for training neural networks and fitting models such as logistic regression. Common approaches include full-batch and stochastic gradient descent, momentum and Nesterov acceleration, adaptive optimizers such as Adam, and geometry-aware variants such as natural, preconditioned, projected, or mirror descent. Theory and applications span deep-network training, matrix recovery, differential privacy, and decentralized or federated learning, with evaluations often measuring convergence, prediction quality, communication, memory, or privacy cost. A central tension is that larger or adaptive steps can speed training but also cause oscillations or instability, while the geometry, noise, and stopping time can change both which solution is reached and how well it generalizes.

Latest papers

122 papers4 papers in the last four weeks, down 79% on the four weeks before. 0.0% of all new papers.

Nov 5, 2026

Adversarial Training with Large Step Sizes: Implicit Bias, Optimization, and Sharpness

Adversarial Training (AT) is an important method for improving model robustness. We study the dynamics of deterministic Gradient Descent (GD) in AT. Most existing works in this direction focus on the small or vanishing step sizes regime, where GD resembles a continuous-time flow. However, such step sizes can make training inefficient and are rarely used in practice. In this paper, we study the AT dynamics of GD with large constant step sizes. We first study GD in adversarial linear logistic regression, focusing on two aspects: where the model parameters converge (implicit bias) and how quickly the losses decrease (optimization). We then turn to neural networks training and study how the sharpness of losses evolve during AT. Our results advance the understanding of the behaviors of GD with large step sizes in AT and highlight three key differences from its behavior in Standard Training (ST): (i) the implicit bias gap between AT and ST, previously established only for small step sizes, persists for arbitrarily large constant step sizes, (ii) different from ST, there is no uniform rate of convergence for the optimization error in AT, and (iii) sharpness can exhibit two-stage dynamics that differ from the Edge-of-Stability behavior observed in ST.
Nov 3, 2026

Stepsize modulation for cross entropy from local quadratic optimization

Two methods are presented that perturb a given learning rate schedule in stochastic gradient descent with cross entropy loss. Both methods use an extra forward pass to estimate various derivatives of the minibatch loss. The first method selects a value ηη by linearising the softmax values and minimizing the squared error 12∣∣y−q−ηq′∣∣F2\tfrac 1 2 ||y - q - ηq'||_F^2, where qq is the matrix representing the softmax values of the minibatch and yy is the matrix with one-hot encodings of the labels. The second method considers a quadratic Taylor approximation of the minibatch loss under the outer approximation of the Hessian. Thus, it minimizes L(0)+ηL′(0)+12η2L′′(0)L(0) + ηL'(0) + \tfrac 1 2 η^2 L''(0). Here, the derivatives L′L' and L′′L'' are computed from the derivatives of the logits (using the outer approximation of the Hessian of the loss). We observe that both methods give very similar values of ηη. Finally, these estimated ηη are used to slightly increase or decrease the learning rate of an existing schedule. The method is evaluated on Cifar10 and Cifar100 datasets for training Resnets, where they decrease the loss faster than the schedule that is perturbed and increase monotonicity. For Cifar10 it also leads to a small improvement of test accuracy, but in Cifar100 test accuracy remains the same.
Oct 19, 2026

Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression

We show that gradient descent (GD) with step size ηη can achieve ε\varepsilon optimality gap on the multiclass logistic regression loss in a number of iterations TT that is independent of ε\varepsilon. To do so, the step size ηη must be chosen large enough as a function of ε\varepsilon (and properties of the linearly separable dataset), while TT is a constant that only depends on the data. The relevant properties of the data include the number of points and their margin (for TT), and one additional quantity (for ηη) that turns out to be necessary in dimension d≥3d \geq 3. The proofs build on the known fact that, as η→∞η\to \infty, suitably rescaled GD becomes the perceptron algorithm, and the latter finds a perfect classifier in TT iterations. A similar claim was shown for two classes in dimension d=2d = 2 using other proof techniques. This result adds to previous works that showed GD on the logistic regression loss can be accelerated by taking large step sizes. Those provoke a wild, oscillatory initial phase, followed by a stable phase. We provide results of this (qualitatively different) nature, too.
Oct 15, 2026

Understanding Stability of Outer Nesterov Momentum on Stochastic Pseudo-Gradients

Large neural networks are commonly trained across many workers, and communication between them is a major cost. Workers therefore take several local optimization steps before sending their net parameter displacements, or pseudo-gradients, to an outer optimizer, which often applies Nesterov momentum. We study how the outer momentum, the number of local steps and the averaging over workers control the training dynamics, and in particular their stability. For random quadratics, we derive an exact mean-square stability criterion in any dimension, which reveals that the inner batch size determines whether increasing the number of local steps eventually stabilizes or destabilizes the outer iteration. Moreover, while averaging the pseudo-gradients of independent workers can make larger outer momentum values admissible, the number of workers required for stability can grow exponentially with the number of local steps. Finally, we show that the mean-square dynamics governing stability can be probed directly at intermediate neural-network checkpoints using shared-minibatch perturbations. We test our theoretical findings across networks, and measure their consequences for training loss.
Oct 9, 2026

Geometry-Aware Multi-Objective Optimization: Norm-Constrained Oracles with Entropic Weight Updates

Multiple-gradient descent is typically formulated in Euclidean geometry, whereas matrix-aware optimizers use directions induced by other norms. We analyze a single-loop multi-objective method combining a norm-constrained linear minimization oracle with entropic updates of task weights. For any finite-dimensional norm pair, we establish an O(T−1/2)O(T^{-1/2}) ergodic stationarity rate in the deterministic setting, deriving the required trajectory gradient bound from smoothness and lower-boundedness in the unregularized case. With stochastic gradients and a bounded-gradient assumption, one persistent blended-gradient momentum buffer yields an O(T−1/4)O(T^{-1/4}) rate whose leading term has no explicit dependence on the number of tasks. We also establish static regret for the inner weighting objective on arbitrary bounded gradient sequences and, with entropy regularization and a weight floor, iteration-wise inner-gap control after burn-in while retaining ergodic stationarity, conditional on a trajectory gradient bound. The optimal blended gradient can be nonunique in spectral and sign geometries, motivating a selection-independent inner gap. Our analysis extends the spectral construction studied by concurrent MOON to general norms. Experiments compare the method with existing multi-task optimizers and examine its oracle, weighting, and momentum choices.
Oct 5, 2026

Inference and learning in sparse autoencoders as natural gradient flow

Sparse autoencoders are widely used to uncover interpretable features in neural networks, yet reliable recovery remains difficult when features overlap or activate infrequently. These challenges involve both inferring which features explain an input and learning the dictionary that represents them. Here, we unify inference and dictionary learning as natural-gradient flows on a shared variational free energy. We instantiate this framework as BeFOND, an encoder-free sparse coding model with closed-form inference and learning dynamics. We show how recurrent explaining away reduces interference between overlapping features, while Fisher preconditioning can compensate for the slow learning of rare features. On synthetic data, BeFOND improves dictionary recovery and rare-feature detection, with a growing advantage over amortized baselines as superposition increases. On language-model activations, it improves single-feature concept detection and selective intervention, outperforming pretrained reference SAEs with substantially less training data. Its feature quality continues to improve with dictionary width, whereas the evaluated baselines largely plateau. Together, these results show how improving inference and learning within a unified probabilistic framework can make better use of data and dictionary capacity to interpret and intervene on neural representations.
Oct 5, 2026

Interleaved Projected Gradient Descent for Safe Imitation Learning

We propose an imitation-learning design for neural-network control policies under state and input constraints. Training alternates a standard imitation gradient step with a block of kk safety steps that pull the network's actions toward their projection onto the safe set; at run time, the controller is the trained network alone, with no safety filter. We analyze this scheme as inexact projected gradient descent in the space of policy actions. When the projected actions are recomputed at every safety step and each step moves the actions consistently toward the safe set, letting kk grow logarithmically yields asymptotic constraint satisfaction on the training states and bounds the distance to the constrained optimum of the imitation loss; with the projected actions held fixed, the same holds only if they are exactly representable by the network. On a nonlinear autonomous racing task, we compare our method with adding a weighted constraint-violation penalty to the imitation loss. With a sufficiently large weight, our method matches the lap time of unconstrained imitation while reducing the fraction of violating episodes from 15%15\% to 1%1\%, about six times fewer than the penalty approach at its best weight. Its lap times are less sensitive to the weight, which instead sets how quickly violations vanish during training. In racing, the safety corrections are sparse and the conditions of the analysis do not hold; the gain arises instead through the data collected during training. These gains come at the cost of additional training computation.
Oct 5, 2026

Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression

We study gradient descent (GD) with a large constant stepsize for logistic regression on linearly separable data. Existing analysis shows an accelerated rate of O~(1/ε)\widetilde{O}(1/\sqrtε) to reach loss εε with an aggressive stepsize, although the loss may initially oscillate. Tighter control of the oscillatory dynamics has been available only for two-dimensional data. We prove a substantially faster rate in arbitrary dimension: GD with a large stepsize η=1/εη=1/ε reaches loss εε within O(ln⁡p(1/ε))O(\ln^{p}(1/ε)) steps, where pp depends only on the margin and the rank of the data. Our proof improves the bound on the transition time of GD from the oscillatory to the stable phase, after which the loss decreases monotonically. We split the oscillatory phase into recursively nested intervals. The margin and the rank bound the nesting depth, and a counting argument bounds the number of intervals at each depth, together yielding the polylogarithmic step complexity.
Oct 5, 2026

Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness

Normalized gradient descent is a widely studied adaptive optimization method. Most existing analyses focus on the best iterate or a weighted average of the iterates, whereas practical implementations typically return the last iterate. In this paper, we study the last-iterate convergence of normalized gradient descent for convex, (ν,Mν)(ν,M_ν)-Hölder-smooth objectives. For a constant stepsize, we establish an upper bound of O((log⁡2(T)/T)(1+ν)/2)\mathcal{O}\bigl((\log^2(T)/T)^{(1+ν)/2}\bigr), which contains a logarithmic overhead relative to the known O(T−(1+ν)/2)\mathcal{O}\bigl(T^{-(1+ν)/2}\bigr) guarantees for the best and weighted-average iterates. For ν=0ν= 0, this overhead is known to be unavoidable. We complement this analysis with numerical results based on the performance estimation problem (PEP), investigating the finite-horizon worst-case behavior in the smooth setting and whether the logarithmic overhead reflects an intrinsic limitation of constant-step normalized gradient descent. We then show that a linearly decreasing stepsize yields a last-iterate guarantee of O(T−(1+ν)/2)\mathcal{O}\bigl(T^{-(1+ν)/2}\bigr), matching the order of the best-iterate/weighted-average guarantees without requiring knowledge of νν and MνM_ν.
Oct 5, 2026

Learning Decision-Stump Thresholds in Context: Dynamics of Softmax Attention

Estimating a decision threshold requires locating observations near an unknown boundary. We study how gradient-based pretraining learns this statistical rule in a two-parameter softmax-attention model with a fixed feature and inequality direction. Pretraining uses labeled contexts and their true thresholds; a fresh threshold must be inferred from context alone. Under a large-resolution initialization, constant-step gradient descent on mm tasks with nn examples each produces a frozen estimator with error O~((m∧n)−1+N−1)\widetilde O((m\wedge n)^{-1}+N^{-1}) for each fixed interior threshold and every fresh-context size NN. The two terms separate finite-pretraining accuracy from fresh-context localization. The mechanism is coordinated parameter divergence: population training calibrates the relative label and feature scores, then increases the attention scale as t1/4t^{1/4}, giving population threshold error O(t−1/4)O(t^{-1/4}). To transfer this mechanism to a fixed finite corpus, we control gradient errors relative to the shrinking directions of progress at successive parameter scales. This certifies a growing training interval without requiring long-time tracking of the population trajectory. We also identify the boundary limitation of the one-head model and explain statistically what a reflected symmetrization could achieve.
Oct 4, 2026

Smoothed Gradient Method for Nonconvex Federated Stochastic Bilevel Optimization

In recent years, federated stochastic bilevel optimization has attracted increasing attention due to its wide range of applications in machine learning. To reduce the computational overhead associated with second-order Hessian and Jacobian matrices, several first-order methods have been proposed. However, existing methods typically impose restrictive assumptions on the lower-level function, suffer from a strong dependence on the condition number in their convergence rates, and require different learning-rate scales for variables across the upper- and lower-level problems, limiting their practical applicability and complicating hyperparameter tuning. To address these challenges, we propose a stochastic doubly smoothed gradient method for nonconvex federated stochastic bilevel optimization problems, which decouples the learning rates of upper- and lower-level variables and does not require a strongly-convex lower-level loss function. We establish rigorous theoretical guarantees for the proposed algorithm, demonstrating an improved convergence rate of O(κ15/2/ε5)O(κ^{15/2}/ε^5) and a communication complexity of O(κ4/ε3)O(κ^{4}/ε^3), where κκ denotes the condition number and εε represents the solution accuracy. Notably, these bounds exhibit significantly better dependence on the condition number κκ than those of existing methods. Extensive experiments validate the effectiveness of our algorithm.
Oct 2, 2026

Differential Privacy of Gradient Descent on Perturbed Objectives

Objective perturbation adds a random linear term to a regularized empirical risk and releases the exact perturbed minimizer. We study the finite computation obtained by releasing the NN-th iterate of deterministic gradient descent on w↦F(w;S)+⟨z,w⟩w\mapsto F(w;S)+\langle z,w\rangle, where z∼N(0,σ2Id)z\sim\mathcal N(0,σ^2I_d) is drawn once before optimization. For strongly convex and smooth objectives with Lipschitz Hessian, we prove an explicit condition under which the map z↦wNz\mapsto w_N is a C1C^1-diffeomorphism on the bounded domains used in the privacy argument, with a quantitative lower bound on the smallest singular value of its Jacobian. This permits a direct change-of-variables analysis of the finite iterate. For generalized linear models, the resulting privacy-profile bound has no explicit ambient-dimension factor once the iteration condition holds, and its finite-iteration correction decreases geometrically. By letting the free truncation parameter grow slowly with NN, we recover the corresponding exact-minimizer certificate in the limit. We also bound the expected excess empirical risk by dσ2/(2μ)dσ^2/(2μ) plus a geometrically decreasing optimization term, and transfer the result to population risk without an additional multiplicative condition-number factor in the leading statistical terms.
Oct 1, 2026

CAGE-NAS: Certified Functional Descent for Efficient Model Growth

The progressive growth of neural networks requires deciding when the current representation remains sufficient for optimization and when it should be expanded. CAGE-NAS formulates this decision in function space through an admissibility criterion on approximations of the functional gradient. As long as a representation enables a certified Functional Gradient Descent step, the architecture remains fixed; when the criterion fails, a function-preserving expansion is applied and the resulting representation is evaluated again. As the main instance, we study the family induced by the tangent space, using a regularized projection of the functional gradient. In a controlled setting with exact certification, CAGE-NAS produces architectures positioned above the 99.8th performance percentile by held-out RMSE among all admissible alternatives within the same parameter budget, without enumerating them during the growth trajectory.
Sep 30, 2026

Convergence of Practical Muon with Finite Newton-Schulz Iterations and Nesterov Momentum

Practical Muon maintains momentum and performs a small, fixed number of Newton--Schulz iterations separately for each parameter matrix, often with a Nesterov correction. We analyze these layer-wise finite-step updates jointly on a coupled nonconvex objective, rather than replacing them by exact polar factors or one global orthogonalization. Under gradient-dependent (L0,L1,q)(\mathcal L_0,\mathcal L_1,q)-smoothness and conditionally unbiased stochastic gradients with bounded layer-wise variance, we establish an O(T−1/4)\mathcal O(T^{-1/4}) bound on the expected average Frobenius gradient norm. The analysis retains the Nesterov recursion and requires neither bounded stochastic gradients, symmetric noise, nor a uniform positive lower bound on the nonzero output singular values. Its constants contain no explicit matrix-dimension or rank factors when the number of blocks and problem constants are fixed. The proof follows a descent inequality and a decomposition of the momentum tracking error into initialization, noise, and drift. For the original five-step quintic, we verify the required scalar-map bounds analytically; the result also allows step-dependent coefficients satisfying the same bounds. A complementary nuclear-norm result quantifies rank dependence under a stronger spectral condition. The vanishing rate uses coupled learning-rate and momentum schedules, including the standard single-coefficient Nesterov rule.
Sep 29, 2026

Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis

Polyak step size (PS) and Armijo line search (ALS) have received increasing attention in stochastic optimization, with encouraging empirical performance and theoretical guarantees. However, their convergence theory for stochastic heavy ball (SHB) methods remains limited. In this work, we develop a unified convergence analysis for SHB equipped with PS and ALS. To this end, we introduce a modified Armijo rule that closely parallels the Polyak step size, together with a decoupling analysis that isolates the historical dependence induced by momentum. For SHB with standard PS and ALS, we establish expected convergence for strongly convex, convex, and non-convex objectives without interpolation or restrictive conditions on the momentum parameter. Under interpolation or strong growth, we further strengthen the results to almost sure rates and last-iterate convergence. Moreover, for general settings beyond interpolation, we prove almost sure convergence to the exact optimum or to stationarity for SHB with diminishing variants of PS and ALS. These results provide a more comprehensive theoretical view of Polyak step size and Armijo line search for stochastic heavy ball methods.
Sep 28, 2026

Convex Optimization Is Free When Accuracy Is Expensive

This paper studies convex optimization when the gradient cannot be evaluated exactly, but only approximated by a hierarchy of algorithms whose compute grows like δ−γδ^{-γ} in the accuracy δδ. When γ>2γ>2, falling into the Harder-Than-Monte-Carlo (HTMC) regime, the price of accuracy outruns the variance reduction that Monte Carlo would buy and we show that minimizing a loss function costs no more, up to a factor depending only on γγ, than a single evaluation of its gradient at the accuracy the problem demands. A randomized multilevel oracle replaces the deterministic approximation of accuracy δδ by an unbiased estimator of it, whose variance σ2σ^2 becomes a second, independently priced dial: the cost of one call drops from δ−γδ^{-γ} to δ2−γσ−2δ^{2-γ}σ^{-2}. Plain inexact gradient descent driven by that oracle reaches loss ε\varepsilon at expected compute Θ(ε−γ)Θ(\varepsilon^{-γ}) in the convex case, against Θ(ε−(γ+1))Θ(\varepsilon^{-(γ+1)}) for the same method run at a fixed accuracy: randomization buys a full power of ε\varepsilon. Under μμ-strong convexity the exponent halves, to ε−γ/2\varepsilon^{-γ/2}, because the iterates settle at a noise floor and the bias budget relaxes accordingly. Both bounds are independent of the step size, and hence of the smoothness constant, and we show that the cost is a functional of the underlying gradient flow rather than of any discretization of it.
Sep 28, 2026

LionMuon: Alternating Spectral and Sign Descent for Efficient Training

Pretraining a language model takes enormous compute, and the right optimizer can save a good part of it. Muon's spectral step gives a stronger direction than a sign step, but it is expensive. Every step runs Newton-Schulz iterations on the full matrix and, in distributed training, an extra all-reduce. Sign steps, as in Lion and Signum, are cheap and stay local to each device. We propose LionMuon, which takes one Muon step every PP iterations and Lion steps in between, with a single dual-EMA momentum buffer shared by both. Muon's compute and communication are paid once per PP steps, and the optimizer state is half of AdamW's. A single-EMA variant, SignMuon, already improves on Muon. We prove complexity bounds under heavy-tailed noise in which the period sets an interpolation between Muon's and Lion's smoothness and noise constants, and which say when LionMuon is faster than both. On 124M and 355M models trained on FineWeb, LionMuon with P=2P=2 and P=5P=5 reaches a lower loss than Muon, AdamW, Lion and Signum at the same number of tokens. Under 4-GPU data-parallel training it reaches Muon's final loss with a third less wall-clock on PCIe, and it beats the communication-efficient Muon variants Dion and MuonBP on loss at no more exposed communication, while keeping the exact gradient. Code: https://github.com/brain-lab-research/lion-muon
Sep 28, 2026

GradLev: Token-Parallel Test-Time Training Via Costate Prediction

Test-time training (TTT) allows a model to improve its predictions at inference time by updating weights after every observed token. However, sequential gra- dient writes make parallel training difficult. We observe that, given layer inputs and activation gradients (costates), online gradient descent admits exact parallel scans for both forward evaluation and reverse backpropagation. GradLev lever- ages this duality: a causal auxiliary network predicts costates across all tokens in parallel; associative scans compute the adapted weights and forward activations and propagate gradients backward; and the resulting gradient targets supervise the predictor via a consistency loss. Exact consistency guarantees exact recovery of the sequential online learner. At deployment, the auxiliary predictor is discarded, and the model updates natively via token-by-token forward and backward passes.
Sep 26, 2026

Overfitting of Spectral Gradient Descent: How Matrix Geometry shapes Generalization and Implicit Bias

We study the generalization of spectral gradient descent (SpecGD) in overparameterized matrix classification with corrupted labels. Each input combines a shared low-rank signal with a rank-one sample-specific perturbation, referred to as a shortcut, that enables memorization but does not generalize. We contrast collapsed shortcuts, which share a singular direction, with dispersed shortcuts, which occupy distinct singular directions. Changing only this geometry can reverse the relative generalization of GD and SpecGD: collapsed shortcuts can favor SpecGD, while dispersed shortcuts can favor GD. In the dispersed regime, exact shortcut orthogonality eliminates the signal from the late-stage SpecGD direction, while vanishing random correlations collectively generate a small but generalization-relevant signal through a second-order effect. To identify the direction selected by SpecGD, which the spectral max-margin problem alone does not determine, we combine a refined analysis of its dual with the exponentiated-gradient dynamics of normalized loss weights. Finally, we show that a single SpecGD step can already interpolate and generalize well, while continued training converges to a direction with substantially worse generalization.
Sep 25, 2026

Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems

The Gromov-Wasserstein (GW) distance measures the discrepancy between metric measure (mm) spaces and identifies optimal alignments between them based solely on their intrinsic structure. Since it identifies isomorphic mm spaces, it provides a natural notion of distance for heterogeneous datasets which may admit isomorphic representations. In order to accelerate computation of GW distances, many practitioners employ entropic regularization to obtain an Entropic GW (EGW) problem. The most popular EGW solver is the Mirror Descent (MD) algorithm, which reduces EGW computations to an iterative process where an entropic optimal transport (EOT) problem is solved at each iteration. Despite its widespread use, the convergence of MD for this problem has only been established for restricted classes of costs. On the other hand, a recently proposed dual gradient method is available for general costs, but requires a choice of step size which depends on the regularization parameter. To address these two issues, we introduce Averaged Mirror Descent (AMD), which averages consecutive MD steps, and prove its convergence for arbitrary costs. Then, we establish that the dual gradient method with a fixed step size also converges for arbitrary costs at the cost of a more complicated iteration. In both cases, we also account for inexact iterations which are inescapable in practice. We compare the empirical performance of these methods across various settings and, in particular, show that AMD and the dual gradient method both converge on an example where classical MD fails.
Sep 21, 2026

Continuous Optimization for p-adic Models

We present the first method for native, continuous gradient descent for machine learning models with pp-adic parameters. Existing native optimizers are discrete, mostly combinatorial searches, as the pp-adic numbers Qp\mathbb{Q}_p are totally disconnected, with standard losses that are flat away from their minima. To enable continuous optimization, we propose working with Qp\mathbb{Q}_p via its Berkovich affine line: a canonical, path-connected expansion of Qp\mathbb{Q}_p that preserves its isometries and uniquely extends its analytic maps. This hull is a metric tree with interpretable points and local derivatives, which we show enables effective optimizers and backpropagation. We formulate gradient descent and show that its approximations efficiently learn linear models with coefficients in Qp\mathbb{Q}_p to do modular arithmetic, an XOR-like task not expressible by linear models in R\mathbb{R}. We also demonstrate momentum and Adam variants, linear regression, and classification on binary-encoded hierarchies (Quillian semantic networks), addressing open problems posed by Martins (2025). Library at https://github.com/google-deepmind/padic-ml
Sep 16, 2026

Gradient Descent with Stochastic Subspaces via Persistence of Memory

Stochastic subspace methods have gained popularity as gradient descent based techniques for large scale optimisation problems, especially in distributed settings. In this paper, we introduce the technique of "persistence of memory" to greatly extend and improve the random subspace methods. To this end, we leverage a vector that is only weakly correlated with the gradient in order to provide a guiding structure to the generative process of the random subspace along which the descent is going to take place. This guidance vector may be fixed for a large number of iterations, only to be refreshed at wide intervals (on whose size we can provide guarantees in terms of problem parameters). In important machine learning settings, such as optimisation problems embodying sparsity or a minibatch structure, we show that the guidance vector can be obtained in an effective and computationally inexpensive manner by leveraging the structured properties of the problem. En route, we establish to our knowledge the first theoretical analysis of classical SSD methods for sparse functions. In a local neighbourhood of the optimum, we demonstrate an alignment phenomenon of our gradient estimates with a low-lying eigenvector of the Hessian, allowing a once-for-all computation of the guidance vector which renders the method computationally favourable even in scenarios with unstructured objectives.
Sep 15, 2026

Geometry of learning dynamics: Gradient descent versus natural gradient on the ridge of optimization

High-capacity associative memories based on Kernel Logistic Regression (KLR) exhibit a "Ridge of Optimization" characterized by extreme stability and a highly skewed weight spectrum. However, the dynamical process by which learning converges to this critical regime has remained unclear. This paper provides a geometric analysis of the learning trajectories on the statistical manifold of a KLR-trained Hopfield network. By comparing the paths of Gradient Descent (GD) and Natural Gradient Descent (NGD), we elucidate the mechanisms governing the optimization process. Our analysis reveals that learning on the Ridge proceeds in two distinct phases. We show that the extreme curvature of the Ridge causes standard GD to follow a highly oscillatory, non-geodesic path. In stark contrast, NGD explicitly corrects for this geometry, following the ideal geodesic path and completely overcoming the instabilities faced by GD. We demonstrate experimentally that NGD not only converges significantly faster but also achieves a solution with superior generalization performance. These results establish that the highly structured geometry of the Ridge is optimally suited for information-geometric optimization, providing a new perspective on the interplay between learning dynamics and emergent representation geometry.
Sep 8, 2026

Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader

Online gradient descent is usually studied through external regret, where the learner competes with fixed alternatives. Recent work shows that first-order methods control richer action-dependent deviations. We ask for a geometric characterization of the deviations with respect to which online gradient descent, mirror descent, and follow-the-regularized-leader (FTRL) achieve no regret. We identify exactness as the common principle. Exactness means that the relevant displacement field is generated by a scalar potential, or equivalently that the associated one-form is exact in the geometry used by the algorithm. This geometry depends on the algorithm. For gradient descent it is Euclidean geometry, for mirror descent it is the geometry induced by the regularizer, and for FTRL it is the cumulative dual state. Under mild regularity conditions, exactness yields sublinear regret, while nonzero circulation provides the complementary obstruction and leads to linear regret. This gives a unified geometric framework for understanding the deviation classes controlled by these algorithms and reveals that different first-order methods can control genuinely different classes of deviations. These deviation classes have direct consequences for learning, particularly in games. We study the equilibrium notions induced by exact-form deviations and introduce conservative correlated equilibrium, reflecting both the conservative geometry of the underlying displacement fields and the restricted family of deviations available to the players. We characterize its relation to correlated equilibrium, determine when the resulting equilibrium notions coincide and when they separate, and show how these relationships depend on the geometry and the learning algorithm. Overall, this work gives a unified geometric account of what first-order online learning algorithms are no-regret with respect to, beyond fixed comparators.
Sep 8, 2026

Silver Rate Is (Almost) Optimal for Gradient Descent

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing psil=log⁡2(1+2)p_{\mathrm{sil}}=\log_2(1+\sqrt{2}), we prove an Ω(n−psil−O(log⁡log⁡n/log⁡n))Ω\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right) non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error Ω(n−2psil1+psil−O(log⁡log⁡n/log⁡n))Ω\left(n^{-\frac{2p_{\mathrm{sil}}}{1+p_{\mathrm{sil}}}-O(\sqrt{\log\log n/\log n})}\right). Together with the silver-schedule upper bound [Altschuler and Parrilo, 2025] and the anytime upper bound [Zhang et al., 2025], our results determine the optimal polynomial convergence exponents in both settings.
Sep 6, 2026

Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption

We investigate stochastic simple bilevel optimization with smooth and possibly nonconvex upper- and lower-level objectives. Existing stochastic extensions of dynamic barrier gradient descent (DBGD) either obtain fast convergence under an unverifiable trajectory-dependent ``rare-visit'' assumption, or remove this assumption at a substantially higher oracle cost. We show that a simple denominator-only regularization of the DBGD multiplier eliminates the need for such an assumption while preserving fast convergence rates. Specifically, our method achieves (ε,ε)(\varepsilon, \varepsilon)-stationarity in O(ε−2)O(\varepsilon^{-2}) iterations using O(ε−4)O(\varepsilon^{-4}) upper-level and O(ε−7)O(\varepsilon^{-7}) lower-level stochastic gradients, which improves upon the best assumption-free complexities. We additionally derive anytime parameter schedules.
Sep 2, 2026

Improved Gradient Descent Lower Bounds Beyond Nesterov

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical Ω(n−2)Ω(n^{-2}) first-order oracle lower bound of Nemirovsky and Yudin (1983), we prove an Ω(n−1.6342)Ω(n^{-1.6342}) non-anytime lower bound and an Ω(n−1.2408)Ω(n^{-1.2408}) anytime lower bound. These improve the recent Ω(n−1.932)Ω(n^{-1.932}) non-anytime lower bound of Ma and Chen (2026) and the Ω(n−4/3)Ω(n^{-4/3}) anytime lower bound of Tsai et al. (2026), respectively. Both results continue to hold when the stepsizes may be negative. Our anytime lower bound also shows that the O(n−log⁡2(1+2))O(n^{-\log_2(1+\sqrt{2})}) rate of non-anytime silver schedules (Altschuler and Parrilo, 2025; Grimmer et al., 2025) is unattainable in the anytime setting. This establishes a strict separation between the two settings.
Sep 2, 2026

Momentum in large-batch training: Polyak enlarges the critical batch size, Nesterov improves data efficiency

We study when and how momentum improves large-batch training in the one-pass regime, using power-law kernel regression as a tractable setting. We first characterize stochastic stability through the critical learning rate, defined as the largest learning rate for stable training, and obtain ηSGDcrit≂1η_{\mathrm{SGD}}^{\mathrm{crit}}\eqsim 1, ηPolyakcrit≂min⁡{1,B(1−β)}η_{\mathrm{Polyak}}^{\mathrm{crit}}\eqsim \min\{1,B(1-β)\}, and ηNesterovcrit≂min⁡{1,Bq(1−β)}η_{\mathrm{Nesterov}}^{\mathrm{crit}}\eqsim \min\{1,B^q(1-β)\}, where BB is the batch size, β∈[0,1)β\in[0,1) is the momentum factor, and q>1q>1 is the capacity exponent governing spectral decay. Within the stable region, we derive scaling laws for the full risk dynamics, capturing the progression from an early transient through power-law decay to a noise floor. We then optimize the final-step risk under a fixed data budget, obtaining a three-regime phase diagram that reveals how the benefits of momentum change with batch size. Notably, Polyak enlarges the critical batch size, the largest batch size preserving the optimal small-batch data-scaling exponent, thereby allowing fewer sequential updates without sacrificing data efficiency. In contrast, Nesterov improves the optimal data-scaling exponent in the large-batch regime through look-ahead-induced suppression of noise amplification. Experiments on PLK regression quantitatively support the theoretical scaling predictions, while neural-network experiments provide qualitative evidence for the predicted batch-size dependence and stability behavior.
Aug 20, 2026

Kähler landscapes for complex neural network descents and guarantees including a search and destroy of the Calabi-Yau manifold

We study landscapes for complex-parameterized networks. Our approach is motivated with an information-theoretic manifold perspective of the parameter and via classical optimization guarantees although of complex geometric variety such as through Dolbeault asymptotics. The descent path admits a Kähler information metric under a cross-entropy via the Wirtinger Hessian on the log-likelihood potential. We restrict attention to a descent update rule with natural gradient descent via a differentiated loss scaled by the inverse metric, so the descent path remains in the holomorphic tangent bundle. We emphasize Calabi-Yau information manifolds which profane theoretical guarantees via an ill-curvature-conditioned, or lack thereof, landscape. We focus on Calabi-Yau metrics specifically in a non-compact setting with a global potential, so defined geometrically rather than invoking the topological requirements of the Calabi conjecture. In non-compact settings, we can write the metric determinant with respect to a background in terms of a function, pluriharmonic or real. Using Yau's Liouville theorem, we get a partial eigenvalue blow-up effect. In an empirical setting, a Ricci-flat metric will not form, but a blow-up can be a local condition and can hold empirically on open sets even partially in generalized Kähler cases due to lower bounds on the Ricci potential. Moreover, it has been discovered that negative curvature subverts the loss landscape, specifically sectional curvature, so we expand on this and draw interconnections to negative-definite Ricci curvature. Our arguments primarily exist via geometric modality, although we establish roots in deep learning theory such as through asymptotics at initialization and connections through failure modes of neural network guarantees under vanishing and negative Ricci curvature.
Aug 11, 2026

Convergence Guarantees of Gradient Descent for Neural Networks via Generalized Lipschitz Smoothness

We establish the first convergence guarantees of gradient descent for general feedforward neural networks of any width or depth, with any initialization or dataset. We only assume that the activation functions are linearly bounded, Lipschitz continuous, and Lipschitz smooth---properties that hold for linear, tanh, softplus, sigmoid, and smoothed ReLU functions---and that the loss function is Lipschitz smooth in the model outputs, a mild condition satisfied by mean squared error and binary cross-entropy loss. By relating the Lipschitz properties of one layer to the next, we obtain a novel generalized Lipschitz smoothness condition for an LL-layer neural network where the change in gradient is upper bounded by the change in the parameter space, multiplied by a polynomial of the parameter norms at both endpoints of degree 2L−22L - 2. This yields a descent lemma where the loss decreases as long as the learning rate is small enough with respect to the parameter norms. By ensuring that the leading term of the polynomial grows at a controlled rate, we prove that the minimum squared gradient norm converges to zero in TT iterations at rate O(1/T1/L)O(1/T^{1/L}).