We derandomize G. Valiant's [J. ACM 62 (2015) Art. 13] subquadratic-time algorithm for finding outlier correlations in binary data. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same parameter range as Valiant's randomized algorithm, but the precise constants we save over quadratic scaling are more modest. Our main technical tool for derandomization is an explicit family of correlation amplifiers built via a family of zigzag-product expanders in Reingold, Vadhan, and Wigderson [Ann. of Math. 155 (2002) 157--187]. We say that a function @math is a correlation amplifier with threshold @math , error @math , and strength @math an even positive integer if for all pairs of vectors @math it holds that (i) @math implies @math ; and (ii) @math implies @math .
With no information on @math , the trivial solution is to enumerate all @math subsets of @math to locate the support @math . Blum, Kalai, and Wasserman @cite_23 provide a non-trivial solution which runs in time and sample complexity @math for any positive integers @math with @math ; this is @math when @math is a constant independent of @math . If we assert that @math is a constant independent of @math , the trivial complexity drops from exponential to @math , and non-trivial speed-ups seek to lower the coefficient @math of @math in the exponent. Randomized solutions for constant @math include Valiant's breakthrough algorithm @cite_27 and our subsequent randomized improvement @cite_15 which runs in time @math for any constant @math .
@cite_27 @cite_23 @cite_15
2263882035 2065151783 2268968630
Given a set of n d-dimensional Boolean vectors with the promise that the vectors are chosen uniformly at random with the exception of two vectors that have Pearson correlation coefficient ρ (Hamming distance dċ 1−ρf2), how quickly can one find the two correlated vectorsq We present an algorithm which, for any constant e>0, and constant ρ>0, runs in expected time O(n5mωf4mωpe pnd) Applications and extensions of this basic algorithm yield significantly improved algorithms for several other problems. Approximate Closest Pair. For any sufficiently small constant e>0, given n d-dimensional vectors, there exists an algorithm that returns a pair of vectors whose Euclidean (or Hamming) distance differs from that of the closest pair by a factor of at most 1pe, and runs in time O(n2mΘ(se)). The best previous algorithms (including Locality Sensitive Hashing) have runtime O(n2mO(e)). Learning Sparse Parities with Noise. Given samples from an instance of the learning parities with noise problem where each example has length n, the true parity set has size at most k « n, and the noise rate is η, there exists an algorithm that identifies the set of k indices in time nωpef3 k poly(1f1m2η) 0.4), improves upon the results of [2011] that give a runtime of n(1p(2 η)2 p o(1))kf2 poly(1f1m2η). Learning k-Juntas with Noise. Given uniformly random length n Boolean vectors, together with a label, which is some function of just k « n of the bits, perturbed by noise rate η, return the set of relevant indices. Leveraging the reduction of [2009], our result for learning k-parities implies an algorithm for this problem with runtime nωpef3 k poly(1f1m2η) Learning k-Juntas without Noise. Given uniformly random length n Boolean vectors, together with a label, which is some function of k « n of the bits, return the set of relevant indices. Using a modification of the algorithm of [2004], and employing our algorithm for learning sparse parities with noise via the reduction of [2009], we obtain an algorithm for this problem with runtime nωp ef4 k poly(n) We describe a slightly subexponential time algorithm for learning parity functions in the presence of random classification noise, a problem closely related to several cryptographic and coding problems. Our algorithm runs in polynomial time for the case of parity functions that depend on only the first O(log n log log n) bits of input, which provides the first known instance of an efficient noise-tolerant algorithm for a concept class that is not learnable in the Statistical Query model of Kearns [1998]. Thus, we demonstrate that the set of problems learnable in the statistical query model is a strict subset of those problems learnable in the presence of noise in the PAC model.In coding-theory terms, what we give is a poly(n)-time algorithm for decoding linear k × n codes in the presence of random noise for the case of k = c log n log log n for some c > 0. (The case of k = O(log n) is trivial since one can just individually check each of the 2k possible messages and choose the one that yields the closest codeword.)A natural extension of the statistical query model is to allow queries about statistical properties that involve t-tuples of examples, as opposed to just single examples. The second result of this article is to show that any class of functions learnable (strongly or weakly) with t-wise queries for t = O(log n) is also weakly learnable with standard unary queries. Hence, this natural extension to the statistical query model does not increase the set of weakly learnable functions. We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d, and we are asked to find all the outlier pairs of vectors whose inner product is at least ρ in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most τ in absolute value for some constants 0 Improving on an algorithm of G. Valiant [FOCS 2012; J. ACM 2015], we present a randomized algorithm that for Boolean inputs ( --1, 1 -valued data normalized to unit Euclidean length) runs in time [EQUATION] where 0 [EQUATION] and in time [EQUATION] where 2 ≤ ω