The ℓpsubspace approximation problem is an NP-hard low rank approximation problem that generalizes the median hyperplane problem (p = 1), principal component analysis (p = 2), and the center hyperplane problem (p = ∞). A popular approach to cope with the NP-hardness of this problem is to compute a strong coreset, which is a small weighted subset of the input points which simultaneously approximates the cost of every k-dimensional subspace, typically to (1 + ε) relative error for a small constant ε.We obtain an algorithm for constructing a strong coreset for ℓpsubspace approximation of size $\tilde O\left( {k{\varepsilon ^{ - 4/p}}} \right)$ for p2. This offers the following improvements over prior work:•We construct the first strong coresets with nearly optimal dependence on k for all p≠ 2. In prior work, [1] constructed coresets of modified points with a similar dependence on k, while [2] constructed true coresets with polynomially worse dependence on k.•We recover or improve the best known ε dependence for all p. In particular, for p > 2, the [1] coreset of modified points had a dependence of ${\varepsilon ^{ - {p^2}/2}}$ and the [2] coreset had a dependence of ε−3p.Our algorithm is based on sampling by root ridge leverage scores, which admits fast algorithms, especially for sparse or structured matrices. Our analysis completely avoids the use of the representative subspace theorem [1], which is a critical component of all prior dimension-independent coresets for ℓpsubspace approximation.Our techniques also lead to the first nearly optimal online strong coresets for ℓpsubspace approximation with similar bounds as the offline setting, resolving a problem of [3]. All prior approaches lose poly(k) factors in this setting, even when allowed to modify the original points.

The seminal work of Cohen and Peng (STOC 2015) introduced Lewis weight sampling to the theoretical computer science community, which yields fast row sampling algorithms for approximating d -dimensional subspaces of \(\ell_{p}\) up to \((1+\varepsilon)\) relative error. Prior works have extended this important primitive to other settings, such as the online coreset and sliding window models . However, these results are only for \(p\in\{1,2\}\) , and results for \(p=1\) require a suboptimal \(\tilde{O}(d^{2}/\varepsilon^{2})\) samples. In this work, we design the first nearly optimal \(\ell_{p}\) subspace embeddings for all \(p\in(0,\infty)\) in the online coreset and sliding window models. In both models, our algorithms store \(\tilde{O}(d/\varepsilon^{2})\) rows for \(p\in(0,2)\) and \(\tilde{O}(d^{p/2}/\varepsilon^{2})\) rows for \(p\in(2,\infty)\) . This answers a substantial generalization of the main open question of Braverman et al. (2020), gives the first results for all \(p\notin\{1,2\}\) , and achieves nearly optimal sample complexities for all p . Towards our result, we give the first analysis of “one-shot” Lewis weight sampling of sampling rows proportionally to their Lewis weights, which gives a sample complexity of \(\tilde{O}(d^{p/2}/\varepsilon^{2})\) rows for \(p > 2\) . Previously, such a sampling scheme was only known to have a sample complexity of \(\tilde{O}(d^{p/2}/\varepsilon^{5})\) , whereas a bound of \(\tilde{O}(d^{p/2}/\varepsilon^{2})\) is known if a more sophisticated recursive sampling algorithm is used. Note that the recursive sampling strategy cannot be implemented in an online setting, thus necessitating an analysis of one-shot Lewis weight sampling. Perhaps surprisingly, our analysis crucially uses a novel connection to online numerical linear algebra, even for offline Lewis weight sampling . As an application, we obtain the first online coreset algorithms for \((1+\varepsilon)\) approximation of important generalized linear models, such as logistic regression and p -probit regression. Our upper bounds are parameterized by a complexity parameter \(\mu\) introduced by Munteanu et al. (2021), and we also provide the first lower bounds showing that a linear dependence on \(\mu\) is necessary.

