Exploring the Power of Wise Queries in Statistical Learning
Vitaly Feldman
Badih Ghazi
IBM Research – Almaden
MIT, CSAIL
2017
Statistical problems
Algorithm
Statistical queries
[Kearns ‘93]
SQ algorithm
Abstraction
•
Noise-tolerance,
privacy,
distributed ML,
evolvability,
adaptive data analysis
SQ complexity
•
Most techniques for statistical problems have SQ analogues
•
Easier to prove lower bound against SQ algorithms
Build on
[
F
. 16]
and
[Steinhardt,Valiant,Wager 16]
Example corollaries
Discussion
•
Implications for additional models
–
Local differential privacy
–
Algorithms that extract few bits from each sample
•
Open problems
–
General approach that unifies the two reductions
Dive into the world of statistical learning with a focus on the impact of wise queries. Discover how statistical problems are approached, the significance of statistical queries, and the comparisons between wise and unary queries. Explore the implications for PAC learning and uncover key insights into algorithm complexity and lower bounds in statistical analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
On the power of learning from ?-wise queries Vitaly Feldman IBM Research Almaden Badih Ghazi MIT, CSAIL 2017
Statistical problems ? is orange ? ? ?: distributions over ? ?1,?2, ,?? ? Algorithm PAC learning a class ? of Boolean functions over ?: ?: (?, ), where ? ? over domain ? and = ?(?) for unknown ? ? Output hypothesis : Pr (?, ) ? ? = 1 ?
Statistical queries [Kearns 93] ?1 ?1 ?2 ? ? ?: distributions over ? ?2 ?1,?2, ,?? ? ? ?? ?? SQ algorithm STAT?(?) oracle ?1 ?? ??1? ? ?1:? 1,1 ? is tolerance of the query; ? 1/?2 Abstraction Noise-tolerance,privacy, distributed ML,evolvability,adaptive data analysis SQ complexity Most techniques for statistical problems have SQ analogues Easier to prove lower bound against SQ algorithms
?-wise SQs ?1 ?1 ?2 ?2 ? ?? ?? ?-wise SQ algorithm (?)(?) oracle STAT? ?1:?? 1,1 , ?1 ??1, ,?? ??1?1, ,?? ? Examples: Collision probability: ?? ?1,?2 ?[?1= ?2] Hardness amplification: ?(? ?1, ,? ??)
Are ?-wise SQs more powerful? PAC learning with fixed ? (?)(?) If ? is learnable using ? queries to STAT? Then learnable using 2? ? queries to STAT?(?/2?) [Blum,Kalai,Wasserman 2000] Separation: For every ?,? there exist a class of functions ? that ?(1/poly(?)) Is PAC learnable using poly(?) queries to STAT? Requires 2? queries to STAT? (? 1)(1/2?) to PAC learn
Reductions from ?-wise to unary ? ? ?0? ? ?0, sup ? ?, ? ? (?)(?) can be simulated using O ?? 1 ?3 If ? is ?-flat then STAT? queries to STAT? ?3 ? ? PAC learning with fixed ? is 2-flat. Generalizes and strengthens [BKW 00] If ?:?? { 1,1} has ?-party randomized communication complexity of ? bits per party then query ? to STAT? answered using O ??/?2 queries to STAT??? ?/? (?)(?) can be Build on [F. 16] and [Steinhardt,Valiant,Wager 16]
Example corollaries Lower bounds against ?1 ?-wise SQ algorithms, ? > 0 Learning DNF formulas of size ? over ? vars Stochastic MAX- -CSPs and -SAT refutation, 3 1 ?2 queries Collision probability can be estimated within ? using ? to STAT??? 1
Discussion Implications for additional models Local differential privacy Algorithms that extract few bits from each sample Open problems General approach that unifies the two reductions
