Natural Gradient Methods

Follow this topic Ask about this topic

Momentum

1 paper in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 16

Oct 7, 2026cs.LG

What a Reporting Convention Hides: A Matched-Budget Audit of Quantum Natural Gradient with an Exactly Computed Metric

Several published comparisons of variational quantum optimizers time only runs that reach a target loss, or read the verdict at a single target. Either convention could decide whether an optimizer's costlier steps pay off. We measure how much each convention changes verdicts among Adam, simultaneous perturbation stochastic approximation (SPSA) and quantum natural gradient (QNG), on initializations held out from the selection of settings. We compute the exact metric that preconditions QNG, price every step in circuit evaluations and give every method the same budget. In a median pooled over circuit widths, cost families and a sweep of settings with common misses, SPSA needs more than twice Adam's evaluations to reach a loose target. Dropping the censored runs that miss the target hides this gap. On the global-cost family we hold fixed the settings selected for a strict target. QNG then usually reaches the loose target after Adam but the strict target first. QNG's strict-target lead disappears when the metric's simulator price, linear in the number of parameters, is replaced by an assumed hardware count quadratic in that number. We recommend charging every miss the budget and reporting verdicts across targets.

Lu Wei, Yufeng Wang, Haibin Ling

Stony Brook University · Westlake University

Quantum Machine Learning Variational Quantum Algorithms Natural Gradient Methods Stochastic Approximation

Oct 5, 2026stat.ML

How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ( \sqrt{ \log d } ) Divergence

Natural gradient descent (NGD) underlies common methods in ML. For dually flat families, idealized NGD on the forward Kullback--Leibler objective follows the mixture geodesic which is often longer than the shortest Fisher--Rao path. We quantify this overhead by the inefficiency ratio

R \ge 1

, the Fisher length of the mixture geodesic divided by the Fisher--Rao distance, and bound its supremum over endpoint pairs as a function of the parameter dimension

d

. A tensor criterion identifies the regime (I) families, with

R=1

everywhere: exactly those with quadratic potential or dimension one, such as fixed-covariance Gaussians. For non-quadratic families, we prove two further regimes: (II) bounded third-order skewness plus finite Fisher--Rao diameter yields a dimension-independent bound; and (III) for products of scale families---including Gaussian covariances and Gamma rates---

R

grows as

Θ(\sqrt{\log d})

, unbounded in

d

. Under a per-step Fisher-chord budget,

R

translates to a practical computational cost: NGD requires asymptotically at least

R

times as many steps as an optimizer following the Fisher--Rao geodesic. Experiments confirm all three regimes:

R=1

to machine precision for quadratic-potential families (I), the categorical bound

π/(2\sqrt{2})

is approached but not attained (II), and sampled scale-product

R

grows with

d

, reaching

R \approx 1.5

for long, high-dimensional moves (III).

Guni Sharon, Alan Kuhnle

Department of Computer Science and Engineering, Texas A&M University, College Station, TX 77843, USA.

Information Geometry Riemannian Optimization Natural Gradient Methods

Sep 27, 2026cs.LG

The cost of useful natural gradient updates

What information is needed to turn a natural-gradient direction into a useful finite update? Under a population Kullback-Leibler (KL) budget, we call a step useful if it is feasible and loses at most a fraction

\varepsilon

of the best feasible gain along the direction. We construct a four-state exponential family whose laws share their initial gradient, scalar Fisher information and natural gradient, yet two laws have disjoint useful-step sets. With these quantities supplied exactly and the law otherwise known only through draws, the family's worst-case sample complexity is

Θ(\log(1/δ)/(p\varepsilon^2))

for small

\varepsilon

, where

p

scales rare-state probabilities and

δ

is the failure probability. The budget is fixed and the optimal gain stays bounded away from zero, so the step length, not the direction, carries this cost. For succinctly described event-tilt models, returning a useful step is NP-hard even with the exact natural gradient and efficient exact sampling. Recovering the unit natural gradient to constant error is also NP-hard even in a two-parameter logistic family with Fisher condition number at most 3. We also give matching sample bounds for event tilts, sample bounds for damped Fisher solves and a population-KL certificate for affine classifiers. In frozen-feature classifier heads, stopping at a sampled KL boundary succeeds in about half of the trials, and a 10% KL margin raises joint success above 93% at a KL budget of 0.01. Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.

Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome

School of Computing, The Australian National University

Sample Complexity Natural Gradient Methods Constrained Optimization

Aug 11, 2026cs.LG

Efficient Hypergradient Descent for Inverse Reinforcement Learning

