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 3091 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 lowdimensional 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 nearoptimal 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 nearoptimal 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).
