REVIEW 3 cited by
Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We prove non-asymptotic lower bounds on the expectation of the maximum of $d$ independent Gaussian variables and the expectation of the maximum of $d$ independent symmetric random walks. Both lower bounds recover the optimal leading constant in the limit. A simple application of the lower bound for random walks is an (asymptotically optimal) non-asymptotic lower bound on the minimax regret of online learning with expert advice.
Forward citations
Cited by 3 Pith papers
-
Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications
A new potential-based algorithm achieves instance-optimal O(sqrt(T·S(X||I/d))) regret for matrix LEA with the same complexity as MMWU, using a one-sided Jensen trace inequality.
-
Online Koml\'os converges to mean curvature flow
As T→∞ the online Komlós game value satisfies lim K_T(m,n)/√T = 1/√(2τ), with τ the extinction time of the unit cube under the associated curvature flow, and 1/√(2τ)=Θ(√log m) for n≥m−1.
-
Enhanced entanglement from quantum ergodicity
Ergodic quantum dynamics, via a non-demolition coupling, generates EPR states with lower purity and higher operator-transfer capacity than infinite-temperature scramblers, with a parametric advantage when initial stat...
Discussion (0). Continue with ORCID to comment.