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.
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.
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.
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.
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 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 …
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.
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 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.
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.
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.
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 method for private density estimation of high-dimensional Gaussian mixtures.
problem Private density estimation for mixtures of unrestricted high-dimensional Gaussians.
method Exploits list global stability to prove upper bound on sample complexity.
result First upper bound on sample complexity for agnostic private density estimation.
Study shows private learning of mixtures of Gaussians is possible with polynomial samples.
problem Estimating mixtures of Gaussians under differential privacy constraints.
method Developed a new framework for privately learning mixtures of Gaussians without structural assumptions.
result Polynomial number of samples (poly(k,d,1/α,1/ε,log(1/δ))) sufficient for estimation up to total variation distance α with (ε, δ)-DP.
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 paper extends financial theory to measure learnable market structure under computational constraints.
problem Understanding learnable market structure under bounded computational capacity.
method Introduces financial epiplexity as a measure of learnable market structure, extending classical information theory.
result Proves that equal entropy does not imply equal epiplexity and derives thresholds for useful regimes.
Study on generating and identifying languages privately, showing privacy imposes costs and creates barriers.
problem Generating and identifying languages privately in the limit model.
method Introduced a continual release model under differential privacy constraints, proving both positive and negative results.
result Privacy imposes quantitative and qualitative costs, and creates fundamental barriers for identification.
A network of agents attempt to learn some unknown state of the world drawn by nature from a finite set. Agents observe private signals conditioned on the true state, and form beliefs about the unknown state accordingly. Each agent may face an identification problem in the sense that she cannot distinguish the truth in …
Few-shot DP image classification models need more data as privacy increases.
problem Few-shot DP image classification challenges in personalization and federated learning.
method Exhaustive experiments on various parameters affecting few-shot DP accuracy and vulnerability.
result Increasing shots per class is necessary for DP accuracy as privacy increases.
Improved learning algorithms with privacy using smoothed analysis.
problem Designing robust and private learning algorithms.
method Smoothed analysis of adversarial and differentially private learning.
result Stronger regret and privacy error guarantees with smoothed adversaries.
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.
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.
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.
Paper tightens privacy and generalization bounds for iterative learning.
problem Balancing privacy and generalization in iterative learning algorithms.
method Established alignment between generalization and privacy, derived composition theorems for iterative algorithms.
result Generalization bounds for iterative learning algorithms are strictly tighter than existing works.
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 …
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.
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 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.
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.
In this paper we study the learnability of deep random networks from both theoretical and practical points of view. On the theoretical front, we show that the learnability of random deep networks with sign activation drops exponentially with its depth. On the practical front, we find that the learnability drops sharply…
Framework for robust decision making in changing environments with privacy constraints.
problem Interactive decision making in changing environments with constraints.
method Hybrid Decision Making with Structured Observations (hybrid DMSO) framework, local differentially private decision making, query-based learning, robust and smooth decision making.
result Strong connections and bounds derived for DEC, SQ dimension, local minimax complexity, learnability, and joint differential privacy.
In Ben-David et al.'s "Learnability Can Be Undecidable," they prove an independence result in theoretical machine learning. In particular, they define a new type of learnability, called Estimating The Maximum (EMX) learnability. They argue that this type of learnability fits in with other notions such as PAC learnabili…
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.
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.
New findings on depth vs. width in neural networks, showing depth can improve learnability.
problem Understanding the role of depth in neural networks, especially when width is unbounded.
method Analyzing sample complexity for learnability in norm-controlled depth-2 and depth-3 ReLU networks.
result Depth can improve learnability of functions that are otherwise unlearnable with depth-2 networks.
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.
Estimating the relative importance of each sample in a training set has important practical and theoretical value, such as in importance sampling or curriculum learning. This kind of focus on individual samples invokes the concept of sample-wise learnability: How easy is it to correctly learn each sample (cf. PAC learn…
This paper studies trade-offs in private prediction methods.
problem Leakage of training data information in machine learning predictions.
method Private training and private prediction methods with trade-offs.
result Private training methods outperform private prediction methods in various settings.
Study shows observing order book can significantly improve online market making performance.
problem Online market making with private valuations and limited feedback.
method Introduces action-dependent feedback model and proposes elimination-based and explore-then-perturb algorithms.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret bounds with high probability in various settings. Private method measures nonlinear correlations between data hosted across two entities.
problem Measuring nonlinear correlations between sensitive data hosted across multiple parties while preserving privacy.
method Differentially private estimator of distance correlation.
result First private estimator of nonlinear correlations in a multi-party setup.
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.
Study reveals how spectral bias affects learnability on real-world data.
problem Understanding how well complex datasets can be learned using kernel methods.
method Use eigenvalues and eigenfunctions from idealized data to reveal spectral bias on real-world data.
result Bound learnability on real-world data using symmetries of realistic kernels.
We study the question of learning an adversarially robust predictor. We show that any hypothesis class H \mathcal{H} 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 \mathcal{H} H with finite VC…
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…
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.
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 p p -Schatten norm, proving impossibility for operator norm. result Separation between online learnability and uniform convergence for bounded linear operators.
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.
Two-parameter models can learn high-dimensional targets via gradient flow.
problem Learning high-dimensional targets with limited parameters.
method Gradient flow approach for W < d W<d W < d models. result Two-parameter models can learn targets with arbitrarily high success probability.