Weighted low rank approximation (WLRA) is an important yet computationally challenging primitive with applications ranging from statistical analysis, model compression, and signal processing. To cope with the NP-hardness of this problem, prior work considers heuristics, bicriteria, or parameterized tractable algorithms to solve this problem. In this work, we introduce a new relaxed solution to WLRA which outputs a matrix that is not necessarily low rank, but can be stored using very few parameters and gives provable approximation guarantees when the weight matrix has low rank. Our central idea is to use the weight matrix itself to reweight a low rank solution, which gives an extremely simple algorithm with remarkable empirical performance in applications to model compression and on synthetic datasets. Our algorithm also gives nearly optimal communication complexity bounds for a natural distributed problem associated with this problem, for which we show matching communication lower bounds. Together, our communication complexity bounds show that the rank of the weight matrix provably parameterizes the communication complexity of WLRA. We also obtain the first relative error guarantees for feature selection with a weighted objective.

Neural network pruning is a key technique towards engineering large yet scalable, interpretable, and generalizable models. Prior work on the subject has developed largely along two orthogonal directions: (1) differentiable pruning for efficiently and accurately scoring the importance of parameters, and (2) combinatorial optimization for efficiently searching over the space of sparse models. We unite the two approaches, both theoretically and empirically, to produce a coherent framework for structured neural network pruning in which differentiable pruning guides combinatorial optimization algorithms to select the most important sparse set of parameters. Theoretically, we show how many existing differentiable pruning techniques can be understood as nonconvex regularization for group sparse optimization, and prove that for a wide class of nonconvex regularizers, the global optimum is unique, group-sparse, and provably yields an approximate solution to a sparse convex optimization problem. The resulting algorithm that we propose, SequentialAttention++, advances the state of the art in large-scale neural network block-wise pruning tasks on the ImageNet and Criteo datasets.

We give a faster algorithm for computing an approximate John ellipsoid around $n$ points in $d$ dimensions. The best known prior algorithms are based on repeatedly computing the leverage scores of the points and reweighting them by these scores (Cohen et al., 2019). We show that this algorithm can be substantially sped up by delaying the computation of high accuracy leverage scores by using sampling, and then later computing multiple batches of high accuracy leverage scores via fast rectangular matrix multiplication. We also give low-space streaming algorithms for John ellipsoids using similar ideas.

Sketching algorithms have recently proven to be a powerful approach both for designing low-space streaming algorithms as well as fast polynomial time approximation schemes (PTAS). In this work, we develop new techniques to extend the applicability of sketching-based approaches to the sparse dictionary learning and the Euclidean $k$-means clustering problems. In particular, we initiate the study of the challenging setting where the dictionary/clustering assignment for each of the $n$ input points must be output, which has surprisingly received little attention in prior work. On the fast algorithms front, we obtain a new approach for designing PTAS's for the $k$-means clustering problem, which generalizes to the first PTAS for the sparse dictionary learning problem. On the streaming algorithms front, we obtain new upper bounds and lower bounds for dictionary learning and $k$-means clustering. In particular, given a design matrix $\mathbf A\in\mathbb R^{n\times d}$ in a turnstile stream, we show an $\tilde O(nr/\epsilon^2 + dk/\epsilon)$ space upper bound for $r$-sparse dictionary learning of size $k$, an $\tilde O(n/\epsilon^2 + dk/\epsilon)$ space upper bound for $k$-means clustering, as well as an $\tilde O(n)$ space upper bound for $k$-means clustering on random order row insertion streams with a natural "bounded sensitivity" assumption. On the lower bounds side, we obtain a general $\tilde\Omega(n/\epsilon + dk/\epsilon)$ lower bound for $k$-means clustering, as well as an $\tilde\Omega(n/\epsilon^2)$ lower bound for algorithms which can estimate the cost of a single fixed set of candidate centers.

