License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.61
URN: urn:nbn:de:0030-drops-188867
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18886/
Go to the corresponding LIPIcs Volume Portal

Ferreira Pinto Jr., Renato

Directed Poincaré Inequalities and L¹ Monotonicity Testing of Lipschitz Functions

pdf-format:
LIPIcs-APPROX61.pdf (0.8 MB)

Abstract

We study the connection between directed isoperimetric inequalities and monotonicity testing. In recent years, this connection has unlocked breakthroughs for testing monotonicity of functions defined on discrete domains. Inspired the rich history of isoperimetric inequalities in continuous settings, we propose that studying the relationship between directed isoperimetry and monotonicity in such settings is essential for understanding the full scope of this connection.
Hence, we ask whether directed isoperimetric inequalities hold for functions f:[0,1]ⁿ → R, and whether this question has implications for monotonicity testing. We answer both questions affirmatively. For Lipschitz functions f:[0,1]ⁿ → ℝ, we show the inequality d^mono₁(f) ≲ ? [‖∇^- f‖₁], which upper bounds the L¹ distance to monotonicity of f by a measure of its "directed gradient". A key ingredient in our proof is the monotone rearrangement of f, which generalizes the classical "sorting operator" to continuous settings. We use this inequality to give an L¹ monotonicity tester for Lipschitz functions f:[0,1]ⁿ → ℝ, and this framework also implies similar results for testing real-valued functions on the hypergrid.

BibTeX - Entry

@InProceedings{ferreirapintojr.:LIPIcs.APPROX/RANDOM.2023.61,
  author =	{Ferreira Pinto Jr., Renato},
  title =	{{Directed Poincar\'{e} Inequalities and L¹ Monotonicity Testing of Lipschitz Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{61:1--61:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18886},
  URN =		{urn:nbn:de:0030-drops-188867},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.61},
  annote =	{Keywords: Monotonicity testing, property testing, isoperimetric inequalities, Poincar\'{e} inequalities}
}

Keywords: Monotonicity testing, property testing, isoperimetric inequalities, Poincaré inequalities
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI