Randomized Matvec Lower Bounds for Simplex-Based Matrix Games
Abstract
We prove randomized matrix-vector query lower bounds for two normalized matrix-game geometries: a Euclidean unit ball against a probability simplex, with row norms at most one, and two probability simplices, with entries of absolute value at most one. Each query returns (Ax,A⊤ y) for arbitrary real vectors. The algorithm must return a feasible pair with full saddle-point gap at most ε, with probability at least 2/3 on every admissible matrix. For sufficiently small ε, the worst-case query complexities are Ω(ε−2/3/(log2(1/ε)loglog(1/ε))) for ball-simplex games and Ω(ε−2/3/(log7/3(1/ε)loglog(1/ε))) for simplex-simplex games. The hard instances have dimensions of order ε−2/3 and ε−2/3/log1/3(1/ε), respectively, and the bounds extend to larger dimensions. These lower bounds match the deterministic upper bounds of Karmarkar, O'Carroll, and Sidford up to logarithmic factors. The proof extracts a fresh Gaussian core after adaptive two-sided queries and uses uncertainty in its smallest singular value to establish linear-system solve hardness. Two reductions transfer this hardness to matrix games by converting a small full gap into a small residual, with an additional logarithmic normalization loss only for simplex-simplex games.
Related
- Sharp Matrix-Weighted Lower Bounds for Non-Degenerate Convolution Calderón--Zygmund Operators
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Nearest structured matrix having an eigenvalue with prescribed lower bounds of algebraic and geometric multiplicities
- Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
- Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
BibTeX
@misc{wu2026randomized,
title = {{Randomized Matvec Lower Bounds for Simplex-Based Matrix Games}},
author = {Wendao Wu and Cong Fang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02095},
eprint = {2610.02095},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02095},
}
RIS
TY - UNPB
TI - Randomized Matvec Lower Bounds for Simplex-Based Matrix Games
AU - Wendao Wu
AU - Cong Fang
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.02095
UR - https://arxiv.org/abs/2610.02095
AB - We prove randomized matrix-vector query lower bounds for two normalized matrix-game geometries: a Euclidean unit ball against a probability simplex, with row norms at most one, and two probability simplices, with entries of absolute value at most one. Each query returns (Ax,A^⊤ y) for arbitrary real vectors. The algorithm must return a feasible pair with full saddle-point gap at most ε, with probability at least 2/3 on every admissible matrix. For sufficiently small ε, the worst-case query complexities are Ω(ε^−2/3/(log^2(1/ε)loglog(1/ε))) for ball-simplex games and Ω(ε^−2/3/(log^7/3(1/ε)loglog(1/ε))) for simplex-simplex games. The hard instances have dimensions of order ε^−2/3 and ε^−2/3/log^1/3(1/ε), respectively, and the bounds extend to larger dimensions. These lower bounds match the deterministic upper bounds of Karmarkar, O'Carroll, and Sidford up to logarithmic factors. The proof extracts a fresh Gaussian core after adaptive two-sided queries and uses uncertainty in its smallest singular value to establish linear-system solve hardness. Two reductions transfer this hardness to matrix games by converting a small full gap into a small residual, with an additional logarithmic normalization loss only for simplex-simplex games.
ER -