2018/10/23 by Alnur Ali, J. Zico Kolter, Ali, Alnur +3 · 6 citations
Engineering · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Random Matrices and Applications #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.1810.10082
openalex publication_date 2018/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the statistical properties of the iterates generated by gradient descent, applied to the fundamental problem of least squares regression. We take a continuous-time view, i.e., consider infinitesimal step sizes in gradient descent, in which case the iterates form a trajectory called gradient flow. Our primary focus is to compare the risk of gradient flow to that of ridge regression. Under the calibration t=1/λ---where t is the time parameter in gradient flow, and λ the tuning parameter in ridge regression---we prove that the risk of gradient flow is no less than 1.69 times that of ridge, along the entire path (for all t ≥ 0). This holds in finite samples with very weak assumptions on the data model (in particular, with no assumptions on the features X). We prove that the same relative risk bound holds for prediction risk, in an average sense over the underlying signal β0. Finally, we examine limiting risk expressions (under standard Marchenko-Pastur asymptotics), and give supporting numerical experiments.