Part of Advances in Neural Information Processing Systems 18 (NIPS 2005)
Anatoli Juditsky, Alexander Nazin, Alexandre Tsybakov, Nicolas Vayatis
We consider the problem of constructing an aggregated estimator from a ﬁnite class of base functions which approximately minimizes a con- vex risk functional under the ℓ1 constraint. For this purpose, we propose a stochastic procedure, the mirror descent, which performs gradient de- scent in the dual space. The generated estimates are additionally aver- aged in a recursive fashion with speciﬁc weights. Mirror descent algo- rithms have been developed in different contexts and they are known to be particularly efﬁcient in high dimensional problems. Moreover their implementation is adapted to the online setting. The main result of the paper is the upper bound on the convergence rate for the generalization error.