Perfect $L_{p}$ sampling in a stream was introduced by Jayaram and Woodruff (FOCS 2018) as a streaming primitive which, given turnstile updates to a vector $x \in\{-\operatorname{poly}(n), \ldots, \operatorname{poly}(n)\}^{n}$, outputs an index $i^{*} \in\{1,2, \ldots, n\}$ such that the probability of returning index i is exactly $\operatorname{Pr}\left[i^{*}=i\right]=\frac{\left|x_{i}\right|^{p}}{\|x\|_{p}^{p}} \pm \frac{1}{n^{C}}$, where $C\gt0$ is an arbitrarily large constant. Jayaram and Woodruff achieved the optimal $\tilde{O}\left(\log ^{2} n\right)$ bits of memory for $0(\lt)p(\lt)2$, but their update time is at least $n^{C}$ per stream update. Thus an important open question is to achieve efficient update time while maintaining optimal space. For $0(\lt)p(\lt)2$, we give the first perfect $L_{p}$-sampler with the same optimal amount of memory but with only poly $(\log n)$ update time. Crucial to our result is an efficient simulation of a sum of reciprocals of powers of truncated exponential random variables by approximating its characteristic function, using the Gil-Pelaez inversion formula, and applying variants of the trapezoid formula to quickly approximate it.

We consider the heavy-hitters and F_p moment estimation problems in the sliding window model. For F_p moment estimation with 1 < p ≤ 2, we show that it is possible to give a (1± ε) multiplicative approximation to the F_p moment with 2/3 probability on any given window of size n using Õ(1/(ε^p)log² n + 1/(ε²)log n) bits of space. We complement this result with a lower bound showing that our algorithm gives tight bounds up to factors of log log n and log1/(ε). As a consequence of our F₂ moment estimation algorithm, we show that the heavy-hitters problem can be solved on an arbitrary window using O(1/(ε²)log² n) space which is tight.

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.

We consider the problem of estimating the spectrum of a symmetric bounded entry (not necessarily PSD) matrix via entrywise sampling. This problem was introduced by [Bhattacharjee, Dexter, Drineas, Musco, Ray ’22], where it was shown that one can obtain an ∈n additive approximation to all eigenvalues of A by sampling a principal submatrix of dimension . We improve their analysis by showing that it suffices to sample a principal submatrix of dimension (with no dependence on n). This matches known lower bounds and therefore resolves the sample complexity of this problem up to log factors. Using similar techniques, we give a tight bound for obtaining an additive ∈ ||A ||F approximation to the spectrum of A via squared row-norm sampling, improving on the previous best bound. We also address the problem of approximating the top eigenvector for a bounded entry, PSD matrix A. In particular, we show that sampling columns of A suffices to produce a unit vector u with uTAu ≥ λ1(A ) — ∈n. This matches what one could achieve via the sampling bound of [Musco, Musco’17] for the special case of approximating the top eigenvector, but does not require adaptivity.

