Efficient noise-tolerant learning from statistical queries
From MaRDI portal
Publication:3158527
DOI10.1145/293347.293351zbMath1065.68605OpenAlexW1995897489WikidataQ127705772 ScholiaQ127705772MaRDI QIDQ3158527
Publication date: 25 January 2005
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/293347.293351
Learning and adaptive systems in artificial intelligence (68T05) Pattern recognition, speech recognition (68T10)
Related Items (70)
On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Learning conjunctions with noise under product distributions ⋮ Learning functions of \(k\) relevant variables ⋮ Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ On the Power of Learning from k-Wise Queries ⋮ Sample Complexity Bounds on Differentially Private Learning via Communication Complexity ⋮ Strong Hardness of Privacy from Weak Traitor Tracing ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ Computational barriers to estimation from low-degree polynomials ⋮ A general dimension for query learning ⋮ Rejoinder ⋮ Achieving Adversarial Robustness Requires An Active Teacher ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ Differentially Private Learning of Geometric Concepts ⋮ Estimation of Wasserstein distances in the spiked transport model ⋮ Polynomial‐time universality and limitations of deep learning ⋮ Adversarial manifold estimation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Random-index oblivious RAM ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Efficient authentication from hard learning problems ⋮ The regularized least squares algorithm and the problem of learning halfspaces ⋮ On biased random walks, corrupted intervals, and learning under adversarial design ⋮ Separating Models of Learning with Faulty Teachers ⋮ Data and task parallelism in ILP using mapreduce ⋮ A complete characterization of statistical query learning with applications to evolvability ⋮ Efficient and effective quantum compiling for entanglement-based machine learning on IBM Q devices ⋮ Unnamed Item ⋮ Learning privately with labeled and unlabeled examples ⋮ Prokaryotic evolutionary mechanisms accelerate learning ⋮ \(L^\ast\)-based learning of Markov decision processes (extended version) ⋮ Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles ⋮ On the noise estimation statistics ⋮ New Algorithms for Learning in Presence of Errors ⋮ Learning nonsingular phylogenies and hidden Markov models ⋮ Bounds on the sample complexity for private learning and private data release ⋮ Evolvability via the Fourier transform ⋮ PAC-learning in the presence of one-sided classification~noise ⋮ Surrogate losses in passive and active learning ⋮ Learning logic programs with structured background knowledge ⋮ Parallel and Concurrent Security of the HB and HB + Protocols ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Partial observability and learnability ⋮ Order-Revealing Encryption and the Hardness of Private Learning ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ Parallel and concurrent security of the HB and \(HB^{+}\) protocols ⋮ Finding a planted clique by adaptive probing ⋮ Separating models of learning with faulty teachers ⋮ Boosting in the presence of noise ⋮ Evolvability of Real Functions ⋮ On Evolvability: The Swapping Algorithm, Product Distributions, and Covariance ⋮ Characterizing Statistical Query Learning: Simplified Notions and Proofs ⋮ Learning a Random DFA from Uniform Strings and State Information ⋮ Cryptography with constant input locality ⋮ Bounds on the Sample Complexity for Private Learning and Private Data Release ⋮ Privacy Aware Learning ⋮ Unnamed Item ⋮ Machine unlearning: linear filtration for logit-based classifiers ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Statistical active learning algorithms for noise tolerance and differential privacy ⋮ Pseudorandom Functions: Three Decades Later ⋮ The Complexity of Differential Privacy ⋮ Private aggregation from fewer anonymous messages
This page was built for publication: Efficient noise-tolerant learning from statistical queries
