A Linearly Convergent Algorithm for Petz-Augustin Means with Applications to Computing Petz-Augustin Capacity and Equilibrium Prices in Fisher Markets

arXiv:2502.06399 · quant-ph, cs.IT, math.IT, math.OC · Submitted 2025-02-10 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai.

Mira: And I'm Mira, here with Lev.

Kai: We're looking at the paper: "A Linearly Convergent Algorithm for Petz-Augustin Means with Applications to Computing Petz-Augustin Capacity and Equilibrium Prices in Fisher Markets".

Mira: Here's the gist of the paper. The gist The proposed algorithm provides the first iterative method with a non-asymptotic convergence guarantee for solving the optimization problem defining the Petz-Augustin mean, achieving a linear rate of O1 − 1/α T with respect to the Thompson metric for orders α ∈ (1/2, 1) ∪ (1, ∞).

Kai: The paper studies the computation of the Petz-Augustin mean Q⋆ of order α ∈ (0, 1) ∪ (1, ∞), which is defined as

Cheng et al., 2022: Q⋆ ∈ arg min F(Q), F(Q):= Xn j=1 w

j: Dα (Aj∥Q).

Mira: The Petz-Augustin mean arises in various contexts, including defining the Petz capacity, characterizing optimal error exponents in classical-quantum channel coding

Dalai, 2013, Dalai and Winter, 2014: .

Kai: A significant gap remains regarding the computation of this mean in the non-commutative setting.

Title and authors: Kai: So let's talk about the paper "A Linearly Convergent Algorithm for Petz-Augustin Means with Applications to Computing Petz-Augustin Capacity and Equilibrium Prices in Fisher Markets". The title tells you exactly what we’re looking at here, connecting the Petz-Augustin mean computation with capacity and equilibrium prices in Fisher markets.

Mira: It's a paper by Chun Neng Chu, Wei-Fu Tseng, and Yen-Huan Li. The authors are from National Taiwan University, and they’ve managed to tackle this complex optimization problem defined by minimizing a weighted sum of n Petz-Rényi divergences of order alpha over d by d quantum states.

Lev: The main implication here is providing the first algorithm with a nonasymptotic convergence guarantee for solving this mean, achieving a linear rate of O one minus one over alpha T with respect to the Thompson metric for orders alpha in (one/two one) union (one infinity) <ref:2502.06399#pg1,T with respect to the Thompson metric for>.

Kai: That convergence guarantee is what’s really exciting. It’s not just saying it converges eventually; it’s giving us a specific rate of convergence based on the Thompson metric.

Mira: And they show that this holds for all orders alpha in (one/two one) union (one infinity), which covers a broad range of scenarios where this mean is relevant <ref:2502.06399#pg1>.

Lev: The initialization time complexity is O nd3 and the per-iteration time complexity is O nd2 + d three <ref:2502.06399#pg1>. That's what you'd need to consider when thinking about running this on actual hardware.

Kai: So, they’ve managed to keep the per-iteration cost relatively low, which is good for practical implementation compared to some other first-order methods mentioned in their work.

Mira: They also show that when the optimization problem has commuting quantum states, it reduces to a classical Augustin mean q star defined by equation two for some aj in delta d.

Lev: That classical form is where things get grounded, because we know the structure of that minimization problem well from the Augustin paper back in one thousand nine hundred seventy-eight <ref:2502.06399#pg2>.

Kai: So they’re bridging the gap between complex quantum optimization and established classical results in a controlled way.

The paper's summary: Mira: Now, let's look at what this paper actually summarizes—it proposes an iteration rule for computing the Petz-Augustin mean, formally defined in equation three. It’s inspired by an existing algorithm for computing lp-Lewis weights.

Lev: So the core of their contribution is proposing this specific iteration rule: Qt+one equals (Xn j=one w

j: Aα j Tr h Aα j Q one minus alpha t i) one/alpha, where Qt is the iterate at step t <ref:2502.06399#pg1>.

Kai: That formula looks like a standard operator update, but they claim it converges to the Petz-Augustin mean Q star. And they prove this convergence at that linear rate O one minus one over alpha T for all alpha in (one/two one) union (one infinity) <ref:2502.06399#pg1>.

Mira: They also show that the operator TF is contractive with a ratio of one minus one over alpha with respect to the Thompson metric, which is the main engine behind their convergence proof <ref:2502.06399#pg1,with respect to the Thompson metric>.

