PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomized Matvec Lower Bounds for Simplex-Based Matrix Games

Wendao Wu, Cong Fang

arXiv:2610.02095v1math.OCcs.DS

TL;DR

Randomized matrix-vector query complexity for normalized simplex-based games remained open despite deterministic lower bounds. The paper uses adaptive Gaussian uncertainty and reductions from linear-system solving to prove randomized lower bounds with the same 2/3 accuracy exponent in the two endpoint geometries.

  • Problem

    Whether randomization can improve the known deterministic lower-bound accuracy exponent for simplex-based games remained open.

    Source: §1 · p. 2

  • Method

    The proof extracts a fresh Gaussian core after adaptive two-sided queries, uses smallest-singular-value uncertainty for solve hardness, and reduces small full game gap to small linear-system residual.

    Source: §1 · p. 2

  • Results

    The randomized lower bounds retain the 2/3 accuracy exponent, with hard-core sizes Θ(ε^-2/3) for ball–simplex games and Θ(ε^-2/3 / log^1/3(1/ε)) for simplex–simplex games.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The bounds extend to larger dimensions, and the paper does not claim matching logarithms or a joint characterization of dimension and accuracy.

    Source: §1 · p. 2

    The dimension regime is essential: basis queries can reconstruct any matrix in at most min{m, n} queries, and the full joint dependence on (m, n, ε) remains unresolved.

    Source: §8 · p. 21

Abstract

from arXiv · show

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^\top y)$ for arbitrary real vectors. The algorithm must return a feasible pair with full saddle-point gap at most $\varepsilon$, with probability at least $2/3$ on every admissible matrix. For sufficiently small $\varepsilon$, the worst-case query complexities are $\Omega(\varepsilon^{-2/3}/(\log^2(1/\varepsilon)\log\log(1/\varepsilon)))$ for ball-simplex games and $\Omega(\varepsilon^{-2/3}/(\log^{7/3}(1/\varepsilon)\log\log(1/\varepsilon)))$ for simplex-simplex games. The hard instances have dimensions of order $\varepsilon^{-2/3}$ and $\varepsilon^{-2/3}/\log^{1/3}(1/\varepsilon)$, 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.

1 Introduction

The paper studies randomized two-sided matrix-vector query complexity for normalized simplex-based matrix games, addressing whether randomization can improve the known accuracy exponent. It establishes worst-case lower bounds through adaptive Gaussian uncertainty and reductions from linear-system solving to small game gaps.

1 Introduction

  • The game models use a Euclidean unit ball against a probability simplex with row norms at most one, or two probability simplices with entries bounded in absolute value by one.Each query returns (Ax, A⊤y); queries may be arbitrary real vectors and adaptive, and success must be at least 2/3 on every admissible matrix.Source: §1 · p. 2
  • Karmarkar, O’Carroll, and Sidford provide deterministic eO(ε^-2/3) query algorithms in both geometries, while randomized complexity remained open.Earlier deterministic bounds were eO(ε^-7/9) for ball–simplex and eO(ε^-8/9) for simplex–simplex games [2].Source: §1 · p. 2
  • Randomized algorithms need lower-bound query complexity with the same 2/3 accuracy exponent as the deterministic benchmark in the two endpoint geometries.The hard-core sizes are N = Θ(ε^-2/3) for ball–simplex games and N = Θ(ε^-2/3 / log^1/3(1/ε)) for simplex–simplex games; the bounds extend to larger dimensions, but matching logarithms are not claimed.Source: §1 · p. 2
  • A fresh Gaussian square core survives adaptive two-sided queries, and its uncertain smallest singular value yields a constant-factor estimation obstruction.Appending queries after the estimator returns creates an invertible pivot; a kernel restriction removes the Schur-complement shift while preserving a fresh Gaussian core.Source: §1 · p. 2
  • Two reductions turn small full game gap into small linear-system residual, with a √log N normalization cost only for simplex–simplex games.The ball–simplex reduction keeps a homogeneous coordinate positive for accurate outputs; the simplex–simplex reduction uses a signed orthogonal dictionary and random rotation.Source: §1 · p. 3

2 Related Work

Prior first-order methods set the classical inverse-accuracy benchmark, while later algorithms exploit game structure to improve matvec counts. Existing deterministic lower bounds left randomized complexity open; this paper addresses that gap using Gaussian posterior uncertainty and a full-gap-to-residual implication.

First-order methods and matrix-vector complexity

  • Nemirovski’s prox method and Nesterov’s smoothing give O(1/T) convergence frameworks, explaining the classical eO(ε^-1) benchmark under these normalizations.Karmarkar, O’Carroll, and Sidford improve matvec counts by exploiting game linear structure [2, 1].Source: §2 · p. 3
  • Karmarkar, O’Carroll, and Sidford combine a prox multi-point outer loop with maintained matrix approximations and amortized regularized-subproblem queries [1].This paper establishes the necessity of their accuracy exponent; it does not give a new game algorithm or improve their upper bounds.Source: §2 · p. 4

