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 .
cor:lightbulb extends to parity functions of larger (constant) weight in the presence of noise (cf. @cite_24 @cite_15 @cite_27 ). This generalized version of the problem is as follows.
@cite_24 @cite_27 @cite_15
1915272284 2263882035 2268968630
We consider the problem of learning sparse parities in the presence of noise. For learning parities on r out of n variables, we give an algorithm that runs in time poly (log 1 δ, 1 1-2η)n(1+(2η)2+o(1))r 2 and uses only r log(n δ)ω(1) (1-2η)2 samples in the random noise setting under the uniform distribution, where η is the noise rate and δ is the confidence parameter. From previously known results this algorithm also works for adversarial noise and generalizes to arbitrary distributions. Even though efficient algorithms for learning sparse parities in the presence of noise would have major implications to learning other hypothesis classes, our work is the first to give a bound better than the brute-force O(nr). As a consequence, we obtain the first nontrivial bound for learning r-juntas in the presence of noise, and also a small improvement in the complexity of learning DNF, under the uniform distribution. 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 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 ≤ ω