Rocco A. Servedio

STOC Conference 2025 Conference Paper

DNF Learning via Locally Mixing Random Walks

• Josh Alman
• Shivam Nadimpalli
• Shyamal Patel
• Rocco A. Servedio

We give two results on PAC learning DNF formulas using membership queries in the challenging “distribution-free” learning framework, where learning algorithms must succeed for an arbitrary and unknown distribution over {0,1} n . (1) We first give a quasi-polynomial time “list-decoding” algorithm for learning a single term of an unknown DNF formula. More precisely, for any target s -term DNF formula f = T 1 ∨ ⋯ ∨ T s over {0,1} n and any unknown distribution D over {0,1} n , our algorithm, which uses membership queries and random examples from D , runs in quasipoly( n , s ) time and outputs a list L of candidate terms such that with high probability some term T i of f belongs to L . (2) We then use result (1) to give a quasipoly( n , s )-time algorithm, in the distribution-free PAC learning model with membership queries, for learning the class of size- s DNFs in which all terms have the same size. Our algorithm learns using a DNF hypothesis. The key tool used to establish result (1) is a new result on “locally mixing random walks,” which, roughly speaking, shows that a random walk on a graph that is covered by a small number of expanders has a non-negligible probability of mixing quickly in a subset of these expanders.

FOCS Conference 2025 Conference Paper

Faster Exact Learning of k-Term DNFs with Membership and Equivalence Queries

• Josh Alman
• Shivam Nadimpalli
• Shyamal Patel
• Rocco A. Servedio

In 1992 Blum and Rudich [1] gave an algorithm that uses membership and equivalence queries to learn k-term DNF formulas over $\{0, 1\}^{n}$ in time $\operatorname{poly}\left(n, 2^{k}\right)$, improving on the naive $O\left(n^{k}\right)$ running time that can be achieved without membership queries [2]. Since then, many alternative algorithms [3]–[6] have been given which also achieve runtime poly $\left(n, 2^{k}\right)$. We give an algorithm that uses membership and equivalence queries to learn k-term DNF formulas in time poly $(n) \cdot 2^{\tilde{O}(\sqrt{k})}$. This is the first improvement for this problem since the original work of Blum and Rudich [1]. Our approach employs the Winnow2 algorithm for learning linear threshold functions over an enhanced feature space which is adaptively constructed using membership queries. It combines a strengthened version of a technique that effectively reduces the length of DNF terms from the original work of [1] with a range of additional algorithmic tools (attribute-efficient learning algorithms for low-weight linear threshold functions and techniques for finding relevant variables from junta testing) and analytic ingredients (extremal polynomials and noise operators) that are novel in the context of query-based DNF learning.

SODA Conference 2025 Conference Paper

Lower Bounds for Convexity Testing

• Xi Chen 0001
• Anindya De
• Shivam Nadimpalli
• Rocco A. Servedio
• Erik Waingarten

SODA Conference 2025 Conference Paper

Relative-error monotonicity testing

• Xi Chen 0001
• Anindya De
• Yizhi Huang
• Yuhao Li 0002
• Shivam Nadimpalli
• Rocco A. Servedio
• Tianqi Yang

STOC Conference 2024 Conference Paper

Detecting Low-Degree Truncation

• Anindya De
• Huan Li 0002
• Shivam Nadimpalli
• Rocco A. Servedio

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution D over ℝ n and a collection of data points in ℝ n , distinguish between the two possibilities that (i) the data was drawn from D , versus (ii) the data was drawn from D | S , i.e. from D subject to truncation by an unknown truncation set S ⊆ ℝ n . We study this problem in the setting where D is a high-dimensional i.i.d. product distribution and S is an unknown degree- d polynomial threshold function (one of the most well-studied types of Boolean-valued function over ℝ n ). Our main results are an efficient algorithm when D is a hypercontractive distribution, and a matching lower bound: 1. For any constant d , we give a polynomial-time algorithm which successfully distinguishes D from D | S using O ( n d /2 ) samples (subject to mild technical conditions on D and S ); 2. Even for the simplest case of D being the uniform distribution over {±1} n , we show that for any constant d , any distinguishing algorithm for degree- d polynomial threshold functions must use Ω( n d /2 ) samples.

FOCS Conference 2024 Conference Paper

Gaussian Approximation of Convex Sets by Intersections of Halfspaces

• Anindya De
• Shivam Nadimpalli
• Rocco A. Servedio

We study the approximability of general convex sets in $\mathbb{R}^{n}$ by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution and the complexity of an approximation is the number of halfspaces used. While a large body of research has considered the approximation of convex sets by intersections of halfspaces under distance metrics such as the Lebesgue measure and Hausdorff distance, prior to our work there has not been a systematic study of convex approximation under the Gaussian distribution. We establish a range of upper and lower bounds, both for general convex sets and for specific natural convex sets that are of particular interest. Our results demonstrate that the landscape of approximation is intriguingly different under the Gaussian distribution versus previously studied distance measures. Our results are proved using techniques from many different areas. These include classical results on convex polyhedral approximation, Cramér-type bounds on large deviations from probability theory, and-perhaps surprisingly-a range of topics from computational complexity, including computational learning theory, unconditional pseudorandomness, and the study of influences and noise sensitivity in the analysis of Boolean functions.

SODA Conference 2024 Conference Paper

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas

• Xi Chen 0001
• Anindya De
• Yuhao Li 0002
• Shivam Nadimpalli
• Rocco A. Servedio

SODA Conference 2023 Conference Paper

Approximate Trace Reconstruction from a Single Trace

• Xi Chen 0001
• Anindya De
• Chin Ho Lee
• Rocco A. Servedio
• Sandip Sinha

The well-known trace reconstruction problem is the problem of inferring an unknown source string x ∈ {0, 1} n from independent “traces”, i. e. copies of x that have been corrupted by a δ-deletion channel which independently deletes each bit of x with probability δ and concatenates the surviving bits. The current paper considers the extreme data-limited regime in which only a single trace is provided to the reconstruction algorithm. In this setting exact reconstruction is of course impossible, and the question is to what accuracy the source string x can be approximately reconstructed. We give a detailed study of this question, providing algorithms and lower bounds for the high, intermediate, and low deletion rate regimes in both the worst-case ( x is arbitrary) and average-case ( x is drawn uniformly from {0, 1} n ) models. In several cases the lower bounds we establish are matched by computationally efficient algorithms that we provide. We highlight our results for the high deletion rate regime: roughly speaking, they show that • Having access to a single trace is already quite useful for worst-case trace reconstruction: an efficient algorithm can perform much more accurate reconstruction, given one trace that is even only a few bits long, than it could given no traces at all. But in contrast • in the average-case setting, having access to a single trace is provably not very useful: no algorithm, computationally efficient or otherwise, can achieve significantly higher accuracy given one trace that is o ( n ) bits long than it could with no traces. * The full version of the paper can be accessed at https: //arxiv. org/abs/2211. 03292

FOCS Conference 2023 Conference Paper

Explicit orthogonal and unitary designs

• Ryan O'Donnell
• Rocco A. Servedio
• Pedro Paredes 0002

We give a strongly explicit construction of ϵ approximate k-designs for the orthogonal group O(N) and the unitary group U(N), for $N=2^{n}$. Our designs are of cardinality $\operatorname{poly}(N^{k}/\epsilon)$ (equivalently, they have seed length $O(nk+\log(1/\epsilon)))$; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.

SODA Conference 2023 Conference Paper

Testing Convex Truncation

• Anindya De
• Shivam Nadimpalli
• Rocco A. Servedio

We study the basic statistical problem of testing whether normally distributed n -dimensional data has been truncated, i. e. altered by only retaining points that lie in some unknown truncation set S ⊆ ℝ n. As our main algorithmic results 1. We give a computationally efficient O(n )-sample algorithm that can distinguish the standard normal distribution N (0, I n ) from N (0, I n ) conditioned on an unknown and arbitrary convex set S. 2. We give a different computationally efficient O ( n )-sample algorithm that can distinguish N (0, I n ) from N (0, I n ) conditioned on an unknown and arbitrary mixture of symmetric convex sets. These results stand in sharp contrast with known results for learning or testing convex bodies with respect to the normal distribution or learning convex-truncated normal distributions, where state-of-the-art algorithms require essentially samples. An easy argument shows that no finite number of samples suffices to distinguish N (0, I n ) from an unknown and arbitrary mixture of general (not necessarily symmetric) convex sets, so no common generalization of results (1) and (2) above is possible. We also prove lower bounds on the sample complexity of distinguishing algorithms (computationally efficient or otherwise) for various classes of convex truncations; in some cases these lower bounds match our algorithms up to logarithmic or even constant factors.

SODA Conference 2022 Conference Paper

Approximating Sumset Size

• Anindya De
• Shivam Nadimpalli
• Rocco A. Servedio

