Summary of The Sample Complexity Of Gradient Descent in Stochastic Convex Optimization, by Roi Livni
The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
by Roi Livni
First submitted to arxiv on: 7 Apr 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Optimization and Control (math.OC)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary The paper analyzes the sample complexity of full-batch Gradient Descent (GD) in non-smooth Stochastic Convex Optimization. It shows that the generalization error of GD with common hyper-parameters can be (d/m + 1/), matching the worst-case empirical risk minimizers’ sample complexity. This implies that GD has no advantage over naive ERMs in this setup. The bound is derived from a new generalization bound dependent on dimension, learning rate, and number of iterations. Additionally, it demonstrates that for general hyper-parameters, when the dimension exceeds the number of samples, T=(1/^4) iterations are required to avoid overfitting. This resolves an open problem by Schlisserman et al.23 and Amir er Al.21, improving previous lower bounds showing that the sample size must be at least square root of the dimension. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper looks at how well a certain type of algorithm (Gradient Descent) performs in a specific task (optimizing convex functions with noisy data). It shows that this algorithm doesn’t have any special advantages when it comes to generalizing from small datasets. The results are important because they help us understand the limits of what we can do with this type of algorithm, and how we need to design new algorithms if we want to improve performance. |
Keywords
* Artificial intelligence * Generalization * Gradient descent * Optimization * Overfitting