The seminal work of Cohen and Peng [CP15] (STOC 2015) introduced Lewis weight sampling to the theoretical computer science community, which yields fast row sampling algorithms for approximating d-dimensional subspaces of ℓp up to (1 + ε) relative error. Several works have extended this important primitive to other settings, including the online coreset and sliding window models [BDM+20] (FOCS 2020) as well as the adversarial streaming model [BHM+21] (NeurIPS 2021). However, these results are only for p ∈ {1, 2}, and results for p = 1 require a suboptimal Õ(d2/ε2) samples. In this work, we design the first nearly optimal ℓp subspace embeddings for all p ∈ (0, ∞) in the online coreset, sliding window, and the adversarial streaming models. In all three models, our algorithms store Õ(d/ε2) rows for p ∈ (0, 2) and Õ(dp/2/ε2) rows for p ∈ (2, ∞). This answers a substantial generalization of the main open question of [BDM+20], and gives the first results for all p ∉ {1, 2} and achieves nearly optimal sample complexities for all p. Towards our result, we give the first analysis of “one-shot” Lewis weight sampling of sampling rows proportionally to their Lewis weights, which gives a sample complexity of Õ(dp/2/ε2) rows for p > 2. Previously, such a sampling scheme was only known to have a sample complexity of Õ(dp/2/ε5) [CP15], whereas a bound of Õ(dp/2/ε2) is known if a more sophisticated recursive sampling algorithm is used [MMWY21, LT91]. Note that the recursive sampling strategy cannot be implemented in an online setting, thus necessitating an analysis of one-shot Lewis weight sampling. Perhaps surprisingly, our analysis crucially uses a novel connection to online numerical linear algebra, even for offline Lewis weight sampling. As an application, we obtain the first one-pass streaming coreset algorithms for (1 + ε) approximation of important generalized linear models, such as logistic regression and p-probit regression. Our upper bounds are parameterized by a complexity parameter μ introduced by [MSSW18], and we also provide the first lower bounds showing that a linear dependence on μ is necessary. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.08268

Subset selection for the rank k approximation of an n× d matrix A offers improvements in the interpretability of matrices, as well as a variety of computational savings. This problem is well-understood when the error measure is the Frobenius norm, with various tight algorithms known even in challenging models such as the online model, where an algorithm must select the column subset irrevocably when the columns arrive one by one. In sharp contrast, when the error measure is replaced by other matrix losses, optimal trade-offs between the subset size and approximation quality have not been settled, even in the standard offline setting. We give a number of results towards closing these gaps.

We study active sampling algorithms for linear regression, which aim to query only a small number of entries of a target vector and output a near minimizer to the objective function. For $\ell_{p}$ norm regression for any $ 0\lt p \lt \infty$, we give an algorithm based on Lewis weight sampling which outputs $\mathrm{a}(1+\epsilon)$-approximate solution using just $\tilde{O}(d/\epsilon^{2})$ queries to b for $p\in(0,1)$, $\tilde{O}$ $(d/\epsilon)$ queries for $p\in(1,2)$, and $\tilde{O}$ $(d^{p/2}/\epsilon^{p})$ queries for $p\in(2,\ \infty)$. For $p\in(0,2)$, our bounds are optimal up to logarithmic factors, thus settling the query complexity for this range of p. For $p\in(2,\ \infty)$, our dependence on d is optimal, while our dependence on $\epsilon$ is off by at most a single $\epsilon$ factor, up to logarithmic factors. Our result resolves an open question of Chen and Dereziński, who gave near optimal bounds for the $\ell_{1}$ norm, but required at least $d^{2}/\epsilon^{2}$ samples for $\ell_{p}$ regression with $p\in(1,2)$, and gave no bounds for $p\in(2,\ \infty)$ or $p\in(0,1)$. We also provide the first total sensitivity upper bound for loss functions with at most degree p polynomial growth. This improves a recent result of Tukan, Maalouf, and Feldman. By combining this with our techniques for $\ell_{p}$ regression, we obtain the first active regression algorithms for such loss functions, including the important cases of the Tukey and Huber losses. This answers another question of Chen and Dereziński. Our sensitivity bounds also give improvements to a variety of previous results using sensitivity sampling, including Orlicz norm subspace embeddings, robust subspace approximation, and dimension reduction for smoothed p-norms. Finally, our active sampling results give the first sublinear time algorithms for Kronecker product regression under every $\ell_{p}$ norm. Previous results required reading the entire b vector in the kernel feature space.11Extended abstract; full version available at https://arxiv.org/abs/2111.04888.

