Search

We study the problem of PAC learning halfspaces on $\mathbb{R}^d$ with Massart noise under the Gaussian distribution. In the Massart model, an adversary is allowed to flip the label of each point $\mathbf{x}$ with unknown probability $\eta(\mathbf{x}) \leq \eta$, for some parameter $\eta \in [0,1/2]$. The goal is to find a hypothesis with misclassification error of $\mathrm{OPT} + \epsilon$, where $\mathrm{OPT}$ is the error of the target halfspace. This problem had been previously studied under two assumptions: (i) the target halfspace is homogeneous (i.e., the separating hyperplane goes through the origin), and (ii) the parameter $\eta$ is strictly smaller than $1/2$. Prior to this work, no nontrivial bounds were known when either of these assumptions is removed. We study the general problem and establish the following: For $\eta, Comment: Revised presentation

We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. Specifically, we are given a set $T$ of $n$ points in $\mathbb{R}^d$ and a parameter $0< \alpha 0$. All prior algorithms for this problem had additional polynomial factors in $\frac 1 \alpha$. We leverage this result, together with additional techniques, to obtain the first almost-linear time algorithms for clustering mixtures of $k$ separated well-behaved distributions, nearly-matching the statistical guarantees of spectral methods. Prior clustering algorithms inherently relied on an application of $k$-PCA, thereby incurring runtimes of $\Omega(n d k)$. This marks the first runtime improvement for this basic statistical problem in nearly two decades. The starting point of our approach is a novel and simpler near-linear time robust mean estimation algorithm in the $\alpha \to 1$ regime, based on a one-shot matrix multiplicative weights-inspired potential decrease. We crucially leverage this new algorithmic framework in the context of the iterative multi-filtering technique of Diakonikolas et al. '18, '20, providing a method to simultaneously cluster and downsample points using one-dimensional projections -- thus, bypassing the $k$-PCA subroutines required by prior algorithms., Comment: 64 pages, 1 figure. v2 improves results on bounded-covariance clustering, polishes exposition

Given a finite set $X\subset \mathbb{R}^{d}$ and a binary linear classifier $c:\mathbb{R}^{d}\rightarrow\{0,1\}$ , how many queries of the form $c(x)$ are required to learn the label of every point in $X$ ? Known as point location, this problem has inspired over 35 years of research in the pursuit of an optimal algorithm. Building on the prior work of Kane, Lovett, and Moran (ICALP 2018), we provide the first nearly optimal solution, a randomized linear decision tree of depth $\tilde{O}(d\log(\vert X\vert))$ , improving on the previous best of $\tilde{O}(\overline{d}^{2}\log(\vert X\vert))$ from Ezra and Sharir (Discrete and Computational Geometry, 2019). As a corollary, we also provide the first nearly optimal algorithm for actively learning halfspaces in the membership query model. En route to these results, building on the work of Carlen, Lieb, and Loss (J. Geometric Analysis 2004), as well as Dvir, Saraf, and Wigderson (STOC 2014), we prove a novel characterization of Barthe's Theorem (Inventiones Mathematicae, 1998) of independent interest. In particular, we show that $X$ may be transformed into approximate isotropic position if and only if there exists no $k$ -dimensional subspace with more than a $k/d$ -fraction of $X$ , and provide a similar characterization for exact isotropic position. The below is an extended abstract. The full work can be found at https://arxiv.org/abs/2004.11380

