A General Convergence Result for Mirror Descent with Armijo Line Search
arXiv:1805.12232
Abstract
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.
arXiv comment21 pages, 3 figures
References in corpus (6)
- Experimental Quantum State Tomography of Optical Fields and Ultrafast Statistical Sampling
- Unknown Quantum States and Operations, a Bayesian View
- Quantum state estimation
- Variable metric inexact line-search based methods for nonsmooth optimization
- Quantum process tomography via completely positive and trace-preserving projection
- Composite Self-Concordant Minimization