Stochastic convex optimization using mirror averaging algorithms

-
Philippe Rigollet, Georgia Institute of Technology

Several statistical problems where the goal is to minimize an unknown convex risk function, can be formulated in the general framework of stochastic convex optimization. For example the problem of model selection and more generally of aggregation can be treated using the machinery of stochastic optimization in several frameworks including density estimation, regression and convex classification. We describe a family of general algorithms called "mirror averaging algorithms" that yield an estimator (or a classifier) which attains optimal rates of model selection in several interesting cases. The theoretical results are presented in the form of exact oracle inequalities similar to those employed in optimization theory. The practical performance of the algorithms is illustrated on several real and artificial examples and compared to standard estimators or classifiers.