Lev: That contraction ratio is what drives the main result, theorem five-one, which bounds the Thompson metric between Q1 minus alpha star and QT plus one at a rate of O one minus one over alpha T <ref:2502.06399#pg1>.

Kai: It’s a lot of machinery to prove that, but for someone listening here, it means there’s a rigorous mathematical foundation for finding this mean.

Mira: And they also show that the function values are non-increasing when alpha is greater than one which adds another nice property to the analysis <ref:2502.06399#pg1>.

Lev: For running on real hardware, we need to focus on the iteration rule itself and its computational cost rather than getting bogged down in all those convergence proofs for now.

Kai: So for a listener, this means they’ve given us a reliable procedure that actually works iteratively to get the mean Q star.

The paper's improvements: Kai: They point out a few specific ways they improve things over what was already out there. One big one is proposing their iteration rule (three) as an alternative to standard first-order methods for computing the gradient of F(Q) <ref:2502.06399#pg1>.

Mira: They state that the time complexity of computing a gradient in problem one is O nd2 + d four according to You et al <ref:2502.06399#pg3,the time complexity of computing a gradient>., and their proposed per-iteration time complexity is only O nd2 + d three <ref:2502.06399#pg1>.

Lev: That difference, that reduction from d four to d three for the iteration step is what makes this method computationally cheaper, as we discussed earlier <ref:2502.06399#pg3>.

Kai: So when you put it all together, the improvement isn't just a theoretical existence of a solution; it’s about making the actual computation step more efficient in practice.

Mira: They also show that their iteration rule (three) is computationally cheaper than standard first-order methods, as mentioned before, and they prove this convergence at that linear rate for all alpha in (one/two one) union (one infinity) <ref:2502.06399#pg1>.

Lev: The improvement is really about showing that the method scales better when we move from theory to actual computation.

Kai: They also address the situation where alpha is not well-defined, saying they replace Q star with the best iterate from entropic mirror descent with a Polyak step size for orders less than or equal to zero point five.

Mira: That’s a necessary caveat, because they admit there isn't actually a nonasymptotic guarantee in that lower range of alpha.

Conclusion: Kai: To wrap up this discussion on "A Linearly Convergent Algorithm for Petz-Augustin Means with Applications to Computing Petz-Augustin Capacity and Equilibrium Prices in Fisher Markets". The paper gives us a rigorous method to compute these means and related quantities with nonasymptotic convergence guarantees.

Mira: They’ve provided a concrete, iterative procedure that works for solving the Petz-Augustin mean across all relevant orders alpha in (zero one) union (one infinity) <ref:2502.06399#pg1>.

Lev: For us in error correction, it means we have a method to compute Q star reliably and understand the associated convergence behavior.

Kai: The application to capacity and equilibrium prices is really interesting because it shows how these concepts intertwine in real-world applications.

Mira: It solidifies the idea that this iterative rule functions as a fixed-point iteration for all those orders, providing a rigorous method for computing the Petz-Augustin mean and related quantities with nonasymptotic convergence guarantees.

Lev: And to summarize, we’ve got a tool to compute the Petz-Augustin mean reliably and understand its associated convergence behavior in quantum settings.

Kai: That's it for this paper. We've seen how this work connects complex optimization with established results in a new way.

Mira: Thanks for joining us today as we discussed "A Linearly Convergent Algorithm for Petz-Augustin Means with Applications to Computing Petz-Augustin Capacity and Equilibrium Prices in Fisher Markets".

Chun-Neng Chu, Wei-Fu Tseng, Yen-Huan Li

National Taiwan University

quant-ph, cs.IT, math.IT, math.OC

Submitted: 2025-02-10

Updated: 2026-10-17

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 76/100

The gist: The gist The proposed algorithm provides the first iterative method with a non-asymptotic convergence guarantee for solving the optimization problem defining the Petz-Augustin mean, achieving a

Key concepts