Inverse reinforcement learning (IRL) aims to recover a reward function under which the resulting policy reproduces the behavior observed in expert demonstrations. A natural approach is to formulate IRL as a bilevel optimization problem, in which the inner level corresponds to policy optimization under the learned reward and the outer level measures the discrepancy between the induced policy and expert data. However, this formulation is computationally challenging in practice because the outer update requires a hypergradient involving an inverse-Hessian-vector product for the inner objective. We address this challenge by showing that, at the inner optimum, the Hessian of the inner objective is proportional to the Fisher information matrix of the policy, yielding a structured Fisher-based hypergradient closely related to Natural Hypergradient Descent. To address the resulting scalability bottleneck associated with large Fisher matrices, we approximate the required inverse-Fisher-vector product using a streaming spectral sketch, avoiding explicit construction of the Fisher matrix. We evaluate our approach against a first-order stochastic bilevel baseline across discrete- and continuous-control environments. The results demonstrate competitive policy performance and strong reward-ranking quality, while Fisher sketching reduces curvature-storage complexity and can improve computational efficiency relative to an explicit Fisher solver.

Nikita Sevriukov, Anna Barabanova, Uliana Gagarina +4

HSE University Moscow, Russia

Reinforcement Learning Gradient Descent Natural Gradient Methods Bilevel Optimization

Aug 11, 2026cs.LG

Fisher8: Stabilizing Neural Heteroscedastic Regression via Output-Layer Fisher Geometry

Training neural networks to jointly predict mean and uncertainty estimates from noisy observations can be unstable, prompting a series of independent stabilization efforts. We argue that these interventions highlight a common underlying issue where gradient steps are poorly aligned with the geometry of the loss landscape. To better align updates with local curvature, we derive Fisher8, an output-layer gradient correction that reorients and rescales updates using Fisher geometry rather than Euclidean geometry. Unlike past stabilizers, Fisher8 introduces no data-dependent hyperparameters beyond learning rate and admits an approximate KL trust radius between successive predictive distributions. We show that prior stabilizers converge on overlapping components of this geometric correction. Across multidimensional regression and representation-learning tasks, Fisher8 obtains superior likelihood--error tradeoffs, predicts calibrated uncertainty estimates, and learns rich uncertainty-aware feature spaces.

Sumedh Vemuganti, Nickvash Kani

Electrical and Computer Engineering Department, University of Illinois at Urbana-Champaign

Natural Gradient Methods Heteroscedastic Regression Uncertainty Calibration

Aug 4, 2026stat.ML

Information-Geometric Forward Policy Training in GFlowNets

Generative Flow Networks (GFlowNets) have emerged as a flexible framework for amortised inference over discrete and mixed discrete-continuous objects, requiring only an unnormalised target density specified through a reward. In this work, we formulate forward-policy training in GFlowNets through the information geometry of the induced trajectory sampler. Treating the forward policy as an induced trajectory sampler, we show that its intrinsic first-order geometry is given by the Fisher-Rao metric of the trajectory family, and that the associated natural gradient provides the canonical local update whenever the corresponding Fisher information is computable or accurately approximable. We derive an exact decomposition of the trajectory Fisher into per-step conditional second moments, which clarifies when temporal score interactions vanish and when dense couplings remain under shared parameterisation. This leads to three computational regimes: settings with tractable exact Fisher information, settings where Monte Carlo estimators of the expected Fisher are sufficient, and structure-exploitable settings in which target locality or factorisation yields accurate approximations of the Fisher expectation. In the latter case, graphical-model tools such as exact marginalisation, separator methods, and belief propagation provide principled surrogates for natural-gradient updates. The resulting framework turns target structure into optimisation geometry and yields a tractable route to structure-aware forward-policy training in GFlowNets. We illustrate the framework empirically through examples comparing convergence and exploration behaviour under Riemannian and Euclidean optimisation.

Yordan Raykov, Rodrigo Veiga

School of Mathematical Sciences, University of Nottingham, Nottingham, UK

Information Geometry Natural Gradient Methods Generative Flow Networks

Jul 25, 2026cs.LG

Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes

Natural Policy Gradient (NPG) is a well-established Reinforcement Learning algorithm that underlies widely used methods such as Trust Region Policy Optimization and Proximal Policy Optimization, both of which have demonstrated strong empirical success. In this paper, we study exact NPG in finite-horizon Markov Decision Processes with known dynamics and horizon-dependent transition kernels. We provide the first finite-time convergence guarantees for this algorithm in this setting, for which we consider both constant and increasing step size regimes. With a constant step size

η_t=η

, we prove that NPG converges sublinearly with a rate of

\mathcal{O}(H^{2}/t)

after

t

