Determinantal Point Processes (DPPs) are a widely used probabilistic model for negatively correlated sets. DPPs are used in Machine Learning applications to select a diverse, yet representative subset of data. In these applications, the parameters of the DPP need to be fit to match the data; typically, we seek a set of parameters that maximize the likelihood of the data. The algorithms used for this task either optimize over a limited family of DPPs, or else use local improvement heuristics that do not provide theoretical guarantees of optimality. It is natural to ask if there exist efficient algorithms for finding a maximum likelihood DPP model for a given data set. In seminal work on DPPs in Machine Learning, Kulesza conjectured in his PhD Thesis (2012) that the problem is NP-complete. In this work we prove Kulesza’s conjecture: we prove moreover, that even computing a $1-\frac{1}{\mathrm{poly} \log N}$-approximation to the maximum log-likelihood of a DPP on a set of $N$ items is NP-complete. At the same time, we also obtain the first polynomial-time algorithm obtaining a nontrivial worst-case approximation to the optimal likelihood: we present a polynomial-time $1/\log m$-approximation algorithm (for data sets of size $m$), which moreover obtains a $1-\frac{1}{\log N}$-approximation if all $N$ elements appear in a $O(1/N)$-fraction of the subsets. In terms of techniques, the hardness result reduces to solving a gap instance of a “vector coloring" problem on a hypergraph obtained from an adaptation of the constructions of Bogdanov, Obata and Trevisan (FOCS 2002), using the strong expanders of Alon and Capalbo (FOCS 2007).

We introduce and study the model of list learning with attribute noise. Learning with attribute noise was introduced by Shackelford and Volper (COLT, 1988) as a variant of PAC learning, in which the algorithm has access to noisy examples and uncorrupted labels, and the goal is to recover an accurate hypothesis. Sloan (COLT, 1988) and Goldman and Sloan (Algorithmica, 1995) discovered information-theoretic limits to learning in this model, which have impeded further progress. In this article we extend the model to that of list learning, drawing inspiration from the list-decoding model in coding theory, and its recent variant studied in the context of learning. On the positive side, we show that sparse conjunctions can be efficiently list learned under some assumptions on the underlying ground-truth distribution. On the negative side, our results show that even in the list-learning model, efficient learning of parities and majorities is not possible regardless of the representation used.

Testing whether the observed data conforms to a purported model (probability distribution) is a basic and fundamental statistical task, and one that is by now well understood. However, the standard formulation, identity testing, fails to capture many settings of interest; in this work, we focus on one such natural setting, identity testing under promise of permutation. In this setting, the unknown distribution is assumed to be equal to the purported one, up to a relabeling (permutation) of the model: however, due to a systematic error in the reporting of the data, this relabeling may not be the identity. The goal is then to test identity under this assumption: equivalently, whether this systematic labeling error led to a data distribution statistically far from the reference model.

Motivated by the question of data quantization and "binning," we revisit the problem of identity testing of discrete probability distributions. Identity testing (a.k.a. one-sample testing), a fundamental and by now well-understood problem in distribution testing, asks, given a reference distribution (model) $\mathbf{q}$ and samples from an unknown distribution $\mathbf{p}$, both over $[n]=\{1,2,\dots,n\}$, whether $\mathbf{p}$ equals $\mathbf{q}$, or is significantly different from it. In this paper, we introduce the related question of 'identity up to binning,' where the reference distribution $\mathbf{q}$ is over $k \ll n$ elements: the question is then whether there exists a suitable binning of the domain $[n]$ into $k$ intervals such that, once "binned," $\mathbf{p}$ is equal to $\mathbf{q}$. We provide nearly tight upper and lower bounds on the sample complexity of this new question, showing both a quantitative and qualitative difference with the vanilla identity testing one, and answering an open question of Canonne (2019). Finally, we discuss several extensions and related research directions.