Deterministic and randomized game lower bounds

  • Kornowski and Shamir prove deterministic lower bounds for simplex-based games and identify randomized complexity as open [3].Their resisting constructions cover broader ℓp–simplex geometries, but the cited discussion notes that known nonlinear modifications for randomized lower bounds do not preserve bilinearity.Source: §2 · p. 4

Adaptive linear algebra and the Gaussian hard edge

  • For direct two-sided access to a nonsymmetric Gaussian matrix, the proof adds a square-pivot and low-rank-shift argument to the deferred-information approach [4].The finite-dimensional smallest-singular-value estimate [7] and Gaussian operator-norm tail supply distributional inputs, not adaptive query hardness by themselves.Source: §2 · p. 4

3 Models and Main Results

The section defines two-sided matrix-game query models and proves randomized lower bounds for both geometries. The hard-core bounds extend to larger dimensions by constructions that preserve query access and the full gap.

3.1 Two matrix-game models

  • The models count adaptive two-sided queries, require feasible outputs and success probability at least 2/3, and include simplex strategies with ∥A∥max ≤ 1.Randomized worst-case query complexity is the minimum query count needed to solve every admissible instance to full gap at most ε.Source: §3.1 · pp. 4–5

3.2 Main sequence theorem

  • For ℓ2–ℓ1 and sufficiently small ε, N = Θ(ε^-2/3); achieving full gap at most ε with probability at least 2/3 requires Ω(N/(log²(N+2) loglog(N+e^e))) two-sided matvec queries.The bound holds for m ≥ 4N and n ≥ 2N + 1.Source: §3.2 · p. 5
  • For ℓ1–ℓ1, the same query lower bound holds with N = Θ(ε^-2/3/log^(1/3)(1/ε)).The bound applies to every admissible instance at the theorem's target full gap.Source: §3.2 · p. 5
  • The hard-core instances extend to larger dimensions by duplicating rows and columns, with zero-column padding for ℓ2–ℓ1, while preserving query simulation and the full gap.For ℓ1–ℓ1, queries are simulated by aggregating coordinates and duplicating responses; for ℓ2–ℓ1, left queries are aggregated over duplicated rows.Source: §3.2 · p. 6

4 Probabilistic Preliminaries

The preliminaries supply Gaussian matrix estimates and Haar-direction bounds used in the proof. They include a Gaussian hard-edge estimate, an operator-norm tail, and projection bounds for random directions.

4 Probabilistic Preliminaries

  • The Gaussian hard-edge estimate [7] is specialized to power exponent one for a k × k real matrix with independent N(0, 1) entries.The section also identifies the elementary Haar projection estimate as proved within the paper.Source: §4 · p. 6
  • For every fixed δ > 0, a universal C(δ) bounds the operator norm of G ∼ Gin(N) with failure probability at most δ; the standard bound is cited to.Source: §4 · p. 6
  • A Haar-uniform random start has a nonzero chance of seeing any fixed direction, uniformly across dimensions.The proof reduces the claim by rotational invariance to a normalized Gaussian vector.Source: §4 · p. 6
  • A Haar-uniform unit vector has a one-dimensional projection tail bound, with the strict tail event empty for t > 1.The proof uses rotational invariance and a normalized Gaussian representation.Source: §4 · p. 7

5 Adaptive Gaussian Spectral Hardness

The section tracks the information left by adaptive two-sided Gaussian queries, then uses an augmented transcript to expose a fresh Gaussian core. Uniform separation of low and high smallest-singular-value events turns that core into an estimation lower bound.

5.1 Two-sided Gaussian oracle and filtration

  • After adaptive two-sided queries, the unobserved Gaussian block remains standard Gaussian conditional on the transcript.The query vectors may depend measurably on the internal seed and previous responses; the posterior tracks separate left and right query spaces.Source: §5.1 · pp. 7–8

5.2 Square-pivot augmentation and a fixed fresh Gaussian core

  • Post-output analysis-only queries create an invertible square pivot and leave a fresh Gaussian core of dimension at least N/2.The estimator’s output remains measurable with respect to its original transcript; for t ≤ N/8, the core dimension is ℓ = N − 4t ≥ N/2.Source: §5.2 · pp. 9–10

5.3 Uniform hard-edge separation

  • For every core dimension in [N/2, N], separated low and high smallest-singular-value events support a lower bound against estimators using at most N/8 adaptive two-sided queries.Theorem 5.4 states a universal-constant lower bound for estimating the smallest singular value after that query budget.Source: §5.3 · pp. 11–12

