Pith. sign in

REVIEW 2 major objections 4 minor 119 references

Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper gives a matrix learning-from-expert-advice algorithm whose regret is O(sqrt(T S(X||d^{-1}I_d))) for every comparator X, at the same time and memory cost as the standard matrix multiplicative weight update.

desk verdict Novel technique, but the central reduction is broken by a normalization mismatch; likely fixable, but not publishable as is. read the letter →

arxiv 2509.08911 v1 pith:X54CEM5B submitted 2025-09-10 cs.LG cs.AIcs.DSquant-phstat.ML

Weiyuan Gong , Tongyang Li , Xinzhao Wang , Zhiyu Zhang This is my paper · ORCID
classification cs.LGcs.AIcs.DSquant-phstat.ML
keywords matrixmultiplicativeweightupdateinstance-optimalregretpotentialmethodone-sidedJensen'straceinequalityLaplacetransformquantumrelativeentropyonlinelearningofstatesparameter-free
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper targets the matrix analogue of the classic "learning from expert advice" problem, played on the spectraplex of unit-trace positive semidefinite matrices. The standard matrix multiplicative weight update (MMWU) achieves worst-case optimal regret O(sqrt(T log d)), independent of the comparator X. This paper constructs an algorithm whose regret is instead O(sqrt(T S(X||d^{-1}I_d))), where S(·||·) is quantum relative entropy, so comparators closer to the maximally mixed state are learned faster. The improvement is "free" in that time and memory complexity match MMWU, and the paper proves a matching regret lower bound up to constants. The technique extends potential-based parameter-free online learning to noncommuting matrices through a new one-sided Jensen trace inequality.

What carries the argument

The load-bearing device is a one-sided Jensen trace inequality: for a function Phi whose second derivative is a two-sided Laplace transform of a nonnegative function, Tr[Phi(S-G)] <= Tr[((epsilon I-G)/2epsilon)Phi(S+epsilon I) + ((epsilon I+G)/2epsilon)Phi(S-epsilon I)] for Hermitian S,G with ||G||_op <= epsilon. The standard two-sided Jensen trace inequality does not imply this; |x| is a counterexample. The paper proves the erfi potential satisfies the condition because its second derivative is the exp-square potential, and that potential is the Gaussian Laplace transform of a nonnegative density. The Fenchel conjugate of the erfi potential then converts the potential bound into the relativ

What would settle it

Search the 2x2 Hermitian space for S and G with ||G||_op <= 2l and fixed t such that Tr[Phi_erfi_t(S-G)] exceeds Tr[((2lI-G)/4l)Phi_erfi_t(S+2lI) + ((2lI+G)/4l)Phi_erfi_t(S-2lI)]. The paper's Theorem 14 guarantees no such pair exists; any concrete violation is a direct computational refutation of the main regret bound.

Watch

Extended reading notes

Core claim

The central result (Theorem 23) is that a potential-based algorithm, using the imaginary-error-function potential and a reduction from the spectraplex to all Hermitian matrices, achieves regret at most l sqrt(T)[sqrt(8 S(X||d^{-1}I_d)) + 6 + 2 sqrt(2)] for every T>=1 and every unit-trace PSD comparator X, where l bounds the operator norm of each loss matrix. Since S(X||d^{-1}I_d) <= log d, this is never worse than the minimax-optimal O(sqrt(T log d)) bound and improves when X is close to the maximally mixed state. The paper also gives a matching regret lower bound up to constants, a memory lower bound of Omega(d^2) for sublinear regret, and shows that the algorithm's time and memory complexi

Load-bearing premise