Given a subset A of the n -dimensional Boolean hypercube, the sumset A+A is the set { a + a′: a, a′ ∊ A } where addition is in. Sumsets play an important role in additive combinatorics, where they feature in many central results of the field. The main result of this paper is a sublinear-time algorithm for the problem of sumset size estimation. In more detail, our algorithm is given oracle access to (the indicator function of) an arbitrary and an accuracy parameter ∊ > 0, and with high probability it outputs a value 0 ≤ v ≤ 1 that is ± ∊ -close to Vol ( A′ + A′ ) for some perturbation A′ ⊆ A of A satisfying Vol ( A \ A′ ) ≤ ∊. It is easy to see that without the relaxation of dealing with A′ rather than A, any algorithm for estimating Vol ( A + A ) to any nontrivial accuracy must make 2 Ω(n ) queries. In contrast, we give an algorithm whose query complexity depends only on ∊ and is completely independent of the ambient dimension n.

SODA Conference 2022 Conference Paper

Average-Case Subset Balancing Problems

• Xi Chen 0001
• Yaonan Jin
• Tim Randolph 0001
• Rocco A. Servedio

Given a set of n input integers, the Equal Subset Sum problem asks us to find two distinct subsets with the same sum. In this paper we present an algorithm that runs in time O ∗(3 0. 387 n ) in the average case, significantly improving over the O ∗(3 0. 488 n ) running time of the best known worst-case algorithm [MNPW19] and the Meet-in-the-Middle benchmark of O ∗(3 0. 5 n ). Our algorithm generalizes to a number of related problems, such as the “Generalized Equal Subset Sum” problem, which asks us to assign a coefficient c i from a set C to each input number x i such that Σ i c i x i = 0. Our algorithm for the average-case version of this problem runs in time for some positive constant c 0, whenever C = {0, ± 1, …, ± d} or {±1, …, ± d } for some positive integer d (with runtime O ∗( |C| 0. 45 n ) when |C| < 10). Our results extend to the problem of finding “nearly balanced” solutions in which the target is a not-too-large nonzero offset τ. Our approach relies on new structural results that characterize the probability that Σ i c i x i = τ has a solution c ∊ C n when x i 's are chosen randomly; these results may be of independent interest. Our algorithm is inspired by the “representation technique” introduced by Howgrave-Graham and Joux [HGJ10]. This requires several new ideas to overcome preprocessing hurdles that arise in the representation framework, as well as a novel application of dynamic programming in the solution recovery phase of the algorithm.

SODA Conference 2022 Conference Paper

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces

• Xi Chen 0001
• Anindya De
• Chin Ho Lee
• Rocco A. Servedio
• Sandip Sinha

In the standard trace reconstruction problem, the goal is to exactly reconstruct an unknown source string x ∊ {0, 1} n from independent “traces”, which are copies of x that have been corrupted by a δ -deletion channel which independently deletes each bit of x with probability δ and concatenates the surviving bits. We study the approximate trace reconstruction problem, in which the goal is only to obtain a high-accuracy approximation of x rather than an exact reconstruction. We give an efficient algorithm, and a near-matching lower bound, for approximate reconstruction of a random source string x ∊ {0, 1} n from few traces. Our main algorithmic result is a polynomial-time algorithm with the following property: for any deletion rate 0 < δ < 1 (which may depend on n ), for almost every source string x ∊ {0, 1} n, given any number M ≤ Θ(1/ δ ) of traces from Del δ (x), the algorithm constructs a hypothesis string that has edit distance at most n · ( δM ) Ω ( M ) from x. We also prove a near-matching information-theoretic lower bound showing that given M ≤ Θ(1/ δ ) traces from Del δ (x) for a random n -bit string x, the smallest possible expected edit distance that any algorithm can achieve, regardless of its running time, is n · ( δM ) O (M).

SODA Conference 2021 Conference Paper

Polynomial-time trace reconstruction in the smoothed complexity model

• Xi Chen 0001
• Anindya De
• Chin Ho Lee
• Rocco A. Servedio
• Sandip Sinha

In the trace reconstruction problem, an unknown source string x ∊ {0, 1} n is sent through a probabilistic deletion channel which independently deletes each bit with probability δ and concatenates the surviving bits, yielding a trace of x. The problem is to reconstruct x given independent traces. This problem has received much attention in recent years both in the worst-case setting where x may be an arbitrary string in {0, 1} n [6, 19, 7, 8, 4] and in the average-case setting where x is drawn uniformly at random from {0, 1} n [21, 9, 8, 4]. This paper studies trace reconstruction in the smoothed analysis setting, in which a “worst-case” string x worst is chosen arbitrarily from {0, 1} n, and then a perturbed version x of x worst is formed by independently replacing each coordinate by a uniform random bit with probability σ. The problem is to reconstruct x given independent traces from it. Our main result is an algorithm which, for any constant perturbation rate 0 < σ < 1 and any constant deletion rate 0 < δ < 1, uses poly( n ) running time and traces and succeeds with high probability in reconstructing the string x. This stands in contrast with the worst-case version of the problem, for which the best known sample complexity is exp( Õ ( n 1/5 )) [5], a recent improvement on exp( O ( n 1/3 )) [6, 19]. Our approach is based on reconstructing x from the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new poly( n )-time procedure for reconstructing the multiset of all O (log n )-length subwords of any source string x ∊ {0, 1} n given access to traces of x.

SODA Conference 2020 Conference Paper

A Lower Bound on Cycle-Finding in Sparse Digraphs

• Xi Chen 0001
• Tim Randolph 0001
• Rocco A. Servedio
• Timothy Sun

STOC Conference 2020 Conference Paper

Fooling Gaussian PTFs via local hyperconcentration

• Ryan O'Donnell
• Rocco A. Servedio
• Li-Yang Tan

We give a pseudorandom generator that fools degree- d polynomial threshold functions over n -dimensional Gaussian space with seed length d O (log d ) · log n . All previous generators had a seed length with at least a 2 d dependence on d . The key new ingredient is our Local Hyperconcentration Theorem , which shows that every degree- d Gaussian polynomial is hyperconcentrated almost everywhere at scale d − O (log d ) .

SODA Conference 2020 Conference Paper

Learning from satisfying assignments under continuous distributions

• Clément L. Canonne
• Anindya De
• Rocco A. Servedio

JMLR Journal 2020 Journal Article

Learning Sums of Independent Random Variables with Sparse Collective Support

• Anindya De
• Philip M. Long
• Rocco A. Servedio

We study the learnability of sums of independent integer random variables given a bound on the size of the union of their supports. For $\mathcal{A} \subset \mathbb{Z}_{+}$, a {sum of independent random variables with collective support $\mathcal{A}$} (called an $\mathcal{A}$-sum in this paper) is a distribution $\mathbf{S} = \mathbf{X}_1 + \cdots + \mathbf{X}_N$ where the $\mathbf{X}_i$'s are mutually independent (but not necessarily identically distributed) integer random variables with $\cup_i \mathrm{supp}(\mathbf{X}_i) \subseteq \mathcal{A}.$ We give two main algorithmic results for learning such distributions. First, for the case $| \mathcal{A} | = 3$, we give an algorithm for learning an unknown $\mathcal{A}$-sum to accuracy $\epsilon$ using $\mathrm{poly}(1/\epsilon)$ samples and running in time $\mathrm{poly}(1/\epsilon)$, independent of $N$ and of the elements of $\mathcal{A}$. Second, for an arbitrary constant $k \geq 4$, if $\mathcal{A} = \{ a_1,...,a_k\}$ with $0 \leq a_1 0$. [abs] [ pdf ][ bib ] &copy JMLR 2020. ( edit, beta )

STOC Conference 2020 Conference Paper

Testing noisy linear functions for sparsity

• Xue Chen 0001
• Anindya De
• Rocco A. Servedio

We consider the following basic inference problem: there is an unknown high-dimensional vector w ∈ ℝ n , and an algorithm is given access to labeled pairs ( x , y ) where x ∈ ℝ n is a measurement and y = w · x + noise . What is the complexity of deciding whether the target vector w is (approximately) k -sparse? The recovery analogue of this problem — given the promise that w is sparse, find or approximate the vector w — is the famous sparse recovery problem, with a rich body of work in signal processing, statistics, and computer science.

FOCS Conference 2019 Conference Paper

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel

• Frank Ban
• Xi Chen 0001
• Adam Freilich
• Rocco A. Servedio
• Sandip Sinha