6 From Residual Solving to Inverse-Norm Estimation

The section reduces fast residual solving for symmetric indefinite systems to estimating an inverse norm. Verified amplification, refinement, and approximate inverse power combine to transfer the Gaussian estimation hardness into a worst-case matvec lower bound.

6 From Residual Solving to Inverse-Norm Estimation

  • A fast constant-residual solver for symmetric indefinite systems would enable smallest-singular-value estimation through verified refinement and approximate inverse power.The section’s reduction amplifies solver reliability, improves inverse applications, then estimates the inverse norm.Source: §6 · p. 12, §6.1 · p. 12, §6.3 · p. 13

6.1 Symmetric indefinite systems

  • The symmetric indefinite systems considered have spectra in [−κ, −1] ∪ [1, κ], and the constant-residual solver is defined by its matvec access and residual guarantee.The solver takes H and a right-hand side r, and returns a vector x.Source: §6.1 · p. 12

6.2 Verified amplification and iterative refinement

  • Independent solver repetitions with exact residual checks amplify success, while iterative refinement repeatedly corrects the residual to obtain an accurate inverse application.The amplification uses one extra matvec per candidate and selects the candidate with minimum verified residual.Source: §6.2 · p. 13

6.3 Approximate inverse power

  • Approximate inverse power uses multiple independent Haar starts and repeated approximate inverse applications to estimate the inverse norm.The guarantee applies when the inverse applications succeed and at least one start has sufficient projection onto a top absolute-eigenvalue eigenvector.Source: §6.3 · p. 13

6.4 Linear-dimensional randomized solve lower bound

  • Theorem 6.5 establishes a worst-case ordinary-matvec lower bound for randomized indefinite solving by contradicting the adaptive Gaussian estimation bound.The reduction simulates Gaussian queries using a symmetric dilation, with amplification and refinement keeping the query count below the Gaussian threshold under a sufficiently small assumed solver bound.Source: §6.4 · pp. 14–16

7 From Linear Systems to Matrix Games

The section embeds symmetric linear-system solving into both matrix-game geometries, so that a small full gap yields a constant-residual solution. The ball-simplex embedding is direct, while the simplex-simplex embedding uses randomized dictionaries and incurs a logarithmic normalization cost.

7.1 A direct ℓ2–ℓ1 embedding

  • The ball-simplex embedding represents the solution homogeneously, keeps every payoff-matrix row norm below one, and turns a small full gap into a constant-residual solution.Each two-sided game query is simulated with two ordinary matvecs, yielding 2T ≥ c N log²(N + 2) log log(N + ee).Source: §7 · p. 16, §7.1 · pp. 16–18

7.2 A bounded ℓ1–ℓ1 embedding

  • The simplex-simplex embedding uses a signed dictionary for ball solutions and a randomized testing basis to satisfy entrywise payoff bounds, at logarithmic normalization cost.The full game gap controls the residual, and each two-sided game query is simulated with two ordinary matvecs; the derived bound is 2T ≥ c N log²(N + 2) log log(N + ee).Source: §7.2 · pp. 18–20
  • The resulting lower bounds extend to larger dimensions within each geometry.The text also states that log N = Θ(log(1/ε)) for the displayed accuracy sequences.Source: §7.2 · p. 21

8 Scope and Remaining Questions

The lower bounds are dimension-specific and information-theoretic: the oracle model allows unlimited exact arithmetic, while the proof charges matvec queries. Reduction costs leave logarithmic gaps, and sharper reductions are needed to close them.

8 Scope and Remaining Questions

  • The simplex–simplex reduction uses Haar rotation to transfer a solver that succeeds on every admissible game to a source solver for every promised linear system.This averaging argument does not construct a universal Yao distribution over games.Source: §8 · p. 21
  • Any m × n matrix can be reconstructed in at most min{m, n} two-sided basis queries, so the bounds do not hold uniformly in fixed small dimensions.The constructions identify hard sizes and extend to larger dimensions; the full joint dependence on (m, n, ε) remains undetermined.Source: §8 · p. 21
  • O(log N) inverse-power steps and O(log N) refinement stages, plus O(log log N) confidence amplification, account for the source denominator log^2 N log log N.The signed dictionary adds a √log N accuracy loss and the additional log^(1/3)(1/ε) factor in the simplex–simplex bound; closing the logarithmic gaps requires sharper reductions.Source: §8 · p. 21
  • The bounds concern information from matvecs, not runtime, memory, communication, or parallel depth, because the oracle model permits unlimited exact arithmetic.The adaptive core argument remains the central unresolved verification task; the probabilistic input estimates are established results with cited sources.Source: §8 · p. 21
Loading 2610.02095v1…