Technical Summary: Query Efficient Structured Matrix Learning

Problem Statement

The paper addresses the problem of learning a structured approximation to an unknown $n \times n$ matrix $A$ given access only to matrix-vector product (matvec) queries. The learner can issue queries of the form $x \to Ax$ and $x \to A^Tx$, where the query vectors $x$ can be chosen adaptively based on previous responses.

The goal is defined as Problem 1: Given a hypothesis class (matrix family) $\mathcal{F} \subset \mathbb{R}^{n \times n}$, find a matrix $\tilde{B} \in \mathcal{F}$ such that:
$$\|A - \tilde{B}\|_F \leq \gamma \cdot \inf_{B \in \mathcal{F}} \|A - B\|_F$$
for some approximation factor $\gamma \geq 1$, using the minimum number of matvec queries. This setting is "agnostic," meaning $A$ is not assumed to belong to $\mathcal{F}$ nor generated from a specific distribution within it.

Prior work has largely focused on specific structured families (e.g., rank-$k$, sparse, hierarchical matrices) and established query complexity bounds, often showing that $O(\log |\mathcal{F}|)$ queries suffice using standard sketching techniques or vector-matrix-vector ($x^T A y$) queries. The paper seeks to generalize this to arbitrary finite families and determine if the multidimensional nature of matvec outputs ($Ax$ is a vector, not a scalar) allows for improved query complexity compared to the vector-matrix-vector model.

Methodology

1. One-Sided Baseline (Iterative Refinement)

The authors first analyze a one-sided algorithm (using only $x \to Ax$) that serves as a baseline. This algorithm iteratively refines a candidate set $\mathcal{C} \subseteq \mathcal{F}$:

1. Draw a random sketching matrix $\Pi$ with $\ell = O(\log \log |\mathcal{F}|)$ columns.
2. Compute $Z = A\Pi$.
3. Eliminate all $B \in \mathcal{C}$ where $\|Z - B\Pi\|_F$ is significantly larger than the optimal error bound.
4. Repeat for $T = O(\log |\mathcal{F}| / \log \log |\mathcal{F}|)$ iterations.

This approach achieves $O(\log |\mathcal{F}|)$ query complexity, matching the bounds known for vector-matrix-vector queries.

2. Two-Sided Simulation (The Core Innovation)

The main contribution is an algorithm that utilizes both $A$ and $A^T$ to achieve a nearly quadratic improvement in query complexity, reducing the dependence on $|\mathcal{F}|$ from $O(\log |\mathcal{F}|)$ to $\tilde{O}(\sqrt{\log |\mathcal{F}|})$.

The algorithm simulates the one-sided iterative refinement but avoids computing $A\Pi$ directly in every step. Instead, it precomputes a left sketch $W = \Psi^T A$ using $\tilde{O}(\sqrt{\log |\mathcal{F}|})$ queries to $A^T$. In each iteration, it draws a right sketch $\Pi$ and attempts to determine if $\Pi$ is "productive" (i.e., eliminates a large fraction of bad candidates) without querying $A$ again.

The simulation relies on a dichotomy:

• Case 1 (Productive Sketch): If the random sketch $\Pi$ eliminates a large fraction of candidates, the algorithm issues the right queries $A\Pi$ to filter the set.
• Case 2 (Unproductive Sketch): If $\Pi$ would eliminate few candidates, the algorithm uses the precomputed left sketch $W$ to find a "representative" matrix $R \in \mathcal{C}$ such that $\|A\Pi - R\Pi\|_F$ is small. This is done by sampling candidates and checking $\|W\Pi - \Psi^T B \Pi\|_F$. If a representative is found, the algorithm can filter the candidate set using the proxy rule $\|R\Pi - B\Pi\|_F$ without ever computing $A\Pi$.

To handle the dependency between the candidate set and the left sketch $\Psi$, the algorithm draws $r = O(\log |\mathcal{F}|)$ right sketches per iteration and uses a union bound over all possible candidate sets that could arise, ensuring the left sketch remains accurate for all potential representatives.

