Window SGD under the PL Condition
Descriptions may be stale. Consult the linked Lean sources.
Window SGD under the PL Condition
We consider minimizing a possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function
Assumption 2 (Polyak–Łojasiewicz condition and
initial gap). There exists
Assumption 3 (Independent stochastic gradients and
fourth moments). There is a probability measure
Our formulation is algorithm-specific: we analyze Window SGD. The
algorithm chooses a constant step size
Let
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) KappaFreeSgdPLHessian
(Ours) |
|||
| (2) SGD (Khaled and Richtárik 2020, Thm. 3, Cor. 2) | (1): statistical factor
|
(1) adds Hessian
regularity and kurtosis; |
|
| (3) Weighted SGD (Stich 2019, Thm. 5); strongly convex restriction | (1): scope extends from strong convexity to PL, allowing non-isolated minimizers. | (1) on the strongly
convex overlap: extra |
|
| (4) Ruppert–Polyak averaging (Gadat and Panloup 2017, Thm. 2); isolated-minimizer restriction | Derived bound: |
(1) allows non-isolated minimizers and gives explicit parameter dependence. Rates are not comparable: squared-distance accuracy and covariance/consistency assumptions differ. | |
| (5) Lower bound (Masiha et al. 2026, Thm. 4.3, Rem. 4.6); broader smooth PL class | (1) improves the statistical dependence on a narrower subclass. The hard instances lack Lipschitz Hessians; this is not an improvement on the full smooth PL class. |
Abbr: