Constant-Stepsize Stochastic Approximation: Finite-Time Convergence, Gaussian Approximation, and Tail Bounds
Constant-stepsize stochastic approximation (SA) is widely used in learning for computational efficiency, yet the distribution of the iterates is typically intractable. Classical asymptotics results give $X_k^{(α)} \approx X^{(α)} \approx x^\star+\sqrtαY$, where $X^{(α)}$ is the steady state and $Y$ is an appropriate Gaussian limit, by progressively taking the time $k\uparrow\infty$ and stepsize $α\downarrow0$. Such limit results, however, do not quantify finite-time, finite-stepsize errors. We develop an explicit pre-limit characterization for SA with i.i.d.\ and Markovian noise. We…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.13960
curl -X POST /api/v1/records/arxiv/2602.13960/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.13960/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'