  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.
