Stochastic Gradient Optimization Techniques

Latest papers

• Shortcuts in the Tail: Debiasing via Post-Hoc Spectral Compression of Fine-Tuning Updates

  Edward Sun, Dmitrii Troitskii · 9 June 2026

  Fine-tuning often introduces spurious correlations alongside task knowledge, causing systematic failures on underrepresented groups. Existing mitigations require retraining, group labels, or curated counterfactual data. We show a simple post-hoc intervention reduces shortcut reliance without any of …

• Neural Legendre-Fenchel transform with Hessian Preconditioning

  Basile Plus-Gourdon, Frank Nielsen · 9 June 2026

  The Legendre-Fenchel (LF) transform is a fundamental tool in convex analysis and machine learning that maps lower semi-continuous functions to their convex conjugates. In practice, when closed-form formula are not available for expressing convex conjugates of given functions, one must approximate th…

• Thresholded Local Hyper-Flow Diffusion

  Meher Chaitanya, Sebastian Dalleiger, Luana Ruiz · 9 June 2026

  Local Hyper-Flow Diffusion (HFD) gives an edge-size-independent Cheeger-type guarantee for seeded clustering in general submodular hypergraphs, but existing HFD solvers do not keep intermediate computation local at every iteration. We introduce Thresholded Local HFD (TL-HFD), a first-order method th…

• Learning Dynamics Reveal a Hierarchy of Weight-Induced Layerwise Gram Metrics

  Claudio Nordio · 9 June 2026

  We study feed-forward ReLU networks with fixed readout and quadratic loss. The aim is to rewrite gradient descent not primarily as a dynamics in weight space, but as a collective dynamics closed in terms of fields defined on the training-set space. For a single hidden layer, the weight variables can…

• Improved Convergence Analysis of Topology Dependence in Decentralized SGD

  Yuki Takezawa, Anastasia Koloskova, Sebastian U. Stich · 9 June 2026

  Decentralized SGD is a fundamental algorithm in decentralized learning, although the influence of an underlying network topology on its convergence behavior is not yet fully understood. Existing convergence analyses have shown that topologies with a small spectral gap significantly deteriorate the c…

• LEAF: A Learning-Enabled ADMM Framework for Accelerated Convex Optimization

  Binh Nguyen, Trinh Tran, Truong X. Nghiem · 9 June 2026

  We propose LEAF, a learning-enabled ADMM framework for accelerated convex optimization. The key idea is to approximate the Moreau envelope of the objective function using an Input Convex Neural Network (ICNN), resulting in a learned model that preserves convexity and smoothness. This leads to the pr…

• Generalization in Nonlinear Least Squares via Learned Feature Geometry

  Ayub Kharel, Ilja Kuzborski, Patrick Rebeschini, Yasin Abbasi-Yadkori · 9 June 2026

  We study the generalization of ridge-regularized nonlinear least-squares models via on-average algorithmic stability, deriving error bounds for local minimizers in terms of a data-dependent effective dimension that reflects the geometry of the gradient model at the trained parameters, through the em…

• Predictive Coding with Bayesian Priors via Proximal Gradients

  Francesco Bullo · 9 June 2026

  We recast predictive coding as continuous-time proximal gradient descent applied to a regularized maximum-a-posteriori (MAP) objective. We study first a single-level problem and then a multi-level hierarchy. For the single-level problem, we show that proximal gradient descent is precisely a leaky fi…

• Breaking the Bubble: Asynchronous Pipeline Parallel Training with Bounded Weight Inconsistency

  Itay Elam, Eliron Rahimi, Avi Mendelson, Chaim Baskin · 9 June 2026

  Pipeline parallelism is essential for training large neural networks, but existing schedules trade off throughput, memory, and optimization consistency. Synchronous pipelines preserve forward/backward weight consistency but suffer from bubbles; asynchronous pipelines remove bubbles but introduce wei…

• OptMuon: Closed-Loop Orthogonalized Momentum Methods for Stochastic Optimization with Zero-Noise Optimality

  Ganzhao Yuan · 9 June 2026

  Orthogonalized momentum updates, as used in Muon-style optimizers, have recently shown strong empirical stability in large-scale deep learning. However, existing orthogonalized methods are typically paired with constant or open-loop magnitude rules, and therefore do not explicitly calibrate their up…

• State-Dependent Lyapunov Analysis of Rank-1 Matrix Factorization

  Jaehong Moon · 9 June 2026

  We study gradient descent for rank-1 matrix factorization through a state-dependent Lyapunov perspective. The central object is a parameterized quadratic certificate $I(\delta;\,\cdot)$ whose boundary-inward property induces a monotone state parameter $\delta_t$, thereby certifying that the trajecto…

• Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation

  Yunbei Xu · 9 June 2026

  We prove a variance-aware pointwise majorizing-measure theorem for centered Gaussian processes. Classical generic chaining characterizes the scalar quantity $\mathbb E\sup_{x\in T}X_x$; the theorem here gives a simultaneous high-probability envelope for the entire field. For an ambient prior $\mu$, …

• Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

  Emre Sahinoglu, Shahin Shahrampour · 9 June 2026

  We study decentralized online Riemannian optimization over manifolds with possibly positive curvature, going beyond the Hadamard manifold setting. Decentralized optimization techniques rely on a consensus step that is well understood in Euclidean spaces because of their linearity. However, in positi…

• Tight Sample Complexity of Transformers

  Chenxiao Yang, Nathan Srebro, Zhiyuan Li · 9 June 2026

  We tightly characterize the VC dimension of depth-$L$ Transformers with a total of $W$ parameters, mapping an input sequence of length $T$ to a single output, establishing an upper bound of $O(L W \log (T W))$ and a nearly matching lower bound of $\Omega(L W \log (T W / L))$. We further tightly char…

• Fourier fractal dimension to predict the generalization of deep neural networks

  Joao B. Florindo, Davi Wanderley Misturini · 9 June 2026

  Predicting the generalization performance of deep neural networks without relying on hold-out validation data is a fundamental challenge in machine learning. While Stochastic Gradient Descent (SGD) drives the optimization of these highly parameterized models, its heavy-tailed, non-Gaussian dynamics …

• Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

  Ming Sun, Kun Yuan · 8 June 2026

  Decentralized stochastic optimization is a fundamental paradigm for large-scale learning over networks, where agents communicate only with their neighbors and no central coordinator is required. For strongly convex problems, communication efficiency is mainly determined by the condition number \(\ka…

• Second-Order Path Kernel Interpolation Formulas in Machine Learning

  Jin Guo, Roy Y. He, Jean-Michel Morel · 8 June 2026

  Understanding how training data shape neural network predictions is a central problem in modern learning theory. In 2020, Pedro Domingos proposed an interpolation formula valid for every model learned by deterministic gradient descent. It expresses the model's prediction as an integral, along the op…

• High entropy leads to symmetry-equivariant policies in Dec-POMDPs

  Johannes Forkel, Constantin Ruhdorfer, Michael Beukman, Andreas Bulling, Jakob Foerster · 8 June 2026

  We prove that in any Dec-POMDP, sufficiently high entropy regularization ensures that the policy gradient flow with tabular softmax parametrization always converges, for any initialization, to the same joint policy, and that this joint policy is equivariant w.r.t. all symmetries of the Dec-POMDP. In…

• Flatland: The Adventures of Gradient Descent with Large Step Sizes

  Leonardo Galli, Curtis Fox, Wiebke Bartolomaeus, Mark Schmidt, Holger Rauhut · 8 June 2026

  The training of neural networks often entails objective functions that are not globally $L$-smooth. For these functions, it is both theoretically and practically difficult to reply to the question: what is the largest possible step size that ensures the convergence of gradient descent (GD)? We addre…

• Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks

  Junyu Zhou, Puyu Wang, Yunwen Lei, Yiming Ying, Ding-Xuan Zhou · 8 June 2026

  Recent progress has been made in understanding the statistical generalization performance of gradient descent methods for overparameterized neural networks within the neural tangent kernel (NTK) regime. However, most of the existing work on regression problems is limited to shallow network architect…

• Generalization in Deep Neural Networks: Minimax Rates for Gradient Methods

  Junyu Zhou, Puyu Wang, Yunwen Lei, Marius Kloft, Yiming Ying · 8 June 2026

  Understanding the generalization performance of over-parameterized neural networks has become a central topic in deep learning theory. While recent advances, particularly works under the Neural Tangent Kernel (NTK) regime, have shed light on the behavior of shallow architectures, the statistical gen…

• Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters

  Jonghyun Shin, Sejun Park · 8 June 2026

  We analyze generalization error, uniform stability, and uniform argument stability of gradient descent (GD) and stochastic gradient descent (SGD) over discrete parameter spaces, where each update involves deterministic or stochastic rounding. We show that deterministic rounding degrades the generali…

• TorchKM: A GPU-Oriented Library for Kernel Learning and Model Selection

  Yikai Zhang, Gaoxiang Jia, Jie Ding, Boxiang Wang · 8 June 2026

  TorchKM is an open-source library for kernel machines, including support vector machines, kernel logistic regression, and kernel quantile regression, with GPU acceleration. The library features a scikit-learn-style API and is designed to exploit GPU-friendly linear algebra, accelerating the full tra…

• Implicit Neural Optimal Transport via Fixed-Point Optimization

  Yesom Park, Eric Gelphman, Stanley Osher, Samy Wu Fung · 8 June 2026

  We propose an implicit neural formulation of optimal transport that eliminates adversarial min--max optimization and multi-network architectures commonly used in existing approaches. Our key idea is to parameterize a single potential in the Kantorovich dual and reformulate the associated c-transform…

• Depth over Fidelity in Fixed-Budget Noisy Evolution Strategies

  Sichen Wang, Zhipeng Lu · 8 June 2026

  Noisy evolution strategies under fixed evaluation budgets face a depth-fidelity trade-off: spending evaluations to denoise intra-generation rankings reduces the number of distribution updates the optimizer can execute. We argue for depth over fidelity and propose probabilistic elite membership (PEM)…