We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix $\boldsymbol{\mathbf{A}}$ given access to matrix-vector product (matvec) queries of the form $\boldsymbol{\mathbf{x}} \mapsto \boldsymbol{\mathbf{A}}\boldsymbol{\mathbf{x}}$ and $\boldsymbol{\mathbf{x}} \mapsto \boldsymbol{\mathbf{A}}^\transpose \boldsymbol{\mathbf{x}}$. This problem is of central importance in scientific computing and machine learning, with applications to structured matrix compression, preconditioning, and as a theoretical model for operator learning. Prior work focuses on obtaining query complexity upper and lower bounds for learning specific structured matrix families that commonly arise in applications. We initiate the study of the problem in greater generality, aiming to understand the query complexity of learning approximations from general matrix families. Our main result focuses on finding a near-optimal approximation to $\boldsymbol{\mathbf{A}}$ from any \emph{finite-sized} family of matrices, $\mathcal{F}$. Standard results from matrix sketching show that $O(\log|\mathcal{F}|)$ matvec queries suffice in this setting. This bound can also be achieved, and is optimal, for vector-matrix-vector queries of the form $\boldsymbol{\mathbf{x}},\boldsymbol{\mathbf{y}}\mapsto \boldsymbol{\mathbf{x}}^\transpose\boldsymbol{\mathbf{A}}\boldsymbol{\mathbf{y}}$, which have been widely studied in work on rank-$1$ matrix sensing. Surprisingly, we show that it is possible to obtain a nearly quadratic improvement in matvec complexity, to $\tilde{O}(\sqrt{\log|\mathcal{F}|})$ and we prove that this bound is tight up to log-log factors. Via covering number arguments, our result extends to well-studied infinite families. For example, we show that a near-optimal approximation from any \emph{linear matrix family} of dimension $q$ can be learned with $\tilde{O}(\sqrt{q})$ matvec queries, improving on an $O(q)$ bound achievable via sketching techniques.

We describe a randomized algorithm for producing a near-optimal hierarchical off-diagonal low-rank (HODLR) approximation to an n × n matrix A, accessible only though matrix-vector products with A and AT. We prove that, for the rank-k HODLR approximation problem, our method achieves a (1 + β )log(n )-optimal approximation in expected Frobenius norm using O (k log(n )/β3) matrix-vector products. In particular, the algorithm obtains a (1 + ∈ )-optimal approximation with O (k log4(n )/∈3) matrix-vector products, and for any constant c, an nc-optimal approximation with O (k log(n )) matrix-vector products. Apart from matrix-vector products, the additional computational cost of our method is just O (n poly(log(n ), k, β )). We complement the upper bound with a lower bound, which shows that any matrix-vector query algorithm requires at least Ω(k log(n ) + k/ε ) queries to obtain a (1 + ε )-optimal approximation.