The regret bound rests on the one-sided Jensen trace inequality holding for the erfi potential; the paper verifies it through a sufficient condition (the potential's second derivative is a nonnegative Laplace transform) but does not prove necessity, and the inequality fails for some convex functions such as |x|.

Editorial extensions

If this is right

  • For comparators with S(X||d^{-1}I_d)=O(1), regret becomes O(sqrt(T)) instead of O(sqrt(T log d)), a saving that can be exponential in auxiliary parameters when d is large, as in quantum information.
  • The algorithm is parameter-free: no learning rate eta needs to be tuned, unlike the standard MMWU bound which would require oracle knowledge of the comparator to reach the same guarantee.
  • Applied to online convex optimization with Lipschitz losses, the algorithm gives relative-entropy-dependent regret for online quantum state learning, including improved rates for depolarized states, random product states, subsystems of Haar random states, and Gibbs states.
  • Nonlinear predictions such as purity/quantum virtual cooling and Renyi-2 correlation inherit the same relative-entropy regret bound.
  • The Omega(d^2) memory lower bound for sublinear regret means the algorithm's d^2 memory cost is optimal among all matrix LEA algorithms.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: if the conjecture that the one-sided inequality holds for all even-degree monomials is true, the Laplace-transform sufficient condition is not necessary, and many more potentials such as exp(x^2) would become admissible, likely simplifying parameter-free matrix algorithms and connecting them to disentanglement inequalities.
  • Editorial inference: the Gaussian-ensemble interpretation suggests a testable design principle: replace the Gaussian prior over learning rates by other priors to obtain different comparator-dependent regret tradeoffs, a direction the paper leaves open.
  • Editorial inference: the packing-based memory lower bound should transfer to constrained quantum state classes, such as rank-r states or bounded-gate states, giving memory-regret tradeoffs in those settings beyond the two examples the paper lists.
  • Editorial inference: because noise and randomness reduce quantum relative entropy, the same algorithm likely gives instance-dependent benefits for online learning of quantum processes under depolarizing or average-case noise, not only states.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes a potential-based algorithm for matrix LEA on the spectraplex, claiming an instance-optimal regret bound O(sqrt(T S(X || d^{-1} I_d))) while retaining the computational complexity of MMWU. The main technical novelty is a one-sided Jensen trace inequality, proved under a Laplace-transform condition on the potential's second derivative, and applied to the erfi potential from the vector parameter-free online learning literature. The paper also gives a regret lower bound, a memory lower bound, and applications to online learning of noisy, random, and Gibbs quantum states, as well as nonlinear quantum properties.

Significance. If the main theorem were established, this would be a significant contribution: it would give the first comparator-adaptive matrix LEA algorithm with the same per-iteration cost as MMWU, introduce a useful new matrix trace inequality, and yield a suite of improved guarantees for quantum state learning. The paper is also unusually careful in several places: Theorem 14 and the master regret bound Theorem 20 are clean and self-contained, and the paper explicitly identifies the nontriviality of the one-sided Jensen inequality with a counterexample. However, the claimed reduction behind the main theorem is not proved for the algorithm as stated; this is a load-bearing issue that must be fixed before the central claim can be accepted.

major comments (2)
  1. [§4 (Algorithm 1) and Appendix B.1 (Lemma 19)] The reduction lemma is not proved for the algorithm as published. Algorithm 1 defines U_t with trace normalization (denominator |Σ_i min{0,λ_i}|), while the proof of Lemma 19 in Appendix B.1 uses U_t = (\tilde X_t - X_t^+)/||\tilde X_t - X_t^+||_F. The reader's 3×3 example is valid: with \tilde X_t = diag(-1,-2,3) and G_t = diag(1,1,-1), one gets X_t = diag(0,0,1), \bar G_t = diag(2,2,0), U_t = diag(-1/3,-2/3,0), and \tilde G_t = diag(4/3,2/3,0). For X = diag(1/3,1/3,1/3), Lemma 19 would require -4/3 ≤ -10/3, which is false. Thus Theorem 23's bound, which relies on Lemma 19 to lift the unconstrained regret to the spectraplex, is not established for the algorithm as stated. The natural fix is to normalize U_t by the Frobenius norm and then reprove Lemma 19; the authors should state and verify this explicitly.
  2. [Appendix B.1, Lemma 19, first condition] The proof of the first condition asserts that \|\tilde G_t\|_{op} ≤ \|\bar G_t\|_{op} because \tilde G_t is either \bar G_t or its projection to a subspace. This is not justified: the projection is in the Frobenius inner product, so it gives a Frobenius-norm bound, not an operator-norm bound. The bound \|\tilde G_t\|_{op} ≤ 2\|G_t\|_{op} is load-bearing, since the unconstrained algorithm (Algorithm 2) is run with ε = 2l. This step needs a genuine argument, especially after renormalizing U_t by the Frobenius norm, where one only has \|U_t\|_F = 1 and \|U_t\|_{op} ≤ 1.
minor comments (4)
  1. [§5.2, proof of Theorem 27] The union bound appears to be misstated: the text says 'with probability at least 1 − 2^m |P| ≥ 0.9', but the correct expression is 1 − 2^m / |P| ≥ 0.9. As written, 2^m |P| is enormous and gives a meaningless probability.
  2. [§4, Algorithm 1] The denominator |Σ_i min{0,λ_i}| should be identified as the trace norm of the negative part; the absolute-value-of-scalar notation is ambiguous and contributes to the normalization confusion.
  3. [Theorem 20] The statement contains the typo 'for all T∈≥ 2'; it should read 'for all T ≥ 2'.
  4. [§4.2, around Eq. (20)] The erfi potential is attributed to Ref. [53], but its first-condition verification is attributed to Ref. [52, Lemma 3.10]. A one-line clarification of the relation between these references would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the matrix LEA regret bound is derived from a new trace inequality and independently published scalar potential analysis.

full rationale

The paper's central claim (Theorem 23) is not an input renamed as an output. The potential-method master theorem (Theorem 20) derives a regret bound from two conditions: a scalar evanescent condition (17) and the one-sided Jensen trace inequality (18). The scalar condition and the Fenchel conjugate for the erfi potential are imported from prior published work ([52, 53, 114]); although [114] shares a coauthor, those are external theorems with scalar assumptions that do not include the matrix LEA result, so they are independent support rather than circular input. The matrix-specific content — Theorem 14's Laplace-transform sufficient condition, Lemma 21's Gaussian representation, and the reduction in Lemma 19 — is proved in the paper from Golden-Thompson, Fubini, and elementary trace identities; it does not assume the regret bound. The final bound then follows by summing and convex duality, with no step where the predicted quantity is defined in terms of itself or fitted to the comparator. I note for completeness an internal normalization mismatch in the proof of Lemma 19 (Algorithm 1 uses trace-normalized U_t while the proof substitutes a Frobenius-normalized version); this is a correctness/rigor concern, not a circularity, and does not change the circularity score.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central theorem relies on standard matrix analysis and on two external results for the erfi potential (propagation inequality and Fenchel conjugate). The quantum applications add standard quantum-information facts (strong data processing inequality, Page formula, random matrix bounds). No fitted parameters or invented entities appear.

assumptions (7)
  • standard math Golden-Thompson inequality: Tr[exp(A+B)] <= Tr[exp A exp B] for Hermitian A,B.
    Used in Lemma 13 to establish the one-sided Jensen inequality for exponential functions.
  • standard math von Neumann trace inequality: for Hermitian A,B with sorted eigenvalues, Tr[AB] <= sum lambda_i lambda'_i.
    Used in Theorem 20 to convert a matrix supremum into a sum of scalar Fenchel conjugates.
  • standard math The erfi and exp-square potentials satisfy the one-dimensional propagation inequality 1/2[Phi_{t+1}(s+eps)+Phi_{t+1}(s-eps)] <= Phi_t(s).
    Taken from Ref. [52, Lemma 3.10] and [114, Lemma B.3]; required by Theorem 20.
  • standard math Fenchel conjugate bound for the erfi potential: Phi_T^{erfi,*}(lambda) <= eps sqrt(T)[d^{-1} + sqrt(2 lambda)(sqrt(log(1+lambda/(sqrt(2) d^{-1}))) + 1)].
    Quoted from Ref. [114, Theorem 4]; it converts the potential bound into the final regret expression.
  • domain assumption Strong data processing inequality for depolarizing channels: S(Phi(rho)||I/d) <= (1-gamma)^2 S(rho||I/d) per layer of local depolarizing noise with rate gamma.
    Used in Corollary 29 to bound the regret for noisy quantum circuits; cited to Refs. [56,93].
  • domain assumption Page formula: a d-dimensional subsystem of a Haar random state of dimension d' has average von Neumann entropy log d - O(d/d') for d << d'.
    Used in Corollary 30 for random states; standard quantum information result.
  • domain assumption Random Hamiltonian norm bounds: ||H_gue|| <= 3 and ||H_RSPS|| <= 3 with probability 1-exp(-Theta(n)).
    Used in Corollary 33 to bound relative entropy of Gibbs states; cited to Refs. [31,28].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications." pith.science (2026). https://pith.science/paper/X54CEM5B