Many existing algorithms for streaming geometric data analysis have been plagued by exponential dependencies in the space complexity, which are undesirable for processing high-dimensional data sets, i.e., large d. In particular, once $d\geq\log n$, there are no known non-trivial streaming algorithms for problems such as maintaining convex hulls and Löwner-John ellipsoids of n points, despite a long line of work in high-dimensional streaming computational geometry since [2]. We simultaneously improve all of these results to poly $(d,\ \log n)$ bits of space by trading off with a poly $(d,\ \log n)$ factor distortion. We achieve these results in a unified manner, by designing the first streaming algorithm for maintaining a coreset for $\ell_{\infty}$ subspace embeddings with poly $(d,\ \log n)$ space and poly $(d,\ \log n)$ distortion. Our algorithm also gives similar guarantees in the online coreset model. Along the way, we sharpen known results for online numerical linear algebra by replacing a $\log$ condition number dependence with a $\log n$ dependence, answering an open question of [13]. Our techniques provide a novel connection between leverage scores, a fundamental object in numerical linear algebra, and computational geometry. For $\ell_{p}$ subspace embeddings, our improvements in online numerical linear algebra yield nearly optimal tradeoffs between space and distortion for one-pass streaming algorithms. For instance, we obtain a deterministic coreset using $o(d^{2}\log n)$ space and $o((d\log n)^{\frac{1}{2}-\frac{1}{p}})$ distortion for $p\gt 2$, whereas previous deterministic algorithms incurred a poly (n) factor in the space or the distortion [26]. Our techniques have implications also in the offline setting, where we give optimal trade-offs between the space complexity and distortion of a subspace sketch data structure, which preprocesses an $n\times d$ matrix A and outputs $\Vert \mathrm{A}\mathrm{x}\Vert_{p}$ up to a poly (d) factor distortion for any x. To do this we give an elementary proof of a “change of density” theorem of [42] and make it algorithmic.11Extended abstract; full version available at https://arxiv.org/abs/ 2204.03790.

We overcome two major bottlenecks in the study of low rank approximation by assuming the low rank factors themselves are sparse. Specifically, (1) for low rank approximation with spectral norm error, we show how to improve the best known running time to running time plus low order terms depending on the sparsity of the low rank factors, and (2) for streaming algorithms for Frobenius norm error, we show how to bypass the known Ω(nk/∊) memory lower bound and obtain an sk(log n)/poly(∊) memory bound, where s is the number of non-zeros of each low rank factor. Although this algorithm runs in exponential time, as it must under standard complexity-theoretic assumptions, we also present polynomial time algorithms using poly(s, k, log n, ∊–1) memory that output rank k approximations supported on an O(sk/∊) × O(sk/∊) submatrix. Both the prior running time and the nk/∊ memory for these problems were long-standing barriers; our results give a natural way of overcoming them assuming sparsity of the low rank factors.

