Manifold Identification of Dual Averaging Methods for

Regularized Stochastic Online Learning

 

Dr. Sangkyun Lee, University of Technology Dortmund, Germany December 29, 2011 10:30 AM

302- 309-1

 

Abstract:

 

Iterative methods that take steps in approximate 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 purpose is to induce structure (for example, sparsity) 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 probability. This observation motivates an algorithmic strategy in which, once a near-optimal manifold is identified, we switch to an algorithm that searches only in this manifold, which typically has much lower intrinsic dimension than the full space, thus converging quickly to a near-optimal point with the desired structure. Computational results are presented to illustrate these claims..

 

This page is maintained by Yumi Yi (ymyi@bi.snu.ac.kr).
Last update: January 17, 2012