Petz-Augustin Mean (Q⋆): This is an optimization problem where you seek a specific mean Q that minimizes a function F(Q) related to the order α. It appears in contexts like defining Petz capacity and characterizes optimal error exponents in quantum channel coding.
Thompson Metric: This is a mathematical distance measure used to quantify how close two sequences of numbers or iterates are. The algorithm proves that the iterates generated by its iteration rule converge towards the true mean Q⋆ at a predictable rate relative to this metric.
Tatonnement Dynamic: This refers to an iterative process, often used in economics, where agents adjust their decisions (like prices) based on market conditions. The proposed algorithm is interpreted as such a dynamic in Fisher markets, helping determine equilibrium prices.
Petz Capacity (Cα): This is a quantity related to quantum information theory that characterizes the maximum rate at which quantum information can be reliably transmitted through a channel of order α. The paper develops an efficient algorithm to compute this capacity with known convergence properties.

Terminology

Generalization — 1× in this paper · explained in 13 episodes

Summary

The gist The proposed algorithm provides the first iterative method with a non-asymptotic convergence guarantee for solving the optimization problem defining the Petz-Augustin mean, achieving a linear rate of O1 − 1/α T with respect to the Thompson metric for orders α ∈ (1/2, 1) ∪ (1, ∞).

Motivation and Problem Formulation

The paper studies the computation of the Petz-Augustin mean Q⋆ of order α ∈ (0, 1) ∪ (1, ∞), which is defined as [Cheng et al., 2022] Q⋆ ∈ arg min F(Q), F(Q):= Xn j=1 w[j]Dα (Aj∥Q). The Petz-Augustin mean arises in various contexts, including defining the Petz capacity, characterizing optimal error exponents in classical-quantum channel coding [Dalai, 2013, Dalai and Winter, 2014]. A significant gap remains regarding the computation of this mean in the non-commutative setting. The optimization problem (1) is convex for orders α ∈ (0, 1) ∪ (1, 2] [Mosonyi and Ogawa, 2017], but its gradient and Hessian are unbounded.

Proposed Iterative Algorithm

The authors propose an iteration rule for computing the Petz-Augustin mean (1), formally defined in (11): Qt+1 = (Xn j=1 w[j] Aα j Tr h Aα j Q 1−α t i) 1/α, where Qt denotes the iterate at step t. This rule is inspired by an existing algorithm for computing the lp-Lewis weights [Cohen and Peng, 2015]. The authors prove that this iteration rule (3) converges at a linear rate of O1 − 1/α T for all α ∈ (1/2, 1) ∪ (1, ∞), making it the first algorithm with a nonasymptotic convergence guarantee for computing the Petz-Augustin mean. The per-iteration time complexity of this algorithm is Ond2 + d3.

Convergence Analysis and Properties

The convergence analysis relies on proving that the powered iterates Q1−α t are contractive with respect to the Thompson metric, and that their limit point coincides with the powered Petz-Augustin mean Q1−α⋆. The operator TF is proven to be contractive with a ratio of 1 − 1/α with respect to the Thompson metric (Lemma 5.2). This leads to the main result, Theorem 5.1, which bounds the Thompson metric between Q1−α⋆ and QT+1 at a rate of O1 − 1/α T. Furthermore, for α > 1, the function values are non-increasing.

Applications

The algorithm is applied to two main applications. First, it develops an iterative method for computing the Petz capacity of order α ∈ (1/2, 1), which converges at a rate of O(log(n)/T). Second, the authors establish that the classical Augustin mean q⋆ corresponds to equilibrium prices in Fisher markets with constant elasticity of substitution (CES) utilities of common elasticity ρ = 1 − 1/α. The proposed algorithm can be interpreted as a tˆatonnement dynamic in this setting, and it is extended to inhomogeneous Fisher markets where buyers have different elasticities, achieving a faster convergence rate compared to existing tˆatonnement-type algorithms.

Comparison with Existing Work

The authors compare their iteration rule (17) with the iteration rule of Cole and Fleischer [2008], which is the only tˆatonnement-type algorithm comparable in Fisher markets with WGS CES utilities that both allows asynchronous price updates and guarantees linear convergence. They also compare their method with the best response dynamic proposed by Dvijotham et al. [2022], showing comparable iteration complexity when all elasticities ρj = ρ ∈ (0, 1/2) and better per-iteration time complexity.

Numerical Results

Numerical experiments show linear convergence rates for the optimization error and the iterate error when α > 0.5. The results suggest that the proposed algorithm seems to diverge for α ∈ (0.2, 0.4). For α ≤ 0.5, where no non-asymptotic guarantee exists, they replace Qˆ⋆ with the best iterate from entropic mirror descent with the Polyak step size.

Conclusion

