Papers

Field

Top tools here

Open problems in Stochastic gradient descent

Convergence guarantees for SGD in non-convex settings1 paper raises it · 1 addresses it
Understanding when and how SGD converges in non-convex problems is critical for training deep neural networks.
- Convergence of stochastic gradient descent for learning linear neural networksraises · addresses
Handling heavy-tailed noise in SGD1 paper raises it · 1 addresses it
Heavy-tailed noise can break standard convergence guarantees, requiring robust methods like gradient clipping.
- Weak-$L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tailsraises · addresses
Variance reduction with delayed feedback in non-convex optimization1 paper raises it · 1 addresses it
Delayed feedback in distributed or asynchronous settings introduces variance that degrades convergence.
- Variance Reduction with Delayed Feedback for Non-Convex Optimizationraises · addresses
Efficiency of deterministic vs. randomized zeroth-order methods1 paper raises it · 1 addresses it
Deterministic methods may require more evaluations than randomized ones in high-dimensional non-convex problems.
- Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Traceraises · addresses
Polyak-Ruppert averaging performance with momentum1 paper raises it · 1 addresses it
Momentum can improve the convergence rate of tail-averaged SGD in strongly convex settings.
- When Momentum Helps Polyak--Ruppert Averagingraises · addresses

Named by an AI from these papers' abstracts.

Open problems

Recently funded

Topics in this field

sample complexity · online learning · complexity100 papers25 this week
stochastic gradient descent · stochastic gradient · optimality135 papers19 this week

Topics in this field

Active contributors · 90 days

Wei Biao WuStochastic Gradient Descent: A Nonlinear Time Series Perspective8
Wei JiangVariance Reduction with Delayed Feedback for Non-Convex Optimization5
Zechao LiVariance Reduction with Delayed Feedback for Non-Convex Optimization5
Alexander GasnikovWeak-$L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails4
Qihao ZhouAccelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles4
Princewill OkoroaforCommunication Complexity of Universal Features3

Active contributors

Activity · 12 weeks

Coming with more sources: repos

Activity

Recent papers

All in Research →

