canonical setting

Stochastic and finite-sum oracles

$V=m^{-1}\sum_{i=1}^m f_i$ or unbiased noisy gradients; oracle cost counts component or stochastic queries.

Updated Oct 5, 2026

Upper and lower bounds

Stochastic gradients

4 scoped results. Tildes suppress logarithmic factors.

Best-known and comparison results for stochastic-gradient oracles
Result	Algorithm or model	Complexity	Guarantee	Oracle / start	Assumptions and notes	Review	Sources
best upper/lower	Fixed-dimensional stochastic-gradient sampling	$\Theta_d\bigl(\log(1+\kappa)+\sigma^2/(\alpha\varepsilon)\bigr)$	$\lVert\mu-\pi\rVert_{\rm TV}\le\varepsilon$	Unbiased full-vector stochastic gradient; conditional total variance $\le\sigma^2$ ; no potential valuesUnknown mode $x_\star$ with $\lVert x_\star\rVert\le\alpha^{-1/2}$ ; no warm start supplied	Fixed $d\ge1$ ; $\alpha I\preceq\nabla^2V\preceq\beta I$ ; $\kappa=\beta/\alpha$ ; $0<\varepsilon\le1/10$ .Worst-case expected number of oracle replies, including repeated and discarded calls. Constants may depend on $d$ . Conditional moment bounds hold given the full query history. Includes $\sigma=0$ ; the upper bound does not claim polynomial dependence on $d$ .	Checkedpreprint	Ou–Wang (2026), Theorems 3.1–3.2; Eq. (3.3) ↗
best upper	FORS	$\widetilde O((\kappa\sqrt d+\sigma_\psi^2/\alpha)\operatorname{polylog}(1/\varepsilon))$	$\lVert\mu_N-\pi\rVert_{\rm TV}\le\varepsilon$	Unbiased sub-exponential stochastic gradientKnown mode / paper initialization	$\alpha I\preceq\nabla^2V\preceq\beta I$ and uniform Orlicz-tail bound.Checked headline for light-tailed stochastic gradients.	Checkedpublished	Chen et al. (COLT 2026); Chewi Theorem 10.1.3 ↗
best lower	Bounded-variance stochastic-gradient lower bound	$\Omega(\sigma^2/(\alpha\varepsilon))$	TV accuracy proportional to $\varepsilon$	Unbiased bounded-variance stochastic gradientOne-dimensional Gaussian testing instance	Independent oracle noise in the stated minimax model.Shows light tails are necessary for polylogarithmic accuracy dependence.	Checkedpublished	Chen et al. (COLT 2026); Chewi Theorem 10.1.2 ↗
upper	Stochastic gradient LMC (SGLD)	$\widetilde O\bigl(C_G/\alpha^2+\kappa\sqrt d/\varepsilon+\min\{\sigma_4^2/(\alpha\varepsilon),\,\sigma_2^2/(\alpha\varepsilon^2)\}\bigr)$	$\sqrt\alpha\,W_2(\mu_N,\pi)\le\varepsilon$	Unbiased stochastic gradient, one query per iteration; error $\eta$ with $\mathbb E\lVert\eta(x)-\eta(y)\rVert^2\le C_G\lVert x-y\rVert^2$ Any $\mu\in\mathcal P_2$ ; initial $W_2(\mu,\pi)$ enters logarithmically	$\alpha I\preceq\nabla^2V\preceq\beta I$ ; $0<\varepsilon\le1$ ; $\sigma_2^2=\int\mathbb E\lVert\eta\rVert^2\,d\pi$ and $\sigma_4^4=\int\mathbb E\lVert\eta\rVert^4\,d\pi$ are averaged under $\pi$ .Asymptotic bias $\sqrt\alpha\,W_2(\tilde\pi_h,\pi)\le12h\beta\sqrt d+\min\{h\sigma_4^2/2,\sqrt{2h}\,\sigma_2\}$ : order $h$ with a finite fourth moment, order $h^{1/2}$ with only a second moment. A spiked-noise example shows a second moment alone cannot give order- $h$ bias uniformly over noise laws with fixed variance. Wasserstein guarantee; not comparable with the TV rows.	Checkedpreprint	Paulin–Whalley (2026), Theorem 1; Corollary 1 ↗

Upper and lower bounds

Finite sums

3 scoped results. Tildes suppress logarithmic factors.

Edit table

Best-known and comparison results for finite-sum oracles
Result	Algorithm or model	Complexity	Guarantee	Oracle / start	Assumptions and notes	Review	Sources
best upper	Variance-reduced high-accuracy sampler	$\widetilde O((m+\kappa\sqrt{dm})\operatorname{polylog}(1/\varepsilon))$	High-accuracy sampling	Individual component value/gradientPaper initialization	Each $f_i$ is $\beta$ -smooth and $V$ is $\alpha$ -strongly convex.Counts individual component queries, not full gradients.	Checkedpublished	Chen et al. (COLT 2026); Chewi §10.1.2 ↗
best upper	Finite-sum RM-ULMC	$\widetilde O(m+\kappa^2+\kappa^{4/3}d^{1/3}m^{2/3}/\varepsilon^{2/3})$	Low-accuracy sampling	Individual component gradientPaper initialization	Finite-sum strong convexity and component smoothness.Low-accuracy row; compare separately from polylogarithmic accuracy.	Checkedmonograph	Chewi (2026), §10.1.2 ↗
best lower	Finite-sum zeroth-order lower bound	$\widetilde\Theta(L^2/\alpha)$	Constant sampling accuracy	Individual component value queriesUnit-ball support	$d\ll L^2/\alpha$ ; Lipschitz component functions.Different oracle and support model from the stochastic-gradient row.	Checkedmonograph	Chewi (2026), Chapter 9 bibliographical notes ↗

Scope

The stochastic-gradient table compares unbiased noisy-gradient oracles under different noise assumptions. The finite-sum table counts individual component queries, distinguishing gradient access from value-only access. Bounds from these two oracle models are not directly interchangeable.

Main separation

Sub-exponential noise permits polylogarithmic accuracy dependence. Bounded variance alone forces inverse-accuracy dependence. In fixed dimension, Ou–Wang (2026) give matching upper and lower bounds when the unknown mode lies in a known ball. Their dimension-dependent constants do not give a growing-dimension complexity bound.