Minimizing Quantum Rényi Divergences via Mirror Descent with Polyak Step Size

Jun-Kai You, Hao-Chung Cheng, Yen-Huan Li

TL;DR

This paper introduces a novel optimization algorithm, "mirror descent with the Polyak step size," designed to efficiently compute crucial quantum information quantities. The method is proven to converge even when standard optimization techniques fail, offering a significant advancement for quantum information theory and related fields.

What Problem Does This Paper Address?

Characterizing quantum information quantities is fundamental to understanding various quantum information-theoretic tasks, from quantum cryptography to error correction. Many of these quantities, such as Petz-Augustin information and Rényi entropies, are computed by minimizing specific quantum Rényi divergences over the set of quantum states. While these optimization problems are theoretically convex, they present a significant numerical challenge. Standard convex optimization algorithms, like projected gradient descent, struggle due to issues like "stalling" where the algorithm gets stuck at low-rank density matrices where the gradient is undefined. Existing methods like entropic mirror descent, while avoiding stalling, lack rigorous convergence guarantees for these specific quantum divergences. This paper aims to bridge this gap by developing a provably convergent optimization method tailored for these challenging quantum information problems.

Methods

The core contribution of this paper is the development of mirror descent with the Polyak step size. This method is a variant of mirror descent, a general class of optimization algorithms. The key innovation lies in the Polyak step size, an adaptive step size rule that has historically been used for gradient descent. The authors adapt this rule for mirror descent, crucially modifying it to avoid requiring knowledge of the optimal function value (which is unknown in this context).

Specifically, the algorithm works as follows:

  • It uses a mirror descent framework, which involves a "mirror map" (a convex function, here related to the von Neumann entropy for quantum states) to transform the problem into a more manageable space.
  • The step size at each iteration is dynamically adjusted using a modified Polyak step size. This modified step size uses an estimate of the optimal function value, derived from past iterates, rather than the true optimal value.
  • The authors provide a theoretical convergence guarantee for this method under a weak condition: that the gradient of the function to be minimized is locally bounded. This is a significant improvement over existing methods that often require stronger conditions like bounded gradients or Hessians.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments on synthetic quantum states generated using standard methods (e.g., RandomDensityMatrix from the QETLAB toolbox).

Key Insights and Ideas

  • Bridging the Gap in Quantum Optimization: The paper successfully addresses a critical gap in quantum information theory by providing a theoretically sound and numerically efficient method for optimizing quantum Rényi divergences, which are central to many important quantum quantities.
  • The Power of the Polyak Step Size: The adaptation of the Polyak step size to mirror descent, particularly without requiring knowledge of the optimal value, is a key insight. This adaptive strategy allows for faster convergence compared to fixed or line-search-based step sizes in many practical scenarios.
  • Weak Convergence Guarantees: The theoretical proof of convergence under a "locally bounded gradient" condition is a significant theoretical achievement. It demonstrates that robust convergence can be achieved without the stringent assumptions often required by other optimization methods.
  • Overcoming "Stalling": By using entropic mirror descent (which inherently generates full-rank iterates), the method avoids the "stalling issue" that plagues simpler algorithms like projected gradient descent when dealing with quantum states.

Key Results

  • Theoretical Convergence: The paper proves that mirror descent with the Polyak step size converges for minimizing quantum Rényi divergences under a weak assumption on the gradient. This is the first guaranteed-to-converge extension of the Polyak step size to mirror descent.
  • Numerical Performance: Numerical experiments demonstrate that entropic mirror descent with the Polyak step size converges fast in practice for minimizing quantum Rényi divergences.
  • Competitive Speed: The proposed method is shown to be competitive with other state-of-the-art methods, such as entropic mirror descent with Armijo line search, in terms of convergence speed, especially when considering elapsed time.
  • Scalability: The method exhibits good scalability with respect to the dimension of the quantum system, a crucial factor for practical applications in quantum information.

Limitations and Future Work

  • Approximate Solution: The current method guarantees convergence to an approximate solution, and the desired numerical accuracy needs to be specified as a parameter. The authors are working on improving the method to provably converge to the exact optimum while maintaining computational efficiency.
  • Parameter Tuning: While the method is robust, achieving optimal convergence speed might require tuning of certain parameters, as observed in the numerical experiments. The authors are exploring the incorporation of line search techniques to accelerate convergence and increase robustness to initial iterate choices.
  • Non-Euclidean Norms: The convergence analysis extends the Polyak step size to possibly non-Euclidean norms, which is essential for mirror descent methods. However, careful selection of the norm in accordance with the Bregman divergence is noted as important.

Summary updated

BibTeX
@inproceedings{you2022minimizing,
  author = {Jun-Kai You and Hao-Chung Cheng and Yen-Huan Li},
  title = {{Minimizing Quantum Rényi Divergences via Mirror Descent with Polyak Step Size}},
  booktitle = {ISIT},
  year = {2022},
  doi = {10.1109/isit50566.2022.9834648},
}
Figure