Population recovery is the problem of learning an unknown distribution over an unknown set of n-bit strings, given access to independent draws from the distribution that have been independently corrupted according to some noise channel. Recent work has intensively studied such problems both for the bit-flip noise channel and for the erasure noise channel. In this paper we initiate the study of population recovery under the deletion channel, in which each bit b is independently deleted with some fixed probability and the surviving bits are concatenated and transmitted. This is a far more challenging noise model than bit-flip~noise or erasure noise; indeed, even the simplest case in which the population is of size 1 (corresponding to a trivial probability distribution supported on a single string) corresponds to the trace reconstruction problem, which is a challenging problem that has received much recent attention. In this work we give algorithms and lower bounds for population recovery under the deletion channel when the population size is some value ℓ > 1. As our main sample complexity upper bound, we show that for any population size ℓ = o(log n / log log n), a population of ℓ strings from {o, 1} n can be learned under deletion channel noise using 2 n(1/2+o(1)) samples. On the lower bound side, we show that at least n Ω(ℓ) samples are required to perform population recovery under the deletion channel when the population size is ℓ, for all ℓ ≤ n 1/2-ε. Our upper bounds are obtained via a robust multivariate generalization of a polynomial-based analysis, due to Krasikov and Roddity [KR97], of how the k-deck of a bit-string uniquely identifies the string; this is a very different approach from recent algorithms for trace reconstruction (the ℓ = 1 case). Our lower bounds build on moment-matching results of Roos[Roos: 00] and Daskalakis and Papadimitriou[DP15].

STOC Conference 2019 Conference Paper

Fooling polytopes

• Ryan O'Donnell
• Rocco A. Servedio
• Li-Yang Tan

SODA Conference 2019 Conference Paper

Pseudorandomness for read-k DNF formulas

• Rocco A. Servedio
• Li-Yang Tan

STOC Conference 2018 Conference Paper

Distribution-free junta testing

• Zhengyang Liu 0002
• Xi Chen 0001
• Rocco A. Servedio
• Ying Sheng 0004
• Jinyu Xie

We study the problem of testing whether an unknown n -variable Boolean function is a k -junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0,1} n . Our first main result is that distribution-free k -junta testing can be performed, with one-sided error, by an adaptive algorithm that uses Õ( k 2 )/є queries (independent of n ). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free k -junta testing algorithm must make Ω(2 k /3 ) queries even to test to accuracy є=1/3. These bounds establish that while the optimal query complexity of non-adaptive k -junta testing is 2 Θ( k ) , for adaptive testing it is poly( k ), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

FOCS Conference 2018 Conference Paper

Learning Sums of Independent Random Variables with Sparse Collective Support

• Anindya De
• Philip M. Long
• Rocco A. Servedio

We study the learnability of sums of independent integer random variables given a bound on the size of the union of their supports. For a A ⊂Z + ubset A of non-negative integers, a sum of independent random variables with collective support A (called an "A-sum" in this paper) is a distribution S = X 1 +. .. + X N where the X i 's are mutually independent (but not necessarily identically distributed) integer random variables all of whose supports are contained in A. We give two main algorithmic results for learning such distributions: 1) For the case |A|=3, we give an algorithm for learning A-sums to accuracy ε that uses poly(1/ε) samples and runs in time poly(1/ε), independent of N and of the elements of A. 2) For an arbitrary constant k>=4, if A = {a 1, .. ., a k } with 0 1 k, we give an algorithm that uses poly(1/ε)*log log a k samples (independent of N) and runs in time poly(1/ε, log a k ). We prove an essentially matching lower bound: if |A| = 4, then any algorithm must use Ω(log log a 4 ) samples even for learning to constant accuracy. We also give similar-in-spirit (but quantitatively very different) algorithmic results, and essentially matching lower bounds, for the case in which A is not known to the learner. Our learning algorithms employ new limit theorems which may be of independent interest. Our algorithms and lower bounds together settle the question of how the sample complexity of learning sums of independent integer random variables scales with the elements in the union of their supports, both in the known-support and unknown-support settings. Finally, all our algorithms easily extend to the "semi-agnostic" learning model, in which training data is generated from a distribution that is only c*ε-close to some A-sum for a constant c>0.

STOC Conference 2017 Conference Paper

Addition is exponentially harder than counting for shallow monotone circuits

• Xi Chen 0001
• Igor C. Oliveira 0001
• Rocco A. Servedio

Let Add k , N denote the Boolean function which takes as input k strings of N bits each, representing k numbers a (1) ,…, a ( k ) in {0,1,…,2 N -1}, and outputs 1 if and only if a (1) + … + a ( k ) ≥ 2 N . Let MAJ t , n denote a monotone unweighted threshold gate , i.e., the Boolean function which takes as input a single string x Ε {0,1} n and outputs 1 if and only if x 1 + … + x n ≥ t . The function Add k , N may be viewed as a monotone function that performs addition, and MAJ t , n may be viewed as a monotone gate that performs counting. We refer to circuits that are composed of MAJ gates as monotone majority circuits. The main result of this paper is an exponential lower bound on the size of bounded-depth monotone majority circuits that compute Add k , N . More precisely, we show that for any constant d ≥ 2, any depth- d monotone majority circuit that computes Add d , N must have size 2 Ω( N 1/ d ) . As Add k , N can be computed by a single monotone weighted threshold gate (that uses exponentially large weights), our lower bound implies that constant-depth monotone majority circuits require exponential size to simulate monotone weighted threshold gates. This answers a question posed by Goldmann and Karpinski (STOC'93) and recently restated by Hastad (2010, 2014). We also show that our lower bound is essentially best possible, by constructing a depth- d , size 2 O ( N 1/ d ) monotone majority circuit for Add d , N . As a corollary of our lower bound, we significantly strengthen a classical theorem in circuit complexity due to Ajtai and Gurevich (JACM'87). They exhibited a monotone function that is in AC 0 but requires super-polynomial size for any constant-depth monotone circuit composed of unbounded fan-in AND and OR gates. We describe a monotone function that is in depth-3 AC 0 but requires exponential size monotone circuits of any constant depth, even if the circuits are composed of MAJ gates.

FOCS Conference 2017 Conference Paper

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time

• Rocco A. Servedio
• Li-Yang Tan

We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a deterministic algorithm which, given an n-variable poly(n)-clause CNF formula F that has at least ε2 n satisfying assignments, runs in time n(Õ(log log n) 2 ) for ε ≥ 1/polylog(n) and outputs a satisfying assignment of F. Prior to our work the fastest known algorithm for this problem was simply to enumerate over all seeds of a pseudorandom generator for CNFs; using the best known PRGs for CNFs [DETT10], this takes time n Ω̃(log n) even for constant ε. Our approach is based on a new general framework relating deterministic search and deterministic approximate counting, which we believe may find further applications.

FOCS Conference 2017 Conference Paper

Fooling Intersections of Low-Weight Halfspaces

• Rocco A. Servedio
• Li-Yang Tan

A weight-t halfspace is a Boolean function f(x) = sign(w 1 x 1 + ⋯ + w n x n - θ) where each w i is an integer in {-t, .. ., t}. We give an explicit pseudorandom generator that δ-fools any intersection of k weight-t halfspaces with seed length poly(log n, log k, t, 1/δ). In particular, our result gives an explicit PRG that fools any intersection of any quasipoly(n) number of halfspaces of any polylog(n) weight to any 1/polylog(n) accuracy using seed length polylog(n). Prior to this work no explicit PRG with non-trivial seed length was known even for fooling intersections of n weight-1 halfspaces to constant accuracy. The analysis of our PRG fuses techniques from two different lines of work on unconditional pseudorandomness for different kinds of Boolean functions. We extend the approach of Harsha, Klivans and Meka [HKM12] for fooling intersections of regular halfspaces, and combine this approach with results of Bazzi [Baz07] and Razborov [Raz09] on bounded independence fooling CNF formulas. Our analysis introduces new couplingbased ingredients into the standard Lindeberg method for establishing quantitative central limit theorems and associated pseudorandomness results.

STOC Conference 2017 Conference Paper

Optimal mean-based algorithms for trace reconstruction

• Anindya De
• Ryan O'Donnell
• Rocco A. Servedio

In the (deletion-channel) trace reconstruction problem, there is an unknown n -bit source string x . An algorithm is given access to independent traces of x , where a trace is formed by deleting each bit of x independently with probability δ. The goal of the algorithm is to recover x exactly (with high probability), while minimizing samples (number of traces) and running time. Previously, the best known algorithm for the trace reconstruction problem was due to Holenstein et al. [SODA 2008]; it uses exp( O ( n 1/2 )) samples and running time for any fixed 0 1/2, the presence of insertions can actually help with trace reconstruction.

STOC Conference 2016 Conference Paper

Near-optimal small-depth lower bounds for small distance connectivity

• Xi Chen 0001
• Igor C. Oliveira 0001
• Rocco A. Servedio
• Li-Yang Tan

We show that any depth- d circuit for determining whether an n -node graph has an s -to- t path of length at most k must have size n Ω( k 1/ d / d ) when k ( n ) ≤ n 1/5 , and n Ω( k 1/5 d / d ) when k ( n )≤ n . The previous best circuit size lower bounds were n k exp(− O ( d )) (by Beame, Impagliazzo, and Pitassi (Computational Complexity 1998)) and n Ω((log k )/ d ) (following from a recent formula size lower bound of Rossman (STOC 2014)). Our lower bound is quite close to optimal, as a simple construction gives depth- d circuits of size n O ( k 2/ d ) for this problem (and strengthening our bound even to n k Ω(1/ d ) would require proving that undirected connectivity is not in NC 1 ). Our proof is by reduction to a new lower bound on the size of small-depth circuits computing a skewed variant of the “Sipser functions” that have played an important role in classical circuit lower bounds. A key ingredient in our proof of the required lower bound for these Sipser-like functions is the use of random projections , an extension of random restrictions which were recently employed by Rossman, Servedio, and Tan (FOCS 2015). Random projections allow us to obtain sharper quantitative bounds while employing simpler arguments, both conceptually and technically, than in the previous works.

