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 papers22 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 cs.LGOct 17
Uniform convergence at optimal rate and scale
Noga Alon, Steve Hanneke, Shay Moran, Tom Waknine
Uniform convergence asks how many random samples suffice for empirical averages to approximate expectations simultaneously over an entire class of functions. It is a central concept in probability and a foundation of statistical learning. For binary-valued classes, the Vapnik--Chervonenkis theorem characterizes uniform convergence by finiteness of the VC dimension. For dimension $d$, the sharp worst-case sample complexity for additive error $\varepsilon$ is of order $d/\varepsilon^2$. For real-valued functions, the analogous combinatorial parameter is the fat-shattering dimension, which depends on an approximation scale $γ$. The challenge is to achieve error $γ+\varepsilon$ with order $d/\varepsilon^2$ samples, matching the sample bound for binary classes, where $d$ is now the fat-shattering dimension at scale $γ$. Previous results achieved either the optimal scale or the optimal sample complexity, but not both. Our main result closes this gap, establishing the sharp sample complexity at the optimal scale. Along the way, we use several tools that may be of independent interest. The first concerns $\varepsilon$-nets with margin. A classical $\varepsilon$-net intersects every set…
PDF arXiv
arXiv cs.LGOct 16
PAC Learning with Query Feedback
Chase Hutton, Adam Melrod, Han Shao
We study realizable multiclass PAC learning with query feedback, where each training example provides a single binary response indicating whether its true label belongs to a chosen subset from a fixed query family. Our main contribution is the query dimension, a combinatorial parameter that captures both the structure of the hypothesis class and the ability of the available queries to distinguish labels. This parameter generalizes the bandit DS dimension, which it recovers under singleton queries. We establish a sample-complexity lower bound of $Ω(D/\varepsilon)$ and an upper bound of $\widetilde{O}(D^2/\varepsilon)$, suppressing factors polylogarithmic in the number of labels and the failure probability. When the available queries can split every candidate set into two parts of comparable size, we improve the upper bound to $\widetilde{O}(D/\varepsilon)$, yielding a characterization up to logarithmic factors.
PDF arXiv
arXiv cs.LGOct 16
Margin Certificates for Voting Classifiers under Mixing Dependence
Adria Binte Habib, Ibne Farabi Shihab
Margin bounds explain why weighted votes generalize after training error vanishes, but dependent observations require concentration arguments that keep the dependence model and failure budget explicit. We study stationary mixing streams without treating dependence as a formal substitution of an "effective sample size." For a finite base class, we combine independent-block Rademacher theory for stationary $β$-mixing processes with a clipped margin loss to obtain an explicit uniform voting-margin certificate, whose dependence penalty is set by the number of approximately independent blocks and the coupling budget $4(μ-1)β(a)$. A black-box transfer theorem shows that any i.i.d. voting-margin guarantee remains valid on a regularly spaced subsequence, with only an additive $β$-mixing failure probability. For votes fixed independently of a stationary finite-state reversible Markov stream, spectral concentration gives the cleaner $\sqrt{t_{rel}/n}$ rate, and a sticky-refresh construction shows this exponent is unavoidable. The constant is statistic-specific: the effective sample size is $n/τ_{int}(g)$, with $τ_{int}(g) \le 2t_{rel}-1$. When the dependence scale is unknown, a batch-means…
PDF arXiv
arXiv stat.MLOct 16
Parametric Resonance in Primal-Dual Learning for Slowly Non-Stationary Constrained MDPs
Maxime Baelde
Primal-dual methods for constrained Markov decision processes are analyzed under a two-timescale assumption, with non-stationarity entering through two channels. In the additive channel, where the constraint level oscillates, the dual oscillation saturates at a floor set by the moving optimum and is amplified linearly by the timescale ratio. In the parametric channel, where the constraint sensitivity oscillates, a coherent modulation carries no resonant forcing at any depth: the dual update's stiffness modulation cancels the primal update's damping modulation. Instability instead comes from a mismatch between the constraint estimate used by the primal update and the measurement used by the dual update, producing a parametric resonance at twice the pair's natural frequency. The tolerated mismatch grows with the square root of the forcing bandwidth and collapses with the square root of the dual-to-primal step-size ratio. These results hold on the tangent linear-quadratic reduction around an active saddle, for one constraint and for $K$ constraints under a common modulation and an isotropy condition. Driving both updates from the same estimate removes the resonant forcing but…
PDF arXiv
arXiv stat.MLOct 16
A general recipe for data-adaptive anytime-valid envelopes for iterative algorithms
Soham Bonnerjee, Aaditya Ramdas
Most convergence guarantees for iterative stochastic algorithms are stated at a fixed iteration count and do not justify stopping at a data-dependent time. Recent work has constructed anytime-valid envelopes that do, but deterministic envelopes are typically too conservative for practical stopping, and existing data-adaptive ones are derived case-by-case, each coupling a specific algorithm to a specific noise model and boundary construction. This paper provides a general recipe for constructing such anytime-valid data-adaptive boundaries for a large class of iterative algorithms. Performance measures of many of these algorithms satisfy a one-step recursion that reduces the entire error analysis to a single general requirement: time-uniform concentration for predictably weighted sums of noise. We formalize this through a strongly adapted sub-$ψ$ condition, and derive off-the-shelf boundary constructions via continuous and discrete mixtures, stitching, and product betting martingales. We show how these boundaries can be directly coupled with a separate algorithmic analysis that derives the one-step recursion to provide a class of readymade anytime-valid envelopes across diverse…
PDF arXiv
arXiv cs.PFOct 16
The Optimal Ranking Tradeoffs Between Two Ranking Scores in Two-Class Classification
Sébastien Piérard, Adrien Deliège, Marc Van Droogenbroeck
The accuracy, true negative rate (negative class recall), true positive rate (positive class recall), negative predictive value (negative class precision), positive predictive value (positive class precision), class-specific intersections over unions, class-specific F-scores, Cohen's kappa, and balanced accuracy are scores that one intuitively wants to maximize when developing machine learning methods. However, they lead to different rankings of such methods. So, how can we establish a ranking that is an optimal tradeoff between any pair of these scores? It turns out that all these scores are special cases of ranking scores: a continuum of scores parameterized by the relative importance values assigned to the true negative, false positive, false negative, and true positive outcomes. Since all these scores are known to induce meaningful rankings, we seek the optimal tradeoffs among them. We consider the tradeoff between two scores to be optimal when it minimizes the Fréchet variance regarding the Kendall distance (also known as the bubble-sort distance) between rankings. For any given set of classifiers to rank, the optimal tradeoff lies at the center of the shortest (geodesic)…
PDF arXiv

