Optimal Sketching Bounds for Exp-concave Stochastic Minimization

Abstract

We derive optimal statistical and computational complexity bounds for exp-concave stochastic minimization in terms of the effective dimension. For common eigendecay patterns of the population covariance matrix, this quantity is significantly smaller than the ambient dimension. Our results reveal interesting connections to sketching results in numerical linear algebra. In particular, our statistical analysis highlights a novel and natural relationship between algorithmic stability of empirical risk minimization and ridge leverage scores, which play significant role in sketching-based methods. Our main computational result is a fast implementation of a sketch-to-precondition approach in the context of exp-concave empirical risk minimization.

References in corpus (8)

• Recursive Sampling for the Nyström Method
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• Efficient Second Order Online Learning by Sketching
• Second-Order Kernel Online Convex Optimization with Adaptive Sketching
• Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimization
• Faster SGD Using Sketched Conditioning
• Fast rates with high probability in exp-concave statistical learning