Stochastic Dual Coordinate Ascent and its Proximal Extension for Regularized Loss Minimization

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=wlO7FbKAfm0


Duration: 55:14
2,186 views
6

Stochastic Gradient Descent (SGD) has become popular for solving large scale supervised machine learning optimization problems such as SVM, due to their strong theoretical guarantees. While the closely related Dual Coordinate Ascent (DCA) method has been implemented in various software packages, it has so far lacked good convergence analysis. We present a new analysis of Stochastic Dual Coordinate Ascent (SDCA) showing that this class of methods enjoy strong theoretical guarantees that are comparable or better than SGD. This analysis justifies the effectiveness of SDCA for practical applications. Moreover, we introduce a proximal version of dual coordinate ascent method. We demonstrate how the derived algorithmic framework can be used for numerous regularized loss minimization problems, including L1 regularization and structured output SVM. The convergence rates we obtain match or improve state-of-the-art results. Joint work with Shai Shalev-Shwartz



Other Videos By Microsoft Research


2016-07-28Quantum Computation for Quantum Chemistry: Status, Challenges, and Prospects - Session 3
2016-07-28Asymptotic behavior of the Cheeger constant of super-critical percolation in the square lattice
2016-07-28Recovering Washington’s Wolves & Preserving the Critical Link
2016-07-28The similarity distance on graphs and graphons
2016-07-28Neural Acceleration for General-Purpose Approximate Programs
2016-07-28Snow Hydrology at the Scale of Mountain Ranges
2016-07-28Vote Privacy, Revisited: New Definitions, Tools and Constructions
2016-07-28Dispelling an Old Myth about an Ancient Algorithm
2016-07-28Behavior Based Authentication using Gestures and Signatures
2016-07-28Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
2016-07-28Stochastic Dual Coordinate Ascent and its Proximal Extension for Regularized Loss Minimization
2016-07-28A Practical Approach to Reduce the Power Consumption of LCD Displays
2016-07-28CryptDB: Processing Queries on an Encrypted Database
2016-07-28Performing Time, Space and Light
2016-07-28Probabilistic Methods for Efficient Search & Statistical Learning in Extremely HighDimensional Data
2016-07-28Quantum Computation for Quantum Chemistry: Status, Challenges, and Prospects - Session 4
2016-07-28Quantum Computation for Quantum Chemistry: Status, Challenges, and Prospects - Session 2
2016-07-28Quantum Computation for Quantum Chemistry: Status, Challenges, and Prospects - Session 1
2016-07-28Bug Finding Techniques for Programs with Infinitely Many States
2016-07-28The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal
2016-07-28TVAL+: Combining TVLA and Value Analyses


Tags:
microsoft research