A function $f:\{0,1\}^n\rightarrow \{0,1\}$ is said to be $k$-monotone if it flips between 0 and 1 at most $k$ times on every ascending chain. Such functions represent a natural generalization of (1-)monotone functions, and have been recently studied in circuit complexity, PAC learning, and cryptography. Our work is part of a renewed focus in understanding testability of properties characterized by freeness of arbitrary order patterns as a generalization of monotonicity. Recently, Canonne et al. [ Innovations in Theoretical Computer Science, Schloss-Dagstuhl--Leibniz-Zentrum für Informatik GmBH, Wadern, Germany, 2017, 29] initiate the study of $k$-monotone functions in the area of property testing, and Newman et al. [SODA, SIAM, Philadelphia, 2017, pp. 1582--1597] study testability of families characterized by freeness from order patterns on real-valued functions over the line $[n]$ domain. We study $k$-monotone functions in the more relaxed parametrized property testing model, introduced by Parnas, Ron, and Rubinfeld [ J. Comput. System Sci., 72 (2006), pp. 1012--1042]. In this process we show strong lower bounds on testing $k$-monotonicity. Specifically, we show that testing 2-monotonicity on the hypercube nonadaptively with one-sided error requires an exponential in $\sqrt{n}$ number of queries. This behavior shows a stark contrast with testing (1-)monotonicity, which only needs $\tilde{O}\mleft(\sqrt{n}\mright)$ queries. Furthermore, even the apparently easier task of distinguishing 2-monotone functions from functions that are far from being $n^{.01}$-monotone also requires an exponential number of queries.

A Boolean $k$-monotone function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$-monotone functions are natural generalizations of the classical monotone functions, which are the $1$-monotone functions. Motivated by the recent interest in $k$-monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing, we initiate a systematic study of $k$-monotone functions, in the property testing model. In this model, the goal is to distinguish functions that are $k$-monotone (or are close to being $k$-monotone) from functions that are far from being $k$-monotone. Our results include the following: - We demonstrate a separation between testing $k$-monotonicity and testing monotonicity, on the hypercube domain $\{0,1\}^d$, for $k\geq 3$; - We demonstrate a separation between testing and learning on $\{0,1\}^d$, for $k=ω(\log d)$: testing $k$-monotonicity can be performed with $2^{O(\sqrt d \cdot \log d\cdot \log{1/\varepsilon})}$ queries, while learning $k$-monotone functions requires $2^{Ω(k\cdot \sqrt d\cdot{1/\varepsilon})}$ queries (Blais et al. (RANDOM 2015)). - We present a tolerant test for functions $f\colon[n]^d\to \{0,1\}$ with complexity independent of $n$, which makes progress on a problem left open by Berman et al. (STOC 2014). Our techniques exploit the testing-by-learning paradigm, use novel applications of Fourier analysis on the grid $[n]^d$, and draw connections to distribution testing techniques.

AC^0 o MOD_2 circuits are AC^0 circuits augmented with a layer of parity gates just above the input layer. We study AC^0 o MOD2 circuit lower bounds for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have highlighted this problem as a frontier problem in circuit complexity that arose both as a first step towards solving natural special cases of the matrix rigidity problem and as a candidate for constructing pseudorandom generators of minimal complexity. We give the first superlinear lower bound for the Boolean Inner Product function against AC^0 o MOD2 of depth four or greater. Specifically, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an ~Omega(n^2) lower bound for the special case of depth-4 AC^0 o MOD_2. Our proof of the depth-4 lower bound employs a new "moment-matching" inequality for bounded, nonnegative integer-valued random variables that may be of independent interest: we prove an optimal bound on the maximum difference between two discrete distributions’ values at 0, given that their first d moments match.

We generalize algorithms from computational learning theory that are successful under the uniform distribution on the Boolean hypercube {0, 1} n to algorithms successful on permutation-invariant distributions, distributions that stay invariant constant on permutating the coordinates in the instances. While the tools in our generalization mimic those used for the Boolean hypercube, the fact that permutation-invariant distributions are not product distributions presents a significant obstacle. We prove analogous results for permutation-invariant distributions; more generally, we work in the domain of the symmetric group. We define noise sensitivity in this setting and show that noise sensitivity has a nice combinatorial interpretation in terms of Young tableaux. The main technical innovations involve techniques from the representation theory of the symmetric group, especially the combinatorics of Young tableaux. We show that low noise sensitivity implies concentration on “simple” components of the Fourier spectrum and that this fact will allow us to agnostically learn halfspaces under permutation-invariant distributions to constant accuracy in roughly the same time as in the uniform distribution over the Boolean hypercube case.

A function f is d-resilient if all its Fourier coefficients of degree at most d are zero, i.e. f is uncorrelated with all low-degree parities. We study the notion of approximate resilience of Boolean functions, where we say that f is α-approximately d-resilient if f is α-close to a [-1, 1]-valued d-resilient function in ℓ1 distance. We show that approximate resilience essentially characterizes the complexity of agnostic learning of a concept class C over the uniform distribution. Roughly speaking, if all functions in a class C are far from being d-resilient then C can be learned agnostically in time nO(d) and conversely, if C contains a function close to being d-resilient then agnostic learning of C in the statistical query (SQ) framework of Kearns has complexity of at least nΩ(d). Focusing on monotone Boolean functions, we exhibit the existence of near-optimal α-approximately -resilient monotone functions for all α > 0. Prior to our work, it was conceivable even that every monotone function is Ω(1)-far from any 1-resilient function. Furthermore, we construct simple, explicit monotone functions based on Tribes and CycleRun that are close to highly resilient functions. Our constructions are based on general resilience analysis and amplification techniques we introduce. These structural results, together with the characterization, imply nearly optimal lower bounds for agnostic learning of monotone juntas, a natural variant of the well-studied junta learning problem. In particular we show that no SQ algorithm can efficiently agnostically learn monotone k-juntas for any k = ω(1) and any constant error less than 1/2.

One of the classic results in analysis of Boolean functions is a result of Friedgut~cite{Fri98} that states that Boolean functions over the hypercube of low influence are approximately juntas, functions which are determined by few coordinates. While this result has also been extended to product distributions, not much is known in the case of nonproduct distributions. We generalize this result to slices of the Boolean cube. A slice of the Boolean cube is the set of strings with some fixed Hamming weight. In this setting, we define the notion of influence and determine a natural orthogonal basis for functions over these domains. We essentially follow the proof for the uniform distribution case, but the set up in order to do so is highly nontrivial. The main techniques used are combinatorics of Young tableaux motivated by the representation theory of the symmetric group along with an application of hypercontractivity in slices of the Boolean hypercube due to O'Donnell and Wimmer OWimmer:[OW09].

We generalize the Kahn--Kalai--Linial (KKL) theorem to random walks on Cayley and Schreier graphs, making progress on an open problem of Hoory, Linial, and Wigderson. In our generalization, the underlying group need not be abelian so long as the generating set is a union of conjugacy classes. An example corollary is that for every $f : \binom{[n]}{k} \to \{0,1\}$ with ${\bf E}[f]$ and $k/n$ bounded away from $0$ and $1$, there is a pair $1 \leq i < j \leq n$ such that ${\cal I}_{ij}(f) \geq \Omega(\frac{\log n}{n})$. Here ${\cal I}_{ij}(f)$ denotes the “influence” on $f$ of swapping the $i$th and $j$th coordinates. Using this corollary we obtain a “robust” version of the Kruskal--Katona theorem: Given a constant-density subset $A$ of a middle slice of the Hamming $n$-cube, the density of $\partial A$ is greater by at least $\Omega(\frac{\log n}{n})$, unless $A$ is noticeably correlated with a single coordinate. As an application of these results, we show that the set of functions $\{0, 1, x_1, \dots, x_n, \mathrm{Maj}\}$ is a $(1/2 - \gamma)$-net for the set of all $n$-bit monotone Boolean functions, where $\gamma = \Omega(\frac{\log n}{\sqrt{n}})$. This distance is optimal for polynomial-size nets and gives an optimal weak-learning algorithm for monotone functions under the uniform distribution, solving a problem of Blum, Burch, and Langford.

We present a range of new results for testing properties of Boolean functions that are defined in terms of the Fourier spectrum. Broadly speaking, our results show that the property of a Boolean function having a concise Fourier representation is locally testable. We give the first efficient algorithms for testing whether a Boolean function has a sparse Fourier spectrum (small number of nonzero coefficients) and for testing whether the Fourier spectrum of a Boolean function is supported in a low-dimensional subspace of $\mathbb{F}_2^n$. In both cases we also prove lower bounds showing that any testing algorithm—even an adaptive one—must have query complexity within a polynomial factor of our algorithms, which are nonadaptive. Building on these results, we give an “implicit learning” algorithm that lets us test any subproperty of Fourier concision. We also present some applications of these results to exact learning and decoding. Our technical contributions include new structural results about sparse Boolean functions and new analysis of the pairwise independent hashing of Fourier coefficients from [V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 563–576].

We generalize algorithms from computational learning theory that are successful under the uniform distribution on the Boolean hypercube {0,1}nto algorithms successful on permutation invariant distributions. A permutation invariant distribution is a distribution where the probability mass remains constant upon permutations in the instances. While the tools in our generalization mimic those used for the Boolean hypercube, the fact that permutation invariant distributions are not product distributions presents a significant obstacle. Under the uniform distribution, halfspaces can be agnostically learned in polynomial time for constant e. The main tools used are a theorem of Peres [Per04] bounding the noise sensitivity of a halfspace, a result of [KOS04] that this theorem implies Fourier concentration, and a modification of the Low-Degree algorithm of Linial, Mansour, Nisan [LMN93] made by Kalai et. al. [KKMS08]. These results are extended to arbitrary product distributions in [BOW08]. We prove analogous results for permutation invariant distributions; more generally, we work in the domain of the symmetric group. We define noise sensitivity in this setting, and show that noise sensitivity has a nice combinatorial interpretation in terms of Young tableaux. The main technical innovations involve techniques from the representation theory of the symmetric group, especially the combinatorics of Young tableaux. We show that low noise sensitivity implies concentration on "simple" components of the Fourier spectrum, and that this fact will allow us to agnostically learn halfspaces under permutation invariant distributions to constant accuracy in roughly the same time as in the uniform distribution over the Boolean hypercube case.

We generalize the Kahn-Kalai-Linial (KKL) Theorem to random walks on Cayley and Schreier graphs, making progress on an open problem of Hoory, Linial, and Wigderson. In our generalization, the underlying group need not be abelian so long as the generating set is a union of conjugacy classes. An example corollary is that for every f : (k[n]) ¿ {0,1} with E[f] and k/n bounded away from 0 and 1, there is a pair 1 ¿ iij(f) ¿ ¿(log n/n). Here lij(f) denotes the "influence" on / of swapping the ith and jth coordinates. Using this corollary we obtain a "robust" version of the Kruskal-Katona Theorem: Given a constant-density subset A of a middle slice of the Hamming n-cube, the density of ¿A is greater by at least ¿(log n/n), unless A is noticeably correlated with a single coordinate. As an application of these results, we show that the set of functions {0,1, x1,..., x¿, Maj} is a (1/2-¿)-net for the set of all n-bit monotone boolean functions, where ¿ = ¿(log n//¿(n)). This distance is optimal for polynomial-size nets and gives an optimal weak-learning algorithm for monotone functions under the uniform distribution, solving a problem of Blum, Burch and Langford.