Existing convergence guarantees for the mirror descent algorithm require the objective function to have a bounded gradient or be smooth relative to a Legendre function. The bounded gradient and relative smoothness conditions, however, may not hold in important applications, such as quantum state tomography and portfolio selection. In this paper, we propose a local version of the relative smoothness condition as a generalization of its existing global version, and prove that under this local relative smoothness condition, the mirror descent algorithm with Armijo line search always converges. Numerical results showed that, therefore, the mirror descent algorithm with Armijo line search was the fastest guaranteed-to-converge algorithm for quantum state tomography, empirically on real data-sets.
@cite_30: Interior gradient (subgradient) and proximal methods for convex constrained minimization have been much studied, in particular for optimization problems over the nonnegative octant. These methods are using non-Euclidean projections and proximal distance functions to exploit the geometry of the constraints. In this paper, we identify a simple mechanism that allows us to derive global convergence results of the produced iterates as well as improved global rates of convergence estimates for a wide class of such methods, and with more general convex constraints. Our results are illustrated with many applications and examples, including some new explicit and simple algorithms for conic optimization problems. In particular, we derive a class of interior gradient algorithms which exhibits an @math global convergence rate estimate.
@cite_35: 
@cite_18: 
@cite_29: The mirror descent algorithm (MDA) was introduced by Nemirovsky and Yudin for solving convex optimization problems. This method exhibits an efficiency estimate that is mildly dependent in the decision variables dimension, and thus suitable for solving very large scale optimization problems. We present a new derivation and analysis of this algorithm. We show that the MDA can be viewed as a nonlinear projected-subgradient type method, derived from using a general distance-like function instead of the usual Euclidean squared distance. Within this interpretation, we derive in a simple way convergence and efficiency estimates. We then propose an Entropic mirror descent algorithm for convex minimization over the unit simplex, with a global efficiency estimate proven to be mildly dependent in the dimension of the problem.
@cite_3: We consider two algorithm for on-line prediction based on a linear model. The algorithms are the well-known Gradient Descent (GD) algorithm and a new algorithm, which we call EG(+ -). They both maintain a weight vector using simple updates. For the GD algorithm, the update is based on subtracting the gradient of the squared error made on a prediction. The EG(+ -) algorithm uses the components of the gradient in the exponents of factors that are used in updating the weight vector multiplicatively. We present worst-case loss bounds for EG(+ -) and compare them to previously known bounds for the GD algorithm. The bounds suggest that the losses of the algorithms are in general incomparable, but EG(+ -) has a much smaller loss if only a few components of the input are relevant for the predictions. We have performed experiments, which show that our worst-case upper bounds are quite tight already on simple artificial data.
@cite_0: The proximal gradient and its variants is one of the most attractive first-order algorithm for minimizing the sum of two convex functions, with one being nonsmooth. However, it requires the differentiable part of the objective to have a Lipschitz continuous gradient, thus precluding its use in many applications. In this paper we introduce a framework which allows to circumvent the intricate question of Lipschitz continuity of gradients by using an elegant and easy to check convexity condition which captures the geometry of the constraints. This condition translates into a new descent lemma which in turn leads to a natural derivation of the proximal-gradient scheme with Bregman distances. We then identify a new notion of asymmetry measure for Bregman distances, which is central in determining the relevant step-size. These novelties allow to prove a global sublinear rate of convergence, and as a by-product, global pointwise convergence is obtained. This provides a new path to a broad spectrum of problems arising in key applications which were, until now, considered as out of reach via proximal gradient methods. We illustrate this potential by showing how our results can be applied to build new and simple schemes for Poisson inverse problems.
The mirror descent algorithm was introduced in @cite_18 . The formulation was proposed in @cite_29 , which is equivalent to the original one under standard assumptions. The interior gradient method studied in @cite_30 is also of the form ; the difference lies in the technical conditions. Standard convergence analyses of the mirror descent, as discussed above, assume either bounded gradient or relative smoothness @cite_30 @cite_0 @cite_29 @cite_35 @cite_18 . The exponentiated gradient method was proposed in @cite_3 ; it is also known as the entropic mirror descent @cite_29 .