Despite many applications, dimensionality reduction in the $\ell_1$-norm is much less understood than in the Euclidean norm. We give two new oblivious dimensionality reduction techniques for the $\ell_1$-norm which improve exponentially over prior ones: - We design a distribution over random matrices $S \in \mathbb{R}^{r \times n}$, where $r = 2^{\textrm{poly}(d/(\varepsilon \delta))}$, such that given any matrix $A \in \mathbb{R}^{n \times d}$, with probability at least $1-\delta$, simultaneously for all $x$, $\|SAx\|_1 = (1 \pm \varepsilon)\|Ax\|_1$. Note that $S$ is linear, does not depend on $A$, and maps $\ell_1$ into $\ell_1$. Our distribution provides an exponential improvement on the previous best known map of Wang and Woodruff (SODA, 2019), which required $r = 2^{2^{\Omega(d)}}$, even for constant $\varepsilon$ and $\delta$. Our bound is optimal, up to a polynomial factor in the exponent, given a known $2^{\textrm{poly}(d)}$ lower bound for constant $\varepsilon$ and $\delta$. - We design a distribution over matrices $S \in \mathbb{R}^{k \times n}$, where $k = 2^{O(q^2)}(\varepsilon^{-1} q \log d)^{O(q)}$, such that given any $q$-mode tensor $A \in (\mathbb{R}^{d})^{\otimes q}$, one can estimate the entrywise $\ell_1$-norm $\|A\|_1$ from $S(A)$. Moreover, $S = S^1 \otimes S^2 \otimes \cdots \otimes S^q$ and so given vectors $u_1, \ldots, u_q \in \mathbb{R}^d$, one can compute $S(u_1 \otimes u_2 \otimes \cdots \otimes u_q)$ in time $2^{O(q^2)}(\varepsilon^{-1} q \log d)^{O(q)}$, which is much faster than the $d^q$ time required to form $u_1 \otimes u_2 \otimes \cdots \otimes u_q$. Our linear map gives a streaming algorithm for independence testing using space $2^{O(q^2)}(\varepsilon^{-1} q \log d)^{O(q)}$, improving the previous doubly exponential $(\varepsilon^{-1} \log d)^{q^{O(q)}}$ space bound of Braverman and Ostrovsky (STOC, 2010). For subspace embeddings, we also study the setting when $A$ is itself drawn from distributions with independent entries, and obtain a polynomial embedding dimension. For independence testing, we also give algorithms for any distance measure with a polylogarithmic-sized sketch and satisfying an approximate triangle inequality.

Graph spanners are sparse subgraphs which approximately preserve all pairwise shortest-path distances in an input graph. The notion of approximation can be additive, multiplicative, or both, and many variants of this problem have been extensively studied. We study the problem of computing a graph spanner when the edges of the input graph are distributed across two or more sites in an arbitrary, possibly worst-case partition, and the goal is for the sites to minimize the communication used to output a spanner. We assume the message-passing model of communication, for which there is a point-to-point link between all pairs of sites as well as a coordinator who is responsible for producing the output. We stress that the subset of edges that each site has is not related to the network topology, which is fixed to be point-to-point. While this model has been extensively studied for related problems such as graph connectivity, it has not been systematically studied for graph spanners. We present the first tradeoffs for total communication versus the quality of the spanners computed, for two or more sites, as well as for additive and multiplicative notions of distortion. We show separations in the communication complexity when edges are allowed to occur on multiple sites, versus when each edge occurs on at most one site. We obtain nearly tight bounds (up to polylog factors) for the communication of additive $2$-spanners in both the with and without duplication models, multiplicative $(2k-1)$-spanners in the with duplication model, and multiplicative $3$ and $5$-spanners in the without duplication model. Our lower bound for multiplicative $3$-spanners employs biregular bipartite graphs rather than the usual Erdős girth conjecture graphs and may be of wider interest.

Kernel methods generalize machine learning algorithms that only depend on the pairwise inner products of the dataset by replacing inner products with kernel evaluations, a function that passes input points through a nonlinear feature map before taking the inner product in a higher dimensional space. In this work, we present nearly tight lower bounds on the number of kernel evaluations required to approximately solve kernel ridge regression (KRR) and kernel $k$-means clustering (KKMC) on $n$ input points. For KRR, our bound for relative error approximation the argmin of the objective function is $\Omega(nd_{\mathrm{eff}}^\lambda/\varepsilon)$ where $d_{\mathrm{eff}}^\lambda$ is the effective statistical dimension, tight up to a $\log(d_{\mathrm{eff}}^\lambda/\varepsilon)$ factor. For KKMC, our bound for finding a $k$-clustering achieving a relative error approximation of the objective function is $\Omega(nk/\varepsilon)$, tight up to a $\log(k/\varepsilon)$ factor. Our KRR result resolves a variant of an open question of El Alaoui and Mahoney, asking whether the effective statistical dimension is a lower bound on the sampling complexity or not. Furthermore, for the important input distribution case of mixtures of Gaussians, we provide algorithms that bypass the above lower bounds.