On the Power of Learning from k-Wise Queries
From MaRDI portal
Publication:4638095
DOI10.4230/LIPIcs.ITCS.2017.41zbMath1402.68111arXiv1703.00066OpenAlexW2593906620MaRDI QIDQ4638095
Publication date: 3 May 2018
Full work available at URL: https://arxiv.org/abs/1703.00066
Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A polynomial-time algorithm for learning noisy linear threshold functions
- General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
- Learning with restricted focus of attention
- Learning by distances
- Statistical active learning algorithms for noise tolerance and differential privacy
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- Interactive privacy via the median mechanism
- Preserving Statistical Validity in Adaptive Data Analysis
- Candidate One-Way Functions Based on Expander Graphs
- What Can We Learn Privately?
- Efficient noise-tolerant learning from statistical queries
- A theory of the learnable
- Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization
- On the Complexity of Random Satisfiability Problems with Planted Solutions
- Communication Complexity
- The fourier transform of poisson multinomial distributions and its algorithmic applications
- Learning from satisfying assignments
- Approximate resilience, monotonicity, and the complexity of agnostic learning
- Statistical algorithms and a lower bound for detecting planted cliques
- Theory of Cryptography
- Evolvability
- Noise-tolerant learning, the parity problem, and the statistical query model
- A simple polynomial-time rescaling algorithm for solving linear programs
This page was built for publication: On the Power of Learning from k-Wise Queries