STOC Conference 2016 Conference Paper

Poly-logarithmic Frege depth lower bounds via an expander switching lemma

• Toniann Pitassi
• Benjamin Rossman
• Rocco A. Servedio
• Li-Yang Tan

We show that any polynomial-size Frege refutation of a certain linear-size unsatisfiable 3-CNF formula over n variables must have depth Ω(√log n ). This is an exponential improvement over the previous best results (Pitassi et al. 1993, Krajíček et al. 1995, Ben-Sasson 2002) which give Ω(loglog n ) lower bounds. The 3-CNF formulas which we use to establish this result are Tseitin contradictions on 3-regular expander graphs. In more detail, our main result is a proof that for every d , any depth- d Frege refutation of the Tseitin contradiction over these n -node graphs must have size n Ω((log n )/ d 2 ) . A key ingredient of our approach is a new switching lemma for a carefully designed random restriction process over these expanders. These random restrictions reduce a Tseitin instance on a 3-regular n -node expander to a Tseitin instance on a random subgraph which is a topological embedding of a 3-regular n ′-node expander, for some n ′ which is not too much less than n . Our result involves Ω(√log n ) iterative applications of this type of random restriction.

FOCS Conference 2015 Conference Paper

An Average-Case Depth Hierarchy Theorem for Boolean Circuits

• Benjamin Rossman
• Rocco A. Servedio
• Li-Yang Tan

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n-variable Boolean function f, computed by a linear-size depth-d formula, which is such that any depth-(d - 1) circuit that agrees with f on (1/2 + o n (1)) fraction of all inputs must have size exp(n Ω(1/d) ). This answers an open question posed by Hastad in his Ph. D. thesis [Has86b]. Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Hastad [Has86a], Cai [Cai86], and Babai [Bab87]. We also use our result to show that there is no “approximate converse” to the results of Linial, Mansour, Nisan [LMN93] and Boppana [Bop97] on the total influence of constant-depth circuits, thus answering a question posed by Kalai [Kal12] and Hatami [Hat14]. A key ingredient in our proof is a notion of random projections which generalize random restrictions.

STOC Conference 2015 Conference Paper

Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries

• Xi Chen 0001
• Anindya De
• Rocco A. Servedio
• Li-Yang Tan

We prove a lower bound of Ω(n 1/2-c ), for all c> 0, on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an n-variable Boolean function is monotone versus constant-far from monotone. This improves a ~Ω(n 1/5 ) lower bound for the same problem that was obtained in [6], and is very close to the recent upper bound of ~O(n 1/2 /ε 2 ) by Khot et al. [13].

SODA Conference 2015 Conference Paper

Learning from satisfying assignments

• Anindya De
• Ilias Diakonikolas
• Rocco A. Servedio

SODA Conference 2014 Conference Paper

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage

• Constantinos Daskalakis
• Anindya De
• Ilias Diakonikolas
• Ankur Moitra
• Rocco A. Servedio

We consider a problem which has received considerable attention in systems literature because of its applications to routing in delay tolerant networks and replica placement in distributed storage systems. In abstract terms the problem can be stated as follows: Given a random variable X generated by a known product distribution over {0, 1} n and a target value 0 ≤ θ ≤ 1, output a non-negative vector w, with ‖ w ‖ 1 ≤ 1, which maximizes the probability of the event w · X ≥ θ. This is a challenging non-convex optimization problem for which even computing the value Pr[ w · X ≥ θ ] of a proposed solution vector w is #P-hard. We provide an additive EPTAS for this problem which, for constant-bounded product distributions, runs in poly( n ) · 2 poly(1/∊) time and outputs an ∊-approximately optimal solution vector w for this problem. Our approach is inspired by, and extends, recent structural results from the complexity-theoretic study of linear threshold functions. Furthermore, in spite of the objective function being non-smooth, we give a unicriterion PTAS while previous work for such objective functions has typically led to a bicriterion PTAS. We believe our techniques may be applicable to get unicriterion PTAS for other non-smooth objective functions.

STOC Conference 2014 Conference Paper

Efficient density estimation via piecewise polynomial approximation

• Siu On Chan
• Ilias Diakonikolas
• Rocco A. Servedio
• Xiaorui Sun

STOC Conference 2014 Conference Paper

Efficient deterministic approximate counting for low-degree polynomial threshold functions

• Anindya De
• Rocco A. Servedio

FOCS Conference 2014 Conference Paper

New Algorithms and Lower Bounds for Monotonicity Testing

• Xi Chen 0001
• Rocco A. Servedio
• Li-Yang Tan

We consider the problem of testing whether an unknown Boolean function f: {- 1, 1} n → {-1, 1} is monotone versus ε-far from every monotone function. The two main results of this paper are a new lower bound and a new algorithm for this well-studied problem. Lower bound: We prove an Ω̅(n 1/5 ) lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown Boolean function f is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of Ω(log n) due to Fischer et al. [1]. We show that the same lower bound holds for monotonicity testing of Boolean-valued functions over hypergrid domains {1, ···, m} n for all m ≥ 2. Upper bound: We present an O(n 5/6 ) poly(1/ε)-query algorithm that tests whether an unknown Boolean function f is monotone versus ε-far from monotone. Our algorithm, which is non-adaptive and makes one-sided error, is a modified version of the algorithm of Chakrabarty and Seshadhri[2], which makes O(n 7/8 ) poly(1/ε) queries.

SODA Conference 2014 Conference Paper

Testing equivalence between distributions using conditional samples

• Clément L. Canonne
• Dana Ron
• Rocco A. Servedio

We study a recently introduced framework [7, 8] for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle. This is an oracle that takes as input a subset S ⊆ [ N ] of the domain [ N ] of the unknown probability distribution D and returns a draw from the conditional probability distribution D restricted to S. This model allows considerable flexibility in the design of distribution testing algorithms; in particular, testing algorithms in this model can be adaptive. In this paper we focus on algorithms for two fundamental distribution testing problems: testing whether D = D * for an explicitly provided D and testing whether two unknown distributions D 1 and D are equivalent. For both problems, the sample complexity of testing in the standard model is at least. For the first problem we give an algorithm in the conditional sampling model that performs only poly(1/∊)-queries (for the given distance parameter ∊) and has no dependence on N. This improves over the poly(log N, 1/∊)-query algorithm of [8]. For the second, more difficult problem, we given an algorithm whose complexity is poly(log N, 1/∊). For both problems we also give efficient algorithms that work under the restriction that the algorithm perform queries only on pairs of points and provide a lower bound that is polynomial in the upper bounds.

JMLR Journal 2013 Journal Article

Algorithms and Hardness Results for Parallel Large Margin Learning

• Philip M. Long
• Rocco A. Servedio

We consider the problem of learning an unknown large-margin halfspace in the context of parallel computation, giving both positive and negative results. As our main positive result, we give a parallel algorithm for learning a large-margin halfspace, based on an algorithm of Nesterov's that performs gradient descent with a momentum term. We show that this algorithm can learn an unknown $\gamma$-margin halfspace over $n$ dimensions using $n \cdot \text{poly}(1/\gamma)$ processors and running in time $\tilde{O}(1/\gamma)+O(\log n)$. In contrast, naive parallel algorithms that learn a $\gamma$-margin halfspace in time that depends polylogarithmically on $n$ have an inverse quadratic running time dependence on the margin parameter $\gamma$. Our negative result deals with boosting, which is a standard approach to learning large-margin halfspaces. We prove that in the original PAC framework, in which a weak learning algorithm is provided as an oracle that is called by the booster, boosting cannot be parallelized. More precisely, we show that, if the algorithm is allowed to call the weak learner multiple times in parallel within a single boosting stage, this ability does not reduce the overall number of successive stages of boosting needed for learning by even a single stage. Our proof is information-theoretic and does not rely on unproven assumptions. [abs] [ pdf ][ bib ] &copy JMLR 2013. ( edit, beta )

ICML Conference 2013 Conference Paper

Consistency versus Realizable H-Consistency for Multiclass Classification

• Philip M. Long
• Rocco A. Servedio

A consistent loss function for multiclass classification is one such that for any source of labeled examples, any tuple of scoring functions that minimizes the expected loss will have classification accuracy close to that of the Bayes optimal classifier. While consistency has been proposed as a desirable property for multiclass loss functions, we give experimental and theoretical results exhibiting a sequence of linearly separable data sources with the following property: a multiclass classification algorithm which optimizes a loss function due to Crammer and Singer (which is known not to be consistent) produces classifiers whose expected error goes to 0, while the expected error of an algorithm which optimizes a generalization of the loss function used by LogitBoost (a loss function which is known to be consistent) is bounded below by a positive constant. We identify a property of a loss function, realizable consistency with respect to a restricted class of scoring functions, that accounts for this difference. As our main technical results we show that the Crammer–Singer loss function is realizable consistent for the class of linear scoring functions, while the generalization of LogitBoost is not. Our result for LogitBoost is a special case of a more general theorem that applies to several other loss functions that have been proposed for multiclass classification.