iterations, where

H

is the horizon length. We also extend this constant step size analysis to linear MDPs in an exact population-projection oracle under a full support projection distribution, recovering the same sublinear rate as in the tabular setting. Furthermore, with increasing step sizes, we prove that this algorithm achieves a linear convergence rate of

\mathcal{O}\left(\left(1-\frac{1}{\vartheta_ρ}\right)^t\right)

for a problem-dependent constant

\vartheta_ρ> 1

, and the horizon-only robust schedule of the form

η_t=η_0(H/(H-1))^t

where

η_0>0

and

H \geq 2

, attains this same geometric rate.

Asha Barua, Sajad Khodadadian

Grado Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061, USA.

Policy Gradient Markov Decision Processes Natural Gradient Methods Policy Gradient Methods Policy Learning

Jul 24, 2026cs.LG

Energy Manifold Natural Gradient Descent: Riemannian Optimization for Neural PDE Solvers

Energy natural gradient descent (ENGD) aligns parameter updates with the curvature of an underlying function-space energy, but existing formulations assume an unconstrained Euclidean parameter domain. We introduce \EMNGDfull{}, a manifold optimization framework for physics-informed and variational neural PDE solvers whose parameters lie on a Riemannian manifold. EMNGD restricts the energy-induced quadratic model to feasible tangent directions and uses retractions to preserve parameter constraints throughout optimization. Under coercivity, we prove that the push-forward of the undamped EMNGD direction is the best feasible approximation to the function-space Newton vector in the energy metric. We establish coordinate invariance, exact reduction to ENGD in Euclidean space, global first-order convergence with Armijo backtracking, and robustness to inexact tangent solves. For quadratic residual energies and generalized Gauss--Newton pullbacks, the Woodbury identity transfers the tangent system to sample space without changing the direction. Nyström approximation provides scalable sample-space solves with controlled direction error and recovers the exact direction after iterative convergence. On the evaluated neural PDE benchmarks, EMNGD achieves higher accuracy and faster convergence than the compared state-of-the-art baselines. Woodbury preserves the EMNGD direction, while scalable-solver diagnostics quantify the accuracy--cost trade-off of preconditioning and residual subsampling.

Zhangyong Liang, Huanhuan Gao

National Center for Applied Mathematics Tianjin University Tianjin, 300072, China · School of Mechanical and Aerospace Engineering Jilin University Changchun, 130025, China

Neural PDE Solvers Riemannian Optimization Natural Gradient Methods Physics-Informed ML

Jul 7, 2026cs.LG

Differentially Private Natural Gradient Descent

Under a fixed privacy budget, the utility of differentially private (DP) training is ultimately determined by its optimization efficiency. Standard first-order DP optimizers such as DP-SGD rely solely on local gradients and ignore the underlying loss curvature. This geometric blindness causes severe zigzagging in ill-conditioned landscapes, squandering precious privacy budgets on inefficient iterations. Practitioners are thus trapped in a bind: either stop training prematurely or inject massive per-step noise, both of which critically compromise final model utility. Natural Gradient Descent (NGD) resolves this by preconditioning gradients with curvature, aligning updates with the loss geometry and extracting more efficient signal from every noisy step, offering a principled pathway to break the privacy-utility bottleneck. Despite its theoretical appeal, directly integrating NGD with DP introduces fundamental challenges: curvature estimation itself consumes prohibitive privacy budgets, isotropic DP operations conflict with the anisotropic scaling of NGD, and the inverse curvature catastrophically amplify parameter updates in flat directions, causing training instability. We propose DP-NGD, a practical framework that systematically addresses these obstacles by decoupling curvature estimation from private data, reconciling isotropic DP constraints with anisotropic second-order optimization via a whitened-space mechanism, and dynamically clamping the curvature to stabilize training. Extensive experiments on standard benchmarks demonstrate that DP-NGD achieves state-of-the-art accuracy, breaking through the utility ceilings of first-order baselines while delivering up to a

10\times

convergence speedup under the same privacy budget.

Pan Li, Kai Chen, Shuai Chang +3

Institute of Information Engineering, Chinese Academy of Sciences Beijing, China · Department of Computer Science, Metropolitan College, Boston University Boston, United States · Nanyang Technological University Singapore, Singapore

Gradient Descent Natural Gradient Methods Privacy-Preserving ML Differential Privacy

May 28, 2026cs.LG

On the Optimizer Dependence of Neural Scaling Laws

The scaling exponent

α

in neural scaling laws

L(N) \propto N^{-α}

is commonly treated as a fixed constant set by architecture and data. We present evidence that

α