We study the problem of list-decodable (robust) Gaussian mean estimation and the related problem of learning mixtures of separated spherical Gaussians. In the former problem, we are given a set T of points in n with the promise that an α-fraction of points in T, where 0G, and no assumptions are made about the remaining points. The goal is to output a small list of candidate vectors with the guarantee that at least one of the candidates is close to the mean of G. In the latter problem, we are given samples from a k-mixture of spherical Gaussians on n and the goal is to estimate the unknown model parameters up to small accuracy. We develop a set of techniques that yield new efficient algorithms with significantly improved guarantees for these problems. Specifically, our main contributions are as follows: List-Decodable Mean Estimation. Fix any d ∈ + and 0Od ((nd/α)) and runtime Od ((n/α)d) that outputs a list of O(1/α) many candidate vectors such that with high probability one of the candidates is within l2-distance Od(α−1/(2d)) from the mean of G. The only previous algorithm for this problem achieved error O(α−1/2) under second moment conditions. For d = O(1/), where >0 is a constant, our algorithm runs in polynomial time and achieves error O(α). For d = Θ(log(1/α)), our algorithm runs in time (n/α)O(log(1/α)) and achieves error O(log3/2(1/α)), almost matching the information-theoretically optimal bound of Θ(log1/2(1/α)) that we establish. We also give a Statistical Query (SQ) lower bound suggesting that the complexity of our algorithm is qualitatively close to best possible. Learning Mixtures of Spherical Gaussians. We give a learning algorithm for mixtures of spherical Gaussians, with unknown spherical covariances, that succeeds under significantly weaker separation assumptions compared to prior work. For the prototypical case of a uniform k-mixture of identity covariance Gaussians we obtain the following: For any >0, if the pairwise separation between the means is at least Ω(k+√log(1/δ)), our algorithm learns the unknown parameters within accuracy δ with sample complexity and running time (n, 1/δ, (k/)1/). Moreover, our algorithm is robust to a small dimension-independent fraction of corrupted data. The previously best known polynomial time algorithm required separation at least k1/4 (k/δ). Finally, our algorithm works under separation of O(log3/2(k)+√log(1/δ)) with sample complexity and running time (n, 1/δ, klogk). This bound is close to the information-theoretically minimum separation of Ω(√logk). Our main technical contribution is a new technique, using degree-d multivariate polynomials, to remove outliers from high-dimensional datasets where the majority of the points are corrupted.

We give a general unified method that can be used for $L_1$ {\em closeness testing} of a wide range of univariate structured distribution families. More specifically, we design a sample optimal and computationally efficient algorithm for testing the equivalence of two unknown (potentially arbitrary) univariate distributions under the $\mathcal{A}_k$-distance metric: Given sample access to distributions with density functions $p, q: I \to \mathbb{R}$, we want to distinguish between the cases that $p=q$ and $\|p-q\|_{\mathcal{A}_k} \ge \epsilon$ with probability at least $2/3$. We show that for any $k \ge 2, \epsilon>0$, the {\em optimal} sample complexity of the $\mathcal{A}_k$-closeness testing problem is $\Theta(\max\{ k^{4/5}/\epsilon^{6/5}, k^{1/2}/\epsilon^2 \})$. This is the first $o(k)$ sample algorithm for this problem, and yields new, simple $L_1$ closeness testers, in most cases with optimal sample complexity, for broad classes of structured distributions., Comment: 27 pages, to appear in FOCS'15

© 2015 Elsevier Inc. All rights reserved. We prove the conjectured limiting normality for the number of crossings of a uniformly chosen set partition of [n] = {1,2,⋯,n}. The arguments use a novel stochastic representation and are also used to prove central limit theorems for the dimension index and the number of levels.

We prove a structural result for degree-$d$ polynomials. In particular, we show that any degree-$d$ polynomial, $p$ can be approximated by another polynomial, $p_0$, which can be decomposed as some function of polynomials $q_1, \ldots, q_m$ with $q_i$ normalized and $m=O_d(1)$, so that if $X$ is a Gaussian random variable, the probability distribution on $(q_1(X), \ldots, q_m(X))$ does not have too much mass in any small box. Using this result, we prove improved versions of a number of results about polynomial threshold functions, including producing better pseudorandom generators, obtaining a better invariance principle, and proving improved bounds on noise sensitivity.

Our main result establishes Andrews’ conjecture for the asymptotic of the generating function for the number of integer partitions of$n$without$k$consecutive parts. The methods we develop are applicable in obtaining asymptotics for stochastic processes that avoid patterns; as a result they yield asymptotics for the number of partitions that avoid patterns.Holroyd, Liggett, and Romik, in connection with certain bootstrap percolation models, introduced the study of partitions without$k$consecutive parts. Andrews showed that when$k=2$, the generating function for these partitions is a mixed-mock modular form and, thus, has modularity properties which can be utilized in the study of this generating function. For$k>2$, the asymptotic properties of the generating functions have proved more difficult to obtain. Using$q$-series identities and the$k=2$case as evidence, Andrews stated a conjecture for the asymptotic behavior. Extensive computational evidence for the conjecture in the case$k=3$was given by Zagier.This paper improved upon early approaches to this problem by identifying and overcoming two sources of error. Since the writing of this paper, a more precise asymptotic result was established by Bringmann, Kane, Parry, and Rhoades. That approach uses very different methods.