SODA Conference 2013 Conference Paper

Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities

• Dana Ron
• Rocco A. Servedio

SODA Conference 2013 Conference Paper

Learning mixtures of structured distributions over discrete domains

• Siu On Chan
• Ilias Diakonikolas
• Rocco A. Servedio
• Xiaorui Sun

Let be a class of probability distributions over the discrete domain [ n ] = {1, …, n }. We show that if satisfies a rather general condition – essentially, that each distribution in can be well-approximated by a variable-width histogram with few bins – then there is a highly efficient (both in terms of running time and sample complexity) algorithm that can learn any mixture of k unknown distributions from. We analyze several natural types of distributions over [ n ], including log-concave, monotone hazard rate and unimodal distributions, and show that they have the required structural property of being well-approximated by a histogram with few bins. Applying our general algorithm, we obtain near-optimally efficient algorithms for all these mixture learning problems as described below. More precisely, Log-concave distributions: We learn any mixture of k log-concave distributions over [ n ] using k · Õ (1/ε 4 ) samples (independent of n ) and running in time Õ ( k log( n )/ε 4 ) bit-operations (note that reading a single sample from [ n ] takes Θ(log n ) bit operations). For the special case k = 1 we give an efficient algorithm using Õ (1/ε 3 ) samples; this generalizes the main result of [DDS12b] from the class of Poisson Binomial distributions to the much broader class of all log-concave distributions. Our upper bounds are not far from optimal since any algorithm for this learning problem requires Ω( k /ε 5/2 ) samples. Monotone hazard rate (MHR) distributions: We learn any mixture of k MHR distributions over [ n ] using O ( k log( n /ε)/ε 4 ) samples and running in time Õ ( k log ( n )/ε 4 ) bit-operations. Any algorithm for this learning problem must use Ω( k log( n )/ε 3 ) samples. Unimodal distributions: We give an algorithm that learns any mixture of k unimodal distributions over [ n ] using O ( k log( n )/ε 4 ) samples and running in time Õ ( k log 2 ( n )/ε 4 ) bit-operations. Any algorithm for this problem must use Ω( k log( n )/ε 3 ) samples.

FOCS Conference 2013 Conference Paper

Learning Sums of Independent Integer Random Variables

• Constantinos Daskalakis
• Ilias Diakonikolas
• Ryan O'Donnell
• Rocco A. Servedio
• Li-Yang Tan

Let bS = bX_1 + ·s + bX_n be a sum of n independent integer random variables bX_i, where each bX_i is supported on 0, 1, ·, k-1 but otherwise may have an arbitrary distribution (in particular the bX_i's need not be identically distributed). How many samples are required to learn the distribution bS to high accuracy? In this paper we show that the answer is completely independent of n, and moreover we give a computationally efficient algorithm which achieves this low sample complexity. More precisely, our algorithm learns any such bS to ε-accuracy (with respect to the total variation distance between distributions) using poly(k, 1/ε) samples, independent of n. Its running time is poly(k, 1/ε) in the standard word RAM model. Thus we give a broad generalization of the main result of DDS12stoc which gave a similar learning result for the special case k=2 (when the distribution bS is a Poisson Binomial Distribution). Prior to this work, no nontrivial results were known for learning these distributions even in the case k=3. A key difficulty is that, in contrast to the case of k = 2, sums of independent 0, 1, 2-valued random variables may behave very differently from (discretized) normal distributions, and in fact may be rather complicated - they are not log-concave, they can be θ(n)-modal, there is no relationship between Kolmogorov distance and total variation distance for the class, etc. Nevertheless, the heart of our learning result is a new limit theorem which characterizes what the sum of an arbitrary number of arbitrary independent 0, 1, ·, k-1-valued random variables may look like. Previous limit theorems in this setting made strong assumptions on the "shift invariance" of the random variables bX_i in order to force a discretized normal limit. We believe that our new limit theorem, as the first result for truly arbitrary sums of independent 0, 1, ·, k-1-valued random variables, is of independent interest.

SODA Conference 2013 Conference Paper

Testing k -Modal Distributions: Optimal Algorithms via Reductions

• Constantinos Daskalakis
• Ilias Diakonikolas
• Rocco A. Servedio
• Gregory Valiant
• Paul Valiant

We give highly efficient algorithms, and almost matching lower bounds, for a range of basic statistical problems that involve testing and estimating the L 1 (total variation) distance between two k -modal distributions p and q over the discrete domain {1, …, n }. More precisely, we consider the following four problems: given sample access to an unknown k -modal distribution p, T esting identity to a known or unknown distribution: 1. Determine whether p = q (for an explicitly given k -modal distribution q ) versus p is e-far from q; 2. Determine whether p = q (where q is available via sample access) versus p is ε-far from q; E stimating L 1 distance (“ tolerant testing ”) against a known or unknown distribution: 3. Approximate d TV ( p, q ) to within additive ε where q is an explicitly given k -modal distribution q; 4. Approximate d TV ( p, q ) to within additive ε where q is available via sample access. For each of these four problems we give sub-logarithmic sample algorithms, and show that our algorithms have optimal sample complexity up to additive poly ( k ) and multiplicative polylog log n + polylog k factors. Our algorithms significantly improve the previous results of [BKR04], which were for testing identity of distributions (items (1) and (2) above) in the special cases k = 0 (monotone distributions) and k = 1 (unimodal distributions) and required O ((log n ) 3 ) samples. As our main conceptual contribution, we introduce a new reduction-based approach for distribution-testing problems that lets us obtain all the above results in a unified way. Roughly speaking, this approach enables us to transform various distribution testing problems for k -modal distributions over {1, …, n } to the corresponding distribution testing problems for unrestricted distributions over a much smaller domain {1, …, ℓ} where ℓ = O ( k log n ).

SODA Conference 2012 Conference Paper

Learning k -modal distributions via testing

• Constantinos Daskalakis
• Ilias Diakonikolas
• Rocco A. Servedio

STOC Conference 2012 Conference Paper

Learning poisson binomial distributions

• Constantinos Daskalakis
• Ilias Diakonikolas
• Rocco A. Servedio

We consider a basic problem in unsupervised learning: learning an unknown Poisson Binomial Distribution . A Poisson Binomial Distribution (PBD) over {0,1,...,n} is the distribution of a sum of n independent Bernoulli random variables which may have arbitrary, potentially non-equal, expectations. These distributions were first studied by S. Poisson in 1837 and are a natural n-parameter generalization of the familiar Binomial Distribution. Surprisingly, prior to our work this basic learning problem was poorly understood, and known results for it were far from optimal. We essentially settle the complexity of the learning problem for this basic class of distributions. As our main result we give a highly efficient algorithm which learns to ε-accuracy using O(1/ε 3 ) samples independent of n . The running time of the algorithm is quasilinear in the size of its input data, i.e. ~O(log(n)/ε 3 ) bit-operations (observe that each draw from the distribution is a log(n)-bit string). This is nearly optimal since any algorithm must use Ω(1/ε 2 ) samples. We also give positive and negative results for some extensions of this learning problem.

STOC Conference 2012 Conference Paper

Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces

• Anindya De
• Ilias Diakonikolas
• Vitaly Feldman
• Rocco A. Servedio

SODA Conference 2012 Conference Paper

Private data release via learning thresholds

• Moritz Hardt
• Guy N. Rothblum
• Rocco A. Servedio

This work considers computationally efficient privacy-preserving data release. We study the task of analyzing a database containing sensitive information about individual participants. Given a set of statistical queries on the data, we want to release approximate answers to the queries while also guaranteeing differential privacy —protecting each participant's sensitive data. Our focus is on computationally efficient data release algorithms; we seek algorithms whose running time is polynomial, or at least sub-exponential, in the data dimensionality. Our primary contribution is a computationally efficient reduction from differentially private data release for a class of counting queries, to learning thresholded sums of predicates from a related class. We instantiate this general reduction with algorithms for learning thresholds, obtaining new results for differentially private data release. As two examples, taking {0, 1} d to be the data domain (of dimension d ), we obtain differentially private algorithms for: 1. Releasing all k -way conjunction counting queries (or k -way contingency tables). For any given k, the resulting data release algorithm has bounded error as long as the database is of size at least (ignoring the dependence on other parameters). The running time is polynomial in the database size. The best sub-exponential time algorithms known prior to our work required a database of size Õ ( d k/2 ) [Dwork McSherry Nissim and Smith 2006]. 2. Releasing any family of counting queries that is specified by a constant depth AC 0 predicate. This algorithm releases accurate answers to a (1 − γ)-fraction of the queries in the family. For any γ ≥ quasipoly (1/ d ), the algorithm has bounded error as long as the database is of size at least quasipoly( d ) (again ignoring the dependence on other parameters). The running time is quasipoly( d ). The first learning algorithm uses techniques for representing thresholded sums of predicates as lowdegree polynomial threshold functions. The second learning algorithm is based on a result of Jackson Klivans and Servedio [JKS 2002], and utilizes Fourier analysis of the database viewed as a function mapping queries to answers.

SODA Conference 2011 Conference Paper

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions

• Ilias Diakonikolas
• Ryan O'Donnell
• Rocco A. Servedio
• Yi Wu 0002

STOC Conference 2010 Conference Paper

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions

• Ilias Diakonikolas
• Prahladh Harsha
• Adam R. Klivans
• Raghu Meka
• Prasad Raghavendra
• Rocco A. Servedio
• Li-Yang Tan

We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of degree-d polynomial threshold functions (PTFs). These bounds hold both for PTFs over the Boolean hypercube {-1,1} n and for PTFs over R n under the standard n-dimensional Gaussian distribution N(0,I n ). Our bound on the Boolean average sensitivity of PTFs represents progress towards the resolution of a conjecture of Gotsman and Linial [17], which states that the symmetric function slicing the middle d layers of the Boolean hypercube has the highest average sensitivity of all degree-d PTFs. Via the L 1 polynomial regression algorithm of Kalai et al. [22], our bounds on Gaussian and Boolean noise sensitivity yield polynomial-time agnostic learning algorithms for the broad class of constant-degree PTFs under these input distributions.

ICML Conference 2010 Conference Paper

Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate

• Philip M. Long
• Rocco A. Servedio

FOCS Conference 2009 Conference Paper

Bounded Independence Fools Halfspaces

• Ilias Diakonikolas
• Parikshit Gopalan
• Ragesh Jaiswal
• Rocco A. Servedio
• Emanuele Viola

We show that any distribution on {-1, +1} n that is k-wise independent fools any halfspace (a. k. a. threshold) h: {-1, +1} n ¿ {-1, +1}, i. e. , any function of the form h(x) = sign(¿ i=1 n w i X i - ¿) where the w 1, .. ., w n, ¿ are arbitrary real numbers, with error ¿ for k = O(¿ -2 log 2 (1/¿)). Our result is tight up to log(1/¿) factors. Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators G: {-1, +1} s ¿ {-1, +1} n that fool halfspaces. Specifically, we fool halfspaces with error e and seed length s = k · log n = O(log n · ¿ -2 log 2 (1/¿)). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Comput. Complexity 2007).