3. Handling Unknown Optimal Error

The algorithms initially require an upper bound $M$ on the optimal error $\text{OPT} = \min_{B \in \mathcal{F}} \|A - B\|_F$. The authors provide a binary search procedure (Algorithm 4) that:

1. Computes a coarse initial bound $M_{init}$ using a simple sketching algorithm.
2. Refines this bound via binary search, using the main two-sided algorithm as a subroutine to test candidate bounds.
3. Achieves a $(3+\epsilon)$-approximation with high probability.

4. Extension to Infinite Families

Using covering number arguments, the results for finite families are extended to infinite families. For a family with covering number $\Gamma_\alpha$, the query complexity becomes $\tilde{O}(\sqrt{\log \Gamma_\alpha})$. Specifically, for linearly parameterized families of dimension $q$ (e.g., banded, Toeplitz, Hankel matrices), the covering number scales with $q$, leading to a query complexity of $\tilde{O}(\sqrt{q})$.

Key Results

Theoretical Bounds

• Theorem 1 (Finite Family Upper Bound): For any finite family $\mathcal{F}$, there exists an algorithm using $\tilde{O}(\sqrt{\log |\mathcal{F}|}/\epsilon^2)$ matvec queries to find $\tilde{B} \in \mathcal{F}$ satisfying $\|A - \tilde{B}\|_F \leq (3+\epsilon) \min_{B \in \mathcal{F}} \|A - B\|_F$ with high probability.
• Theorem 2 (Lower Bound): Any algorithm solving Problem 1 for general finite families with constant approximation factor $\gamma$ requires $\Omega(\sqrt{\log |\mathcal{F}|}/\log \gamma)$ matvec queries. This establishes that the $\sqrt{\log |\mathcal{F}|}$ dependence in the upper bound is tight up to log-log factors.
• Corollary 1 (Linear Families): For linearly parameterized families of dimension $q$, a near-optimal approximation can be learned with $\tilde{O}(\sqrt{q})$ queries. This improves upon the $O(q)$ bound achievable via one-sided sketching or vector-matrix-vector queries.

Specific Improvements

• Quadratic Improvement: The work demonstrates that matvec queries ($x \to Ax$) offer a nearly quadratic advantage over vector-matrix-vector queries ($x^T A y$) for structured matrix learning. While vector-matrix-vector queries require $O(\log |\mathcal{F}|)$ queries, matvec queries require only $\tilde{O}(\sqrt{\log |\mathcal{F}|})$.
• Butterfly Matrices: The lower bound implies that for constant-rank butterfly matrices (which have $\tilde{O}(n)$ parameters), $\tilde{O}(\sqrt{n})$ queries are necessary and sufficient, matching the best-known upper bounds up to logarithmic factors.

Significance and Claims

The paper claims to initiate the study of structured matrix approximation in greater generality, moving beyond specific matrix families to arbitrary finite and infinite families. Its primary significance lies in:

1. Establishing a General Theory: Providing a framework to characterize query complexity based on the size (or covering number) of the hypothesis class, analogous to VC dimension in supervised learning but adapted for the matvec model.
2. Demonstrating the Power of Multidimensional Output: Proving that the ability to query $A$ and $A^T$ and observe vector outputs allows for a fundamental reduction in query complexity compared to scalar-output models (vector-matrix-vector).
3. Tightness of Bounds: Showing that the $\tilde{O}(\sqrt{\log |\mathcal{F}|})$ bound is essentially optimal for finite families, closing the gap between upper and lower bounds for this general setting.

The authors note that their current results achieve a constant factor approximation ($\gamma = 3+\epsilon$) and that achieving a $(1+\epsilon)$ approximation with the same query complexity remains an open problem. They also highlight that their algorithm relies on adaptivity for the right-side queries, and the necessity of adaptivity for achieving the $\sqrt{\log |\mathcal{F}|}$ bound is not yet proven.