Raphael A. Meyer

ICML Conference 2025 Conference Paper

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra

• Raphael A. Meyer
• William Swartworth
• David P. Woodruff

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.

SODA Conference 2024 Conference Paper

On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation

• Raphael A. Meyer
• Cameron Musco
• Christopher Musco

SODA Conference 2023 Conference Paper

Near-Linear Sample Complexity for L p Polynomial Regression

• Raphael A. Meyer
• Cameron Musco
• Christopher Musco
• David P. Woodruff
• Samson Zhou

We study L p 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 L p 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 L p 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 L 2 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 L p 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 Ω (d p/2 ) samples are required.

ICLR Conference 2022 Conference Paper

Fast Regression for Structured Inputs

• Raphael A. Meyer
• Cameron Musco
• Christopher Musco
• David P. Woodruff
• Samson Zhou

We study the $\ell_p$ regression problem, which requires finding $\mathbf{x}\in\mathbb R^{d}$ that minimizes $\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_p$ for a matrix $\mathbf{A}\in\mathbb R^{n \times d}$ and response vector $\mathbf{b}\in\mathbb R^{n}$. There has been recent interest in developing subsampling methods for this problem that can outperform standard techniques when $n$ is very large. However, all known subsampling approaches have run time that depends exponentially on $p$, typically, $d^{\mathcal{O}(p)}$, which can be prohibitively expensive. We improve on this work by showing that for a large class of common \emph{structured matrices}, such as combinations of low-rank matrices, sparse matrices, and Vandermonde matrices, there are subsampling based methods for $\ell_p$ regression that depend polynomially on $p$. For example, we give an algorithm for $\ell_p$ regression on Vandermonde matrices that runs in time $\mathcal{O}(n\log^3 n+(dp^2)^{0.5+\omega}\cdot\text{polylog}\,n)$, where $\omega$ is the exponent of matrix multiplication. The polynomial dependence on $p$ crucially allows our algorithms to extend naturally to efficient algorithms for $\ell_\infty$ regression, via approximation of $\ell_\infty$ by $\ell_{\mathcal{O}(\log n)}$. Of practical interest, we also develop a new subsampling algorithm for $\ell_p$ regression for arbitrary matrices, which is simpler than previous approaches for $p \ge 4$.

ICML Conference 2019 Conference Paper

Optimality Implies Kernel Sum Classifiers are Statistically Efficient

• Raphael A. Meyer
• Jean Honorio

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.