We revisit the problem of robust linear regression under Gaussian covariates with an unknown covariance matrix of condition number $\kappa$. For this fundamental problem, significant gaps remain in our understanding of the trade-offs among sample complexity, condition number, runtime, and prediction error for efficient algorithms. Our first result is a near-linear-time algorithm that uses $\widetilde{O}(d/\varepsilon^4)$ samples, where $d$ is the dimension and $\varepsilon$ is the corruption rate, and achieves prediction error $O(\sqrt{\varepsilon\kappa})$ under the condition $\varepsilon\kappa \lesssim 1$, improving over all prior works. We complement this result with a Statistical Query (SQ) lower bound showing that efficient SQ algorithms achieving error $o(\sqrt{\varepsilon\kappa})$ when $\varepsilon \kappa \lesssim 1$ require queries that take $\Omega(d^2)$ samples to simulate. Finally, we prove a low-degree polynomial lower bound that gives fine-grained evidence that, without assumptions such as $\varepsilon \kappa \lesssim 1$, efficient algorithms may require $\tilde{\Omega}\left(\min{d\varepsilon^{2}\kappa^{2}, \varepsilon^{2}d^{2}}\right)$ samples to significantly outperform the trivial estimator that always guesses $0$.

We consider a problem of approximating the size of the largest clique in a graph, with a monotone circuit. Concretely, we focus on distinguishing a random Erdős-Renyi graph $\mathcal{G}_{n,p}$, with $p=n^{-\frac{2}{α-1}}$ chosen st. with high probability it does not even have an $α$-clique, from a random clique on $β$ vertices (where $α\leq β$). Using the approximation method of Razborov, Alon and Boppana showed in 1987 that as long as $\sqrtα β< n^{1-δ}/\log n$, this problem requires a monotone circuit of size $n^{Ω(δ\sqrtα)}$, implying a lower bound of $2^{\tildeΩ(n^{1/3})}$ for the exact version of the problem when $k\approx n^{2/3}$. Recently Cavalar, Kumar, and Rossman improved their result by showing the tight lower bound $n^{Ω(k)}$, in a limited range $k \leq n^{1/3}$, implying a comparable $2^{\tildeΩ(n^{1/3})}$ lower bound. We combine the ideas of Cavalar, Kumar and Rossman with the recent breakthrough results on the sunflower conjecture by Alweiss, Lovett, Wu and Zhang to show that as long as $αβ< n^{1-δ}/\log n$, any monotone circuit rejecting $\mathcal{G}_{n,p}$ while accepting a $β$-clique needs to have size at least $n^{Ω(δ^2 α)}$; this implies a stronger $2^{\tildeΩ(\sqrt{n})}$ lower bound for the unrestricted version of the problem. We complement this result with a construction of an explicit monotone circuit of size $O(n^{δ^2 α/2})$ which rejects $\mathcal{G}_{n,p}$, and accepts any graph containing $β$-clique whenever $β> n^{1-δ}$. Those two theorems explain the largest $β$-clique that can be distinguished from $\mathcal{G}_{n, 1/2}$: when $β> n / 2^{C \sqrt{\log n}}$, polynomial size circuit co do it, while for $β< n / 2^{ω(\sqrt{\log n})}$ every circuit needs size $n^{ω(1)}$.

