Abstract
In this paper we derive high probability lower and upper bounds on the excess risk of stochastic optimization of exponentially concave loss functions. Exponentially concave loss functions encompass several fundamental problems in machine learning such as squared loss in linear regression, logistic loss in classification, and negative logarithm loss in portfolio management. We demonstrate an O(d log T/T ) upper bound on the excess risk of stochastic online Newton step algorithm, and an O(d/T ) lower bound on the excess risk of any stochastic optimization method for squared loss, indicating that the obtained upper bound is optimal up to a logarithmic factor. The analysis of upper bound is based on recent advances in concentration inequalities for bounding self-normalized martingales, which is interesting by its own right, and the proof technique used to achieve the lower bound is a probabilistic method and relies on an information-theoretic minimax analysis.
Original language | English (US) |
---|---|
Journal | Journal of Machine Learning Research |
Volume | 40 |
Issue number | 2015 |
State | Published - 2015 |
Event | 28th Conference on Learning Theory, COLT 2015 - Paris, France Duration: Jul 2 2015 → Jul 6 2015 |
All Science Journal Classification (ASJC) codes
- Software
- Artificial Intelligence
- Control and Systems Engineering
- Statistics and Probability