# Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging

arXiv: https://arxiv.org/abs/2311.02557 · HTML: https://mlsanity.com/paper/2311.02557/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 75 references that are in the map.
- First posted on arXiv 5 Nov 2023.

## Builds on (most cited first, 28 of 28)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Quantum State Tomography with Conditional Generative Adversarial Networks](https://mlsanity.com/paper/2008.03240/) (2020)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications](https://mlsanity.com/paper/1706.04957/) (2017)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Efficient Online Portfolio with Logarithmic Regret](https://mlsanity.com/paper/1805.07430/) (2018)
- [Experimental neural network enhanced quantum tomography](https://mlsanity.com/paper/1904.05902/) (2019)
- [Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States](https://mlsanity.com/paper/2202.02765/) (2022)
- [Fastest Rates for Stochastic Mirror Descent Methods](https://mlsanity.com/paper/1803.07374/) (2018)
- [Efficient and Near-Optimal Online Portfolio Selection](https://mlsanity.com/paper/2209.13932/) (2022)
- [When Does Adaptivity Help for Quantum State Learning?](https://mlsanity.com/paper/2206.05265/) (2022)
- [A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions](https://mlsanity.com/paper/1508.04625/) (2015)
- [Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barrier](https://mlsanity.com/paper/2010.08999/) (2020)
- [Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness](https://mlsanity.com/paper/2305.13946/) (2023)
- [Composite Self-Concordant Minimization](https://mlsanity.com/paper/1308.2867/) (2013)
- [On the convergence of stochastic primal-dual hybrid gradient](https://mlsanity.com/paper/1911.00799/) (2019)
- [Convergence of the Exponentiated Gradient Method with Armijo Line Search](https://mlsanity.com/paper/1712.08480/) (2017)
- [Online Self-Concordant and Relatively Smooth Minimization, With Applications to Online Portfolio Selection and Learning Quantum States](https://mlsanity.com/paper/2210.00997/) (2022)
- [A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization](https://mlsanity.com/paper/2002.07003/) (2020)
- [Generalized Self-Concordant Analysis of Frank-Wolfe algorithms](https://mlsanity.com/paper/2010.01009/) (2020)
- [A General Convergence Result for Mirror Descent with Armijo Line Search](https://mlsanity.com/paper/1805.12232/) (2018)
- [Maximizing Products of Linear Forms, and The Permanent of Positive Semidefinite Matrices](https://mlsanity.com/paper/2002.04149/) (2020)
- [Maximum-Likelihood Quantum State Tomography by Soft-Bayes](https://mlsanity.com/paper/2012.15498/) (2020)
- [Maximum-Likelihood Quantum State Tomography by Cover's Method with Non-Asymptotic Analysis](https://mlsanity.com/paper/2110.00747/) (2021)
- [Faster Stochastic First-Order Method for Maximum-Likelihood Quantum State Tomography](https://mlsanity.com/paper/2211.12880/) (2022)

## Built on by (most cited first, 1 of 1)

- [Online Learning Quantum States with the Logarithmic Loss via VB-FTRL](https://mlsanity.com/paper/2311.04237/) (2023)

## Abstract (arXiv)

Consider the problem of minimizing an expected logarithmic loss over either the probability simplex or the set of quantum density matrices. This problem includes tasks such as solving the Poisson inverse problem, computing the maximum-likelihood estimate for quantum state tomography, and approximating positive semi-definite matrix permanents with the currently tightest approximation ratio. Although the optimization problem is convex, standard iteration complexity guarantees for first-order methods do not directly apply due to the absence of Lipschitz continuity and smoothness in the loss function. In this work, we propose a stochastic first-order algorithm named B-sample stochastic dual averaging with the logarithmic barrier. For the Poisson inverse problem, our algorithm attains an varepsilon-optimal solution in smashtildeO(d2/varepsilon2) time, matching the state of the art, where d denotes the dimension. When computing the maximum-likelihood estimate for quantum state tomography, our algorithm yields an varepsilon-optimal solution in smashtildeO(d3/varepsilon2) time. This improves on the time complexities of existing stochastic first-order methods by a factor of dω-2 and those of batch methods by a factor of d2, where ω denotes the matrix multiplication exponent. Numerical experiments demonstrate that empirically, our algorithm outperforms existing methods with explicit complexity guarantees.