 Home
 Search Results
 Page 1 of 1
Search for: All records

Total Resources1
 Resource Type

01000000000
 More
 Availability

10
 Author / Contributor
 Filter by Author / Creator


Feldman, Vitaly (1)

Ghazi, Badih (1)

#Tyler Phillips, Kenneth E. (0)

#Willis, Ciara (0)

& AbreuRamos, E. D. (0)

& Abramson, C. I. (0)

& AbreuRamos, E. D. (0)

& Adams, S.G. (0)

& Ahmed, K. (0)

& Ahmed, Khadija. (0)

& Aina, D.K. Jr. (0)

& AkcilOkan, O. (0)

& Akuom, D. (0)

& Aleven, V. (0)

& AndrewsLarson, C. (0)

& Archibald, J. (0)

& Arnett, N. (0)

& Arya, G. (0)

& Attari, S. Z. (0)

& Ayala, O. (0)

 Filter by Editor


& Spizer, S. M. (0)

& . Spizer, S. (0)

& Ahn, J. (0)

& Bateiha, S. (0)

& Bosch, N. (0)

& Brennan K. (0)

& Brennan, K. (0)

& Chen, B. (0)

& Chen, Bodong (0)

& Drown, S. (0)

& Ferretti, F. (0)

& Higgins, A. (0)

& J. Peters (0)

& Kali, Y. (0)

& RuizArias, P.M. (0)

& S. Spitzer (0)

& Sahin. I. (0)

& Spitzer, S. (0)

& Spitzer, S.M. (0)

(submitted  in Review for IEEE ICASSP2024) (0)


Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Several wellstudied models of access to data samples, including statistical queries, local differential privacy and lowcommunication algorithms rely on queries that provide information about a function of a single sample. (For example, a statistical query (SQ) gives an estimate of $\E_{x\sim D}[q(x)]$ for any choice of the query function $q:X\rightarrow \R$, where $D$ is an unknown data distribution.) Yet some data analysis algorithms rely on properties of functions that depend on multiple samples. Such algorithms would be naturally implemented using $k$wise queries each of which is specified by a function $q:X^k\rightarrow \R$. Hence it is natural to ask whether algorithms using $k$wise queries can solve learning problems more efficiently and by how much. Blum, Kalai, Wasserman~\cite{blum2003noise} showed that for any weak PAC learning problem over a fixed distribution, the complexity of learning with $k$wise SQs is smaller than the (unary) SQ complexity by a factor of at most $2^k$. We show that for more general problems over distributions the picture is substantially richer. For every $k$, the complexity of distributionindependent PAC learning with $k$wise queries can be exponentially larger than learning with $(k+1)$wise queries. We then give two approaches for simulating a $k$wise query using unary queries. The first approach exploits the structure of the problem that needs to be solved. It generalizes and strengthens (exponentially) the results of Blum \etal \cite{blum2003noise}. It allows us to derive strong lower bounds for learning DNF formulas and stochastic constraint satisfaction problems that hold against algorithms using $k$wise queries. The second approach exploits the $k$party communication complexity of the $k$wise query function.more » « less