arXiv cs.LGOct 3
Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning
Aoran Zhang, César A. Uribe
The Gromov-Wasserstein (GW) problem compares structured distributions without requiring a shared feature space or known correspondences, but its nonconvex objective and coupled marginal constraints make computation challenging. Bregman alternating projected gradient (BAPG) uses inexpensive alternating row and column updates, yet its fixed-penalty relaxation leaves a persistent feasibility gap. We propose Adaptive KL-BAPG (A-KL-BAPG), which combines a finite fixed-penalty burn-in with a guarded increasing-penalty phase. At each tail iteration, the method reuses BAPG's alternating updates and backtracks a delayed-power step until a Sinkhorn-inspired projective-diameter safeguard is satisfied. We prove finite termination of the backtracking at each iteration and show that the feasibility gap vanishes asymptotically. We further establish a best-iterate $O(1/\log N)$ bound for the weighted squared corrected residual and, under a support regularity condition, the existence of a stationary accumulation point for the original GW problem. This distinguishes A-KL-BAPG from fixed-penalty BAPG, whose stationarity guarantees are given for the relaxed problem. Experiments show that A-KL-BAPG…
PDF arXiv
arXiv cs.LGOct 2
Ideal Paths for Approximating Logistic Gradient Descent Trajectories at Large Initialization
Junjie Xiao, Huiwen Jia
Modern training on a new task often starts from a previously trained model rather than from scratch, raising the question of how this initialization affects the subsequent training trajectory. Classical implicit-bias results characterize the direction selected by prolonged training, but this direction alone does not provide information regarding the intermediate behavior. We address this question through a geometric approximation of full-batch logistic gradient descent (GD) trajectories on strictly linearly separable data, with large initialization of scale $R$ motivated by prior training. From any limiting normalized initial position, we use minimum-norm projection rules to construct a unique continuous ideal path consisting of finitely many linear segments. The path has two stages: negative-margin correction followed by minimum-margin growth. We prove that, after an explicit two-stage time reparameterization, the fixed-step GD trajectory divided by $R$ converges uniformly to this path on every fixed parameter interval as $R\to\infty$. Further, our quantitative error bounds account for initialization perturbations and the transition between stages. This approximation provides…
PDF arXiv
arXiv cs.DSOct 2
Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization
Vaneet Aggarwal
We study nonnegative, non-monotone $k$-submodular maximization with $k\ge2$ labels under support constraints, and show how the certified approximation coefficient improves as the support region permits more uniform selection. For a compact convex down-closed support region $P\subseteq[0,1]^n$, the diagonal level $ζ(P)=\max\{t\in[0,1]:t {\bf 1} \in P\}$ ranges from $ζ=0$, which carries no geometric promise, to $ζ=1$, which is unrestricted support. Our main structural result is a comparator-uniform linearization of the multilinear extension, built from an objective-independent action and a comparator-independent update field. For $k\ge3$, its validity reduces, independently of the number of elements, to four polynomial inequalities of degree at most three in one or two variables, only one of which depends on $k$. Explicit parameter choices give a nondecreasing certified profile $\underlineα_k(ζ)$, in closed form on all of $[0,1]$ when $k=2$. At $ζ=0$ we certify $0.4456\ldots$ for $k=2$ and $0.4541\ldots$ for every $k\ge3$, improving the recent $\sqrt2-1$ guarantee for one matroid or one knapsack, as well as the $1/3$-type guarantees for a fixed number of budgets; at $ζ=1$ we…
PDF arXiv
arXiv math.OCOct 2
Information Limits of Low-Rank Approximation Certification
Kang Liu, Bohao Qu
Low-rank approximation can require additional matrix--vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across $W$ paths, a concentration bound exploiting shared residual energy yields a $\sqrt{\log(W+1)}$ dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders $N^{1/3}$ and $N^{2/3}$ for validation and construction beyond the true target. Code is available at…
PDF arXiv
arXiv math.OCOct 2
Near-Optimal Convex Optimization with Lazy Second-Order Oracles
Xinliang Zhang, Lesi Chen, Chengchang Liu, Jingzhao Zhang
This paper studies the complexity of convex optimization using lazy second-order oracles (Doikov, Chayti, and Jaggi, ICML 2023), where an algorithm queries gradients every iteration and Hessians once per $m$ iterations. Under this setting, we show a lower bound of $Ω(m+ m^{1/7} ε^{-2/7})$ on the number of total iterations to find an $ε$-solution using a novel block zero-chain construction. Then we propose a novel method that achieves a new upper bound of $\tilde{\mathcal{O}}(m+ m^{1/7} ε^{-2/7})$, which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of $\tilde{\mathcal{O}}(m+ m^{13/21} ε^{-2/7})$ and is tight up to logarithmic factors.
PDF arXiv
arXiv cs.LGOct 1
Muon meets Tamed Langevin: Momentum Preconditioning beyond Convex and gradient-Lipschitz Potentials
Nikolaos Makras, Sotirios Sabanis
We consider the problem of sampling from Gibbs distributions on matrix spaces whose potential energies are neither convex nor globally gradient-Lipschitz. We introduce a family of non-quadratic kinetic energies that lead to a new underdamped Langevin system with momentum preconditioning, in which the gradient of the kinetic energy acts as a smooth spectral taming of the momentum. We prove that, under these relaxed assumptions on the potential, the resulting dynamics leaves the target Gibbs measure invariant, and we establish exponential convergence to equilibrium in a weighted total variation distance. Finally, we show that the corresponding Euler-Maruyama discretization admits moment bounds that are uniform in time, without any modification of the potential gradient, which ensures the stability of the resulting sampling algorithm.
PDF arXiv

Papers

Topics in this field

