COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Dykstra’s Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions

## Dykstra’s Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and ExtensionsAdd to your list(s) Download to your calendar using vCal - Ryan Tibshirani (Carnegie Mellon University)
- Tuesday 26 June 2018, 11:00-11:45
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact info@newton.ac.uk. STSW04 - Future challenges in statistical scalability We study connections between Dykstra’s algorithm for projecting onto an intersection of convex sets, the augmented Lagrangian method of multipliers or ADMM , and block coordinate descent. We prove that coordinate descent for a regularized regression problem, in which the penalty is a separable sum of support functions, is exactly equivalent to Dykstra’s algorithm applied to the dual problem. ADMM on the dual problem is also seen to be equivalent, in the special case of two sets, with one being a linear subspace. These connections, aside from being interesting in their own right, suggest new ways of analyzing and extending coordinate descent. For example, from existing convergence theory on Dykstra’s algorithm over polyhedra, we discern that coordinate descent for the lasso problem converges at an (asymptotically) linear rate. We also develop two parallel versions of coordinate descent, based on the Dykstra and ADMM connections. Finally, we discuss the implications of this work for backfitting in additive models. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
Note that ex-directory lists are not shown. |
## Other listsInfant Sorrow Arrol Adam Lecture Series PublicHealth@Cambridge## Other talksLanguage Adaptation experiments: Cross-lingual embeddings for related languages Back on the Agenda? Industrial Policy revisited Conference From memory: Nigel Hall, sculpture and drawing Weather Forecast Improvements at the UK Met Office: Responding to the Big Data Challenge It takes two to tango:platelet collagen receptor GPVI-dimer in thrombosis and clinical implications Solving the Reproducibility Crisis |