Effective Dimension of Exp-concave Optimization

While the worst-case complexity of exp-concave stochastic optimization is fairly understood ([22, 28, 18, 15]), a promising avenue is to investigate these complexities under distributional assumptions. One common possibility is the common fast eigendecay assumption ([12, 5, 25, 1]). Namely, in many machine learning problems, the eigenvalues associated with the empirical covariance matrix exhibit a fast decay, where the tail of the eigenvalues are significantly smaller than the desired precision. Naturally, this phenomenon suggests a sketch-and-solve approach, where a sufficiently accurate solution is obtained by projecting the data onto a low-dimensional space and solving the smaller problem. Indeed, many algorithmic ideas in this spirit have been suggested in the recent years ([3, 25]). A more sophisticated approach, which we name sketch-to-precondition, ([2, 8]) is to enhance the performance of first-order optimization methods via preconditioning, where the preconditioner is based on a coarse low-rank approximation to the data matrix. The main message of our paper is as follows: 1 The sample complexity of exp-concave stochastic optimization scales optimally with the effective dimension, rendering the sketch-and-solve approach useless in this context. On the other hand, the sketch-to-precondition approach is effective and can be accelerated via model selection.