@misc{pith2026250908911,
  author       = {Pith},
  title        = {Pith review of: Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X54CEM5B}},
  note         = {Machine review of arXiv:2509.08911}
}
abstract

The Matrix Multiplicative Weight Update (MMWU) is a seminal online learning algorithm with numerous applications. Applied to the matrix version of the Learning from Expert Advice (LEA) problem on the $d$-dimensional spectraplex, it is well known that MMWU achieves the minimax-optimal regret bound of $O(\sqrt{T\log d})$, where $T$ is the time horizon. In this paper, we present an improved algorithm achieving the instance-optimal regret bound of $O(\sqrt{T\cdot S(X||d^{-1}I_d)})$, where $X$ is the comparator in the regret, $I_d$ is the identity matrix, and $S(\cdot||\cdot)$ denotes the quantum relative entropy. Furthermore, our algorithm has the same computational complexity as MMWU, indicating that the improvement in the regret bound is ``free''. Technically, we first develop a general potential-based framework for matrix LEA, with MMWU being its special case induced by the standard exponential potential. Then, the crux of our analysis is a new ``one-sided'' Jensen's trace inequality built on a Laplace transform technique, which allows the application of general potential functions beyond exponential to matrix LEA. Our algorithm is finally induced by an optimal potential function from the vector LEA problem, based on the imaginary error function. Complementing the above, we provide a memory lower bound for matrix LEA, and explore the applications of our algorithm in quantum learning theory. We show that it outperforms the state of the art for learning quantum states corrupted by depolarization noise, random quantum states, and Gibbs states. In addition, applying our algorithm to linearized convex losses enables predicting nonlinear quantum properties, such as purity, quantum virtual cooling, and R\'{e}nyi-$2$ correlation.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

119 extracted references · 12 linked inside Pith

  1. [1]

    Shadow tomography of quantum states

    Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 325--338, 2018

    2018

  2. [2]

    Online learning of quantum states

    Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. Online learning of quantum states. Advances in Neural Information Processing Systems , 31, 2018

    2018

  3. [3]

    Rothblum

    Scott Aaronson and Guy N. Rothblum. Gentle measurement of quantum states and differential privacy. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 322--333, 2019

    2019

  4. [4]

    A polynomial-time classical algorithm for noisy random circuit sampling

    Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 945--957, 2023

    2023

  5. [5]

    Some bounds for expected values of order statistics

    Mir M Ali and Lai K Chan. Some bounds for expected values of order statistics. The Annals of Mathematical Statistics , pages 1055--1057, 1965

    1965

  6. [6]

    Follow the compressed leader: Faster online learning of eigenvectors and faster MMWU

    Zeyuan Allen-Zhu and Yuanzhi Li. Follow the compressed leader: Faster online learning of eigenvectors and faster MMWU . In International Conference on Machine Learning , pages 116--125. PMLR, 2017

    2017

  7. [7]

    Spectral sparsification and regret minimization beyond matrix multiplicative updates

    Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings of the 47th Annual ACM SIGACT Symposium on Theory of Computing , pages 237--245, 2015

    2015

  8. [8]

    Anderson, Alice Guionnet, and Ofer Zeitouni

    Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction to random matrices . Cambridge University Press, 2010

    2010