sample complexity · online learning · complexity100 papers25 this week
stochastic gradient descent · stochastic gradient · optimality135 papers19 this week

Recent papers

All in Research →

arXiv cs.LGOct 3
Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning
Aoran Zhang, César A. Uribe
The Gromov-Wasserstein (GW) problem compares structured distributions without requiring a shared feature space or known correspondences, but its nonconvex objective and coupled marginal constraints make computation challenging. Bregman alternating projected gradient (BAPG) uses inexpensive alternating row and column updates, yet its fixed-penalty relaxation leaves a persistent feasibility gap. We propose Adaptive KL-BAPG (A-KL-BAPG), which combines a finite fixed-penalty burn-in with a guarded increasing-penalty phase. At each tail iteration, the method reuses BAPG's alternating updates and backtracks a delayed-power step until a Sinkhorn-inspired projective-diameter safeguard is satisfied. We prove finite termination of the backtracking at each iteration and show that the feasibility gap vanishes asymptotically. We further establish a best-iterate $O(1/\log N)$ bound for the weighted squared corrected residual and, under a support regularity condition, the existence of a stationary accumulation point for the original GW problem. This distinguishes A-KL-BAPG from fixed-penalty BAPG, whose stationarity guarantees are given for the relaxed problem. Experiments show that A-KL-BAPG…
PDF arXiv
arXiv cs.LGOct 2
Ideal Paths for Approximating Logistic Gradient Descent Trajectories at Large Initialization
Junjie Xiao, Huiwen Jia
Modern training on a new task often starts from a previously trained model rather than from scratch, raising the question of how this initialization affects the subsequent training trajectory. Classical implicit-bias results characterize the direction selected by prolonged training, but this direction alone does not provide information regarding the intermediate behavior. We address this question through a geometric approximation of full-batch logistic gradient descent (GD) trajectories on strictly linearly separable data, with large initialization of scale $R$ motivated by prior training. From any limiting normalized initial position, we use minimum-norm projection rules to construct a unique continuous ideal path consisting of finitely many linear segments. The path has two stages: negative-margin correction followed by minimum-margin growth. We prove that, after an explicit two-stage time reparameterization, the fixed-step GD trajectory divided by $R$ converges uniformly to this path on every fixed parameter interval as $R\to\infty$. Further, our quantitative error bounds account for initialization perturbations and the transition between stages. This approximation provides…
PDF arXiv
arXiv cs.DSOct 2
Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization
Vaneet Aggarwal
We study nonnegative, non-monotone $k$-submodular maximization with $k\ge2$ labels under support constraints, and show how the certified approximation coefficient improves as the support region permits more uniform selection. For a compact convex down-closed support region $P\subseteq[0,1]^n$, the diagonal level $ζ(P)=\max\{t\in[0,1]:t {\bf 1} \in P\}$ ranges from $ζ=0$, which carries no geometric promise, to $ζ=1$, which is unrestricted support. Our main structural result is a comparator-uniform linearization of the multilinear extension, built from an objective-independent action and a comparator-independent update field. For $k\ge3$, its validity reduces, independently of the number of elements, to four polynomial inequalities of degree at most three in one or two variables, only one of which depends on $k$. Explicit parameter choices give a nondecreasing certified profile $\underlineα_k(ζ)$, in closed form on all of $[0,1]$ when $k=2$. At $ζ=0$ we certify $0.4456\ldots$ for $k=2$ and $0.4541\ldots$ for every $k\ge3$, improving the recent $\sqrt2-1$ guarantee for one matroid or one knapsack, as well as the $1/3$-type guarantees for a fixed number of budgets; at $ζ=1$ we…
PDF arXiv
arXiv math.OCOct 2
Information Limits of Low-Rank Approximation Certification
Kang Liu, Bohao Qu
Low-rank approximation can require additional matrix--vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across $W$ paths, a concentration bound exploiting shared residual energy yields a $\sqrt{\log(W+1)}$ dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders $N^{1/3}$ and $N^{2/3}$ for validation and construction beyond the true target. Code is available at…
PDF arXiv
arXiv math.OCOct 2
Near-Optimal Convex Optimization with Lazy Second-Order Oracles
Xinliang Zhang, Lesi Chen, Chengchang Liu, Jingzhao Zhang
This paper studies the complexity of convex optimization using lazy second-order oracles (Doikov, Chayti, and Jaggi, ICML 2023), where an algorithm queries gradients every iteration and Hessians once per $m$ iterations. Under this setting, we show a lower bound of $Ω(m+ m^{1/7} ε^{-2/7})$ on the number of total iterations to find an $ε$-solution using a novel block zero-chain construction. Then we propose a novel method that achieves a new upper bound of $\tilde{\mathcal{O}}(m+ m^{1/7} ε^{-2/7})$, which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of $\tilde{\mathcal{O}}(m+ m^{13/21} ε^{-2/7})$ and is tight up to logarithmic factors.
PDF arXiv
arXiv cs.LGOct 1
Muon meets Tamed Langevin: Momentum Preconditioning beyond Convex and gradient-Lipschitz Potentials
Nikolaos Makras, Sotirios Sabanis
We consider the problem of sampling from Gibbs distributions on matrix spaces whose potential energies are neither convex nor globally gradient-Lipschitz. We introduce a family of non-quadratic kinetic energies that lead to a new underdamped Langevin system with momentum preconditioning, in which the gradient of the kinetic energy acts as a smooth spectral taming of the momentum. We prove that, under these relaxed assumptions on the potential, the resulting dynamics leaves the target Gibbs measure invariant, and we establish exponential convergence to equilibrium in a weighted total variation distance. Finally, we show that the corresponding Euler-Maruyama discretization admits moment bounds that are uniform in time, without any modification of the potential gradient, which ensures the stability of the resulting sampling algorithm.
PDF arXiv

