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
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 (firstname.lastname@example.org).