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 R n with the promise that an α-fraction of points in T , where 0 < α < 1/2, are drawn from an unknown mean identity covariance Gaussian G, 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 R 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 ∈ Z + and 0 < α < 1/2. We design an algorithm with sample complexity O d (poly(n d /α)) and runtime O d (poly(n/α) d) that outputs a list of O (1/α) many candidate vectors such that with high probability one of the candidates is within ℓ 2-distance O d (α-1/(2d)) from the mean of G. The only previous algorithm for this problem achieved error Õ (α-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 (log 3/2 (1/α)), almost matching the information-theoretically optimal bound of Θ(log 1/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
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 q1,· · ·, 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), · · · , 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.
We prove new bounds on the average sensitivity of polynomial threshold functions. In particular, we show the average sensitivity of a polynomial threshold function of constant degree is not much more than the square root of the dimension of its space of definition. This bound amounts to a significant improvement over previous bounds, and in particular, for fixed degree provides the correct asymptotic exponent in the dimension.
Spatial ability is a well-known predictor of success in science, technology, engineering, and mathematics (STEM) fields. The purpose of this study was to investigate and understand the spatial strategies that were used by blind and low-vision (BLV) individuals as they solved problems on the tactile mental cutting test (TMCT), an instrument that was designed to measure the spatial ability of BLV audiences. The TMCT is an accessible adaptation of the older, 1938 version of the mental cutting test (MCT) that has been used extensively in spatial ability research. Additionally, this paper seeks to compare these strategies with existing strategies that have been investigated with sighted populations. The BLV community is underrepresented in engineering and in spatial ability research. By understanding how BLV students understand and solve spatial problems and concepts, educators can develop and enhance educational content that is relevant to this population. By incorporating perspectives from the BLV community and making STEM curricula accessible to this population, more BLV individuals may be encouraged to pursue STEM or engineering career pathways.