---
title: "Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.01155v1"
permalink: "https://feed.astralor.com/items/itm_fc80005d5c96049a72db948b"
published: "2026-10-31T17:47:59.000Z"
score: 55
channel: "tech"
tags: ["推理效率","RAG","Lower Bounds","Inference Complexity","Polyak-Ruppert Averaged Stochastic","Gradient Descent","Gaussian","Polyak-Ruppert"]
---

# Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

## At a glance

In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent $γ\in(1/2,1)$, a single …

## Key points

- In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes.
- For every fixed exponent $γ\in(1/2,1)$, a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order $n^{1/2-γ}+n^{γ-1}$ in Kolmogorov and convex distances.
- This matches the existing upper bound throughout the range of $γ$.

## Full text

In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent $γ\in(1/2,1)$, a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order $n^{1/2-γ}+n^{γ-1}$ in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of $γ$. The nonlinear bias contributes $n^{1/2-γ}$ even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order $n^{-(1-γ)/2}$ for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error $\varepsilon$ on this example takes order $\varepsilon^{-4}$ iterations for the best choice $γ=3/4$. Achieving both Gaussian approximation and relative mean variance-estimation errors at most $\varepsilon$ uniformly over the model class requires at least order $\varepsilon^{-6}$ iterations for every fixed $γ$.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_fc80005d5c96049a72db948b