We give a simple, greedy$O(n^{\omega+0.5})=O(n^{2.872})$- time algorithm to list-decode planted cliques in a semirandom model introduced in [CSV17] (following [FK01) that succeeds whenever the size of the planted clique is$k\geq O(\sqrt{n}\log^{2}n)$. In the model, the edges touching the vertices in the planted k-clique are drawn independently with probability$p=1/2$while the edges not touching the planted clique are chosen by an adversary in response to the random choices. Our result shows that the computational threshold in the semirandom setting is within a$O(\log^{2}n)$factor of the information-theoretic one [Ste17] thus resolving an open question of Steinhardt. This threshold also essentially matches the conjectured computational threshold for the well-studied special case of fully random planted clique. All previous algorithms [CSV17], [MMT20], [BKS23] in this model are based on rather sophisticated rounding algorithms for entropy-constrained semidefinite programming relaxations and their sum-of-squares strengthenings and the best known guarantee is a$n^{O(1/\varepsilon}$) -time algorithm to list-decode planted cliques of size$k\geq\tilde{O}(n^{1/2+\varepsilon})$. In particular, the guarantee trivializes to quasi-polynomial time if the planted clique is of size$O (\sqrt{n}$poly log$n$). Our algorithm achieves an almost optimal guarantee with a surprisingly simple greedy algorithm. The prior state-of-the-art algorithmic result above is based on a reduction to certifying bounds on the size of unbalanced bicliques in random graphs - closely related to certifying the restricted isometry property (RIP) of certain random matrices and known to be hard in the low-degree polynomial model. Our key idea is a new approach that relies on the truth of - but not efficient certificates for - RIP of a new class of matrices built from the input graphs.

Calibration measures and reliability diagrams are two fundamental tools for measuring and interpreting the calibration of probabilistic predictors. Calibration measures quantify the degree of miscalibration, and reliability diagrams visualize the structure of this miscalibration. However, the most common constructions of reliability diagrams and calibration measures --- binning and ECE --- both suffer from well-known flaws (e.g. discontinuity). We show that a simple modification fixes both constructions: first smooth the observations using an RBF kernel, then compute the Expected Calibration Error (ECE) of this smoothed function. We prove that with a careful choice of bandwidth, this method yields a calibration measure that is well-behaved in the sense of (Blasiok, Gopalan, Hu, and Nakkiran 2023) --- a consistent calibration measure. We call this measure the SmoothECE. Moreover, the reliability diagram obtained from this smoothed function visually encodes the SmoothECE, just as binned reliability diagrams encode the BinnedECE. We also release a Python package with simple, hyperparameter-free methods for measuring and plotting calibration: "pip install relplot." Code at: https://github.com/apple/ml-calibration

Multicalibration is a notion of fairness for predictors that requires them to provide calibrated predictions across a large set of protected groups. Multicalibration is known to be a distinct goal than loss minimization, even for simple predictors such as linear functions. In this work, we consider the setting where the protected groups can be represented by neural networks of size $k$, and the predictors are neural networks of size $n > k$. We show that minimizing the squared loss over all neural nets of size $n$ implies multicalibration for all but a bounded number of unlucky values of $n$. We also give evidence that our bound on the number of unlucky values is tight, given our proof technique. Previously, results of the flavor that loss minimization yields multicalibration were known only for predictors that were near the ground truth, hence were rather limited in applicability. Unlike these, our results rely on the expressivity of neural nets and utilize the representation of the predictor.

Suppose that S ⊆ [n]² contains no three points of the form (x,y), (x,y+δ), (x+δ,y'), where δ ≠ 0. How big can S be? Trivially, n ≤ |S| ≤ n². Slight improvements on these bounds are obtained from Shkredov’s upper bound for the corners problem [Shkredov, 2006], which shows that |S| ≤ O(n²/(log log n)^c) for some small c > 0, and a construction due to Petrov [Fedor Petrov, 2023], which shows that |S| ≥ Ω(n log n/√{log log n}). Could it be that for all ε > 0, |S| ≤ O(n^{1+ε})? We show that if so, this would rule out obtaining ω = 2 using a large family of abelian groups in the group-theoretic framework of [Cohn and Umans, 2003; Cohn et al., 2005] (which is known to capture the best bounds on ω to date), for which no barriers are currently known. Furthermore, an upper bound of O(n^{4/3 - ε}) for any fixed ε > 0 would rule out a conjectured approach to obtain ω = 2 of [Cohn et al., 2005]. Along the way, we encounter several problems that have much stronger constraints and that would already have these implications.

Optimizing proper loss functions is popularly believed to yield predictors with good calibration properties; the intuition being that for such losses, the global optimum is to predict the ground-truth probabilities, which is indeed calibrated. However, typical machine learning models are trained to approximately minimize loss over restricted families of predictors, that are unlikely to contain the ground truth. Under what circumstances does optimizing proper loss over a restricted family yield calibrated models? What precise calibration guarantees does it give? In this work, we provide a rigorous answer to these questions. We replace the global optimality with a local optimality condition stipulating that the (proper) loss of the predictor cannot be reduced much by post-processing its predictions with a certain family of Lipschitz functions. We show that any predictor with this local optimality satisfies smooth calibration as defined in [Kakade and Foster, 2008, Błasiok et al., 2023]. Local optimality is plausibly satisfied by well-trained DNNs, which suggests an explanation for why they are calibrated from proper loss minimization alone. Finally, we show that the connection between local optimality and calibration error goes both ways: nearly calibrated predictors are also nearly locally optimal.

We study the fundamental question of how to define and measure the distance from calibration for probabilistic predictors. While the notion of perfect calibration is well-understood, there is no consensus on how to quantify the distance from perfect calibration. Numerous calibration measures have been proposed in the literature, but it is unclear how they compare to each other, and many popular measures such as Expected Calibration Error (ECE) fail to satisfy basic properties like continuity.

Having similar behavior at training time and test time—what we call a “What You See Is What You Get” (WYSIWYG) property—is desirable in machine learning. Models trained with standard stochastic gradient descent (SGD), however, do not necessarily have this property, as their complex behaviors such as robustness or subgroup performance can differ drastically between training and test time. In contrast, we show that Differentially-Private (DP) training provably ensures the high-level WYSIWYG property, which we quantify using a notion of distributional generalization. Applying this connection, we introduce new conceptual tools for designing deep-learning methods by reducing generalization concerns to optimization ones: to mitigate unwanted behavior at test time, it is provably sufficient to mitigate this behavior on the training data. By applying this novel design principle, which bypasses “pathologies” of SGD, we construct simple algorithms that are competitive with SOTA in several distributional-robustness applications, significantly improve the privacy vs. disparate impact trade-off of DP-SGD, and mitigate robust overfitting in adversarial training. Finally, we also improve on theoretical bounds relating DP, stability, and distributional generalization.

The distinct elements problem is one of the fundamental problems in streaming algorithms—given a stream of integers in the range { 1,… , n }, we wish to provide a (1+ε) approximation to the number of distinct elements in the input. After a long line of research an optimal solution for this problem with constant probability of success, using O (1/ε 2 +lg n ) bits of space, was given by Kane, Nelson, and Woodruff in 2010. The standard approach used to achieve low failure probability δ is to take the median of lg δ −1 parallel repetitions of the original algorithm. We show that such a multiplicative space blow-up is unnecessary: We provide an optimal algorithm using O (lg δ −1 /ε 2 + lg n ) bits of space—matching known lower bounds for this problem. That is, the lg δ −1 ; factor does not multiply the lg n term. This settles completely the space complexity of the distinct elements problem with respect to all standard parameters. We consider also the strong tracking (or continuous monitoring ) variant of the distinct elements problem, where we want an algorithm that provides an approximation of the number of distinct elements seen so far, at all times of the stream. We show that this variant can be solved using O (lg lg n + lg δ −1 /ε 2 + lg n ) bits of space, which we show to be optimal.

We give a short argument that yields a new lower bound on the number of subsampled rows from a bounded, orthonormal matrix necessary to form a matrix with the restricted isometry property. We show that a matrix formed by uniformly subsampling rows of an N × N Hadamard matrix contains a K-sparse vector in the kernel, unless the number of subsampled rows is Ω(K log K log (N/K)) --- our lower bound applies whenever min(K, N/K) > logCN. Containing a sparse vector in the kernel precludes not only the restricted isometry property, but more generally the application of those matrices for uniform sparse recovery.

We study efficient mechanisms for the query release problem in differential privacy: given a workload of m statistical queries, output approximate answers to the queries while satisfying the constraints of differential privacy. In particular, we are interested in mechanisms that optimally adapt to the given workload. Building on the projection mechanism of Nikolov, Talwar, and Zhang, and using the ideas behind Dudley's chaining inequality, we propose new efficient algorithms for the query release problem, and prove that they achieve optimal sample complexity for the given workload (up to constant factors, in certain parameter regimes) with respect to the class of mechanisms that satisfy concentrated differential privacy. We also give variants of our algorithms that satisfy local differential privacy, and prove that they also achieve optimal sample complexity among all local sequentially interactive private mechanisms.

Using a mild variant of polar codes we design linear compression schemes compressing Hidden Markov sources (where the source is a Markov chain, but whose state is not necessarily observable from its output), and to decode from Hidden Markov channels (where the channel has a state and the error introduced depends on the state). We give the first polynomial time algorithms that manage to compress and decompress (or encode and decode) at input lengths that are polynomial both in the gap to capacity and the mixing time of the Markov chain. Prior work achieved capacity only asymptotically in the limit of large lengths, and polynomial bounds were not available with respect to either the gap to capacity or mixing time. Our results operate in the setting where the source (or the channel) is known. If the source is unknown then compression at such short lengths would lead to effective algorithms for learning parity with noise - thus our results are the first to suggest a separation between the complexity of the problem when the source is known versus when it is unknown.

The distinct elements problem is one of the fundamental problems in streaming algorithms — given a stream of integers in the range {1, … n}, we wish to provide a (1+ε) approximation of the number of distinct elements in the input. After a long line of research optimal solution for this problem with constant probability of success, using bits of space, was given by Kane, Nelson and Woodruff in [KNW10]. The standard approach used in order to achieve low failure probability δ, is to take a median of 1g δ–1 parallel repetitions of the original algorithm. We show that such a multiplicative space blow-up is unnecessary: we provide an optimal algorithm using bits of space — matching known lower bounds for this problem. That is, the lg δ–1 factor does not multiply the lg n term. This settles completely the space complexity of the distinct elements problem with respect to all standard parameters. Recently some attention in streaming algorithms has turned into continuously reporting the estimate of the statistic of interest, as opposed to reporting it only at the end of the stream. In this scenario, we want an algorithm which provides a (1 + ε) multiplicative approximation of the number of distinct elements at all times with probability 1 – δ, we call this strong tracking or continuous monitoring. The traditional way to achieve this kind of guarantee is to use a low failure probability algorithm, and union bound over carefully chosen subset of positions — this method, using as black-box the optimal streaming algorithm for distinct elements with low failure probability, would require bits of space. We show that this approach can be improved upon: we propose a stronger analysis of the algorithm, with space complexity . Finally, we show the matching lower bound for the strong tracking of the number of distinct elements with accuracy (1 + ε), proving optimality of our algorithm in terms of space usage.

Arikan’s exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix M, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the polarization of an associated [0,1]-bounded martingale, namely its convergence in the limit to either 0 or 1 with probability 1. Arikan showed appropriate polarization of the martingale associated with the matrix G2 = ( [complex formula not displayed] ) to get capacity achieving codes. His analysis was later extended to all matrices M which satisfy an obvious necessary condition for polarization.

In insertion-only streaming, one sees a sequence of indices a_1, a_2, ..., a_m in [n]. The stream defines a sequence of m frequency vectors x(1), ..., x(m) each in R^n, where x(t) is the frequency vector of items after seeing the first t indices in the stream. Much work in the streaming literature focuses on estimating some function f(x(m)). Many applications though require obtaining estimates at time t of f(x(t)), for every t in [m]. Naively this guarantee is obtained by devising an algorithm with failure probability less than 1/m, then performing a union bound over all stream updates to guarantee that all m estimates are simultaneously accurate with good probability. When f(x) is some l_p norm of x, recent works have shown that this union bound is wasteful and better space complexity is possible for the continuous monitoring problem, with the strongest known results being for p=2. In this work, we improve the state of the art for all 0<p<2, which we obtain via a novel analysis of Indyk's p-stable sketch.

We characterize the streaming space complexity of every symmetric norm l (a norm on ℝn invariant under sign-flips and coordinate-permutations), by relating this space complexity to the measure-concentration characteristics of l. Specifically, we provide nearly matching upper and lower bounds on the space complexity of calculating a (1 ± ε)-approximation to the norm of the stream, for every 0 < ε ≤ 1/2. (The bounds match up to (ε-1 logn) factors.) We further extend those bounds to any large approximation ratio D≥ 1.1, showing that the decrease in space complexity is proportional to D2, and that this factor the best possible. All of the bounds depend on the median of l(x) when x is drawn uniformly from the l2 unit sphere. The same median governs many phenomena in high-dimensional spaces, such as large-deviation bounds and the critical dimension in Dvoretzky's Theorem.

Given two finite partially ordered sets P and Q, we say that P is a chain minor of Q if there exists a partial function f from the elements of Q to the elements of P such that for every chain in P there is a chain $$C_Q$$ in Q with the property that f restricted to $$C_Q$$ is an isomorphism of chains C and $$C_Q$$ . We give an algorithm to decide whether a partially ordered set P is a chain minor of a partially ordered set Q, which runs in time $${\mathcal {O}}\left( |Q| \log |Q|\right) $$ for every fixed partially ordered set P. This solves an open problem from the monograph by Downey and Fellows (Parameterized complexity. Springer, New York, 1999) who asked whether the problem was fixed parameter tractable.

In dictionary learning we observe Y = AX + E for some Y in R^{n*p}, A in R^{m*n}, and X in R^{m*p}, where p >= max{n, m}, and typically m >=n. The matrix Y is observed, and A, X, E are unknown. Here E is a "noise" matrix of small norm, and X is column-wise sparse. The matrix A is referred to as a dictionary, and its columns as atoms. Then, given some small number p of samples, i.e. columns of Y , the goal is to learn the dictionary A up to small error, as well as the coefficient matrix X. In applications one could for example think of each column of Y as a distinct image in a database. The motivation is that in many applications data is expected to sparse when represented by atoms in the "right" dictionary A (e.g. images in the Haar wavelet basis), and the goal is to learn A from the data to then use it for other applications. Recently, the work of [Spielman/Wang/Wright, COLT'12] proposed the dictionary learning algorithm ER-SpUD with provable guarantees when E = 0 and m = n. That work showed that if X has independent entries with an expected Theta n non-zeroes per column for 1/n <~ Theta <~ 1/sqrt(n), and with non-zero entries being subgaussian, then for p >~ n^2 log^2 n with high probability ER-SpUD outputs matrices A', X' which equal A, X up to permuting and scaling columns (resp. rows) of A (resp. X). They conjectured that p >~ n log n suffices, which they showed was information theoretically necessary for any algorithm to succeed when Theta =~ 1/n. Significant progress toward showing that p >~ n log^4 n might suffice was later obtained in [Luh/Vu, FOCS'15]. In this work, we show that for a slight variant of ER-SpUD, p >~ n log(n/delta) samples suffice for successful recovery with probability 1 - delta. We also show that without our slight variation made to ER-SpUD, p >~ n^{1.99} samples are required even to learn A, X with a small success probability of 1/ poly(n). This resolves the main conjecture of [Spielman/Wang/Wright, COLT'12], and contradicts a result of [Luh/Vu, FOCS'15], which claimed that p >~ n log^4 n guarantees high probability of success for the original ER-SpUD algorithm.

Many important applications, including signal reconstruction, parameter estimation, and signal processing in a compressed domain, rely on a low-dimensional representation of the dataset that preserves all pairwise distances between the data points and leverages the inherent geometric structure that is typically present. Recently Hedge, Sankaranarayanan, Yin and Baraniuk [19] proposed the first data-aware near-isometric linear embedding which achieves the best of both worlds. However, their method NuMax does not scale to large-scale datasets. Our main contribution is a simple, data-aware, near-isometric linear dimensionality reduction method which significantly outperforms a state-of-the-art method [19] with respect to scalability while achieving high quality near-isometries. Furthermore, our method comes with strong worst-case theoretical guarantees that allow us to guarantee the quality of the obtained nearisometry. We verify experimentally the efficiency of our method on numerous real-world datasets, where we find that our method (9 hours) on medium scale datasets with 60000 datapoints in 784 dimensions. Finally, we use our method as a preprocessing step to increase the computational efficiency of a classification application and for speeding up approximate nearest neighbor queries.