156 citations · 418 across the 15 of their papers we have counts for
4 papers · 1 filter
Leverage Score Sampling for Faster Accelerated Regression and ERM
Naman Agarwal, Sham Kakade, Rahul Kidambi +3
Given a matrix and a vector , we show how to compute an -approximate solution to the regression problem $ \min_{x\in\m…
Efficient Estimation of Generalization Error and Bias-Variance Components of Ensembles
Dhruv Mahajan, Vivek Gupta, S Sathiya Keerthi +3
For many applications, an ensemble of base classifiers is an effective solution. The tuning of its parameters(number of classes, amount of data on which each classifier is to be tr…
A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
Prateek Jain, Sham M. Kakade, Rahul Kidambi +3
This work provides a simplified proof of the statistical minimax optimality of (iterate averaged) stochastic gradient descent (SGD), for the special case of least squares. This res…
Accelerating Stochastic Gradient Descent For Least Squares Regression
Prateek Jain, Sham M. Kakade, Rahul Kidambi +2
There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g. Nesterov's acceleration, conjugate gradient, heavy ball) for the purposes o…