Publications
- • Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions
- Hadley Black
Manuscript.
-
[arXiv]
[short summary]
We study monotonicity testing of functions $f \colon \{0,1\}^d \to \{0,1\}$ using \emph{sample-based} algorithms, which are only allowed to observe the value of $f$ on points drawn independently from the uniform distribution. A classic result by Bshouty-Tamon (J. ACM 1996) proved that monotone functions can be learned with $\exp(O(\min\{\frac{1}{\eps}\sqrt{d},d\}))$ samples and it is not hard to show that this bound extends to testing. Prior to our work the only lower bound for this problem was $\Omega(\sqrt{\exp(d)/\varepsilon})$ in the small $\eps$ parameter regime, when $\varepsilon = O(d^{-3/2})$, due to Goldreich-Goldwasser-Lehman-Ron-Samorodnitsky (Combinatorica 2000). Thus, the sample complexity of monotonicity testing was wide open for $\eps \gg d^{-3/2}$. We resolve this question, obtaining a tight lower bound of $\exp(\Omega(\min\{\frac{1}{\eps}\sqrt{d},d\}))$ for all $\eps$ at most a sufficiently small constant. In fact, we prove a much more general result, showing that the sample complexity of $k$\emph{-monotonicity} testing and learning for functions $f \colon \{0,1\}^d \to [r]$ is $\exp(\Theta(\min\{\frac{rk}{\eps}\sqrt{d},d\}))$. For testing with one-sided error we show that the sample complexity is $\exp(\Theta(d))$.
Beyond the hypercube, we prove nearly tight bounds (up to polylog factors of $d,k,r,1/\eps$ in the exponent) of $\exp(\widetilde{\Theta}(\min\{\frac{rk}{\varepsilon}\sqrt{d},d\}))$ on the sample complexity of testing and learning measurable $k$-monotone functions $f \colon \mathbb{R}^d \to [r]$ under product distributions. Our upper bound improves upon the previous bound of $\exp(\widetilde{O}(\min\{\frac{k}{\varepsilon^2}\sqrt{d},d\}))$ by Harms-Yoshida (ICALP 2022) for Boolean functions ($r=2$).
- • Testing and Learning Convex Sets in the Ternary Hypercube
- Hadley Black, Eric Blais, and Nathaniel Harms
Innovations in Theoretical Computer Science (ITCS) 2024.
-
[arXiv]
[short summary]
We study the problems of testing and learning high-dimensional discrete convex sets. The simplest high-dimensional discrete domain where convexity is a non-trivial property is the ternary hypercube, $\{-1,0,1\}^n$. The goal of this work is to understand structural combinatorial properties of convex sets in this domain and to determine the complexity of the testing and learning problems. We obtain the following results.
Structural: We prove nearly tight bounds on the edge boundary of convex sets in $\{0,\pm 1\}^n$, showing that the maximum edge boundary of a convex set is $\widetilde \Theta(n^{3/4}) \cdot 3^n$, or equivalently that every convex set has influence $\widetilde{O}(n^{3/4})$ and a convex set exists with influence $\Omega(n^{3/4})$.
Learning and sample-based testing: We prove upper and lower bounds of $3^{\widetilde{O}(n^{3/4})}$ and $3^{\Omega(\sqrt{n})}$ for the task of learning convex sets under the uniform distribution from random examples. The analysis of the learning algorithm relies on our upper bound on the influence. Both the upper and lower bound also hold for the problem of sample-based testing with two-sided error. For sample-based testing with one-sided error we show that the sample-complexity is $3^{\Theta(n)}$.
Testing with queries: We prove nearly matching upper and lower bounds of $3^{\widetilde{\Theta}(\sqrt{n})}$ for one-sided error testing of convex sets with non-adaptive queries.
- • A d^{1/2+o(1)} Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids
- Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
Foundations of Computer Science (FOCS) 2023. Invited to SICOMP special issue.
-
[arXiv]
[ECCC]
[short summary]
This work studies the problem of testing monotonicity of Boolean-valued functions over the d-dimensional, n-width hypergrid. For the special case of n = 2 (the hypercube), a seminal work of Khot-Minzer-Safra (SICOMP 2018) showed that you can test with essentially d^{1/2} queries and this is optimal among all non-adaptive testers (Chen-Waingarten-Xie STOC 2017). To analyze their tester, they proved a directed analogue of Talagrand's isoperimetric inequality for Boolean functions from 1993. In our paper from STOC 2023 we generalized the directed Talagrand inequality to hypergrids and using this we analyzed a tester that makes n*d^{1/2} queries.
Can we remove the dependence on n from our STOC 2023 result and obtain a monotonicity tester for Boolean-valued functions over hypergrids that makes d^{1/2} queries, matching the upper and lower bound for the n = 2 case?
Our main result is a non-adaptive, 1-sided error monotonicity tester for such functions that makes d^{1/2 + o(1)} queries, thus resolving the non-adaptive monotonicity testing question for all values of n, up to a d^{o(1)} factor. Central to our analysis is the inequality obtained in our STOC 2023 paper and our Domain Reduction Theorem from our SODA 2020 paper. We also introduce many new technical ingredients that allow us to replace n by d^{o(1)} in the query complexity.
- • Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid
and an ~O(n\sqrt{d}) Monotonicity Tester
- Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
Symposium on Theory of Computing (STOC) 2023.
-
[arXiv]
[ECCC]
[short summary]
This work studies the problem of testing monotonicity of Boolean-valued functions over the d-dimensional, n-width hypergrid. For the special case of n = 2 (the hypercube), a seminal work of Khot-Minzer-Safra (SICOMP 2018) showed that you can test with essentially d^{1/2} queries. To analyze their tester, they proved a directed analogue of Talagrand's isoperimetric inequality for Boolean functions from 1993. Previous works of ours from SODA 2018 and SODA 2020 showed that for general hypergrids (arbitrary n) there is a d^{5/6} query tester (ignoring poly(log(d),epsilon) factors). This result was obtained by proving a directed analogue of an inequality by Margulis for hypergrids. The Margulis inequality is weaker than the Talagrand inequality and so a natural next step in this line of inquiry was to try to generalize Khot-Minzer-Safra's directed Talagrand inequality to hypergrids.
Is there a generalization of the directed Talagrand inequality for hypergrids? Can we test monotonicity of Boolean-valued functions over the d-dimensional, n-width hypergrid with d^{1/2} queries?
In this paper, we prove a generalization of the directed Talagrand inequality for hypergrids and use it to analyze a tester for Boolean functions on this domain which makes n*d^{1/2} queries. This is the first result to achieve the optimal dependence on d for any n > 2.
- • Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing
- Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova
Random Structures and Algorithms (RSA) 2024.
-
Preliminary version in International Colloquium on Automata, Languages, and Programming (ICALP) 2023.
-
[arXiv]
[ECCC]
[Journal]
[short summary]
Monotonicity testing of Boolean functions over the hypercube domain has been studied extensively since its introduction by Goldreich-Goldwasser-Lehman-Ron-Samorodnitsky in 1999. A seminal work of Khot-Minzer-Safra (SICOMP 2018) showed that you can test with essentially d^{1/2} queries. To analyze their tester, they proved a directed analogue of Talagrand's isoperimetric inequality for Boolean functions from 1993. In contrast, the complexity of monotonicity testing of real-valued functions over the hypercube has been established as Theta(d) with matching upper and lower bounds (Chakrabarty-Seshadhri 2013, Blais-Brody-Matulef 2012), although the lower bound relies on a family of functions with a large range.
What is the complexity of testing monotonicity of functions over the hypercube with range size at most r? Do the known directed isoperimetric inequalities extend beyond the Boolean range?
Our main result is a generalization of Khot-Minzer-Safra's directed Talagrand inequality to real-valued functions whose range consists of any number of elements. To obtain this generalization we prove what we call the Boolean Decomposition Theorem, which informally says that any real-valued function f over any DAG G can be "decomposed" into a collection of {0,1}-valued functions f_1,...,f_k over G which (a) collectively "preserve" the distance to monotonicity of f and (b) any edge that violates monotonicity of f_i also is a violation for f. This allows us to "lift" known inequalities for Boolean functions to real-valued functions.
Using our generalized directed Talagrand inequality we establish the following two results. (a) We give a non-adaptive, 1-sided error monotonicity tester for functions over the hypercube with range size at most r that makes r sqrt(d) queries and show a matching lower bound for this class of testers. (b) We give an algorithm for approximating the distance to monotonicity of real-valued functions that matches the state of the art for Boolean functions.
- • Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
- Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2020.
-
[arXiv]
[ECCC]
[short summary]
This work studies the problem of monotonicity testing of Boolean-valued functions over the d-dimensional, n-width hypergrid. A previous work of ours from SODA 2018 showed that there is a o(d) polylog(n) query tester. Other prior work (Dodis-Goldreich-Lehman-Raskhodnikova-Ron-Samorodnitsky 1999, Berman-Raskhodnikova-Yaroslavtsev 2014) showed that O(d) queries are possible with no dependence on n.
Can we remove the polylog(n) dependence from our SODA 2018 result, and more generally is there a black-box method for removing dependencies on n? If so, can testing results over hypergrids be extended to continuous space?
In this paper we showed that n can be replaced by poly(d) in a black-box fashion, thus implying a o(d) tester with no dependence on n by combining with our previous paper. The theorem that achieves this reduction is our main contribution, which we call the Domain Reduction Theorem which says the following. Suppose f is a Boolean-valued function over the d-dimensional, n-width hypergrid. Now sub-sample k values from [n] iid in each dimension and consider the restriction of f to the resulting d-dimensional, k-width sub-hypergrid. We prove that if k > poly(d/epsilon), then the distance to monotonicity is preserved by the restriction, up to a constant factor. Therefore, it suffices to test for monotonicity of the restriction, replacing any dependence on n by a dependence on k. Using standard measure-theoretic tools we are also able to extend the Domain Reduction Theorem and testing result to apply to measurable Boolean-valued functions over d-dimensional continuous space under product distributions.
- • A o(d) polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d
- Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2018.
-
[arXiv]
[ECCC]
[short summary]
This work studies the problem of monotonicity testing of Boolean-valued functions over the d-dimensional, n-width hypergrid. Prior to this paper the best known testers had query complexity linear in d, and independent of n. For the special case of n = 2, it was known that o(d)-query testers are possible by exploiting a beautiful connection to isoperimetric inequalities from the theory of Boolean functions.
To what extent does this connection extend to hypergrids and can we achieve o(d) query testers?
In this paper we gave the first tester for the setting of arbitrary n > 2 with query complexity sublinear in d, although with a poly-logarithmic depedendence on n. Our tester is non-adaptive and has 1-sided error. The main technical contribution is a directed Margulis-style isoperimetric inequality for hypergrids, generalizing an inequality proven by Chakrabarty-Seshadhri (STOC 2013) who obtained the first sublinear in d tester for the hypercube (n = 2) setting.
|