depends systematically on the optimizer. In controlled random-feature regression experiments -- the canonical theoretical framework for neural scaling -- we measure

α

across five optimizer variants and six spectral conditions. Preconditioned optimizers consistently yield steeper scaling (larger

α

), with the

α

-shift increasing across most of the tested spectral range, peaking near

s = 1.5

, and remaining large at

s = 2.0

. At

s \approx 1.0

(characteristic of natural language), the full natural gradient achieves

α\approx 0.31

versus

α\approx 0.12

for gradient descent -- a

2.6\times

larger fitted exponent that, within the random-feature model, compounds with each model-size doubling. Whether and how this exponent shift transfers to large-scale LLM training -- where recent evidence suggests the advantage may attenuate with scale -- remains an important open question. Our results imply that scaling-law forecasts should account for optimizer choice, and we provide a spectral diagnostic predicting when advanced optimizers will pay off.

Vansh Ramani, Shourya Vir Jain

Department of Computer Science and Engineering, Indian Institute of Technology Delhi · Department of Electrical Engineering, Indian Institute of Technology Delhi

Natural Gradient Methods Neural Network Optimization Neural Scaling Laws

May 18, 2026cs.LG

Randomized Advantage Transformation (RAT): Computing Natural Policy Gradients via Direct Backpropagation

Natural policy gradients improve optimization by accounting for the geometry of distribution space, but their practical use is limited by the cost of estimating and inverting the Fisher matrix. We present Randomized Advantage Transformation (RAT), a method for estimating Tikhonov-regularized natural policy gradients via direct backpropagation. By applying the Woodbury formula, we reformulate the regularized natural policy gradients as vanilla policy gradients with a transformed advantage. RAT computes this transformation efficiently via randomized block Kaczmarz iterations on on-policy mini-batches, avoiding explicit Fisher construction, conjugate-gradient solvers, and architecture-specific approximations. We provide convergence guarantees for RAT and demonstrate empirically that it matches or exceeds established natural-gradient methods across continuous and visual control benchmarks, while remaining simple to implement and compatible with various architectures.

Mingfei Sun

The University of Manchester, United Kingdom.

Policy Gradient Natural Gradient Methods Policy Gradient Methods Policy Learning

May 18, 2026cs.NE

Adaptive Stochastic Natural Gradient Method for Safe Optimization on Binary Space

Optimization problems in real-world applications across the medical and engineering domains often involve potential risks when evaluating candidate solutions. Safe optimization aims to perform optimization while suppressing unsafe solution evaluations in such situations. For continuous search spaces, there exist safe optimization methods based on evolutionary computation. However, the algorithm development of safe optimization methods for binary search spaces has not been adequately addressed. In this study, we incorporate additional mechanisms for safe optimization into a binary optimization method, the adaptive stochastic natural gradient method (ASNG) with a family of Bernoulli distributions. For safety functions that must be kept non-negative during optimization, the proposed method, safe ASNG, estimates the Lipschitz constants with respect to the Hamming distance by constructing surrogate models of safety functions based on discrete Walsh functions. Then, safe ASNG computes a safe region that consists of safe solutions around the previously evaluated safe solutions. By projecting newly generated solutions to their nearest neighbors within the safe region, safe ASNG suppresses unsafe solution evaluations. Experimental results on benchmark problems on binary domains confirm that, while the comparative methods fail to suppress unsafe solution evaluations, safe ASNG achieves efficient optimization while effectively suppressing unsafe solution evaluations.

Kento Uchida, Ryoki Hamano, Masahiro Nomura +1

Black-Box Optimization Natural Gradient Methods Constrained Optimization

May 11, 2026cs.LG

Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework

In this work, we show that natural policy gradient, a core algorithm in reinforcement learning, admits an exact formulation as a smoothed and averaged form of policy iteration. Specifically, we introduce doubly smoothed policy iteration (DSPI), a Bellman-operator framework in which each policy is obtained by applying a regularized greedy step to a weighted average of past

Q

-functions. DSPI includes policy iteration, dual-averaged policy iteration, natural policy gradient, and more general policy dual averaging methods as special cases. Using only monotonicity and contraction of smoothed Bellman operators, we prove distribution-free global geometric convergence of DSPI. Consequently, standard natural policy gradient and policy dual averaging achieve an iteration complexity of

\mathcal{O}((1-γ)^{-1}\log((1-γ)^{-1}ε^{-1}))

for computing an

ε

-optimal policy, without modifying the MDP, adding regularization beyond the mirror map inherent in the update, or using adaptive, trajectory-dependent stepsizes. For the unregularized greedy case, corresponding to dual-averaged policy iteration, we also prove finite termination. The same Bellman-operator framework further extends to discounted MDPs with linear function approximation and stochastic shortest path problems.

