License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.22
URN: urn:nbn:de:0030-drops-117076
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11707/
Go to the corresponding LIPIcs Volume Portal

Fleming, Noah ; Yoshida, Yuichi

Distribution-Free Testing of Linear Functions on ℝⁿ

pdf-format:
LIPIcs-ITCS-2020-22.pdf (0.6 MB)

Abstract

We study the problem of testing whether a function f:ℝⁿ → ℝ is linear (i.e., both additive and homogeneous) in the distribution-free property testing model, where the distance between functions is measured with respect to an unknown probability distribution over ℝⁿ. We show that, given query access to f, sampling access to the unknown distribution as well as the standard Gaussian, and ε > 0, we can distinguish additive functions from functions that are ε-far from additive functions with O((1/ε)log(1/ε)) queries, independent of n. Furthermore, under the assumption that f is a continuous function, the additivity tester can be extended to a distribution-free tester for linearity using the same number of queries. On the other hand, we show that if we are only allowed to get values of f on sampled points, then any distribution-free tester requires Ω(n) samples, even if the underlying distribution is the standard Gaussian.

BibTeX - Entry

@InProceedings{fleming_et_al:LIPIcs:2020:11707,
  author =	{Noah Fleming and Yuichi Yoshida},
  title =	{{Distribution-Free Testing of Linear Functions on ??}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11707},
  URN =		{urn:nbn:de:0030-drops-117076},
  doi =		{10.4230/LIPIcs.ITCS.2020.22},
  annote =	{Keywords: Property Testing, Distribution-Free Testing, Linearity Testing}
}

Keywords: Property Testing, Distribution-Free Testing, Linearity Testing
Collection: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 06.01.2020

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