Papers

Field

Top tools here

Open problems in Stochastic gradient descent

Handling non-strongly convex lower-level problems in bilevel optimization1 paper raises it · 2 address it
Many bilevel optimization methods assume lower-level strong convexity, limiting applicability to real-world problems where this does not hold.
- Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexityraises · addresses
- Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oraclesaddresses
Last-iterate convergence of SGD in low-noise regimes1 paper raises it · 1 addresses it
Understanding the last-iterate behavior of SGD in interpolation or low-noise settings is critical for practical deployment.
- Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regimeraises · addresses
Acceleration of heavy-ball method in general settings1 paper raises it · 1 addresses it
The heavy-ball method's acceleration properties remain unresolved for broad classes of functions, affecting optimization efficiency.
- Non-Acceleration of the Heavy-Ball Method in 1Draises · addresses
Finite-sum dependence in bilevel optimization with first-order oracles1 paper raises it · 1 addresses it
Efficient bilevel optimization with finite-sum objectives and first-order oracles requires better handling of component-wise dependencies.
- Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oraclesraises · addresses
Tracking drifting fixed points in linear stochastic approximation1 paper raises it · 1 addresses it
Time-varying operators in linear SA complicate convergence analysis and practical stepsize selection.
- Stochastic Tracking of Drifting Affine Fixed Pointsraises · addresses

Named by an AI from these papers' abstracts.

Open problems

Recently funded

Topics in this field

sample complexity · online learning · complexity94 papers23 this week
stochastic gradient descent · stochastic gradient · optimality130 papers19 this week

Topics in this field

Active contributors · 90 days

Wei Biao WuStochastic Gradient Descent: A Nonlinear Time Series Perspective8
Qihao ZhouAccelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles4
Wei JiangLast-Iterate Convergence of Clipped SGD with Linear Decay4
Zechao LiLast-Iterate Convergence of Clipped SGD with Linear Decay4
Steve HannekeUniform convergence at optimal rate and scale3
Xiaoyu LiRecalibrating Many Questions with Few Labels: Minimax Rates and Identification Limits3

Active contributors

Activity · 12 weeks

Coming with more sources: repos

Activity

Recent papers

All in Research →

