Weakly learning DNF and characterizing statistical query learning using Fourier analysis
From MaRDI portal
Publication:2817616
DOI10.1145/195058.195147zbMath1345.68186OpenAlexW2064680241MaRDI QIDQ2817616
Steven Rudich, Michael Kearns, Yishay Mansour, Merrick L. Furst, Jeffrey C. Jackson, Avrim L. Blum
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/195058.195147
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)
Related Items (43)
On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ On approximating weighted sums with exponentially many terms ⋮ On learning monotone DNF under product distributions ⋮ Learning functions of \(k\) relevant variables ⋮ Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ Algorithmic Signaling of Features in Auction Design ⋮ On the Power of Learning from k-Wise Queries ⋮ Simple learning algorithms using divide and conquer ⋮ A general dimension for query learning ⋮ Quantum machine learning: a classical perspective ⋮ Learning intersections and thresholds of halfspaces ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ Selection of relevant features and examples in machine learning ⋮ An efficient membership-query algorithm for learning DNF with respect to the uniform distribution ⋮ Polynomial‐time universality and limitations of deep learning ⋮ Adversarial manifold estimation ⋮ Unnamed Item ⋮ VC bounds on the cardinality of nearly orthogonal function classes ⋮ Learning random monotone DNF ⋮ BKW meets Fourier new algorithms for LPN with sparse parities ⋮ A complete characterization of statistical query learning with applications to evolvability ⋮ Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles ⋮ Learning nonsingular phylogenies and hidden Markov models ⋮ Rapidly computing sparse Legendre expansions via sparse Fourier transforms ⋮ Predicting nearly as well as the best pruning of a decision tree through dynamic programming scheme ⋮ On learning thresholds of parities and unions of rectangles in random walk models ⋮ Unnamed Item ⋮ New lower bounds for statistical query learning ⋮ Unnamed Item ⋮ Maximizing agreements with one-sided error with applications to heuristic learning ⋮ Exact learning of DNF formulas using DNF hypotheses ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ Maximizing agreements with one-sided error with applications to heuristic learning ⋮ Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning ⋮ Specification and simulation of statistical query algorithms for efficiency and noise tolerance ⋮ Characterizing Statistical Query Learning: Simplified Notions and Proofs ⋮ Learning DNF from random walks ⋮ Learning with queries corrupted by classification noise ⋮ On the boosting ability of top-down decision tree learning algorithms ⋮ PAC learning with nasty noise. ⋮ Statistical active learning algorithms for noise tolerance and differential privacy
This page was built for publication: Weakly learning DNF and characterizing statistical query learning using Fourier analysis
