We provide new insight into a generalized conditional subgradient algorithm and a generalized mirror descent algorithm for the convex minimization problem [ ; f(Ax) + h(x) . ] As Bach showed in [ SIAM J. Optim. , 25 (2015), pp. 115--129], applying either of these two algorithms to this problem is equivalent to applying the other one to its Fenchel dual. We leverage this duality relationship to develop new upper bounds and convergence results for the gap between the primal and dual iterates generated by these two algorithms. We also propose a new primal-dual hybrid algorithm that combines features of the conditional subgradient and mirror descent algorithms to solve the primal and dual problems in a symmetric fashion. Our algorithms and main results rely only on the availability of computable oracles for @math and @math , and for @math and @math .
This paper sheds new light into the close duality connection between generalizations of two popular algorithmic schemes for problems of the form , namely the conditional gradient (also known as Frank-Wolfe) algorithm @cite_16 @cite_21 @cite_7 and the mirror descent algorithm @cite_18 @cite_20 @cite_8 . The conditional gradient and the mirror descent algorithms share the feature of not requiring any orthogonal projections. This feature makes them attractive in a variety of applications where orthogonal projections are too costly or impractical but where subgradient oracles and Bregman projections are viable. Both the conditional gradient and mirror descent algorithms as well as numerous variants of them have been subjects of active research for several years. Some of the many articles in this rapidly evolving literature include @cite_2 @cite_5 @cite_6 @cite_21 @cite_4 @cite_10 @cite_7 @cite_17 @cite_19 @cite_14 @cite_23 @cite_3 @cite_22 @cite_13 as well as the many references therein.
@cite_13 @cite_18 @cite_14 @cite_4 @cite_22 @cite_7 @cite_8 @cite_21 @cite_6 @cite_3 @cite_19 @cite_23 @cite_2 @cite_5 @cite_16 @cite_10 @cite_20 @cite_17
2964177174 1971945429 2150695437 2949510529
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 nonsmooth losses or problems regularized by nonsmooth 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. We prove the equivalence of two online learning algorithms, mirror descent and natural gradient descent. Both mirror descent and natural gradient descent are generalizations of online gradient descent when the parameter of interest lies on a non-Euclidean manifold. Natural gradient descent selects the steepest descent direction along a Riemannian manifold by multiplying the standard gradient by the inverse of the metric tensor. Mirror descent induces non-Euclidean structure by solving iterative optimization problems using different proximity functions. In this paper, we prove that mirror descent induced by a Bregman divergence proximity functions is equivalent to the natural gradient descent algorithm on the Riemannian manifold in the dual co-ordinate system. We use techniques from convex analysis and connections between Riemannian manifolds, Bregman divergences and convexity to prove this result. This equivalence between natural gradient descent and mirror descent, implies that (1) mirror descent is the steepest descent direction along the Riemannian manifold corresponding to the choice of Bregman divergence and (2) mirror descent with log-likelihood loss applied to parameter estimation in exponential families asymptotically achieves the classical Cramer-Rao lower bound. The mirror descent algorithm (MDA) generalizes gradient descent by using a Bregman divergence to replace squared Euclidean distance. In this paper, we similarly generalize the alternating direction method of multipliers (ADMM) to Bregman ADMM (BADMM), which allows the choice of different Bregman divergences to exploit the structure of problems. BADMM provides a unified framework for ADMM and its variants, including generalized ADMM, inexact ADMM and Bethe ADMM. We establish the global convergence and the O(1 T) iteration complexity for BADMM. In some cases, BADMM can be faster than ADMM by a factor of O(n ln n) where n is the dimensionality. In solving the linear program of mass transportation problem, BADMM leads to massive parallelism and can easily run on GPU. BADMM is several times faster than highly optimized commercial software Gurobi. This paper explores a new framework for reinforcement learning based on online convex optimization, in particular mirror descent and related algorithms. Mirror descent can be viewed as an enhanced gradient method, particularly suited to minimization of convex functions in highdimensional spaces. Unlike traditional gradient methods, mirror descent undertakes gradient updates of weights in both the dual space and primal space, which are linked together using a Legendre transform. Mirror descent can be viewed as a proximal algorithm where the distance generating function used is a Bregman divergence. A new class of proximal-gradient based temporal-difference (TD) methods are presented based on different Bregman divergences, which are more powerful than regular TD learning. Examples of Bregman divergences that are studied include p-norm functions, and Mahalanobis distance based on the covariance of sample gradients. A new family of sparse mirror-descent reinforcement learning methods are proposed, which are able to find sparse fixed points of an l1-regularized Bellman equation at significantly less computational cost than previous methods based on second-order matrix methods. An experimental study of mirror-descent reinforcement learning is presented using discrete and continuous Markov decision processes.