We prove a new bound on the average sensitivity of polynomial threshold functions. In particular we show that a polynomial threshold function of degree $d$ in at most $n$ variables has average sensitivity at most $\sqrt{n}(\log(n))^{O(d\log(d))}2^{O(d^2\log(d)}$. For fixed $d$ the exponent in terms of $n$ in this bound is known to be optimal. This bound makes significant progress towards the Gotsman-Linial Conjecture which would put the correct bound at $\Theta(d\sqrt{n})$.

We develop and analyze a new family of pseudorandom generators for polynomial threshold functions with respect to the Gaussian distribution. In particular, for any fixed degree we develop a generator whose seed length is subpolynomial in the error parameter, epsilon. We get particularly nice results for degree 1 and degree 2 threshold functions, in which cases our seed length is O(log(n) + log^{3/2}(1/epsilon)) and exp(O~(log^{2/3}(1/epsilon))), respectively.

For relatively prime positive integers $u_0$ and $r$, we consider the least common multiple $L_n:=\mathrm{lcm}(u_0,u_1,\ldots, u_n)$ of the finite arithmetic progression $\{u_k:=u_0+kr\}_{k=0}^n$. We derive new lower bounds on $L_n$ which improve upon those obtained previously when either $u_0$ or $n$ is large. When $r$ is prime, our best bound is sharp up to a factor of $n+1$ for $u_0$ properly chosen, and is also nearly sharp as $n\to\infty$., Comment: 10 pages

We establish upper and lower bounds for the number of solutions to A + B = C in relatively prime integers A , B , C with max ⁡ ( | A | , | B | , | C | ) ≤ N and Rad ( A ) ≤ | A | a , Rad ( B ) ≤ | B | b , Rad ( C ) ≤ | C | c , valid when 0 a , b , c ≤ 1 . The lower bound is Ω ( N a + b + c − 1 ( log ⁡ N ) − 2 ) , and the upper bound is of the form O ( N a + b + c − 1 + ϵ + N 1 + ϵ ) , for any fixed ϵ > 0 . In particular, these bounds match up to N ϵ factors so long as a + b + c ≥ 2 , verifying a conjecture or Mazur in this parameter range.

We discuss a psuedorandom generator to $\epsilon$-fool degree-d polynomial threshold functions with respect to the Gaussian distribution with seed length $2^O_c(d)\log(n) \epsilon^{-4-c}$. Our analysis involves several new ideas including what we term the "noisy derivative" of a function and a stronger version of standard anticoncentration results.

We extend known results on the number of solutions to a linear equation in at least three prime numbers when the primes involved are required to lie in specified Chebotarev classes. We prove asymptotic results similar to previous ones only now taking into account corrections coming form the Chebotarev Density Theorem and Global Class Field Theory. We then apply these results to find elliptic curves whose discriminants split completely of a given number field.

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of k-wise independent distributions, we obtain a broad class of explicit generators that epsilon-fool the class of degree-2 threshold functions with seed length log(n)*poly(1/epsilon). Our approach is quite robust: it easily extends to yield that the intersection of any constant number of degree-2 threshold functions is epsilon-fooled by poly(1/epsilon)-wise independence. Our results also hold if the entries of x are k-wise independent standard normals, implying for example that bounded independence derandomizes the Goemans-Williamson hyperplane rounding scheme. To achieve our results, we introduce a technique we dub multivariate FT-mollification, a generalization of the univariate form introduced by Kane et al. (SODA 2010) in the context of streaming algorithms. Along the way we prove a generalized hypercontractive inequality for quadratic forms which takes the operator norm of the associated matrix into account. These techniques may be of independent interest., Comment: Using v1 numbering: removed Lemma G.5 from the Appendix (it was wrong). Net effect is that Theorem G.6 reduces the m^6 dependence of Theorem 8.1 to m^4, not m^2