JMLR Journal 2009 Journal Article

Learning Halfspaces with Malicious Noise

• Adam R. Klivans
• Philip M. Long
• Rocco A. Servedio

We give new algorithms for learning halfspaces in the challenging malicious noise model, where an adversary may corrupt both the labels and the underlying distribution of examples. Our algorithms can tolerate malicious noise rates exponentially larger than previous work in terms of the dependence on the dimension n, and succeed for the fairly broad class of all isotropic log-concave distributions. We give poly( n, 1/&epsilon;)-time algorithms for solving the following problems to accuracy &epsilon;: Learning origin-centered halfspaces in R n with respect to the uniform distribution on the unit ball with malicious noise rate &eta; = &Omega;(&epsilon; 2 / log( n /&epsilon;)). (The best previous result was &Omega;(&epsilon; / ( n log( n /&epsilon;)) 1/4 ).) Learning origin-centered halfspaces with respect to any isotropic log-concave distribution on R n with malicious noise rate &eta; = &Omega;(&epsilon; 3 / log 2 ( n /&epsilon;)). This is the first efficient algorithm for learning under isotropic log-concave distributions in the presence of malicious noise. We also give a poly( n,1/&epsilon;)-time algorithm for learning origin-centered halfspaces under any isotropic log-concave distribution on R n in the presence of adversarial label noise at rate &eta; = &Omega;(&epsilon; 3 / log(1/&epsilon;)). In the adversarial label noise setting (or agnostic model), labels can be noisy, but not example points themselves. Previous results could handle &eta; = &Omega;(&epsilon;) but had running time exponential in an unspecified function of 1/&epsilon;. Our analysis crucially exploits both concentration and anti-concentration properties of isotropic log-concave distributions. Our algorithms combine an iterative outlier removal procedure using Principal Component Analysis together with "smooth" boosting. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

TCS Journal 2009 Journal Article

Preface

• Marcus Hutter
• Rocco A. Servedio

SODA Conference 2009 Conference Paper

Testing halfspaces

• Kevin Matulef
• Ryan O'Donnell
• Ronitt Rubinfeld
• Rocco A. Servedio

FOCS Conference 2008 Conference Paper

Learning Geometric Concepts via Gaussian Surface Area

• Adam R. Klivans
• Ryan O'Donnell
• Rocco A. Servedio

