New algorithms reduce communication costs in collaborative learning.
problem Reducing communication costs in collaborative learning.
method Distributed boosting and adaptation to classification noise.
result Communication-efficient algorithms for collaborative PAC learning robust to noise.
Efficient PAC learning for contrastive linear representations is achieved.
problem Efficient PAC learning for contrastive linear representations.
method Relaxing the problem to a semi-definite program and using Rademacher complexity.
result First efficient PAC learning algorithm for contrastive learning.
This work establishes a new upper bound on the number of samples sufficient for PAC learning in the realizable case. The bound matches known lower bounds up to numerical constant factors. This solves a long-standing open problem on the sample complexity of PAC learning. The technique and analysis build on a recent brea…
Develops higher arity VC theory and characterizes PAC learning in product spaces.
problem Characterizing PAC learning in multi-dimensional product spaces.
method Introduces higher arity VC dimension, generalizes Haussler packing lemma, and develops hypergraph regularity lemma.
result Characterizes higher arity PAC learning in n-fold product spaces.
In this paper, we analyze PAC learnability from labels produced by crowdsourcing. In our setting, unlabeled examples are drawn from a distribution and labels are crowdsourced from workers who operate under classification noise, each with their own noise parameter. We develop an end-to-end crowdsourced PAC learning algo…
PAC learning simplified as bipartite matching.
problem Efficiently solving PAC learning problems.
method Transductive learning and one-inclusion graphs.
result PAC learning can be reduced to bipartite matching.
Survey on learning Boolean functions in computational theory.
problem Learning Boolean function classes in computational theory.
method Overview of known results in PAC and related models.
result Discussion of various learning results for Boolean functions.
Sharp sample complexity for multiclass PAC learning with bandit feedback.
problem Multiclass PAC learning with bandit feedback.
method Characterization of optimal sample complexity using a new combinatorial dimension (bandit DS dimension) and a learning algorithm (ListCascade).
result Sharp sample complexity characterization for every concept class up to logarithmic factors.
PAC learning sample complexity is decidable with finite support bounds.
problem Determining the exact sample complexity for PAC learning concepts.
method Observation and proof of decidability with a-priori bounds.
result Sample complexity can be exactly determined for various concepts with finite support bounds.
New findings on PAC learning and marginal distribution estimation.
problem Understanding how PAC learning relates to marginal distribution estimation under distributional constraints.
method Revisited the connection between PAC learning, uniform convergence, and density estimation, considering a known family of marginal distributions.
result PAC learning is sandwiched between two refined models of density estimation, differing only in whether the learner knows the set of well-estimated events in H.
The paper solves open questions in computable PAC learning, providing a complete landscape.
problem Understanding the boundaries and capabilities of computable PAC learning.
method Analyzing and constructing decidable hypothesis classes with different sample complexities and Littlestone dimensions.
result A complete understanding of CPAC learnability, answering open questions and confirming conjectures.
Learn conditional averages in PAC framework for better predictions.
problem Learning average labels over neighborhoods in unknown concept class.
method Characterization of learnability using combinatorial parameters.
result Complete characterization and sample complexity bounds.
New algorithm for learning ReLU networks with Gaussian noise, improving previous results.
problem PAC learning one-hidden-layer ReLU networks with Gaussian marginals and label noise.
method First polynomial-time algorithm for k k k up to i l d e O ( log d ) ilde{O}(\sqrt{\log d}) i l d e O ( log d ) for positive coefficients, no assumptions on rank or condition number. result Proves a Statistical Query lower bound of d Ω ( k ) d^{Ω(k)} d Ω ( k ) for arbitrary real coefficients, separating learnability classes. Paper analyzes error exponent in agnostic PAC learning.
problem Analyzing performance of agnostic PAC learning.
method Using error exponent from Information Theory to analyze PAC learning.
result Improved distribution-dependent error exponent for agnostic learning.
In this work, we initiate a formal study of probably approximately correct (PAC) learning under evasion attacks, where the adversary's goal is to \emph{misclassify} the adversarially perturbed sample point x ~ \widetilde{x} x , i.e., h ( x ~ ) ≠ c ( x ~ ) h(\widetilde{x})\neq c(\widetilde{x}) h ( x ) = c ( x ) , where c c c is the ground truth concept and h h h is t…
Develops a new learning framework for dynamic data.
problem Poor performance of existing strategies in dynamic data and goals.
method Prospective Learning framework and Prospective ERM algorithm.
result Prospective ERM converges to Bayes risk under certain assumptions.
New method learns robustly with less data, bridging theory and practice.
problem Adversarial robust learning with metric perturbation.
method Tolerant adversarial PAC-learning with perturb-and-smooth approach and compression-based algorithm.
result First PAC-type guarantees for popular adversarial learning techniques.
Paper proves L2 regression can learn k-juntas without distributional assumptions.
problem Learning k-juntas using L2 regression without distributional restrictions.
method L2 polynomial regression and minimum mean square estimation (MMSE).
result Agnostic PAC learning of k-juntas using L2 polynomial regression.
New algorithm reduces worst-case sample complexity for learning best arm.
problem Identifying a best arm with confidence in multi-armed bandit settings.
method Proposed a new ( ε , δ ) (ε,δ) ( ε , δ ) -PAC learning algorithm for multi-armed bandits. result Algorithm achieves optimal sample complexity for ( ε , δ ) (ε,δ) ( ε , δ ) -learning. Study efficient learning of halfspaces with constant noise tolerance.
problem Learning halfspaces in the presence of both instance and label corruption.
method Develops an algorithm to minimize reweighted hinge loss for robustness.
result Achieves constant noise tolerance for halfspace learning.
New algorithm learns PTFs with noisy data efficiently.
problem Learning low-degree PTFs with noisy data efficiently.
method Structural result and novel robust Chow vector estimation.
result PAC learns PTFs with nasty noise using efficient samples.
Study on proper learning under relaxed worst-case robust loss for VC classes.
problem Proper adversarially robust PAC learning under relaxed worst-case robust loss.
method Introduced a family of robust loss relaxations and showed their effectiveness for proper learnability.
result VC classes are properly PAC learnable with sample complexity close to standard PAC learning setup.
Study shows transductive learning is equivalent to PAC learning for most natural loss functions.
problem Understanding the relationship between transductive and PAC learning models.
method Extending existing results and developing new techniques to analyze the equivalence of the two models.
result Transductive learning is essentially equivalent to PAC learning for realizable learning with most natural loss functions.
Defines computable learning for binary classification over metric spaces.
problem Defines computable PAC learning for binary classification over computable metric spaces.
method Provides sufficient conditions for ERM learners to be computable and bounds the strong Weihrauch degree of an ERM learner.
result Gives a hypothesis class that does not admit any proper computable PAC learner with computable sample function.
We consider the problems of robust PAC learning from distributed and streaming data, which may contain malicious errors and outliers, and analyze their fundamental complexity questions. In particular, we establish lower bounds on the communication complexity for distributed robust learning performed on multiple machine…
Improved PAC learning algorithm for multiclass classification with bandit feedback.
problem Efficiently learning multiclass classification with limited feedback.
method Novel algorithm using stochastic optimization and Frank-Wolfe updates.
result Improved sample complexity bounds for multiclass PAC learning.
Strongly polynomial algorithm for approximate Forster transforms and halfspace learning.
problem Computing approximate Forster transforms and halfspace learning.
method Strongly polynomial time algorithm for approximate Forster transforms and halfspace learning.
result First strongly polynomial time algorithm for distribution-free PAC learning of halfspaces.
Paper generalizes strategic classification framework and introduces SVC for PAC-learning.
problem Strategic manipulation of testing data to fool classifiers.
method Unified framework for strategic classification, strategic VC-dimension (SVC).
result Characterizes the learnability and computational tractability of linear classifiers.
Investigates principles of generalization in list learning, refutes sample compression conjecture.
problem Determining applicability of classical principles in list PAC learning.
method Examines uniform convergence and sample compression in list PAC learning.
result Sample compression fails in list PAC learning, refutes conjecture.
PACC Discovery improves causal inference from limited data.
problem Inferring causal relationships from finite data.
method Extends PAC learning principles to causal inference.
result Theoretical guarantees for various causal methods.
This paper improves coreset size via smoothed analysis.
problem Efficiently computing small subsets that approximate query errors.
method Smoothed analysis for approximate average error over queries.
result Deterministic and randomized algorithms for smaller coresets.
The paper explores learning from label proportions, showing differences in efficiency between LLP and PAC learning.
problem Learning from label proportions (LLP) in unlabeled data with given label proportions.
method Formal definition and computational complexity analysis of LLP learning.
result LLP learning is more restrictive than PAC learning for finite VC classes, and some classes are uncharacterizable.
Proves SQ lower bounds for learning two-hidden-layer neural networks.
problem Learning two-hidden-layer ReLU networks with Gaussian inputs.
method Refined lifting procedure to reduce Boolean PAC learning to Gaussian.
result Superpolynomial SQ lower bounds for Gaussian inputs.
Study computable multiclass learning within PAC framework.
problem Computable multiclass learnability in finite label space.
method Proposed computable version of Natarajan dimension and generalized to distinguishers.
result Characterizes CPAC learnability for certain dimensions and embeddings.
Improved sample complexity for learning halfspaces with malicious noise.
problem Efficiently learning halfspaces in the presence of malicious noise.
method New analysis of Awasthi et al. algorithm with matrix Chernoff inequality and localization schemes.
result Achieved near-optimal sample complexity of i l d e O ( d ) ilde{O}(d) i l d e O ( d ) for isotropic log-concave distributions. New insights into learning from only positive examples.
problem Characterizing proper learning from positive-only samples.
method Introducing a new combinatorial condition for proper positive-only learning.
result Proper positive-only learning is characterized by finite VC dimension and uniform exterior separability.
Paper settles sample complexity for learning from multiple distributions.
problem Learning from multiple data distributions with a hypothesis class of bounded VC dimension.
method Introduced an algorithm with sample complexity of O((d+k)ε^-2)·(k/ε)^o(1).
result Algorithm matches lower bound up to sub-polynomial factor.
Study improves learning algorithms for convex polyhedra in Hilbert spaces.
problem Learning convex polyhedra in Hilbert spaces.
method Proposes an algorithm for learning a polyhedron in a Hilbert space.
result Correctly classifies at least 1-ε of the distribution with high probability.
New bounds on learning from multiple distributions for VC classes.
problem Understanding the sample complexity of learning from multiple data distributions.
method Analyzing the gap between known upper and lower bounds for PAC-learnable classes.
result Recent progress on sample complexity for VC dimension d classes on k distributions.
Characterizes statistical complexity of realizable regression in PAC and online learning.
problem Understanding the statistical complexity of realizable regression in both PAC and online learning settings.
method Introduces minimax instance optimal learners, novel and combinatorial dimensions to characterize learnability.
result Characterizes which classes of real-valued predictors are learnable and provides necessary conditions for learnability.
Study shows realizable learnability doesn't imply agnostic learnability for distributions.
problem Learnability and robustness of distribution classes.
method Analyzes the relationship between learnability and robustness for distribution learning.
result Realizable learnability does not imply agnostic learnability for distributions.
Randomized SINDy learns dynamic data structures using probabilistic methods.
problem Learning time-dependent data structures in dynamic systems.
method Sequential machine learning with a probabilistic approach, incorporating feature augmentation and Tikhonov regularization.
result Demonstrated effectiveness in regression and binary classification using real-world data.
We clarify measurability assumptions in the agnostic PAC learning theorem.
problem Measurability assumptions in the Fundamental Theorem of Statistical Learning.
method Measure-theoretic scrutiny of existing proofs to extract minimal assumptions.
result Sound statement and detailed proof of the Fundamental Theorem in the agnostic setting.
New algorithm learns halfspaces with noise using Forster decomposition.
problem Learning halfspaces in noisy data.
method Forster decomposition and efficient mixture of distributions.
result First polynomial-time algorithm with strongly polynomial sample complexity.
The paper bridges theory and practice in query-driven selectivity learning.
problem Insufficient theoretical understanding of query-driven selectivity learning.
method Demonstrates learnability of selectivity predictors and establishes favorable OOD generalization error bounds.
result Theoretical advances improve OOD generalization of query-driven selectivity models.
The problem of attempting to learn the mapping between data and labels is the crux of any machine learning task. It is, therefore, of interest to the machine learning community on practical as well as theoretical counts to consider the existence of a test or criterion for deciding the feasibility of attempting to learn…
The paper calculates how much data is needed to learn decision lists in the presence of evasion attacks.
problem Quantifying sample complexity for robust learning of decision lists against evasion attacks.
method PAC learning framework, Lipschitz condition on distributions, lower and upper bounds on sample complexity.
result Upper and lower bounds on sample complexity for robust learning of decision lists, showing exponential vs polynomial dependence on adversary's budget.
We study a recent model of collaborative PAC learning where k k k players with k k k different tasks collaborate to learn a single classifier that works for all tasks. Previous work showed that when there is a classifier that has very small error on all tasks, there is a collaborative algorithm that finds a single classifi…