A recent work, [Jayaram, Woodruff, Zhou '24] studied the problem of designing streaming algorithms with few changes memory. In particular they showed that one can solve the ε-l k -heavy-hitters problem using O(1/ε n 1-1/k polylog(n/ε)) state changes and O(poly(1/ε) log n) space, although the log factors here are too large for reasonable implementation. Our first result is a new algorithm for solving the l k heavy hitters problem for k ∈ [1,2]. Our algorithm requires only O(1/ε n 1-1/k poly(log log n)log 1/ε) state changes and O(1/ ε k polylog(n)) space. We also extend our algorithm to k ≥ 2, giving the same state change bound, but with an additional n 1-2/k factor in the space. Finally, we complement this result by a lower bound showing that our state change complexity is optimal up to log log n factors. At the core of our improved algorithm is a new, and very simple algorithm for solving heavy-hitters in insertion only streams, which may be of independent interest.

We introduce a new approach for applying sampling-based sketches to two and three mode tensors. We illustrate our technique to construct sketches for the classical problems of $\ell_0$ sampling and producing $\ell_1$ embeddings. In both settings we achieve sketches that can be applied to a rank one tensor in $(\mathbb{R}^d)^{\otimes q}$ (for $q=2,3$) in time scaling with $d$ rather than $d^2$ or $d^3$. Our main idea is a particular sampling construction based on fast convolution which allows us to quickly compute sums over sufficiently random subsets of tensor entries.

We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen known bounds for approximately solving linear regression, p-norm regression (for 1≤ p≤ 2), linear programming, minimizing the sum of finitely many convex nonsmooth functions with varying supports, and low rank approximation; for a number of these fundamental problems our bounds are nearly optimal, as proven by our lower bounds. Among our techniques, we use the notion of block leverage scores, which have been relatively unexplored in this context, as well as dropping all but the “middle” bits in Richardson-style algorithms. We also introduce a new communication problem for accurately approximating inner products and establish a lower bound using the spherical Radon transform. Our lower bound can be used to show the first separation of linear programming and linear systems in the distributed model when the number of constraints is polynomial, addressing an open question in prior work.

We study benign overfitting in two-layer ReLU networks trained using gradient descent and hinge loss on noisy data for binary classification. In particular, we consider linearly separable data for which a relatively small proportion of labels are corrupted or flipped. We identify conditions on the margin of the clean data that give rise to three distinct training outcomes: benign overfitting, in which zero loss is achieved and with high probability test data is classified correctly; overfitting, in which zero loss is achieved but test data is misclassified with probability lower bounded by a constant; and non-overfitting, in which clean points, but not corrupt points, achieve zero loss and again with high probability test data is classified correctly. Our analysis provides a fine-grained description of the dynamics of neurons throughout training and reveals two distinct phases: in the first phase clean points achieve close to zero loss, in the second phase clean points oscillate on the boundary of zero loss while corrupt points either converge towards zero loss or are eventually zeroed by the network. We prove these results using a combinatorial approach that involves bounding the number of clean versus corrupt updates during these phases of training.

We provide theoretical bounds on the forgetting quantity in the continual learning setting for linear tasks, where each round of learning corresponds to projecting onto a linear subspace. For a cyclic task ordering on $T$ tasks repeated $m$ times each, we prove the best known upper bound of $O(T^2/m)$ on the forgetting. Notably, our bound holds uniformly over all choices of tasks and is independent of the ambient dimension. Our main technical contribution is a characterization of the union of all numerical ranges of products of $T$ (real or complex) projections as a sinusoidal spiral, which may be of independent interest.

Given a symmetric matrix A, we show from the simple sketch GAGT, where G is a Gaussian matrix with k = O(1/є2) rows, that there is a procedure for approximating all eigenvalues of A simultaneously to within є ||A||F additive error with large probability. Unlike the work of (Andoni, Nguyen, SODA, 2013), we do not require that A is positive semidefinite and therefore we can recover sign information about the spectrum as well. Our result also significantly improves upon the sketching dimension of recent work for this problem (Needell, Swartworth, Woodruff FOCS 2022), and in fact gives optimal sketching dimension. Our proof develops new properties of singular values of GA for a k × n Gaussian matrix G and an n × n matrix A which may be of independent interest. Additionally we achieve tight bounds in terms of matrix-vector queries. Our sketch can be computed using O(1/є2) matrix-vector multiplies, and by improving on lower bounds for the so-called rank estimation problem, we show that this number is optimal even for adaptive matrix-vector queries.

Motivated by the problem of identifying potential hierarchical population structure on modern survey data containing a wide range of complex data types, we introduce population-based hierarchical non-negative matrix factorization (PHNMF). PHNMF is a variant of hierarchical non-negative matrix factorization based on feature similarity. As such, it enables an automatic and interpretable approach for identifying and understanding hierarchical structure in a data matrix constructed from a wide range of data types. Our numerical experiments on synthetic and real survey data demonstrate that PHNMF can recover latent hierarchical population structure in complex data with high accuracy. Moreover, the recovered subpopulation structure is meaningful and can be useful for improving downstream inference.

We study the problem of testing whether a symmetric $d\times d$ input matrix A is symmetric positive semidefinite (PSD), or is $\epsilon$-far from the PSD cone, meaning that $\lambda_{min}(A)\leq-\epsilon\Vert A\Vert_{p}$, where $\Vert A\Vert_{p}$ is the Schatten-p norm of A. In applications one often needs to quickly tell if an input matrix is PSD, and a small distance from the PSD cone may be tolerable. We consider two well-studied query models for measuring efficiency, namely, the matrix-vector and vector-matrix-vector query models. We first consider one-sided testers, which are testers that correctly classify any PSD input, but may fail on a non-PSD input with a tiny failure probability. Up to logarithmic factors, in the matrix-vector query model we show a tight $\tilde{\Theta}(1/\epsilon^{p/(2p+1)})$ bound, while in the vector-matrix-vector query model we show a tight $\tilde{\Theta}(d^{1-1/p}/\epsilon)$ bound, for every $p\geq 1$. We also show a strong separation between one-sided and two-sided testers in the vector-matrix-vector model, where a two-sided tester can fail on both PSD and non-PSD inputs with a tiny failure probability. In particular, for the important case of the Frobenius norm, we show that any one-sided tester requires $\tilde{\Omega}(\sqrt{d}/\epsilon)$ queries. However we introduce a bilinear sketch for two-sided testing from which we construct a Frobenius norm tester achieving the optimal $\tilde{O}(1/\epsilon^{2})$ queries. We also give a number of additional separations between adaptive and non-adaptive testers. Our techniques have implications beyond testing, providing new methods to approximate the spectrum of a matrix with Frobenius norm error using dimensionality reduction in a way that preserves the signs of eigenvalues.

A hereditary property of a sequence is one that is preserved when restricting to subsequences. We show that there exist hereditary properties of sequences that cannot be tested with sublinear queries, resolving an open question posed by Newman et al. This proof relies crucially on an infinite alphabet, however; for finite alphabets, we observe that any hereditary property can be tested with a constant number of queries.