We study the learnability of sets in Ropf n under the Gaussian distribution, taking Gaussian surface area as the "complexity measure" of the sets being learned. Let C S denote the class of all (measurable) sets with surface area at most S. We first show that the class C S is learnable to any constant accuracy in time n O(S 2 ), even in the arbitrary noise ("agnostic'') model. Complementing this, we also show that any learning algorithm for C S information-theoretically requires 2 Omega(S 2 ) examples for learning to constant accuracy. These results together show that Gaussian surface area essentially characterizes the computational complexity of learning under the Gaussian distribution. Our approach yields several new learning results, including the following (all bounds are for learning to any constant accuracy): The class of all convex sets can be agnostically learned in time 2 O ~ (radicn) (and we prove a 2 Omega(radicn) lower bound for noise-free learning). This is the first subexponential time algorithm for learning general convex sets even in the noise-free (PAC) model. Intersections of k halfspaces can be agnostically learned in time n O(log k) (cf. Vempala's n O(k) time algorithm for learning in the noise-free model). Cones (with apex centered at the origin), and spheres witharbitrary radius and center, can be agnostically learned in time poly(n).

TCS Journal 2008 Journal Article

Learning unions of ω ( 1 ) -dimensional rectangles

• Alp Atıcı
• Rocco A. Servedio

We consider the problem of learning unions of rectangles over the domain [ b ] n, in the uniform distribution membership query learning setting, where both b and n are “large”. We obtain poly ( n, log b ) -time algorithms for the following classes: • poly ( n log b ) -way Majority of O ( log ( n log b ) log log ( n log b ) ) -dimensional rectangles. • Union of poly ( log ( n log b ) ) many O ( log 2 ( n log b ) ( log log ( n log b ) log log log ( n log b ) ) 2 ) -dimensional rectangles. • poly ( n log b ) -way Majority of poly ( n log b ) -Or of disjoint O ( log ( n log b ) log log ( n log b ) ) dimensional rectangles. Our main algorithmic tool is an extension of Jackson’s boosting- and Fourier-based Harmonic Sieve algorithm [J. C. Jackson, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, Journal of Computer and System Sciences 55 (3) (1997) 414–440] to the domain [ b ] n, building on work of Akavia et al. [A. Akavia, S. Goldwasser, S. Safra, Proving hard core predicates using list decoding, in: Proc. of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’03, 2003, pp. 146–156]. Other ingredients used to obtain the results stated above are techniques from exact learning [A. Beimel, E. Kushilevitz, Learning boxes in high dimension, Algorithmica 22 (1/2) (1998) 76–90] and ideas from recent work on learning augmented AC 0 circuits [J. C. Jackson, A. R. Klivans, R. A. Servedio, Learnability beyond AC 0, in: Proc. of the 34th Annual ACM Symposium on Theory of Computing, STOC ’02, 2002, pp. 776–784] and on representing Boolean functions as thresholds of parities [A. R. Klivans, R. A. Servedio, Learning DNF in time 2 O ̃ ( n 1 / 3 ), Journal of Computer and System Sciences 68 (2) (2004) 303–318].

ICML Conference 2008 Conference Paper

Random classification noise defeats all convex potential boosters

• Philip M. Long
• Rocco A. Servedio

STOC Conference 2008 Conference Paper

The chow parameters problem

• Ryan O'Donnell
• Rocco A. Servedio

In the 2nd Annual FOCS (1961), C. K. Chow proved that every Boolean threshold function is uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers became known as the Chow Parameters . Providing an algorithmic version of Chow's theorem --- i.e., efficiently constructing a representation of a threshold function given its Chow Parameters --- has remained open ever since. This problem has received significant study in the fields of circuit complexity, game theory and the design of voting systems, and learning theory. In this paper we effectively solve the problem, giving a randomized PTAS with the following behavior: Theorem: Given the Chow Parameters of a Boolean threshold function f over n bits and any constant ε > 0, the algorithm runs in time O(n 2 log 2 n) and with high probability outputs a representation of a threshold function f' which is ε-close to f. Along the way we prove several new results of independent interest about Boolean threshold functions. In addition to various structural results, these include the following new algorithmic results in learning theory (where threshold functions are usually called "halfspaces"): An ~O(n 2 )-time uniform distribution algorithm for learning halfspaces to constant accuracy in the "Restricted Focus of Attention" (RFA) model of Ben-David et al. [3]. This answers the main open question of [6]. An O(n 2 )-time agnostic-type learning algorithm for halfspaces under the uniform distribution. This contrasts with recent results of Guruswami and Raghavendra [21] who show that the learning problem we solve is NP-hard under general distributions. As a special case of the latter result we obtain the fastest known algorithm for learning halfspaces to constant accuracy in the uniform distribution PAC learning model. For constant ε our algorithm runs in time ~O(n 2 ), which substantially improves on previous bounds and nearly matches the Ω(n 2 ) bits of training data that any successful learning algorithm must use.

TCS Journal 2007 Journal Article

On PAC learning algorithms for rich Boolean function classes

• Lisa Hellerstein
• Rocco A. Servedio

We give an overview of the fastest known algorithms for learning various expressive classes of Boolean functions in the Probably Approximately Correct (PAC) learning model. In addition to surveying previously known results, we use existing techniques to give the first known subexponential-time algorithms for PAC learning two natural and expressive classes of Boolean functions: sparse polynomial threshold functions over the Boolean cube { 0, 1 } n and sparse GF 2 polynomials over { 0, 1 } n.

JMLR Journal 2007 Journal Article

Separating Models of Learning from Correlated and Uncorrelated Data

• Ariel Elbaz
• Homin K. Lee
• Rocco A. Servedio
• Andrew Wan

We consider a natural framework of learning from correlated data, in which successive examples used for learning are generated according to a random walk over the space of possible examples. A recent paper by Bshouty et al. (2003) shows that the class of polynomial-size DNF formulas is efficiently learnable in this random walk model; this result suggests that the Random Walk model is more powerful than comparable standard models of learning from independent examples, in which similarly efficient DNF learning algorithms are not known. We give strong evidence that the Random Walk model is indeed more powerful than the standard model, by showing that if any cryptographic one-way function exists (a universally held belief in cryptography), then there is a class of functions that can be learned efficiently in the Random Walk setting but not in the standard setting where all examples are independent. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

FOCS Conference 2007 Conference Paper

Testing for Concise Representations

• Ilias Diakonikolas
• Homin K. Lee
• Kevin Matulef
• Krzysztof Onak
• Ronitt Rubinfeld
• Rocco A. Servedio
• Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. 16 with ideas from learning theory, and yields property testers that make po! y(s/epsiv) queries (independent of n) for Boolean function classes such as s-term DNF formulas (answering a question posed by Parnas et al. [12]), sizes. decision trees, sizes Boolean formulas, and sizes Boolean circuits. The method can be applied to non-Boolean valued function classes as well. This is achieved via a generalization of the notion of van at ion/row Fischer et al. to non-Boolean functions. Using this generalization we extend the original junta test of Fischer et al. to work for non-Boolean functions, and give poly(s/e)-query testing algorithms for non-Boolean valued function classes such as sizes algebraic circuits and s-sparse polynomials over finite fields. We also prove an Omega(radic(s)) query lower bound for nonadaptively testing s-sparse polynomials over finite fields of constant size. This shows that in some instances, our general method yields a property tester with query complexity that is optimal (for nonadaptive algorithms) up to a polynomial factor.

TCS Journal 2006 Journal Article

On learning embedded midbit functions

• Rocco A. Servedio

A midbit function on ℓ binary inputs x 1, …, x ℓ outputs the middle bit in the binary representation of x 1 + ⋯ + x ℓ. We consider the problem of Probably Approximately Correct (PAC) learning embedded midbit functions, where the set S ⊂ { x 1, …, x n } of relevant variables on which the midbit depends is unknown to the learner. To motivate this problem, we first point out that a result of Green et al. implies that a polynomial time learning algorithm for the class of embedded midbit functions would immediately yield a fairly efficient (quasipolynomial time) (PAC) learning algorithm for the entire complexity class ACC. We then give two different subexponential learning algorithms, each of which learns embedded midbit functions under any probability distribution in 2 n log n time. Finally, we give a polynomial time algorithm for learning embedded midbit functions under the uniform distribution.

I&C Journal 2006 Journal Article

Polynomial certificates for propositional classes

• Marta Arias
• Aaron Feigelson
• Roni Khardon
• Rocco A. Servedio

This paper studies the complexity of learning classes of expressions in propositional logic from equivalence queries and membership queries. In particular, we focus on bounding the number of queries that are required to learn the class ignoring computational complexity. This quantity is known to be captured by a combinatorial measure of concept classes known as the certificate complexity. The paper gives new constructions of polynomial size certificates for monotone expressions in conjunctive normal form (CNF), for unate CNF functions where each variable affects the function either positively or negatively but not both ways, and for Horn CNF functions. Lower bounds on certificate size for these classes are derived showing that for some parameter settings the new certificate constructions are optimal. Finally, the paper gives an exponential lower bound on the certificate size for a natural generalization of these classes known as renamable Horn CNF functions, thus implying that the class is not learnable from a polynomial number of queries.

JMLR Journal 2006 Journal Article

Toward Attribute Efficient Learning of Decision Lists and Parities

• Adam R. Klivans
• Rocco A. Servedio

We consider two well-studied problems regarding attribute efficient learning: learning decision lists and learning parity functions. First, we give an algorithm for learning decision lists of length k over n variables using 2 Õ(k 1/3 ) log n examples and time n Õ(k 1/3 ). This is the first algorithm for learning decision lists that has both subexponential sample complexity and subexponential running time in the relevant parameters. Our approach is based on a new construction of low degree, low weight polynomial threshold functions for decision lists. For a wide range of parameters our construction matches a lower bound due to Beigel for decision lists and gives an essentially optimal tradeoff between polynomial threshold function degree and weight. Second, we give an algorithm for learning an unknown parity function on k out of n variables using O(n 1-1/k ) examples in poly (n) time. For k=o( log n) this yields the first polynomial time algorithm for learning parity on a superconstant number of variables with sublinear sample complexity. We also give a simple algorithm for learning an unknown length- k parity using O(k log n) examples in n k/2 time, which improves on the naive n k time bound of exhaustive search. [abs] [ pdf ][ bib ] &copy JMLR 2006. ( edit, beta )

FOCS Conference 2005 Conference Paper

Agnostically Learning Halfspaces

• Adam Tauman Kalai
• Adam R. Klivans
• Yishay Mansour
• Rocco A. Servedio

We give the first algorithm that (under distributional assumptions) efficiently learns halfspaces in the notoriously difficult agnostic framework of Kearns, Schapire, & Sellie, where a learner is given access to labeled examples drawn from a distribution, without restriction on the labels (e. g. adversarial noise). The algorithm constructs a hypothesis whose error rate on future examples is within an additive /spl epsi/ of the optimal halfspace, in time poly(n) for any constant /spl epsi/ > 0, under the uniform distribution over {-1, 1}/sup n/ or the unit sphere in /spl Ropf//sup n/, as well as under any log-concave distribution over /spl Ropf/ /sup n/. It also agnostically learns Boolean disjunctions in time 2/sup O~(/spl radic/n)/ with respect to any distribution. The new algorithm, essentially L/sub 1/ polynomial regression, is a noise-tolerant arbitrary distribution generalization of the "low degree" Fourier algorithm of Linial, Mansour, & Nisan. We also give a new algorithm for PAC learning halfspaces under the uniform distribution on the unit sphere with the current best bounds on tolerable rate of "malicious noise".

FOCS Conference 2005 Conference Paper

Every decision tree has an in. uential variable

• Ryan O'Donnell
• Michael E. Saks
• Oded Schramm
• Rocco A. Servedio

We prove that for any decision tree calculating a Boolean function f: {-1, 1}/sup n/ /spl rarr/ {-1, 1}, Var[f] /spl les/ /spl Sigma/ /sub i=1/ /sup n/ /spl delta//sup i/Inf/sub i/(f), i = 1 where /spl delta//sup i/ is the probability that the ith input variable is read and Inf/sub i/(f) is the influence of the ith variable on f. The variance, influence and probability are taken with respect to an arbitrary product measure on {-1, 1}/sup n/n. It follows that the minimum depth of a decision tree calculating a given balanced function is at least the reciprocal of the largest influence of any input variable. Likewise, any balanced Boolean function with a decision tree of depth d has a variable with influence at least 1/d. The only previous nontrivial lower bound known was /spl Omega/(d2/sup -d/). Our inequality has many generalizations, allowing us to prove influence lower bounds for randomized decision trees, decision trees on arbitrary product probability spaces, and decision trees with nonBoolean outputs. As an application of our results we give a very easy proof that the randomized query complexity of nontrivial monotone graph properties is at least/spl Omega/(v/sup 4/3//p/sup 1/3/), where v is the number of vertices and p /spl les/ 1/2 is the critical threshold probability. This supersedes the milestone /spl Omega/(v/sup 4/3//p/sup 1/3/) bound of Hajnal (1991) and is sometimes superior to the best known lower bounds of Chakrabarti-Khot (2001) and Friedgut-Kahn-Wigderson (2002).

FOCS Conference 2005 Conference Paper

Learning mixtures of product distributions over discrete domains

• Jon Feldman
• Ryan O'Donnell
• Rocco A. Servedio

We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. (1994). We give a poly(n//spl epsi/) time algorithm for learning a mixture of k arbitrary product distributions over the n-dimensional Boolean cube {0, 1}/sup n/ to accuracy /spl epsi/, for any constant k. Previous poly(n)-time algorithms could only achieve this for k = 2 product distributions; our result answers an open question stated independently in M. Cryan (1999) and Y. Freund and Y. Mansour (1999). We further give evidence that no polynomial time algorithm can succeed when k is superconstant, by reduction from a notorious open problem in PAC learning. Finally, we generalize our poly(n//spl epsi/) time algorithm to learn any mixture of k = O(1) product distributions over {0, 1, .. ., b }/sup n/, for any b = O(1).

JMLR Journal 2005 Journal Article

Maximum Margin Algorithms with Boolean Kernels

• Roni Khardon
• Rocco A. Servedio

Recent work has introduced Boolean kernels with which one can learn linear threshold functions over a feature space containing all conjunctions of length up to k (for any 1 ≤ k ≤ n ) over the original n Boolean features in the input space. This motivates the question of whether maximum margin algorithms such as Support Vector Machines can learn Disjunctive Normal Form expressions in the Probably Approximately Correct (PAC) learning model by using this kernel. We study this question, as well as a variant in which structural risk minimization (SRM) is performed where the class hierarchy is taken over the length of conjunctions. We show that maximum margin algorithms using the Boolean kernels do not PAC learn t ( n )-term DNF for any t ( n ) = ω(1), even when used with such a SRM scheme. We also consider PAC learning under the uniform distribution and show that if the kernel uses conjunctions of length ˜ω(√ n ) then the maximum margin hypothesis will fail on the uniform distribution as well. Our results concretely illustrate that margin based algorithms may overfit when learning simple target functions with natural kernels. [abs] [ pdf ][ bib ] &copy JMLR 2005. ( edit, beta )

STOC Conference 2005 Conference Paper

Testing monotone high-dimensional distributions

• Ronitt Rubinfeld
• Rocco A. Servedio

A monotone distribution P over a (partially) ordered domain has P ( y ) ≥ P ( x ) if y ≥ x in the order. We study several natural problems of testing properties of monotone distributions over the n -dimensional Boolean cube, given access to random draws from the distribution being tested. We give a poly( n )-time algorithm for testing whether a monotone distribution is equivalent to or ε-far (in the L 1 norm) from the uniform distribution. A key ingredient of the algorithm is a generalization of a known isoperimetric inequality for the Boolean cube. We also introduce a method for proving lower bounds on testing monotone distributions over the n -dimensional Boolean cube, based on a new decomposition technique for monotone distributions. We use this method to show that our uniformity testing algorithm is optimal up to polylog( n ) factors, and also to give exponential lower bounds on the complexity of several other problems (testing whether a monotone distribution is identical to or ε-far from a fixed known monotone product distribution and approximating the entropy of an unknown monotone distribution).

ICML Conference 2005 Conference Paper

Unsupervised evidence integration

• Philip M. Long
• Vinay Varadan
• Sarah Gilman
• Mark Treshock
• Rocco A. Servedio

STOC Conference 2003 Conference Paper

Boosting in the presence of noise

• Adam Tauman Kalai
• Rocco A. Servedio

Boosting algorithms are procedures that "boost" low accuracy weak learning algorithms to achieve arbitrarily high accuracy. Over the past decade boosting has been widely used in practice and has become a major research topic in computational learning theory. In this paper we study boosting in the presence of random classification noise, giving both positive and negative results.We show that a modified version of a boosting algorithm due to Mansour and McAllester [14] can achieve accuracy arbitrarily close to the noise rate. We also give a matching lower bound by showing that no efficient black-box boosting algorithm can boost accuracy beyond the noise rate (assuming that one-way functions exist). Finally, we consider a variant of the standard scenario for boosting in which the "weak learner" satisfies a slightly stronger condition than the usual weak learning guarantee. We give an efficient algorithm in this framework which can boost to arbitrarily high accuracy in the presence of classification noise.

FOCS Conference 2003 Conference Paper

Learning DNF from Random Walks

• Nader H. Bshouty
• Elchanan Mossel
• Ryan O'Donnell
• Rocco A. Servedio

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1}/sup n/. We give a polynomial time algorithm for learning decision trees and DNF formulas in this model. This is the first efficient algorithm for learning these classes in a natural passive learning model where the learner has no influence over the choice of examples used for learning.

STOC Conference 2003 Conference Paper

Learning juntas

• Elchanan Mossel
• Ryan O'Donnell
• Rocco A. Servedio

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for learning such functions from uniform random examples which runs in time roughly (n k ) ω/(ω + 1) , where ω < 2.376 is the matrix multiplication exponent. We thus obtain the first polynomial factor improvement on the naive n k time bound which can be achieved via exhaustive search. Our algorithm and analysis exploit new structural properties of Boolean functions.

STOC Conference 2003 Conference Paper

New degree bounds for polynomial threshold functions

• Ryan O'Donnell
• Rocco A. Servedio

We give new upper and lower bounds on the degree of real multivariate polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively ; we give explicit dual solutions to the necessary linear programs.

JMLR Journal 2003 Journal Article

Smooth Boosting and Learning with Malicious Noise

• Rocco A. Servedio

We describe a new boosting algorithm which generates only smooth distributions which do not assign too much weight to any single example. We show that this new boosting algorithm can be used to construct efficient PAC learning algorithms which tolerate relatively high rates of malicious noise. In particular, we use the new smooth boosting algorithm to construct malicious noise tolerant versions of the PAC-model p -norm linear threshold learning algorithms described by Servedio (2002). The bounds on sample complexity and malicious noise tolerance of these new PAC algorithms closely correspond to known bounds for the online p -norm algorithms of Grove, Littlestone and Schuurmans (1997) and Gentile and Littlestone (1999). As special cases of our new algorithms we obtain linear threshold learning algorithms which match the sample complexity and malicious noise tolerance of the online Perceptron and Winnow algorithms. Our analysis reveals an interesting connection between boosting and noise tolerance in the PAC setting. [abs] [ pdf ][ ps.gz ][ ps ]

STOC Conference 2002 Conference Paper

Learnability beyond AC0

• Jeffrey C. Jackson
• Adam R. Klivans
• Rocco A. Servedio

FOCS Conference 2002 Conference Paper

Learning Intersections and Thresholds of Halfspaces

• Adam R. Klivans
• Ryan O'Donnell
• Rocco A. Servedio

We give the first polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution to within any constant error parameter. We also give the first quasipolynomial time algorithm for learning any function of a polylog number of polynomial-weight halfspaces under any distribution. As special cases of these results we obtain algorithms for learning intersections and thresholds of halfspaces. Our uniform distribution learning algorithms involve a novel non-geometric approach to learning halfspaces; we use Fourier techniques together with a careful analysis of the noise sensitivity of functions of halfspaces. Our algorithms for learning under any distribution use techniques from real approximation theory to construct low degree polynomial threshold functions.

STOC Conference 2001 Conference Paper

Learning DNF in time 2 Õ(n 1/3 )

• Adam R. Klivans
• Rocco A. Servedio

Using techniques from learning theory, we show that any s -term DNF over n variables can be computed by a polynomial threshold function of degree O(n^{1/3} \log s) . This upper bound matches, up to a logarithmic factor, the longstanding lower bound given by Minsky and Papert in their 1968 book {\em Perceptrons}. As a consequence of this upper bound we obtain the fastest known algorithm for learning polynomial size DNF, one of the central problems in computational learning theory.

FOCS Conference 1999 Conference Paper

Boosting and Hard-Core Sets

• Adam R. Klivans
• Rocco A. Servedio

This paper connects two fundamental ideas from theoretical computer science hard-core set construction, a type of hardness amplification from computational complexity, and boosting, a technique from computational learning theory. Using this connection we give fruitful applications of complexity-theoretic techniques to learning theory and vice versa. We show that the hard-core set construction of R. Impagliazzo (1995), which establishes the existence of distributions under which boolean functions are highly inapproximable, may be viewed as a boosting algorithm. Using alternate boosting methods we give an improved bound for hard-core set construction which matches known lower bounds from boosting and thus is optimal within this class of techniques. We then show how to apply techniques from R. Impagliazzo to give a new version of Jackson's celebrated Harmonic Sieve algorithm for learning DNF formulae under the uniform distribution using membership queries. Our new version has a significant asymptotic improvement in running time. Critical to our arguments is a careful analysis of the distributions which are employed in both boosting and hard-core set constructions.

STOC Conference 1999 Conference Paper

Computational Sample Complexity and Attribute-Efficient Learning

• Rocco A. Servedio