arXiv math.OCOct 18
Non-Acceleration of the Heavy-Ball Method in 1D
Konstantinos Fotopoulos, Michael Helcig, Karl Deck, Jannis Alsbach
Despite having an asymptotically optimal rate of convergence on convex quadratics, the acceleration of Polyak's heavy-ball method and a characterization of its dynamics within more general settings have remained long standing open problems. Recently, the work of Goujaud et al. [Math. Program. (2025)] made progress regarding acceleration in the context of smooth, strongly convex minimization: for a small enough inverse condition number, either the method does not accelerate on quadratics, or there exists a smooth strongly convex function such that heavy-ball cycles over the roots of unity. The constructed functions have two variables, thus leaving the question of acceleration over univariate functions open. In this work, we use a Fourier-based analysis to i) provide a proof for the non-acceleration of the heavy-ball method over the class of univariate smooth strongly convex functions. We also ii) provide a strict enlargement of the previous root-of-unity cycling region, with insights regarding the "fractional" sets of Goujaud et al. [arXiv:2502.19916], and iii) give a higher dimensional cycling instance which is not covered by root-of-unity cycling.
PDF arXiv
arXiv cs.LGOct 18
The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning
Guangjian Zhang
Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension $d\ge1$, the required number of independent examples is $Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$, uniformly over independent accuracy, failure, and disagreement parameters $α,β,ρ\in(0,1/10)$. The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the…
PDF arXiv
arXiv cs.ITOct 17
Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation
Krishnakumar Balasubramanian, Siddharth Bhandari, Shiva Prasad Kasiviswanathan
We study quantization for inner-product estimation when storage and reading have separate budgets. In the static bit-probe model [Yao, 1981], an encoder stores $w$ bits about $x$ before seeing a query $y$, and a reader probes at most $r<w$ bits to estimate $x^\top y$. Both vectors lie in the $d$-dimensional Euclidean unit ball. Protocols may be randomized, and computation is unrestricted. Performance is measured by $d$ times the worst-case mean-squared error over $x,y$, averaged over protocol randomness. First, we show that query-independent reading cannot benefit from extra storage. Any such reader is equivalent to fully reading an $r$-bit message, even when later reads depend on previously returned bits. At fixed positive rates $W=w/d$ and $R=r/d$, the normalized minimax error converges to $1/(4^R-1)$, independent of $W$. The upper bound was already known [Ordentlich and Polyanskiy, 2025]. We prove the matching lower bound for arbitrary scalar decoders, extending the result for unbiased compressors [Safaryan et al., 2020]. Then, we show that query-dependent reading makes extra storage useful. We construct a two-batch protocol using Gaussian projections and random thresholds,…
PDF arXiv
arXiv math.OCOct 17
Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
Qihao Zhou, Shanshui Niu
We study nonconvex--strongly-convex bilevel optimization with finite-sum objectives and fully first-order oracles. We propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, SICBO finds a point $x$ satisfying $\mathbb{E}\|\nablaΦ(x)\|^2\le\varepsilon^2$ within $\tilde{O}(N+\sqrt{N}κ^{7/2}\varepsilon^{-2})$ component-gradient calls, where $N$ is the total number of components and $κ$ is the normalized lower-level condition number. The bound achieves square-root finite-sum dependence using only gradients and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. Our improvement follows from a curvature-dependent bound for nonlinear correction errors, which permits epochs of length $\tildeΘ(\sqrt{N/κ})$ with batches of size $\tildeΘ(\sqrt{Nκ})$. A single-level reduction shows that the dependence on $N$ and $\varepsilon$ is optimal up to logarithmic factors for fixed $κ$.
PDF arXiv
arXiv cs.GTOct 17
Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion
Gabriel Chen, Yu Cheng, Alice Wang
We consider the metric distortion framework for voting, where $n$ voters and $m$ candidates are embedded in an unknown metric space. A voting rule selects a candidate using only voters' ordinal preferences, and its distortion is the worst-case ratio between the social cost of the selected candidate and the minimum social cost. We study how round complexity trades off against total communication in deterministic voting protocols with low distortion. Deterministic rules can achieve the optimal distortion of $3$ in one round by eliciting complete rankings using $Θ(nm\log m)$ bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only $O(n\log m)$ bits but requires $Θ(n)$ rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every $r\ge 2$, achieves distortion at most $2r-1$ using at most $r$ rounds and $O(n\log m+n s^{1/(r-1)}\log s)$ bits of total communication, where $s = \min\{n, m\}$. The protocol runs PluralityVeto on a hierarchical partition of the voters, collecting restricted rankings in parallel at each level. The branching factor controls the tradeoff between rounds and communication, and a…
PDF arXiv
arXiv cs.LGOct 17
The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs
Rui Wang
Before a new policy replaces a deployed one, we often want a certificate, computed from logged episodes, that it is better. We ask how many episodes such a certificate needs when the logging policy is known but history-dependent, and the error probability must stay below $δ$ in every environment consistent with the logs. The answer is an exponent $K^\star$: the smallest KL divergence from the logged law to a law with the same logged action probabilities under which the target does not improve. No sound certifier stops in fewer than $\log(1/δ)/K^\star$ expected episodes, at any $δ$, and whenever $0<K^\star<\infty$ a plug-in Kelly certifier attains this rate to first order as $δ\to0$. Coverage, computed by one backward induction, decides whether certification is impossible ($K^\star=0$), possible at a finite rate, or possible in a constant number of episodes ($K^\star=\infty$). By convex duality, the optimal certificate bets on the importance-weighted advantage and also places fair bets on the logged actions, so doubly robust control variates act as hedges rather than estimators. As a consequence, no choice of off-policy estimator changes $K^\star$, a coverage ceiling explains the…
PDF arXiv

Papers

Topics in this field

