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.
Study extends learnability equivalence to multi-class and regression, overcoming binary classification limits.
problem Equivalence of online and private learnability in multi-class and regression settings.
method Introduced a novel Littlestone dimension variant and threshold functions for multi-class classification.
result Online learnability implies private learnability in multi-class classification but not in regression.
Example shows learnable distributions not privately learnable.
problem Learnable distributions under non-private conditions not transferable to differential privacy.
method Example of a distribution class learnable up to constant error in total variation distance but not under differential privacy.
result Contradicts conjecture of Ashtiani on learnability under differential privacy.
Characterizes learnability of multioutput functions in various settings.
problem Learning multioutput function classes in batch and online settings.
method Characterizes learnability based on single-output restrictions.
result Complete characterization of learnability in multioutput classification and regression.
No single parameter characterizes the learnability of probability distributions.
problem Finding a parameter to characterize the learnability of probability distributions.
method Analyzing various notions of learnability and showing impossibility results.
result No such parameter exists for characterizing learnability of probability distributions.
Research characterizes learnability of multilabel ranking problems.
problem Learnability of multilabel ranking problems with relevance-score feedback.
method Characterizes learnability in batch and online settings for a large family of ranking losses.
result Characterizes two equivalence classes of ranking losses based on learnability.
Characterizes concept classes for optimistic online learning.
problem Understanding minimal assumptions for online learnability.
method Investigates two questions about concept classes' learnability.
result Characterizes all concept classes for optimistically universal online learnability.
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.
This work characterizes when a hypothesis class can be k-list learned.
problem Characterizing when a hypothesis class can be k-list learned.
method Introducing the k-DS dimension and proving the equivalence of k-list learnability and the finiteness of the k-DS dimension.
result A hypothesis class is k-list learnable if and only if the k-DS dimension is finite.
We study the question of learning an adversarially robust predictor. We show that any hypothesis class H with finite VC dimension is robustly PAC learnable with an improper learning rule. The requirement of being improper is necessary as we exhibit examples of hypothesis classes H with finite VC…
New algorithm learns regression models privately under growth condition.
problem Private learning of nonparametric regression models.
method Novel filtering procedure to output stable hypotheses for nonparametric function classes.
result Established first nonparametric private learnability guarantee for diverging fat shattering dimensions.
Study robust regression learning under adversarial attacks.
problem Understanding which function classes are learnable in the presence of adversarial attacks.
method Introduced a novel agnostic sample compression scheme and used fat-shattering dimension to construct adversarially robust sample compression schemes.
result Finite fat-shattering dimension classes are learnable in both realizable and agnostic settings.
New insights into Valiant's learnability model reveal classes learnable with membership queries.
problem Which classes are learnable in Valiant's original model?
method Characterization using poly-size adaptive query-compression schemes and techniques for arbitrary domains.
result Learnability in Valiant's model is sandwiched between PAC and query-less variants, with halfspaces learnable with queries.
New learning rule for quantum measurement classes overcomes uniform convergence issues.
problem Characterizing learnability of POVM hypothesis classes in quantum settings.
method Introduced a new learning rule called denoised ERM to address uniform convergence issues.
result Characterized learnability conditions and sample complexity bounds for POVM classes.
We characterize learnability for stochastic noisy bandits, identifying optimal query complexities.
problem Learnability of stochastic noisy bandit models.
method Complete characterization through model class analysis and proof of optimal query complexities.
result Characterization of learnability for stochastic noisy bandit models.
This work proves DP learnability implies online learnability for general classification tasks.
problem Link between differential privacy and online learning for general classification tasks.
method Establishes Ramsey-type theorems for trees to prove DP learnability implies online learnability.
result DP learnability implies online learnability for general classification tasks.
We consider the fundamental question of learnability of a hypotheses class in the supervised learning setting and in the general learning setting introduced by Vladimir Vapnik. We survey classic results characterizing learnability in term of suitable notions of complexity, as well as more recent results that establish …
New approach to nonuniform learnability using measure theory.
problem Nonuniform learnability of hypotheses with varying sample sizes.
method Measure theoretic approach to redefine nonuniform learnability, introducing a new algorithm (Generalize Measure Learnability).
result Achieved statistical consistency in learning countable hypothesis classes.
Online learning of linear operators between infinite-dimensional spaces is possible but with limitations.
problem Learning linear operators between infinite-dimensional Hilbert spaces in an online setting.
method Online learning approach for linear operators with bounded p-Schatten norm, proving impossibility for operator norm. result Separation between online learnability and uniform convergence for bounded linear operators.
Study on the limits of bandit learning, showing hardness and limitations.
problem Understanding the learnability of bandit learning under arbitrary reward functions.
method Investigation into which classes of reward functions are learnable and how they can be learned.
result No combinatorial dimension can characterize bandit learnability, and computational hardness is inherent.
Learnable multiclass hypothesis classes don't always have a sample compression scheme of fixed size.
problem The limitation of sample compression schemes for multiclass hypothesis classes.
method Analysis of DS dimension and sample compression schemes.
result Learnable multiclass hypothesis classes do not always have a sample compression scheme of fixed size.
Deep networks can learn functions approximated by shallow networks, but not all functions.
problem The learnability of functions by deep neural networks and the approximation capacity of simpler classes.
method Study the connection between learnability and approximation capacity of functions by deep neural networks and simpler classes.
result A necessary condition for a function to be learnable by deep neural networks is to be approximable by shallow networks.
New learnability criteria for non-iid processes equivalent to online learning.
problem Statistical learning under non-iid stochastic processes is underdeveloped.
method Defined two learnability notions and showed their equivalence to online learning.
result Learnability criteria for non-iid processes are equivalent to online learning.
Improved multi-class AdaBoost algorithm with stronger weak learnability condition.
problem Multi-class classification problem with at least two labels.
method Recursive ensemble algorithm inspired by SAMME, strengthening weak learnability condition.
result Final hypothesis converges to correct label with probability 1 and generalization error bounds exponentially.
New framework for understanding adversarial and stochastic learning.
problem Understanding the continuum from adversarial to stochastic settings in online learning.
method Distributionally constrained adversaries framework.
result Characterization of learnable distribution classes for various function classes.
Characterizes learnability of forgiving 0-1 loss functions in multiclass settings.
problem Understanding when multiclass learning with forgiving 0-1 loss functions is possible.
method Introduces a new combinatorial dimension based on Natarajan Dimension to determine learnability.
result A hypothesis class is learnable if and only if the Generalized Natarajan Dimension is finite.
This research sets limits on how complex multi-class learning problems can be.
problem Understanding the complexity of multi-class classification problems.
method Established upper bounds on Natarajan dimensions for specific function classes.
result Upper bounds on Natarajan dimensions for multi-class decision trees, random forests, and neural networks.
Stability is a general notion that quantifies the sensitivity of a learning algorithm's output to small change in the training dataset (e.g. deletion or replacement of a single training sample). Such conditions have recently been shown to be more powerful to characterize learnability in the general learning setting und…
While machine learning has proven to be a powerful data-driven solution to many real-life problems, its use in sensitive domains has been limited due to privacy concerns. A popular approach known as **differential privacy** offers provable privacy guarantees, but it is often observed in practice that it could substanti…
New insights into learning from distributional adversaries and private data.
problem Understanding minimal assumptions for learning and generalization under distributional constraints.
method Generalized smoothness as a characterization of learnability and privacy under distributional adversaries.
result Near complete characterization of families that admit learnability and privacy under distributional adversaries.
New findings show learnable distributions remain learnable even with noisy or adversarial perturbations.
problem Learning from perturbed samples in high-dimensional spaces.
method Developed a perturbation-quantization framework to analyze additive noise and adversarial corruption models.
result Sample compressible families remain learnable even under noisy or adversarial perturbations.
In many domains, collecting sufficient labeled training data for supervised machine learning requires easily accessible but noisy sources, such as crowdsourcing services or tagged Web data. Noisy labels occur frequently in data sets harvested via these means, sometimes resulting in entire classes of data on which learn…
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.
New algorithm learns multiclass concepts with finite Littlestone dimension.
problem Agnostic online multiclass classification in adversarial settings.
method Multiplicative weights algorithm with experts based on subsequences.
result Proves agnostic learnability if and only if Littlestone dimension is finite.
We study the sample complexity of private synthetic data generation over an unbounded sized class of statistical queries, and show that any class that is privately proper PAC learnable admits a private synthetic data generator (perhaps non-efficient). Previous work on synthetic data generators focused on the case that …
The Predictive Normalized Maximum Likelihood (pNML) scheme has been recently suggested for universal learning in the individual setting, where both the training and test samples are individual data. The goal of universal learning is to compete with a ``genie'' or reference learner that knows the data values, but is res…
We informally call a stochastic process learnable if it admits a generalization error approaching zero in probability for any concept class with finite VC-dimension (IID processes are the simplest example). A mixture of learnable processes need not be learnable itself, and certainly its generalization error need not de…
System discovers new classes from unlabeled data, improving model performance.
problem Handling datapoints outside initial training distribution.
method Develops new classes through semi-supervised learning, using Dataset Reconstruction Accuracy and class learnability.
result Demonstrates improved model quality through automatic class discovery.
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.
New binary classification techniques help multiclass classification by aggregating proper learners.
problem Multiclass classification faces a properness barrier that prevents optimal learning by proper learners.
method Aggregations of proper binary learners, generalized to multiclass settings, achieve optimal sample complexity.
result Optimal binary learners can achieve sample complexity $O\left(\frac{d_G + \ln(1 / δ)}ε
ight)$ for classes with finite Graph dimension dG. Private classification and online prediction are shown to be equivalent.
problem Learning with differential privacy and online prediction equivalence.
method Introducing global stability and proving equivalence between online learnability and private PAC learnability.
result Every concept class with finite Littlestone dimension can be learned by a differentially-private algorithm.
Unified framework for realizable and agnostic learning.
problem Lack of a unified theory for realizable and agnostic learnability.
method Three-line blackbox reduction.
result Unified understanding across various learning settings.
Smoothed analysis shows that many classes become learnable from positive-only samples.
problem Learning from positive-only samples is challenging due to negative results in worst-case settings.
method Smoothed analysis of positive-only learning, assuming samples from a reference distribution smooth with respect to the true distribution.
result All VC classes become learnable in the smoothed model with O(VC/ε2) positive samples for ε classification error. Research on predicting with lists of labels, characterizing learnability and providing algorithms.
problem Multiclass online prediction with multiple labels.
method Characterization using b-ary Littlestone dimension, adaptation of classical algorithms, combinatorial results. result Achievement of negative regret in some scenarios, complete characterization of learnability.
Proposes a new approach to regression learning that addresses overfitting and underfitting.
problem Regression learning issues, including overfitting and underfitting.
method Introduces epsilon-Confidence Approximately Correct (epsilon CoAC) framework using Kullback Leibler divergence.
result Demonstrates improved learnability and accuracy compared to cross-validation.
Proper learning is possible with labeled data, but unlabeled data can improve performance.
problem Problems that can only be learned improperly, like multiclass classification.
method Distributional regularization and worst-case performance evaluation.
result Proper learnability is possible under certain conditions involving unlabeled data.
Paper investigates learnability of OOD detection under various conditions.
problem Learnability of OOD detection under different scenarios.
method Investigates PAC learning theory, proves impossibility theorems, and provides necessary and sufficient conditions.
result Some conditions for learnability of OOD detection may not hold in practical scenarios.
We present a formal proof in Lean of probably approximately correct (PAC) learnability of the concept class of decision stumps. This classic result in machine learning theory derives a bound on error probabilities for a simple type of classifier. Though such a proof appears simple on paper, analytic and measure-theoret…