Fast Rates for Exp-concave Empirical Risk Minimization
We consider Empirical Risk Minimization (ERM) in the context of stochastic optimization with exp-concave and smooth losses-a general optimization framework that captures several important learning problems including linear and logistic regression, learning SVMs with the squared hinge-loss, portfolio selection and more. In this setting, we establish the first evidence that ERM is able to attain fast generalization rates, and show that the expected loss of the ERM solution in d dimensions converges to the optimal expected loss in a rate of d/n. This rate matches existing lower bounds up to constants and improves by a log n factor upon the state-of-the-art, which is only known to be attained by an online-to-batch conversion of computationally expensive online algorithms.
SUMMARY: Studying Empirical Risk Minimization (ERM) with exp-concave loss, which is more general than strong convexity, is the topic of this paper. The goal is to provide an upper bound for the excess loss. The domain is assumed to be a compact subset of R^d. In addition to the exp-concavity, the smoothness of the loss function is assumed too. Moreover, the estimator requires a small amount of strongly convex regularization to be added to the ERM objective. The paper shows that under these assumptions and with the modified estimator, the expectation of the excess loss behaves as O(d/n).The proof has some key elements:Even though we do not have strong convexity in the whole domain, we can still define a local notion of strong convexity, which holds around the empirical minimizer w.r.t. a norm that depends on each of n data points. In other words, the proof does not use a single norm for all points. This leads to an upper bound for leave-one-out kind of stability terms (Lemma 6). Even though the upper bound of Lemma 6 is not uniformly small for all data points, Lemma 8 shows that not many of them can be large (order of d), and the rest are small. These along the i.i.d. property of data allows one to provide a fast upper bound on the expectation of the excess loss.  EVALUATION and QUESTIONS: I think this is a nice theoretical paper. It generalizes the results that are known for strongly convex losses to a more relaxed class of losses. The proofs seem to be correct.Here are some comments and questions:- It might be helpful to provide some concrete examples of exp-concave losses that are used in practice, which are not strongly convex.- What would happen if the parameter domain is not compact? Presumably one cannot prove an upper bound for the unregularized ERM. What about this regularized variant? Is the current 1/n R(w) regularization enough to prove something meaningful?- Is it possible to relax the requirement of the strong convexity of the regularizer? It appears that the proof of Lemma 6 breaks down without that.