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.
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 …
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.
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.
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.
New findings show limitations in converting private learning to online learning efficiently.
problem Limitations in converting private learning to online learning efficiently.
method Assuming one-way functions, we show an efficient conversion from pure-private learners to online learners is impossible.
result Efficient conversion from pure-private learners to online learners is impossible under certain assumptions.
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.
Study on computational aspects of replicable learning, bridging statistical and algorithmic perspectives.
problem Understanding the computational connections between replicability and various learning paradigms.
method Design of replicable learners, lifting framework, and transformation techniques.
result Efficient replicable learners for specific learning problems under various distributions.
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.
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.
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.
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…
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.
Differentially-private Bayes consistency rule for binary classification and density estimation.
problem Privacy constraints limit private learning in the distribution-free PAC model.
method Constructs a universally Bayes consistent learning rule that satisfies differential privacy.
result Private learning is possible for arbitrary distributions, even with a single algorithm.
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.
Framework for private, noise-tolerant, and efficient learning algorithms.
problem Private and efficient learning of large-margin halfspaces in noisy environments.
method Simple framework using differential privacy and noise tolerance conditions.
result Noise-tolerant and private PAC learners for large-margin halfspaces with sample complexity independent of dimension.
The paper explores how machine learning models can be learnable despite label shifts.
problem Learnability of binary classification models in the presence of label shifts.
method Developed a performative empirical risk function that is an unbiased estimate of the true risk on the shifted distribution.
result PAC-learnable hypothesis spaces remain PAC-learnable for performative scenarios.
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.
PAC-Bayes framework fails on simple 1D linear classification task.
problem Proving the learnability of simple 1D linear classification tasks using PAC-Bayes bounds.
method Demonstrated a specific 1D linear classification task that PAC-Bayes cannot analyze.
result PAC-Bayes framework cannot prove learnability of simple 1D linear classification tasks.
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.
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…
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…
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.
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.
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 algorithms for privately learning decision lists and halfspaces.
problem Private learning of decision lists and halfspaces.
method Differentially private algorithms for PAC and online models.
result Private algorithms match or surpass non-private guarantees.
We study the problem of learning influence functions under incomplete observations of node activations. Incomplete observations are a major concern as most (online and real-world) social networks are not fully observable. We establish both proper and improper PAC learnability of influence functions under randomly missi…
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.
Extends PAC learning theory to handle partial concepts with special properties.
problem Traditional PAC learning theory cannot handle tasks with special data properties.
method Introduces partial concepts and new PAC learning framework.
result Partial concept classes cannot be captured by traditional PAC theory.
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.
Private RL algorithm with privacy guarantees for personalized medicine decisions.
problem Privacy-preserving reinforcement learning for personalized medicine decisions.
method Developed a private optimism-based RL algorithm using joint differential privacy (JDP).
result Achieved strong PAC and regret bounds with a privacy guarantee.
Two different views on machine learning problem: Applied learning (machine learning with business applications) and Agnostic PAC learning are formalized and compared here. I show that, under some conditions, the theory of PAC Learnable provides a way to solve the Applied learning problem. However, the theory requires t…
New findings show modern neural networks have finite sample complexity in o-minimal structures.
problem Understanding the learnability of modern neural networks in a broad context.
method Analyzing feedforward neural networks definable in o-minimal structures.
result Modern neural networks, including MLPs, CNNs, GNNs, and transformers, have finite sample complexity in the agnostic PAC setting.
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…
The Probably Approximately Correct (PAC) Bayes framework (McAllester, 1999) can incorporate knowledge about the learning algorithm and (data) distribution through the use of distribution-dependent priors, yielding tighter generalization bounds on data-dependent posteriors. Using this flexibility, however, is difficult,…
We revisit the problem of differentially private release of classification queries. In this problem, the goal is to design an algorithm that can accurately answer a sequence of classification queries based on a private training set while ensuring differential privacy. We formally study this problem in the agnostic PAC …
Private distribution learning with public data, leveraging sample compression schemes.
problem Private distribution learning with public and private samples under differential privacy constraints.
method Connection to sample compression schemes and list learning.
result At least d public samples are necessary for private learnability of Gaussians in R^d.
Study shows multi-source learning is more resilient to adversarial corruption than single-source learning.
problem Learning from multiple untrusted data sources, especially when some are adversarially corrupted.
method Analyzed the scenario where an adversary can corrupt a fixed fraction of data sources, derived a generalization bound for this setting.
result PAC-learnability is possible in the multi-source setting even when some data sources are adversarially corrupted.
Unified model for interactive estimation with improved learnability measure.
problem Improving learnability in interactive estimation models.
method Introducing a combinatorial measure (dissimilarity dimension) and a general algorithm with polynomial bounds.
result Unified model subsumes statistical-query learning and structured bandits.
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.
Local regularization fails in transductive learning for some multiclass problems.
problem Whether local regularization can learn all transductive multiclass problems.
method Provided a negative answer by exhibiting a specific multiclass problem.
result Local regularization cannot learn all transductive multiclass problems.
In response to a 1997 problem of M. Vidyasagar, we state a criterion for PAC learnability of a concept class C under the family of all non-atomic (diffuse) measures on the domain Ω. The uniform Glivenko--Cantelli property with respect to non-atomic measures is no longer a necessary condition, and consisten…
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.
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.
Study shows how many domains are needed for generalization, using a new measure called domain shattering dimension.
problem How many domains are needed for domain generalization?
method Introduced a new combinatorial measure called the domain shattering dimension to model domain sample complexity.
result Established a tight quantitative relationship between domain shattering dimension and classic VC dimension.
Efficiently learns private models using public data.
problem Improving private learning performance with public data.
method Proves computationally efficient algorithms for private learning with public data.
result First computationally efficient algorithms for private learning with public data.
Develops a theory to make learning solutions fair and safe.
problem Ensuring learning solutions are unbiased and safe in critical applications.
method Generates a generalization theory based on PAC learning framework, introduces constrained learning algorithm.
result Proves that constrained learning is as learnable as unconstrained learning, provides practical algorithm.
Improved private learning for Littlestone classes with a doubly-exponential mistake bound.
problem Private learning of Littlestone classes with approximate differential privacy constraints.
method Combines refined interpretation of irreducibility technique, improved sparse selection algorithm, and Exponential Mechanism.
result Achieved a mistake bound of \(\tilde{O}(d^{9.5} \cdot \log(T))\) for online learning of Littlestone classes.