Duality between subgradient and conditional gradient methods

Understand

Given a convex optimization problem and its dual, there are many possible first-order algorithms.

• In this paper, we show the equivalence between mirror descent algorithms and algorithms generalizing the conditional gradient method.
• This is done through convex duality, and implies notably that for certain problems, such as for supervised machine learning problems with non-smooth losses or problems regularized by non-smooth regularizers, the primal subgradient method and the dual conditional gradient method are formally equivalent.
• The dual interpretation leads to a form of line search for mirror descent, as well as guarantees of convergence for primal-dual certificates.