Matrix–vector algorithms, particularly Krylov subspace methods, are widely viewed as the most effective algorithms for solving large systems of linear equations. This paper establishes lower bounds on the worst-case number of matrix–vector products needed by such an algorithm to approximately solve a general linear system. The first main result is that, for any matrix–vector algorithm which is allowed the use of randomization and can perform products with both a matrix and its transpose, $\Omega(\kappa \log(1/\varepsilon))$ matrix–vector products are necessary to solve a linear system with condition number $\kappa$ to accuracy $\varepsilon$, matching an upper bound for conjugate gradient on the normal equations. The second main result is that one-sided algorithms, which lack access to the transpose, must use $n$ matrix–vector products to solve an $n \times n$ linear system, even when the problem is perfectly conditioned. Both main results include explicit constants that match known upper bounds up to a factor of four. These results rigorously demonstrate the limitations of matrix–vector algorithms and confirm the optimality of widely used Krylov subspace algorithms.

We study the problem of computing a rank-\(k\) approximation of a matrix using randomized block Krylov iteration. Prior work has shown that, for block size \(b = 1\) or \(b = k\), a \((1+\varepsilon)\)-factor approximation to the best rank-\(k\) approximation can be obtained after \(\tilde{O}(k/\sqrt{\varepsilon})\) matrix-vector products with the target matrix. On the other hand, when \(b\) is between \(1\) and \(k\), the best known bound on the number of matrix-vector products scales with \(b(k-b)\), which could be as large as \(O(k^2)\). Nevertheless, in practice, the performance of block Krylov methods is often optimized by choosing a block size \(1 \ll b \ll k\). We address this theory-practice gap by proving that randomized block Krylov iteration produces a \((1+\varepsilon)\)-factor approximate rank-\(k\) approximation using \(\tilde{O}(k/\sqrt{\varepsilon})\) matrix-vector products for any block size \(1 \le b \le k\). Our analysis relies on new bounds for the minimum singular value of a random block Krylov matrix, which may be of independent interest. Similar bounds are central to recent breakthroughs on faster algorithms for sparse linear systems [Peng & Vempala 2021; SODA 2021; Nie, STOC 2022].

We study the computational model where we can access a matrix $\mathbf{A}$ only by computing matrix-vector products $\mathbf{A}\mathrm{x}$ for vectors of the form $\mathrm{x} = \mathrm{x}_1 \otimes \cdots \otimes \mathrm{x}_q$. We prove exponential lower bounds on the number of queries needed to estimate various properties, including the trace and the top eigenvalue of $\mathbf{A}$. Our proofs hold for all adaptive algorithms, modulo a mild conditioning assumption on the algorithm's queries. We further prove that algorithms whose queries come from a small alphabet (e.g., $\mathrm{x}_i \in \\{\pm1\\}^n$) cannot test if $\mathbf{A}$ is identically zero with polynomial complexity, despite the fact that a single query using Gaussian vectors solves the problem with probability 1. In steep contrast to the non-Kronecker case, this shows that sketching $\mathbf{A}$ with different distributions of the same subguassian norm can yield exponentially different query complexities. Our proofs follow from the observation that random vectors with Kronecker structure have exponentially smaller inner products than their non-Kronecker counterparts.

Krylov subspace methods are a ubiquitous tool for computing near-optimal rank k approximations of large matrices. While “large block” Krylov methods with block size at least k give the best known theoretical guarantees, block size one (a single vector) or a small constant is often preferred in practice. Despite their popularity, we lack theoretical bounds on the performance of such “small block” Krylov methods for low-rank approximation.

We study Lp polynomial regression. Given query access to a function f : [−1,1]→ℝ, the goal is to find a degree d polynomial q̂ such that, for a given parameter ε > 0 Here || · ||p is the Lp norm, ‖g‖p = (∫1−1|g(t)|p dt)1/p. We show that querying f at points randomly drawn from the Chebyshev measure on [-1,1] is a near-optimal strategy for polynomial regression in all Lp norms. In particular, to find q̂, it suffices to sample points from [-1,1] with probabilities proportional to this measure. While the optimal sample complexity for polynomial regression was well understood for L2 and L∞, our result is the first that achieves sample complexity linear in d and error (1 + ε) for other values of p without any assumptions. Our result requires two main technical contributions. The first concerns p ≤ 2, for which we provide explicit bounds on the Lp Lewis weight function of the infinite linear operator underlying polynomial regression. Using tools from the orthogonal polynomial literature, we show that this function is bounded by the Chebyshev density. Our second key contribution is to take advantage of the structure of polynomials to reduce the p > 2 case to the p ≤ 2 case. By doing so, we obtain a better sample complexity than what is possible for general p-norm linear regression problems, for which Ω(dp/2) samples are required.

This paper studies the statistical complexity of kernel hyperparameter tuning in the setting of active regression under adversarial noise. We consider the problem of finding the best interpolant from a class of kernels with unknown hyperparameters, assuming only that the noise is square-integrable. We provide finite-sample guarantees for the problem, characterizing how increasing the complexity of the kernel class increases the complexity of learning kernel hyperparameters. For common kernel classes (e.g. squared-exponential kernels with unknown lengthscale), our results show that hyperparameter optimization increases sample complexity by just a logarithmic factor, in comparison to the setting where optimal parameters are known in advance. Our result is based on a subsampling guarantee for linear regression under multiple design matrices which may be of independent interest.

We propose a novel combination of optimization tools with learning theory bounds in order to analyze the sample complexity of optimal kernel sum classifiers. This contrasts the typical learning theoretic results which hold for all (potentially suboptimal) classifiers. Our work also justifies assumptions made in prior work on multiple kernel learning. As a byproduct of our analysis, we also provide a new form of Rademacher complexity for hypothesis classes containing only optimal classifiers.

Secure multi-party computation allows mutually distrusting parties to compute securely over their private data. However, even in the semi-honest two-party setting, most interesting functions cannot be computed securely in the information-theoretic plain model. Intuitively, the objective of accurately evaluating the output of such functions is inherently inimical to the privacy concerns of the parties. Securely evaluating OR of the input bits of two parties is the simplest example, and captures the essence of the hardness in securely evaluating most functions. This work studies the interplay between accuracy and privacy of secure 2-party function evaluation in the information-theoretic plain model. We provide an optimal accuracy versus privacy tradeoff for computing OR(x, y), where x and y are, respectively, the private input bits of Alice and Bob. In particular, we construct a round-optimal two-party protocol for OR that has maximum semi-honest security in the information-theoretic plain model. Prior results exhibit only weak tradeoffs that are far from the optimal. We generalize our techniques to obtain a tight accuracy-versus-privacy tradeoff characterization for a stronger notion of security, namely differentially-private semi-honest security. The technical heart of our result is a new technique to derive inequalities for distributions of transcripts generated by protocols. This approach reduces the domain of the optimization problem from an unbounded number of transcripts to a constant size while preserving the optimal solution to the original problem. We believe that these techniques for analyzing protocols in the information-theoretic plain model will be of independent interest.