sample complexity · online learning · complexity94 papers23 this week
stochastic gradient descent · stochastic gradient · optimality130 papers19 this week

Recent papers

All in Research →

arXiv math.OCOct 18
Non-Acceleration of the Heavy-Ball Method in 1D
Konstantinos Fotopoulos, Michael Helcig, Karl Deck, Jannis Alsbach
Despite having an asymptotically optimal rate of convergence on convex quadratics, the acceleration of Polyak's heavy-ball method and a characterization of its dynamics within more general settings have remained long standing open problems. Recently, the work of Goujaud et al. [Math. Program. (2025)] made progress regarding acceleration in the context of smooth, strongly convex minimization: for a small enough inverse condition number, either the method does not accelerate on quadratics, or there exists a smooth strongly convex function such that heavy-ball cycles over the roots of unity. The constructed functions have two variables, thus leaving the question of acceleration over univariate functions open. In this work, we use a Fourier-based analysis to i) provide a proof for the non-acceleration of the heavy-ball method over the class of univariate smooth strongly convex functions. We also ii) provide a strict enlargement of the previous root-of-unity cycling region, with insights regarding the "fractional" sets of Goujaud et al. [arXiv:2502.19916], and iii) give a higher dimensional cycling instance which is not covered by root-of-unity cycling.
PDF arXiv
arXiv cs.LGOct 18
The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning
Guangjian Zhang
Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension $d\ge1$, the required number of independent examples is $Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$, uniformly over independent accuracy, failure, and disagreement parameters $α,β,ρ\in(0,1/10)$. The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the…
PDF arXiv
arXiv cs.ITOct 17
Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation
Krishnakumar Balasubramanian, Siddharth Bhandari, Shiva Prasad Kasiviswanathan
We study quantization for inner-product estimation when storage and reading have separate budgets. In the static bit-probe model [Yao, 1981], an encoder stores $w$ bits about $x$ before seeing a query $y$, and a reader probes at most $r<w$ bits to estimate $x^\top y$. Both vectors lie in the $d$-dimensional Euclidean unit ball. Protocols may be randomized, and computation is unrestricted. Performance is measured by $d$ times the worst-case mean-squared error over $x,y$, averaged over protocol randomness. First, we show that query-independent reading cannot benefit from extra storage. Any such reader is equivalent to fully reading an $r$-bit message, even when later reads depend on previously returned bits. At fixed positive rates $W=w/d$ and $R=r/d$, the normalized minimax error converges to $1/(4^R-1)$, independent of $W$. The upper bound was already known [Ordentlich and Polyanskiy, 2025]. We prove the matching lower bound for arbitrary scalar decoders, extending the result for unbiased compressors [Safaryan et al., 2020]. Then, we show that query-dependent reading makes extra storage useful. We construct a two-batch protocol using Gaussian projections and random thresholds,…
PDF arXiv
arXiv math.OCOct 17
Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
Qihao Zhou, Shanshui Niu
We study nonconvex--strongly-convex bilevel optimization with finite-sum objectives and fully first-order oracles. We propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, SICBO finds a point $x$ satisfying $\mathbb{E}\|\nablaΦ(x)\|^2\le\varepsilon^2$ within $\tilde{O}(N+\sqrt{N}κ^{7/2}\varepsilon^{-2})$ component-gradient calls, where $N$ is the total number of components and $κ$ is the normalized lower-level condition number. The bound achieves square-root finite-sum dependence using only gradients and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. Our improvement follows from a curvature-dependent bound for nonlinear correction errors, which permits epochs of length $\tildeΘ(\sqrt{N/κ})$ with batches of size $\tildeΘ(\sqrt{Nκ})$. A single-level reduction shows that the dependence on $N$ and $\varepsilon$ is optimal up to logarithmic factors for fixed $κ$.
PDF arXiv
arXiv cs.GTOct 17
Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion
Gabriel Chen, Yu Cheng, Alice Wang
We consider the metric distortion framework for voting, where $n$ voters and $m$ candidates are embedded in an unknown metric space. A voting rule selects a candidate using only voters' ordinal preferences, and its distortion is the worst-case ratio between the social cost of the selected candidate and the minimum social cost. We study how round complexity trades off against total communication in deterministic voting protocols with low distortion. Deterministic rules can achieve the optimal distortion of $3$ in one round by eliciting complete rankings using $Θ(nm\log m)$ bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only $O(n\log m)$ bits but requires $Θ(n)$ rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every $r\ge 2$, achieves distortion at most $2r-1$ using at most $r$ rounds and $O(n\log m+n s^{1/(r-1)}\log s)$ bits of total communication, where $s = \min\{n, m\}$. The protocol runs PluralityVeto on a hierarchical partition of the voters, collecting restricted rankings in parallel at each level. The branching factor controls the tradeoff between rounds and communication, and a…
PDF arXiv
arXiv cs.LGOct 17
The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs
Rui Wang
Before a new policy replaces a deployed one, we often want a certificate, computed from logged episodes, that it is better. We ask how many episodes such a certificate needs when the logging policy is known but history-dependent, and the error probability must stay below $δ$ in every environment consistent with the logs. The answer is an exponent $K^\star$: the smallest KL divergence from the logged law to a law with the same logged action probabilities under which the target does not improve. No sound certifier stops in fewer than $\log(1/δ)/K^\star$ expected episodes, at any $δ$, and whenever $0<K^\star<\infty$ a plug-in Kelly certifier attains this rate to first order as $δ\to0$. Coverage, computed by one backward induction, decides whether certification is impossible ($K^\star=0$), possible at a finite rate, or possible in a constant number of episodes ($K^\star=\infty$). By convex duality, the optimal certificate bets on the importance-weighted advantage and also places fair bets on the logged actions, so doubly robust control variates act as hedges rather than estimators. As a consequence, no choice of off-policy estimator changes $K^\star$, a coverage ceiling explains the…
PDF arXiv