Show all 119 references
  1. [9]

    A survey on the complexity of learning quantum states

    Anurag Anshu and Srinivasan Arunachalam. A survey on the complexity of learning quantum states. Nature Reviews Physics , 6(1):59--69, 2024

    2024

  2. [10]

    A combinatorial, primal-dual approach to semidefinite programs

    Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings of the 39th Annual ACM SIGACT Symposium on Theory of Computing , pages 227--236, 2007

    2007

  3. [11]

    Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G

    Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks F...

    2019

  4. [12]

    Improved quantum data analysis

    Costin B a descu and Ryan O'Donnell. Improved quantum data analysis. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 1398--1411, 2021

    2021

  5. [13]

    Bandeira, March T

    Afonso S. Bandeira, March T. Boedihardjo, and Ramon van Handel. Matrix concentration inequalities and free probability. Inventiones Mathematicae , 234(1):419--487, 2023

    2023

  6. [14]

    Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time

    Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, and Nikhil Srivastava. Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time. Foundations of Computational Mathematics , 23(6):1959--2047, 2023

    1959

  7. [15]

    Online learning of a panoply of quantum objects

    Akshay Bansal, Ian George, Soumik Ghosh, Jamie Sikora, and Alice Zheng. Online learning of a panoply of quantum objects. Quantum Machine Intelligence , 7(2):1--22, 2025

    2025

  8. [16]

    Boyd and Lieven Vandenberghe

    Stephen P. Boyd and Lieven Vandenberghe. Convex optimization . Cambridge University Press, 2004

    2004

  9. [17]

    Universality and sharp matrix concentration inequalities

    Tatiana Brailovskaya and Ramon van Handel. Universality and sharp matrix concentration inequalities. Geometric and Functional Analysis , 34(6):1734--1838, 2024

    2024

  10. [18]

    Brand \ a o, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M Svore, and Xiaodi Wu

    Fernando G.S.L. Brand \ a o, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M Svore, and Xiaodi Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In Proceedings of the 46th International Colloquium on Automata, Languages, and Progr...

    2019

  11. [19]

    Brandao, Richard Kueng, and Daniel Stilck Fran c a

    Fernando G.S.L. Brandao, Richard Kueng, and Daniel Stilck Fran c a. Faster quantum and classical SDP approximations for quadratic binary optimization. Quantum , 6:625, 2022

    2022

  12. [20]

    Fernando GSL Brandao and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science , pages 415--426. IEEE, 2017

    2017

  13. [21]

    Lanyon, Peter Zoller, Rainer Blatt, and Christian F

    Tiff Brydges, Andreas Elben, Petar Jurcevic, Beno \^ t Vermersch, Christine Maier, Ben P. Lanyon, Peter Zoller, Rainer Blatt, and Christian F. Roos. Probing R \'e nyi entanglement entropy via randomized measurements. Science , 364(6437):260--263, 2019

    2019

  14. [22]

    Benjamin, Suguru Endo, William J

    Zhenyu Cai, Ryan Babbush, Simon C. Benjamin, Suguru Endo, William J. Huggins, Ying Li, Jarrod R. McClean, and Thomas E. O’Brien. Quantum error mitigation. Reviews of Modern Physics , 95(4):045005, 2023

    2023

  15. [23]

    Duchi, Sidford Aaron, and Tian Kevin

    Yair Carmon, John C. Duchi, Sidford Aaron, and Tian Kevin. A rank-1 sketch for matrix multiplicative weights. In Conference on Learning Theory , pages 589--623. PMLR, 2019

    2019

  16. [24]

    Helmbold, Robert E

    Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM , 44(3):427--485, 1997

    1997

  17. [25]

    Prediction, learning, and games

    Nicolo Cesa-Bianchi and G \'a bor Lugosi. Prediction, learning, and games . Cambridge University Press, 2006

    2006

  18. [26]

    A parameter-free hedging algorithm

    Kamalika Chaudhuri, Yoav Freund, and Daniel J Hsu. A parameter-free hedging algorithm. Advances in Neural Information Processing Systems , 22, 2009

    2009

  19. [27]

    Quantum G ibbs Sampling

    Chi-Fang Chen. Quantum G ibbs Sampling . PhD thesis, California Institute of Technology, 2025

    2025

  20. [28]

    Dalzell, Mario Berta, Fernando GSL Brand \ a o, and Joel A

    Chi-Fang Chen, Alexander M. Dalzell, Mario Berta, Fernando GSL Brand \ a o, and Joel A. Tropp. Sparse random H amiltonians are quantumly easy. Physical Review X , 14(1):011014, 2024

    2024

  21. [29]

    Impossible tuning made possible: A new expert algorithm and its applications

    Liyu Chen, Haipeng Luo, and Chen-Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory , pages 1216--1259. PMLR, 2021

    2021

  22. [30]

    Efficient P auli channel estimation with logarithmic quantum memory

    Sitan Chen and Weiyuan Gong. Efficient P auli channel estimation with logarithmic quantum memory. PRX Quantum , 6(2):020323, 2025

    2025

  23. [31]

    Information-computation gaps in quantum learning via low-degree likelihood

    Sitan Chen, Weiyuan Gong, Jonas Haferkamp, and Yihui Quek. Information-computation gaps in quantum learning via low-degree likelihood. arXiv:2505.22743 , 2025

    2025 arXiv

  24. [32]

    Adaptive online learning of quantum states

    Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang, and Rui Yang. Adaptive online learning of quantum states. Quantum , 8:1471, 2024

    2024

  25. [33]

    More practical and adaptive algorithms for online quantum state learning

    Yifang Chen and Xin Wang. More practical and adaptive algorithms for online quantum state learning. arXiv:2006.01013 , 2020

    2006 arXiv

  26. [34]

    Prediction with advice of unknown number of experts

    Alexey Chernov and Vladimir Vovk. Prediction with advice of unknown number of experts. In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence , pages 117--125, 2010

    2010

  27. [35]

    Quantum algorithms for gibbs sampling and hitting-time estimation

    Anirban Narayan Chowdhury and Rolando D Somma. Quantum algorithms for gibbs sampling and hitting-time estimation. Quantum Information & Computation , 17(1-2):41--64, 2017

    2017

  28. [36]

    Eric Tai, Matthew Rispoli, Robert Schittko, Philipp M

    Jordan Cotler, Soonwon Choi, Alexander Lukin, Hrant Gharibyan, Tarun Grover, M. Eric Tai, Matthew Rispoli, Robert Schittko, Philipp M. Preiss, Adam M. Kaufman, Markus Greiner, Hannes Pichler, and Patrick Hayden. Quantum virtual cooling. Physical Review X , 9(3):031013, 2019

    2019

  29. [37]

    Fully unconstrained online learning

    Ashok Cutkosky and Zak Mhammedi. Fully unconstrained online learning. Advances in Neural Information Processing Systems , 37:10148--10201, 2024

    2024

  30. [38]

    Black-box reductions for parameter-free online learning in B anach spaces

    Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in B anach spaces. In Conference on Learning Theory , pages 1493--1529. PMLR, 2018

    2018

  31. [39]

    Order statistics

    Herbert A David and Haikady N Nagaraja. Order statistics . John Wiley & Sons, 2004

    2004

  32. [40]

    Quantum certification and benchmarking

    Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Quantum certification and benchmarking. Nature Reviews Physics , 2(7):382--390, 2020

    2020

  33. [41]

    Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Beno \^ t Vermersch, and Peter Zoller

    Andreas Elben, Steven T. Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Beno \^ t Vermersch, and Peter Zoller. The randomized measurement toolbox. Nature Reviews Physics , 5(1):9--24, 2023

    2023

  34. [42]

    Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan

    Dylan J. Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan. Parameter-free online learning via model selection. Advances in Neural Information Processing Systems , 30, 2017

    2017

  35. [43]

    Foster, Alexander Rakhlin, and Karthik Sridharan

    Dylan J. Foster, Alexander Rakhlin, and Karthik Sridharan. Adaptive online learning. Advances in Neural Information Processing Systems , 28, 2015

    2015

  36. [44]

    Online learning: Sufficient statistics and the B urkholder method

    Dylan J Foster, Alexander Rakhlin, and Karthik Sridharan. Online learning: Sufficient statistics and the B urkholder method. In Conference On Learning Theory , pages 3028--3064. PMLR, 2018

    2018

  37. [45]

    Advances in quantum metrology

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Advances in quantum metrology. Nature Photonics , 5(4):222--229, 2011

    2011

  38. [46]

    Lower bounds for the H elmholtz function

    Sidney Golden. Lower bounds for the H elmholtz function. Physical Review , 137(4B):B1127, 1965

    1965

  39. [47]

    Learning distributions over quantum measurement outcomes

    Weiyuan Gong and Scott Aaronson. Learning distributions over quantum measurement outcomes. In International Conference on Machine Learning , pages 11598--11613. PMLR, 2023

    2023

  40. [48]

    On the sample complexity of purity and inner product estimation

    Weiyuan Gong, Jonas Haferkamp, Qi Ye, and Zhihan Zhang. On the sample complexity of purity and inner product estimation. arXiv:2410.12712 , 2024

    2024 arXiv

  41. [49]

    Robert D. Gordon. Values of M ills' ratio of area to bounding ordinate and of the normal probability integral for large values of the argument. The Annals of Mathematical Statistics , 12(3):364--366, 1941

    1941

  42. [50]

    Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu

    Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing , pages 913--925, 2016

    2016

  43. [51]

    Pedersen

    Frank Hansen and Gert K. Pedersen. Jensen's operator inequality. Bulletin of the London Mathematical Society , 35(4):553--564, 2003

    2003

  44. [52]

    Optimal anytime regret with two experts

    Nicholas JA Harvey, Christopher Liaw, Edwin Perkins, and Sikander Randhawa. Optimal anytime regret with two experts. Mathematical Statistics and Learning , 6(1):87--142, 2023

    2023

  45. [53]

    Optimal anytime regret for two experts

    Nicholas JA Harvey, Christopher Liaw, Edwin A Perkins, and Sikander Randhawa. Optimal anytime regret for two experts. In Proceedings of the 61st Annual Symposium on Foundations of Computer Science , pages 1404--1415. IEEE, 2020

    2020

  46. [54]

    Continuous prediction with experts' advice

    Nicholas JA Harvey, Christopher Liaw, and Victor S Portella. Continuous prediction with experts' advice. Journal of Machine Learning Research , 25(228):1--32, 2024

    2024

  47. [55]

    Introduction to online convex optimization

    Elad Hazan. Introduction to online convex optimization. arXiv:1909.05207v3 , 2023

    1909 arXiv

  48. [56]

    On contraction coefficients, partial orders and approximation of capacities for quantum channels

    Christoph Hirche, Cambyse Rouz \' e , and Daniel Stilck Fran c a. On contraction coefficients, partial orders and approximation of capacities for quantum channels. Quantum , 6:862, 2022. https://doi.org/10.22331/q-2022-11-28-862 doi:10.22331/q-2022-11-28-862

    2022 doi

  49. [57]

    Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R. McClean. Quantum advantage in learning from experiments. Science , 376(6598):1182--1186, 2022

    2022

  50. [58]

    Predicting many properties of a quantum system from very few measurements

    Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics , 16(10):1050--1057, 2020

    2020

  51. [59]

    Huggins, Sam McArdle, Thomas E

    William J. Huggins, Sam McArdle, Thomas E. O’Brien, Joonho Lee, Nicholas C. Rubin, Sergio Boixo, K. Birgitta Whaley, Ryan Babbush, and Jarrod R. McClean. Virtual distillation for quantum error mitigation. Physical Review X , 11(4):041036, 2021

    2021

  52. [60]

    Preiss, M

    Rajibul Islam, Ruichao Ma, Philipp M. Preiss, M. Eric Tai, Alexander Lukin, Matthew Rispoli, and Markus Greiner. Measuring entanglement entropy in a quantum many-body system. Nature , 528(7580):77--83, 2015

    2015

  53. [61]

    Pseudorandom quantum states

    Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Annual International Cryptology Conference , pages 126--152. Springer, 2018

    2018

  54. [62]

    Kastoryano and Fernando G.S.L

    Michael J. Kastoryano and Fernando G.S.L. Brandao. Quantum gibbs samplers: The commuting case. Communications in Mathematical Physics , 344(3):915--957, 2016

    2016

  55. [63]

    Eric Tai, Alexander Lukin, Matthew Rispoli, Robert Schittko, Philipp M

    Adam M Kaufman, M. Eric Tai, Alexander Lukin, Matthew Rispoli, Robert Schittko, Philipp M. Preiss, and Markus Greiner. Quantum thermalization through entanglement in an isolated many-body system. Science , 353(6301):794--800, 2016

    2016

  56. [64]

    Exponential error suppression for near-term quantum devices

    B \'a lint Koczor. Exponential error suppression for near-term quantum devices. Physical Review X , 11(3):031057, 2021

    2021

  57. [65]

    Koolen and Tim Van Erven

    Wouter M. Koolen and Tim Van Erven. Second-order quantile methods for experts and combinatorial games. In Conference on Learning Theory , pages 1155--1175. PMLR, 2015

    2015

  58. [66]

    Dima Kuzmin and Manfred K. Warmuth. Online kernel PCA with entropic matrix updates. In International Conference on Machine Learning , pages 465--472, 2007

    2007

  59. [67]

    Lecture 3: Golden-thompson and the frobenius inner product

    James R Lee. Lecture 3: Golden-thompson and the frobenius inner product. https://homes.cs.washington.edu/ jrl/teaching/cse599Isp21/notes/lecture3.pdf, 2021

    2021

  60. [68]

    Lessa, Ruochen Ma, Jian-Hao Zhang, Zhen Bi, Meng Cheng, and Chong Wang

    Leonardo A. Lessa, Ruochen Ma, Jian-Hao Zhang, Zhen Bi, Meng Cheng, and Chong Wang. Strong-to-weak spontaneous symmetry breaking in mixed quantum states. PRX Quantum , 6(1):010344, 2025

    2025

  61. [69]

    Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation , 108(2):212--261, 1994

    1994

  62. [70]

    Exponential separations between quantum learning with and without purification

    Zhenhuan Liu, Weiyuan Gong, Zhenyu Du, and Zhenyu Cai. Exponential separations between quantum learning with and without purification. arXiv:2410.17718 , 2024

    2024 arXiv

  63. [71]

    Quantum principal component analysis

    Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics , 10(9):631--633, 2014

    2014

  64. [72]

    Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states

    Josep Lumbreras, Erkka Haapasalo, and Marco Tomamichel. Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states. Quantum , 6:749, 2022

    2022

  65. [73]

    Schapire

    Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: Adanormalhedge. In Conference on Learning Theory , pages 1286--1304. PMLR, 2015

    2015

  66. [74]

    Minimax optimal algorithms for unconstrained linear optimization

    Brendan McMahan and Jacob Abernethy. Minimax optimal algorithms for unconstrained linear optimization. Advances in Neural Information Processing Systems , 26:2724--2732, 2013

    2013

  67. [75]

    Unconstrained online linear learning in H ilbert spaces: Minimax algorithms and normal approximations

    Brendan McMahan and Francesco Orabona. Unconstrained online linear learning in H ilbert spaces: Minimax algorithms and normal approximations. In Conference on Learning Theory , pages 1020--1039. PMLR, 2014

    2014

  68. [76]

    Introduction to H aar measure tools in quantum information: A beginner's tutorial

    Antonio Anna Mele. Introduction to H aar measure tools in quantum information: A beginner's tutorial. Quantum , 8:1340, 2024

    2024

  69. [77]

    Zakaria Mhammedi and Wouter M. Koolen. Lipschitz and comparator-norm adaptivity in online learning. In Conference on Learning Theory , pages 2858--2887. PMLR, 2020

    2020

  70. [78]

    A trace inequality of J ohn von N eumann

    Leon Mirsky. A trace inequality of J ohn von N eumann. Monatshefte f \"u r mathematik , 79(4):303--306, 1975

    1975

  71. [79]

    Quantum speedup of Monte Carlo methods

    Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 471(2181):20150301, 2015

    2015

  72. [80]

    Tan, Matthew J

    Mario Motta, Chong Sun, Adrian T.K. Tan, Matthew J. O’Rourke, Erika Ye, Austin J Minnich, Fernando G.S.L. Brandao, and Garnet Kin-Lic Chan. Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nature Physics , 16(2):205--210, 2020

    2020

  73. [81]

    Minimax optimal quantile and semi-adversarial regret via root-logarithmic regularizers

    Jeffrey Negrea, Blair Bilodeau, Nicol \`o Campolongo, Francesco Orabona, and Dan Roy. Minimax optimal quantile and semi-adversarial regret via root-logarithmic regularizers. Advances in Neural Information Processing Systems , 34:26237--26249, 2021

    2021

  74. [82]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information . Cambridge University Press , Cambridge , 2010. https://doi.org/10.1017/CBO9780511976667 doi:10.1017/CBO9780511976667

    2010 doi

  75. [83]

    Efficient quantum tomography

    Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing , pages 899--912, 2016

    2016

  76. [84]

    Dimension-free exponentiated gradient

    Francesco Orabona. Dimension-free exponentiated gradient. In Advances in Neural Information Processing Systems , pages 1806--1814, 2013

    2013

  77. [85]

    A modern introduction to online learning

    Francesco Orabona. A modern introduction to online learning. arXiv:1912.13213v7 , 2025

    1912 arXiv

  78. [86]

    Optimal non-asymptotic lower bound on the minimax regret of learning with expert advice

    Francesco Orabona and D \'a vid P \'a l. Optimal non-asymptotic lower bound on the minimax regret of learning with expert advice. arXiv:1511.02176 , 2015

    2015 arXiv

  79. [87]

    Coin betting and parameter-free online learning

    Francesco Orabona and D \'a vid P \'a l. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems , 29, 2016

    2016

  80. [88]

    Don N. Page. Average entropy of a subsystem. Physical Review Letters , 71(9):1291, 1993

    1993

  81. [89]

    Near optimal memory-regret tradeoff for online learning

    Binghui Peng and Aviad Rubinstein. Near optimal memory-regret tradeoff for online learning. In Proceedings of the 64th Annual Symposium on Foundations of Computer Science , pages 1171--1194. IEEE, 2023

    2023

  82. [90]

    Online prediction in sub-linear space

    Binghui Peng and Fred Zhang. Online prediction in sub-linear space. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1611--1634. SIAM, 2023

    2023

  83. [91]

    On a matrix trace inequality due to A ndo, H iai and O kubo

    Lucijan Plevnik. On a matrix trace inequality due to A ndo, H iai and O kubo. Indian Journal of Pure and Applied Mathematics , 47(3):491--500, 2016

    2016

  84. [92]

    Quantum computing in the NISQ era and beyond

    John Preskill. Quantum computing in the NISQ era and beyond. Quantum , 2:79, 2018

    2018

  85. [93]

    Exponentially tighter bounds on limitations of quantum error mitigation

    Yihui Quek, Daniel Stilck Fran c a, Sumeet Khatri, Johannes Jakob Meyer, and Jens Eisert. Exponentially tighter bounds on limitations of quantum error mitigation. Nature Physics , 20(10):1648--1658, 2024. https://arxiv.org/abs/2210.11505 arXiv:2210.11505

    2024 arXiv

  86. [94]

    Caro, Jens Eisert, and Sumeet Khatri

    Asad Raza, Matthias C. Caro, Jens Eisert, and Sumeet Khatri. Online learning of quantum processes. arXiv:2406.04250 , 2024

    2024 arXiv

  87. [95]

    Hermitian diagonalization in linear precision

    Rikhav Shah. Hermitian diagonalization in linear precision. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms , pages 5599--5615. SIAM, 2025

    2025

  88. [96]

    Shaw, Zhuo Chen, Joonhee Choi, Daniel K

    Adam L. Shaw, Zhuo Chen, Joonhee Choi, Daniel K. Mark, Pascal Scholl, Ran Finkelstein, Andreas Elben, Soonwon Choi, and Manuel Endres. Benchmarking highly entangled states on a 60-atom analogue quantum simulator. Nature , 628(8006):71--77, 2024

    2024

  89. [97]

    Deterministic complexity analysis of hermitian eigenproblems

    Aleksandros Sobczyk. Deterministic complexity analysis of hermitian eigenproblems. In 52nd International Colloquium on Automata, Languages, and Programming , pages 131--1, 2025

    2025

  90. [98]

    Woodruff, Ziyu Xu, and Samson Zhou

    Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou. Memory bounds for the experts problem. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1158--1171, 2022

    2022

  91. [99]

    No-regret algorithms for unconstrained online convex optimization

    Matthew Streeter and H Brendan McMahan. No-regret algorithms for unconstrained online convex optimization. In Advances in Neural Information Processing Systems , pages 2402--2410, 2012

    2012

  92. [100]

    Thompson

    Colin J. Thompson. Inequality with applications in statistical mechanics. Journal of Mathematical Physics , 6(11):1812--1813, 1965

    1965

  93. [101]

    Cs395t: Continuous algorithms, part vi matrix analysis and concentration

    Kevin Tian. Cs395t: Continuous algorithms, part vi matrix analysis and concentration. https://kjtian.github.io/notes/CS

  94. [102]

    Cs395t: Continuous algorithms, part viii matrix multiplicative weights

    Kevin Tian. Cs395t: Continuous algorithms, part viii matrix multiplicative weights. https://kjtian.github.io/notes/CS

  95. [103]

    Joel A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning , 8(1-2):1--230, 2015. https://arxiv.org/abs/1501.01571 arXiv:1501.01571

    2015 arXiv

  96. [104]

    Joel A. Tropp. Second-order matrix concentration inequalities. Applied and Computational Harmonic Analysis , 44(3):700--736, 2018. https://arxiv.org/abs/1305.0612 arXiv:1305.0612

    2018 arXiv

  97. [105]

    Matrix exponentiated gradient updates for on-line learning and B regman projection

    Koji Tsuda, Gunnar R \"a tsch, and Manfred K Warmuth. Matrix exponentiated gradient updates for on-line learning and B regman projection. Journal of Machine Learning Research , 6(Jun):995--1018, 2005

    2005

  98. [106]

    Quantum SDP -solvers: Better upper and lower bounds

    Joran Van Apeldoorn, Andr \'a s Gily \'e n, Sander Gribling, and Ronald de Wolf. Quantum SDP -solvers: Better upper and lower bounds. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science , pages 403--414. IEEE, 2017

    2017

  99. [107]

    Warmuth and Dima Kuzmin

    Manfred K. Warmuth and Dima Kuzmin. Online variance minimization. In International Conference on Computational Learning Theory , pages 514--528. Springer, 2006

    2006

  100. [108]

    Warmuth and Dima Kuzmin

    Manfred K. Warmuth and Dima Kuzmin. Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension. Journal of Machine Learning Research , 9(10):2287--2320, 2008

    2008

  101. [109]

    D.V. Widder. The Laplace Transform . Princeton University Press, 1946

    1946

  102. [110]

    Quantum deep learning

    Nathan Wiebe, Ashish Kapoor, and Krysta M Svore. Quantum deep learning. arXiv:1412.3489 , 2014

    2014 arXiv

  103. [111]

    Eugene P. Wigner. On the distribution of the roots of certain symmetric matrices. Annals of Mathematics , 67(2):325--327, 1958

    1958

  104. [112]

    Revisiting online quantum state learning

    Feidiao Yang, Jiaqing Jiang, Jialin Zhang, and Xiaoming Sun. Revisiting online quantum state learning. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 34, pages 6607--6614, 2020

    2020

  105. [113]

    Experimental quantum state measurement with classical shadows

    Ting Zhang, Jinzhao Sun, Xiao-Xu Fang, Xiao-Ming Zhang, Xiao Yuan, and He Lu. Experimental quantum state measurement with classical shadows. Physical Review Letters , 127(20):200501, 2021

    2021

  106. [114]

    PDE -based optimal strategy for unconstrained online learning

    Zhiyu Zhang, Ashok Cutkosky, and Ioannis Paschalidis. PDE -based optimal strategy for unconstrained online learning. In International Conference on Machine Learning , pages 26085--26115. PMLR, 2022

    2022

  107. [115]

    Optimal comparator adaptive online learning with switching cost

    Zhiyu Zhang, Ashok Cutkosky, and Yannis Paschalidis. Optimal comparator adaptive online learning with switching cost. Advances in Neural Information Processing Systems , 35:23936--23950, 2022

    2022

  108. [116]

    Paschalidis

    Zhiyu Zhang, Heng Yang, Ashok Cutkosky, and Ioannis C. Paschalidis. Improving adaptive online learning using refined discretization. In International Conference on Algorithmic Learning Theory , pages 1208--1233. PMLR, 2024

    2024

  109. [117]

    Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C. Caro. Learning quantum states and unitaries of bounded gate complexity. PRX Quantum , 5(4):040306, 2024

    2024

  110. [118]

    Quantum computational advantage using photons

    Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-...

    2020

  111. [119]

    Pushing the efficiency-regret pareto frontier for online learning of portfolios and quantum states

    Julian Zimmert, Naman Agarwal, and Satyen Kale. Pushing the efficiency-regret pareto frontier for online learning of portfolios and quantum states. In Conference on Learning Theory , pages 182--226. PMLR, 2022

    2022

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.