Papers

Topics in this field

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

Recent papers

All in Research →

arXiv cs.LGOct 17
Uniform convergence at optimal rate and scale
Noga Alon, Steve Hanneke, Shay Moran, Tom Waknine
Uniform convergence asks how many random samples suffice for empirical averages to approximate expectations simultaneously over an entire class of functions. It is a central concept in probability and a foundation of statistical learning. For binary-valued classes, the Vapnik--Chervonenkis theorem characterizes uniform convergence by finiteness of the VC dimension. For dimension $d$, the sharp worst-case sample complexity for additive error $\varepsilon$ is of order $d/\varepsilon^2$. For real-valued functions, the analogous combinatorial parameter is the fat-shattering dimension, which depends on an approximation scale $γ$. The challenge is to achieve error $γ+\varepsilon$ with order $d/\varepsilon^2$ samples, matching the sample bound for binary classes, where $d$ is now the fat-shattering dimension at scale $γ$. Previous results achieved either the optimal scale or the optimal sample complexity, but not both. Our main result closes this gap, establishing the sharp sample complexity at the optimal scale. Along the way, we use several tools that may be of independent interest. The first concerns $\varepsilon$-nets with margin. A classical $\varepsilon$-net intersects every set…
PDF arXiv
arXiv cs.LGOct 16
PAC Learning with Query Feedback
Chase Hutton, Adam Melrod, Han Shao
We study realizable multiclass PAC learning with query feedback, where each training example provides a single binary response indicating whether its true label belongs to a chosen subset from a fixed query family. Our main contribution is the query dimension, a combinatorial parameter that captures both the structure of the hypothesis class and the ability of the available queries to distinguish labels. This parameter generalizes the bandit DS dimension, which it recovers under singleton queries. We establish a sample-complexity lower bound of $Ω(D/\varepsilon)$ and an upper bound of $\widetilde{O}(D^2/\varepsilon)$, suppressing factors polylogarithmic in the number of labels and the failure probability. When the available queries can split every candidate set into two parts of comparable size, we improve the upper bound to $\widetilde{O}(D/\varepsilon)$, yielding a characterization up to logarithmic factors.
PDF arXiv
arXiv cs.LGOct 16
Margin Certificates for Voting Classifiers under Mixing Dependence
Adria Binte Habib, Ibne Farabi Shihab
Margin bounds explain why weighted votes generalize after training error vanishes, but dependent observations require concentration arguments that keep the dependence model and failure budget explicit. We study stationary mixing streams without treating dependence as a formal substitution of an "effective sample size." For a finite base class, we combine independent-block Rademacher theory for stationary $β$-mixing processes with a clipped margin loss to obtain an explicit uniform voting-margin certificate, whose dependence penalty is set by the number of approximately independent blocks and the coupling budget $4(μ-1)β(a)$. A black-box transfer theorem shows that any i.i.d. voting-margin guarantee remains valid on a regularly spaced subsequence, with only an additive $β$-mixing failure probability. For votes fixed independently of a stationary finite-state reversible Markov stream, spectral concentration gives the cleaner $\sqrt{t_{rel}/n}$ rate, and a sticky-refresh construction shows this exponent is unavoidable. The constant is statistic-specific: the effective sample size is $n/τ_{int}(g)$, with $τ_{int}(g) \le 2t_{rel}-1$. When the dependence scale is unknown, a batch-means…
PDF arXiv
arXiv stat.MLOct 16
Parametric Resonance in Primal-Dual Learning for Slowly Non-Stationary Constrained MDPs
Maxime Baelde
Primal-dual methods for constrained Markov decision processes are analyzed under a two-timescale assumption, with non-stationarity entering through two channels. In the additive channel, where the constraint level oscillates, the dual oscillation saturates at a floor set by the moving optimum and is amplified linearly by the timescale ratio. In the parametric channel, where the constraint sensitivity oscillates, a coherent modulation carries no resonant forcing at any depth: the dual update's stiffness modulation cancels the primal update's damping modulation. Instability instead comes from a mismatch between the constraint estimate used by the primal update and the measurement used by the dual update, producing a parametric resonance at twice the pair's natural frequency. The tolerated mismatch grows with the square root of the forcing bandwidth and collapses with the square root of the dual-to-primal step-size ratio. These results hold on the tangent linear-quadratic reduction around an active saddle, for one constraint and for $K$ constraints under a common modulation and an isotropy condition. Driving both updates from the same estimate removes the resonant forcing but…
PDF arXiv
arXiv stat.MLOct 16
A general recipe for data-adaptive anytime-valid envelopes for iterative algorithms
Soham Bonnerjee, Aaditya Ramdas
Most convergence guarantees for iterative stochastic algorithms are stated at a fixed iteration count and do not justify stopping at a data-dependent time. Recent work has constructed anytime-valid envelopes that do, but deterministic envelopes are typically too conservative for practical stopping, and existing data-adaptive ones are derived case-by-case, each coupling a specific algorithm to a specific noise model and boundary construction. This paper provides a general recipe for constructing such anytime-valid data-adaptive boundaries for a large class of iterative algorithms. Performance measures of many of these algorithms satisfy a one-step recursion that reduces the entire error analysis to a single general requirement: time-uniform concentration for predictably weighted sums of noise. We formalize this through a strongly adapted sub-$ψ$ condition, and derive off-the-shelf boundary constructions via continuous and discrete mixtures, stitching, and product betting martingales. We show how these boundaries can be directly coupled with a separate algorithmic analysis that derives the one-step recursion to provide a class of readymade anytime-valid envelopes across diverse…
PDF arXiv
arXiv cs.PFOct 16
The Optimal Ranking Tradeoffs Between Two Ranking Scores in Two-Class Classification
Sébastien Piérard, Adrien Deliège, Marc Van Droogenbroeck
The accuracy, true negative rate (negative class recall), true positive rate (positive class recall), negative predictive value (negative class precision), positive predictive value (positive class precision), class-specific intersections over unions, class-specific F-scores, Cohen's kappa, and balanced accuracy are scores that one intuitively wants to maximize when developing machine learning methods. However, they lead to different rankings of such methods. So, how can we establish a ranking that is an optimal tradeoff between any pair of these scores? It turns out that all these scores are special cases of ranking scores: a continuum of scores parameterized by the relative importance values assigned to the true negative, false positive, false negative, and true positive outcomes. Since all these scores are known to induce meaningful rankings, we seek the optimal tradeoffs among them. We consider the tradeoff between two scores to be optimal when it minimizes the Fréchet variance regarding the Kendall distance (also known as the bubble-sort distance) between rankings. For any given set of classifiers to rank, the optimal tradeoff lies at the center of the shortest (geodesic)…
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 5m ago

Stochastic gradient descent

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

41papers this week−25.5% 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.