identification of dual averaging methods for regularized stochastic online learning

Iterative methods that take steps in approxi-mate subgradient directions have proved to be useful for stochastic learning problems over large or streaming data sets. When the objective consists of a loss function plus a nonsmooth regularization term, whose pur-pose is to induce structure (for example, spar-sity) in the solution, the solution often lies on a low-dimensional manifold along which the regularizer is smooth. This paper shows that a regularized dual averaging algorithm can identify this manifold with high probabil-ity. This observation motivates an algorith-mic strategy in which, once a near-optimal manifold is identified, we switch to an al-gorithm that searches only in this manifold, which typically has much lower intrinsic di-mension than the full space, thus converg-ing quickly to a near-optimal point with the desired structure. Computational results are presented to illustrate these claims. 1