Phalguni Nanda, Zaiwei Chen

Edwardson School of Industrial Engineering, Purdue University

Policy Gradient Reinforcement Learning Natural Gradient Methods Policy Optimization Policy Iteration Policy Gradient Methods+1

Apr 16, 2026cs.LG

Natural gradient descent with momentum

We consider the problem of approximating a function by an element of a nonlinear manifold which admits a differentiable parametrization, typical examples being neural networks with differentiable activation functions or tensor networks. Natural gradient descent (NGD) for the optimization of a loss function can be seen as a preconditioned gradient descent where updates in the parameter space are driven by a functional perspective. In a spirit similar to Newton's method, a NGD step uses, instead of the Hessian, the Gram matrix of the generating system of the tangent space to the approximation manifold at the current iterate, with respect to a suitable metric. This corresponds to a locally optimal update in function space, following a projected gradient onto the tangent space to the manifold. Still, both gradient and natural gradient descent methods get stuck in local minima. Furthermore, when the model class is a nonlinear manifold or the loss function is not ideally conditioned (e.g., the KL-divergence for density estimation, or a norm of the residual of a partial differential equation in physics informed learning), even the natural gradient might yield non-optimal directions at each step. This work introduces a natural version of classical inertial dynamic methods like Heavy-Ball or Nesterov and show how it can improve the learning process when working with nonlinear model classes.

Anthony Nouy, Agustín Somacal

Centrale Nantes, Nantes Universit´e, Laboratoire de Math´ematiques Jean Leray UMR CNRS 6629

Deep Learning Optimization Riemannian Optimization Momentum Methods Gradient Descent Natural Gradient Methods Neural Network Optimization

Apr 1, 2026cs.LG

Sven: Singular Value Descent as a Computationally Efficient Natural Gradient Method

We introduce Sven (Singular Value dEsceNt), a new optimization algorithm for neural networks that exploits the natural decomposition of loss functions into a sum over individual data points, rather than reducing the full loss to a single scalar before computing a parameter update. Sven treats each data point's residual as a separate condition to be satisfied simultaneously, using the Moore-Penrose pseudoinverse of the loss Jacobian to find the minimum-norm parameter update that best satisfies all conditions at once. In practice, this pseudoinverse is approximated via a truncated singular value decomposition, retaining only the

k

most significant directions. We show that Sven can be understood as a natural gradient method generalized to the overparametrized regime, recovering natural gradient descent in the underparametrized limit. We test Sven on a variety of regression and classification tasks, including small-scale language modeling with transformers, and find that it is competitive with leading baselines such as Adam, Muon, and K-FAC. We also discuss Sven's memory overhead, which presents a barrier to scaling under a naive implementation, and introduce an optimized implementation that keeps memory usage on par with standard baselines under mild restrictions on model architecture. Beyond standard machine learning benchmarks, we anticipate that Sven will find natural application in scientific computing settings where custom loss functions decompose into several conditions.

Samuel Bright-Thonney, Thomas R. Harvey, Andre Lukas +1

Department of Physics, Massachusetts Institute of Technology · The NSF Institute for Artificial Intelligence and Fundamental Interactions · Rudolf Peierls Centre for Theoretical Physics, University of Oxford +2

Deep Learning Optimization Natural Gradient Methods Neural Network Optimization

Mar 28, 2024math.OC

Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients

Kakade's natural policy gradient method has been studied extensively in recent years, showing linear convergence with and without regularization. We study another natural gradient method based on the Fisher information matrix of the state-action distributions which has received little attention from the theoretical side. Here, the state-action distributions follow the Fisher-Rao gradient flow inside the state-action polytope with respect to a linear potential. Therefore, we study Fisher-Rao gradient flows of linear programs more generally and show linear convergence with a rate that depends on the geometry of the linear program. Equivalently, this yields an estimate on the error induced by entropic regularization of the linear program which improves existing results. We extend these results and show sublinear convergence for perturbed Fisher-Rao gradient flows and natural gradient flows up to an approximation error. In particular, these general results cover the case of state-action natural policy gradients.

Johannes Müller, Semih Çaycı, Guido Montúfar

Department of Mathematics, RWTH Aachen University, Aachen, 52062, Germany · Departments of Mathematics and Statistics & Data Science, University of California, Los Angeles, 90095, USA · Max Planck Institute for Mathematics in the Sciences, Leipzig, 04103, Germany

Policy Gradient Optimization Convergence Analysis Natural Gradient Methods Constrained Optimization Linear Programming