Authors: Lee, Sangkyun
Wright, Stephen J.
Title: Manifold Identification in Dual Averaging Methods for Regularized Stochastic Online Learning
Language (ISO): en
Abstract: Iterative methods that calculate their steps from approximate subgradient directions have proved to be useful for stochastic learning problems over large and streaming data sets. When the objective consists of a loss function plus a nonsmooth regularization term whose purpose is to induce structure in the solution, the solution often lies on a low-dimensional manifold of parameter space along which the regularizer is smooth. (When an l1 regularizer is used to induce sparsity in the solution, for example, this manifold is defined by the set of nonzero components of the parameter vector.) This paper shows that a regularized dual averaging algorithm can identify this manifold, with high probability, before reaching the solution. This observation motivates an algorithmic strategy in which, once an iterate is suspected of lying on an optimal or near-optimal manifold, we switch to an “local phase” algorithm that searches in this manifold, thus converging rapidly to a near-optimal point. Computational results are presented to verify the identification property and to illustrate the effectiveness of this approach.
Subject Headings: dual averaging
manifold identification
partly smooth manifold
regularization
URI: http://hdl.handle.net/2003/29382
http://dx.doi.org/10.17877/DE290R-3418
Issue Date: 2012-03-07
URL: http://www.optimization-online.org/DB_FILE/2011/07/3103.pdf
Appears in Collections:Sonderforschungsbereich (SFB) 876

Files in This Item:
File Description SizeFormat 
lee_wright_2011b.pdf2.18 MBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.