Active contributors · 90 days

Wei Biao WuStochastic Gradient Descent: A Nonlinear Time Series Perspective8
Wei JiangVariance Reduction with Delayed Feedback for Non-Convex Optimization5
Zechao LiVariance Reduction with Delayed Feedback for Non-Convex Optimization5
Alexander GasnikovWeak-$L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails4
Qihao ZhouAccelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles4
Princewill OkoroaforCommunication Complexity of Universal Features3

Activity · 12 weeks

Coming with more sources: repos

Fields · AI · updated 33m ago

Stochastic gradient descent

Found by the topic model: stochastic gradient descent, sample complexity.

44papers this week−27.9% vs last week

All papers · 235 With code · 0

Newest Most relevant

225 papers this month

Open problems in Stochastic gradient descent

Convergence guarantees for SGD in non-convex settings1 paper raises it · 1 addresses it
Understanding when and how SGD converges in non-convex problems is critical for training deep neural networks.
- Convergence of stochastic gradient descent for learning linear neural networksraises · addresses
Handling heavy-tailed noise in SGD1 paper raises it · 1 addresses it
Heavy-tailed noise can break standard convergence guarantees, requiring robust methods like gradient clipping.
- Weak-$L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tailsraises · addresses
Variance reduction with delayed feedback in non-convex optimization1 paper raises it · 1 addresses it
Delayed feedback in distributed or asynchronous settings introduces variance that degrades convergence.
- Variance Reduction with Delayed Feedback for Non-Convex Optimizationraises · addresses
Efficiency of deterministic vs. randomized zeroth-order methods1 paper raises it · 1 addresses it
Deterministic methods may require more evaluations than randomized ones in high-dimensional non-convex problems.
- Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Traceraises · addresses
Polyak-Ruppert averaging performance with momentum1 paper raises it · 1 addresses it
Momentum can improve the convergence rate of tail-averaged SGD in strongly convex settings.
- When Momentum Helps Polyak--Ruppert Averagingraises · addresses

Named by an AI from these papers' abstracts.