On the Power of Learning from k-Wise Queries

DOI10.4230/LIPICS.ITCS.2017.41MaRDI QIDQ4638095zbMATH OpenOpenAlexFDO

Authors Vitaly Feldman, Badih Ghazi

Publication date 3 May 2018

Full work available at URL https://arxiv.org/abs/1703.00066

zbMATH Keywords

communication complexitydifferential privacylower boundsPAC learningstatistical queries

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32)

Abstract: Several well-studied models of access to data samples, including statistical queries, local differential privacy and low-communication 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}_{xsimD}[q(x)]$ for any choice of the query function $q$ mapping $X$ to the reals, where $D$ is an unknown data distribution over $X$.) 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$ mapping $X^k$ to the reals. Hence it is natural to ask whether algorithms using $k$-wise queries can solve learning problems more efficiently and by how much. Blum, Kalai and Wasserman (2003) 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 distribution-independent 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 et al.. 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.

Recommendations

• Learning via finitely many queries
• A general dimension for query learning
• A framework for polynomial-time query learnability
• scientific article; zbMATH DE number 67809
• Learning via queries and oracles
• Learning via queries in [+, <]
• scientific article; zbMATH DE number 2080666
• Characterizing statistical query learning: simplified notions and proofs
• Complexity theoretic hardness results for query learning
• Publication:4955302

Cites work

• A polynomial-time algorithm for learning noisy linear threshold functions
• A simple polynomial-time rescaling algorithm for solving linear programs
• A theory of the learnable
• Approximate resilience, monotonicity, and the complexity of agnostic learning
• Candidate one-way functions based on expander graphs
• Communication Complexity
• Dealing with range anxiety in mean estimation via statistical queries
• Efficient noise-tolerant learning from statistical queries
• Evolvability
• General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
• scientific article; zbMATH DE number 2038320 (Why is no real title available?)
• scientific article; zbMATH DE number 5485575 (Why is no real title available?)
• Interactive privacy via the median mechanism
• Learning by distances
• Learning from satisfying assignments
• Learning with restricted focus of attention
• Noise-tolerant learning, the parity problem, and the statistical query model
• On the complexity of random satisfiability problems with planted solutions
• Preserving statistical validity in adaptive data analysis (extended abstract)
• Statistical active learning algorithms for noise tolerance and differential privacy
• Statistical algorithms and a lower bound for detecting planted cliques
• The Fourier transform of Poisson multinomial distributions and its algorithmic applications
• Theory of Cryptography
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• What can we learn privately?

Cited in

(2)

• The consistency dimension and distribution-dependent learning from queries.
• LAQP: learning-based approximate query processing

Describes a project that uses

Uses Software

• RAPPOR

This page was built for publication: On the Power of Learning from k-Wise Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638095)