Timezone: »
Poster
Efficient Learning using Forward-Backward Splitting
John Duchi · Yoram Singer
We describe, analyze, and experiment with a new framework for empirical loss minimization with regularization. Our algorithmic framework alternates between two phases. On each iteration we first perform an {\em unconstrained} gradient descent step. We then cast and solve an instantaneous optimization problem that trades off minimization of a regularization term while keeping close proximity to the result of the first phase. This yields a simple yet effective algorithm for both batch penalized risk minimization and online learning. Furthermore, the two phase approach enables sparse solutions when used in conjunction with regularization functions that promote sparsity, such as $\ell_1$. We derive concrete and very simple algorithms for minimization of loss functions with $\ell_1$, $\ell_2$, $\ell_2^2$, and $\ell_\infty$ regularization. We also show how to construct efficient algorithms for mixed-norm $\ell_1/\ell_q$ regularization. We further extend the algorithms and give efficient implementations for very high-dimensional data with sparsity. We demonstrate the potential of the proposed framework in experiments with synthetic and natural datasets.
Author Information
John Duchi (Stanford)
Yoram Singer (Princeton)
Related Events (a corresponding poster, oral, or spotlight)
-
2009 Oral: Efficient Learning using Forward-Backward Splitting »
Wed. Dec 9th 06:40 -- 07:00 PM Room
More from the Same Authors
-
2016 Poster: Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity »
Amit Daniely · Roy Frostig · Yoram Singer -
2013 Poster: Information-theoretic lower bounds for distributed statistical estimation with communication constraints »
Yuchen Zhang · John Duchi · Michael Jordan · Martin J Wainwright -
2013 Oral: Information-theoretic lower bounds for distributed statistical estimation with communication constraints »
Yuchen Zhang · John Duchi · Michael Jordan · Martin J Wainwright -
2013 Poster: Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation »
John Duchi · Martin J Wainwright · Michael Jordan -
2013 Poster: Estimation, Optimization, and Parallelism when Data is Sparse »
John Duchi · Michael Jordan · Brendan McMahan -
2012 Workshop: Big Learning : Algorithms, Systems, and Tools »
Sameer Singh · John Duchi · Yucheng Low · Joseph E Gonzalez -
2012 Poster: Privacy Aware Learning »
John Duchi · Michael Jordan · Martin J Wainwright -
2012 Poster: Communication-Efficient Algorithms for Statistical Optimization »
Yuchen Zhang · John Duchi · Martin J Wainwright -
2012 Oral: Privacy Aware Learning »
John Duchi · Michael Jordan · Martin J Wainwright -
2012 Poster: Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods »
John Duchi · Michael Jordan · Martin J Wainwright · Andre Wibisono -
2011 Poster: Distributed Delayed Stochastic Optimization »
Alekh Agarwal · John Duchi -
2010 Workshop: Learning on Cores, Clusters, and Clouds »
Alekh Agarwal · Lawrence Cayton · Ofer Dekel · John Duchi · John Langford -
2010 Talk: Learning Structural Sparsity »
Yoram Singer -
2010 Spotlight: Distributed Dual Averaging In Networks »
John Duchi · Alekh Agarwal · Martin J Wainwright -
2010 Poster: Distributed Dual Averaging In Networks »
John Duchi · Alekh Agarwal · Martin J Wainwright -
2009 Poster: Group Sparse Coding »
Samy Bengio · Fernando Pereira · Yoram Singer · Dennis Strelow -
2006 Poster: Online Classification for Complex Problems Using Simultaneous Projections »
Yonatan Amit · Shai Shalev-Shwartz · Yoram Singer -
2006 Poster: Convex Repeated Games and Fenchel Duality »
Shai Shalev-Shwartz · Yoram Singer -
2006 Poster: Support Vector Machines on a Budget »
Ofer Dekel · Yoram Singer -
2006 Poster: Using Combinatorial Optimization within Max-Product Belief Propagation »
John Duchi · Danny Tarlow · Gal Elidan · Daphne Koller -
2006 Spotlight: Using Combinatorial Optimization within Max-Product Belief Propagation »
John Duchi · Danny Tarlow · Gal Elidan · Daphne Koller -
2006 Spotlight: Convex Repeated Games and Fenchel Duality »
Shai Shalev-Shwartz · Yoram Singer -
2006 Spotlight: Support Vector Machines on a Budget »
Ofer Dekel · Yoram Singer -
2006 Poster: Image Retrieval and Classification Using Local Distance Functions »
Andrea Frome · Yoram Singer · Jitendra Malik