Active contributors · 90 days

Wei Biao WuStochastic Gradient Descent: A Nonlinear Time Series Perspective8
Qihao ZhouAccelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles4
Wei JiangLast-Iterate Convergence of Clipped SGD with Linear Decay4
Zechao LiLast-Iterate Convergence of Clipped SGD with Linear Decay4
Steve HannekeUniform convergence at optimal rate and scale3
Xiaoyu LiRecalibrating Many Questions with Few Labels: Minimax Rates and Identification Limits3

Activity · 12 weeks

Coming with more sources: repos

Fields · AI · updated 31m ago

Stochastic gradient descent

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

42papers this week−25.0% vs last week

All papers · 224 With code · 0

Newest Most relevant

216 papers this month

Open problems in Stochastic gradient descent

Handling non-strongly convex lower-level problems in bilevel optimization1 paper raises it · 2 address it
Many bilevel optimization methods assume lower-level strong convexity, limiting applicability to real-world problems where this does not hold.
- Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexityraises · addresses
- Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oraclesaddresses
Last-iterate convergence of SGD in low-noise regimes1 paper raises it · 1 addresses it
Understanding the last-iterate behavior of SGD in interpolation or low-noise settings is critical for practical deployment.
- Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regimeraises · addresses
Acceleration of heavy-ball method in general settings1 paper raises it · 1 addresses it
The heavy-ball method's acceleration properties remain unresolved for broad classes of functions, affecting optimization efficiency.
- Non-Acceleration of the Heavy-Ball Method in 1Draises · addresses
Finite-sum dependence in bilevel optimization with first-order oracles1 paper raises it · 1 addresses it
Efficient bilevel optimization with finite-sum objectives and first-order oracles requires better handling of component-wise dependencies.
- Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oraclesraises · addresses
Tracking drifting fixed points in linear stochastic approximation1 paper raises it · 1 addresses it
Time-varying operators in linear SA complicate convergence analysis and practical stepsize selection.
- Stochastic Tracking of Drifting Affine Fixed Pointsraises · addresses

Named by an AI from these papers' abstracts.