The paper concludes that the proposed iteration rule functions as a fixed-point iteration for α ∈ (0, 1) ∪ (1, ∞). The algorithm provides a rigorous method for computing the Petz-Augustin mean and related quantities with non-asymptotic convergence guarantees.

--- Page 32 ---

References H. Araki. On an inequality of Lieb and Thirring. Lett. Math. Phys., 19:167–170, 1990 p. 14 S. Arimoto. Computation of random coding exponent functions IEEE Trans Inf Theory, 22(6):665–671 p. 5 U Augustin Noisy channels Habilitation thesis Univ Erlangen-Nurnberg, 1978 p. 2, p. 2, p. 4, p. 6, p. 44, p. 44 H H Bauschke J Bolte and M Teboulle A descent lemma beyond Lipschitz gradient continuity first-order methods revisited and applications Math Oper Res., 42(2):330–348, 2017 p. 21 X Bei J Garg and M Hoefer Ascending-price algorithms for unknown markets ACM Trans Algorithms, 15(3):1–33, 2019 p. 5, p. 6, p. 28 R Bhatia Matrix Analysis Springer, New York NY, 1997 p. 10 B Birnbaum N R Devanur and L Xiao Distributed algorithms via gradient descent for Fisher markets In Proc. 12th ACM Conf Electronic Commerce pages 127–136 New York NY, 2011 p. 4, p. 5 R Cole L Fleischer Fast-converging tatonnement algorithms for one-time and ongoing market problems In Proc. 40th Annu ACM Symp Theory of Computing pages 315–324, 2008 p. 5, p. 6, p. 28, p. 28, p. 28 R Cole L Fleischer and A Rastogi Discrete price updates yield fast convergence in ongoing markets with finite warehouses arXiv:1012.2124 p. 5 R Cole L Fleischer Fast-converging tatonnement algorithms for one-time and ongoing market problems In Proc. 40th Annu ACM Symp Theory of Computing pages 315–324, 2008 p. 5, p. 6, p. 28, p. 28 R Cole L Fleischer and Y Tao Dynamics of distributed updating in Fisher markets In Proc. 2018 ACM Conf Economics and Computation pages 351–368 New York NY, 2018 p. 5, p. 6, p. 6, p. 6, p. 44, p. 44 R Cole L Fleischer and N R Devanur Tatonnement beyond gross substitutes? gradient descent to the rescue Games Econ Behav., 123:295–326, 2020 p. 5, p. 6, p. 24, p. 28 G Koßmann and R Schwonnek Optimising the relative entropy under semi definite constraints a new tool for estimating key rates in QKD 2024 arXiv:2404.17016 p. 2 G Koßmann and M M Wilde Semidefinite optimization of the quantum relative entropy of channels 2024 arXiv:2410.16362 p. 2 H C Cheng B Nakibo˘glu A new characterization of Augustin information and mean In IEEE Int Symp Information Theory pages 2538–2543, 2024a p. 5, p. 5, p. 5 H C Cheng B Nakibo˘glu Augustin information in the vicinity of Augustin capacity-achieving input distributions In IEEE Inf Theory Workshop pages 567–572, 2024b p. 21, p. 39 H C Cheng L Gao and M H Hsieh Properties of noncommutative R´enyi and Augustin information Commun Math Phys., 390:501–544, 2022 p. 1, p. 17, p. 23 Y K Cheung R Cole and A Rastogi Tatonnement in ongoing markets of complementary goods In Proc.

Improvements for AI systems

Bold header: Non-Asymptotic Convergence Guarantee for Quantum Optimization

The improved AI system can solve complex quantum optimization problems, such as computing the Petz-Augustin mean Q⋆, using an iterative rule (11) that is guaranteed to converge linearly at a rate of O(1 − 1/αT) with respect to the Thompson metric for all order α ∈ (0, 1) ∪ (1, ∞).

Bold header: Efficient Computation of Quantum Capacity

The system can compute the Petz capacity Cα for orders α ∈ (1/2, 1) with a non-asymptotic convergence guarantee at a rate of O(log(n)/T), representing the first algorithm for this computation.

Bold header: Fast Equilibrium Price Determination in Inhomogeneous Markets

The system can determine equilibrium prices in inhomogeneous Fisher markets with WGS CES utilities and asynchronous price updates using the adapted iteration rule (17), achieving faster convergence than existing tˆatonnement-type algorithms, with a rate of OρˆT, where ˆρ = maxi ρˆi.