arXiv preprint ·
Asymptotic Risk of Learning-Rate Schedules for Least-Squares Regression with Discretely Distributed Features
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the last iterate of stochastic gradient descent (SGD) on streaming least squares with discretely distributed features (Slock's model), which decouples the dynamics across eigendirections. Under power-law source and capacity conditions, we derive the exact finite-time risk and asymptotic equivalents of constant and Warmup-Stable-Decay (WSD) schedules. With a tuned base learning-rate, the resulting scaling law decays as $Θ(T^{-q})$, where $T$ is the horizon, and $q$ is independent of the cooldown length $c \in (0,1]$ but is strictly smaller for the constant schedule: any cooldown of fixed relative length $c > 0$, however short, improves the risk by a polynomial factor, while its length only affects the constant, which is minimized by linear decay ($c = 1$). Finally, we show that the optimal risk depends on the batch size $b$ and horizon $T$ only through $bT$, up to a critical batch size.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
A Mean Field Model of Consumption Inertia and Keeping Up with the Joneses
Convex-Analytic View of Query Selection for Safety Verification of Markov Decision Processes
Online Submodular Welfare Maximization: Computation is not the Bottleneck
Risk-Averse Inference-Time Diffusion Model Alignment with Finite-Sample Guarantees
Exploration strategies for Gaussian process bandit optimization with inference regret guarantees
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.