Search Results

Documents authored by Black, Hadley

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.37
Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions

Authors: Hadley Black

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
We study monotonicity testing of functions f : {0,1}^d → {0,1} using 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(Õ(min{(1/ε)√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 Ω(√{exp(d)/ε}) in the small ε parameter regime, when ε = O(d^{-3/2}), due to Goldreich-Goldwasser-Lehman-Ron-Samorodnitsky (Combinatorica 2000). Thus, the sample complexity of monotonicity testing was wide open for ε ≫ d^{-3/2}. We resolve this question, obtaining a nearly tight lower bound of exp(Ω(min{(1/ε)√d,d})) for all ε at most a sufficiently small constant. In fact, we prove a much more general result, showing that the sample complexity of k-monotonicity testing and learning for functions f : {0,1}^d → [r] is exp(Ω(min{(rk/ε)√d,d})). For testing with one-sided error we show that the sample complexity is exp(Ω(d)). Beyond the hypercube, we prove nearly tight bounds (up to polylog factors of d,k,r,1/ε in the exponent) of exp(Θ̃(min{(rk/ε)√d,d})) on the sample complexity of testing and learning measurable k-monotone functions f : ℝ^d → [r] under product distributions. Our upper bound improves upon the previous bound of exp(Õ(min{(k/ε²)√d,d})) by Harms-Yoshida (ICALP 2022) for Boolean functions (r = 2).
Cite as

Hadley Black. Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{black:LIPIcs.APPROX/RANDOM.2024.37,
  author =	{Black, Hadley},
  title =	{{Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{37:1--37:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.37},
  URN =		{urn:nbn:de:0030-drops-210308},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.37},
  annote =	{Keywords: Property testing, learning, Boolean functions, monotonicity, k-monotonicity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.15
Testing and Learning Convex Sets in the Ternary Hypercube

Authors: Hadley Black, Eric Blais, and Nathaniel Harms

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
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}ⁿ. 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,±1}ⁿ, showing that the maximum edge boundary of a convex set is Õ(n^{3/4})⋅3ⁿ, or equivalently that every convex set has influence Õ(n^{3/4}) and a convex set exists with influence Ω(n^{3/4}). Learning and sample-based testing: We prove upper and lower bounds of 3^{Õ(n^{3/4})} and 3^{Ω(√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^{Θ(n)}. Testing with queries: We prove nearly matching upper and lower bounds of 3^{Θ̃(√n)} for one-sided error testing of convex sets with non-adaptive queries.
Cite as

Hadley Black, Eric Blais, and Nathaniel Harms. Testing and Learning Convex Sets in the Ternary Hypercube. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{black_et_al:LIPIcs.ITCS.2024.15,
  author =	{Black, Hadley and Blais, Eric and Harms, Nathaniel},
  title =	{{Testing and Learning Convex Sets in the Ternary Hypercube}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{15:1--15:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.15},
  URN =		{urn:nbn:de:0030-drops-195435},
  doi =		{10.4230/LIPIcs.ITCS.2024.15},
  annote =	{Keywords: Property testing, learning theory, convex sets, testing convexity, fluctuation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.25
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

Authors: Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions f:{0,1}^d → ℝ. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function f over an arbitrary partially ordered domain as a collection of Boolean functions over the same domain, roughly capturing the distance of f to monotonicity and the structure of violations of f to monotonicity. We apply our generalized isoperimetric inequality to improve algorithms for testing monotonicity and approximating the distance to monotonicity for real-valued functions. Our tester for monotonicity has query complexity Õ(min(r √d,d)), where r is the size of the image of the input function. (The best previously known tester makes O(d) queries, as shown by Chakrabarty and Seshadhri (STOC 2013).) Our tester is nonadaptive and has 1-sided error. We prove a matching lower bound for nonadaptive, 1-sided error testers for monotonicity. We also show that the distance to monotonicity of real-valued functions that are α-far from monotone can be approximated nonadaptively within a factor of O(√{d log d}) with query complexity polynomial in 1/α and the dimension d. This query complexity is known to be nearly optimal for nonadaptive algorithms even for the special case of Boolean functions. (The best previously known distance approximation algorithm for real-valued functions, by Fattal and Ron (TALG 2010) achieves O(d log r)-approximation.)
Cite as

Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{black_et_al:LIPIcs.ICALP.2023.25,
  author =	{Black, Hadley and Kalemaj, Iden and Raskhodnikova, Sofya},
  title =	{{Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.25},
  URN =		{urn:nbn:de:0030-drops-180774},
  doi =		{10.4230/LIPIcs.ICALP.2023.25},
  annote =	{Keywords: Isoperimetric inequalities, property testing, monotonicity testing}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact