Samplinglib
Lean gate not recorded for this source state main · 0e31a3cda412
best upper · Normalized SampleWiki statement

High-accuracy stochastic-gradient sampler

A paper-first mathematical case study: read the theorem, the derivation route, and the hidden prerequisites before opening formal infrastructure.

Formal topologyOpen this result's proof branch↗
Statement

Normalized SampleWiki statement

Primary theorem audit pending — this is not presented as a verbatim paper theorem

Chen et al. (COLT 2026); Chewi Theorem 10.1.3primary theorem audit in progress
Guarantee / accuracy
\[\lVert\mu_N-\pi\rVert_{\rm TV}\le\varepsilon\]
Complexity / rate
\[\widetilde O((\kappa\sqrt d+\sigma_\psi^2/\alpha)\operatorname{polylog}(1/\varepsilon))\]

Reading. Read the accuracy guarantee together with the complexity/rate: the source assumptions and its notion of oracle cost are part of the result.

Primary theorem audit pending. The formulas below are the cleaned SampleWiki normalization of the cited result, not a claim of verbatim theorem transcription.

Proof / derivation

Reader derivation map · Oracle-noise and sampling-error route

This is a source-linked reading map for Chen et al. (COLT 2026); Chewi Theorem 10.1.3, not a transcription of the paper's proof. Exact source proof equations replace this map once theorem-level audit is complete.

01

Fix the stochastic/finite-sum oracle and the exact quantity controlled for one update or inner call.

02

Bound the sampling/discretization error together with the oracle-noise or variance-reduction contribution.

03

Propagate the error through the continuous or proximal mixing argument used by the source.

\[\lVert\mu_N-\pi\rVert_{\rm TV}\le\varepsilon\]
04

Choose batch/epoch/step parameters so oracle cost and target sampling accuracy balance at the displayed rate.

\[\widetilde O((\kappa\sqrt d+\sigma_\psi^2/\alpha)\operatorname{polylog}(1/\varepsilon))\]
Assumptions and implicit prerequisites

What must be true before the rate can be read

Model and geometry

  • The oracle model is part of the theorem: stochastic-gradient noise and finite-sum access are not interchangeable.
  • Variance, component count, convexity/functional-inequality constants, and initialization are inherited from the cited result.
  • The displayed query complexity counts the oracle calls used by that source model.

Analytic / proof prerequisites

  • Exact theorem-level parameter ranges and technical hypotheses remain controlled by the cited paper until primary-source audit is complete.
ASTIS rigorous LaTeX
Guarantee / accuracy
\[\lVert\mu_N-\pi\rVert_{\rm TV}\le\varepsilon\]
Complexity / rate
\[\widetilde O((\kappa\sqrt d+\sigma_\psi^2/\alpha)\operatorname{polylog}(1/\varepsilon))\]
Lean formalization

This fold is intentionally quiet while the source statement, proof route, and assumptions are being completed case by case. A source-facing Lean theorem will appear here only after it compiles and its statement has been matched to the audited source.

References and provenance

SampleWiki setting

ASTIS-SW-SETTING-STOCHASTIC-FINITE-SUM-BEST-UPPER-HIGH-ACCURACY-STOCHASTIC-GRADIENT-SAMPLER · source snapshot a409105a2ae07ed5