Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions

Understand

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 (separable) penalty functions are seminorms, 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.