Shape adaptor learns flexible resizing factors for neural networks.
problem Fixed resizing layers limit network performance.
method Learnable reshaping factor for traditional resizing layers.
result Performance increases consistently across multiple datasets.
In this paper we study the approximate learnability of valuations commonly used throughout economics and game theory for the quantitative encoding of agent preferences. We provide upper and lower bounds regarding the learnability of important subclasses of valuation functions that express no-complementarities. Our main…
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.
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.
LSD distills high-quality samplers for DDMs with fewer steps.
problem Inefficient sampling in DDMs leads to low quality and high computational cost.
method LSD employs a distillation approach to train fast samplers with learnable coefficients and time schedules.
result LSD+ achieves higher sampling quality with fewer steps compared to existing samplers.
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.
FLDD improves discrete diffusion models by learning a non-Markovian noising process.
problem Efficiency and quality of discrete diffusion models in few-step generation.
method Introduces a learnable non-Markovian forward (noising) process to match the target distribution.
result FLDD produces higher quality samples in fewer steps compared to conventional discrete diffusion models.
Efficiently learns deep factor graphs using Gaussian belief propagation.
problem Learning in deep factor graphs with efficient inference.
method Treats all relevant quantities as random variables, uses belief propagation for inference.
result Efficiently solves training and prediction problems in deep factor graphs with belief propagation.
Compact learning results across various loss functions.
problem Understanding sample complexity in transductive learning.
method Analyzing finite projections and sample complexities for different loss functions.
result Exact compactness of sample complexity holds broadly across realizable and agnostic learning.
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.
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.
New method optimizes complex models with minimal data, proving global optimality.
problem Optimizing complex models with unknown cost functions and prior distributions.
method Introduces 'coarse learnability' and an iterative MBO algorithm with sample correction.
result Achieves global optimality with polynomial sample complexity.
It has been postulated that a good representation is one that disentangles the underlying explanatory factors of variation. However, it remains an open question what kind of training framework could potentially achieve that. Whereas most previous work focuses on the static setting (e.g., with images), we postulate that…
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.
Sharp asymptotics reveal how network width controls learnability in quadratic neural networks.
problem Understanding learnability in overparameterized quadratic neural networks.
method Mapping ERM to convex matrix sensing with nuclear norm penalization.
result Characterization of global minima and precise generalization thresholds.
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.
It has been postulated that a good representation is one that disentangles the underlying explanatory factors of variation. However, it remains an open question what kind of training framework could potentially achieve that. Whereas most previous work focuses on the static setting (e.g., with images), we postulate that…
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…
LITE models improve query-document relevance with learnable late interactions.
problem Improving query-document relevance with lower latency and storage.
method Proposes learnable late-interaction models (LITE) that use factorized query and document embeddings followed by a learnable scorer.
result Empirically, LITE outperforms previous late-interaction models in re-ranking tasks.
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.
A framework for disentangling class-related and class-independent factors in data.
problem Learning disentangled representations in variational autoencoders.
method Attention mechanism in latent space, mixture models, Bhattacharyya coefficient, semi-supervised training.
result Disentangles class-related and class-independent factors of variation.
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.
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. We propose a new nonlinear factorization model for graphs that are with topological structures, and optionally, node attributes. This model is based on a pseudometric called Gromov-Wasserstein (GW) discrepancy, which compares graphs in a relational way. It estimates observed graphs as GW barycenters constructed by a se…
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.
Study risk-sensitive reinforcement learning with optimized certainty equivalents.
problem Risk-sensitive reinforcement learning in finite discounted MDPs.
method Analyzed a simple model-based approach and derived PAC sample complexity bounds.
result Established tight sample complexity bounds for value and policy learning.
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 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 framework learns disentangled causal representations from observed labels.
problem Learning meaningful disentangled causal representations from observed data.
method ICM-VAE framework using flow-based diffeomorphic functions and causal disentanglement prior.
result Induces highly disentangled causal factors and improves robustness.
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.
NCPF model improves traffic data imputation with neural and tensor methods.
problem Pervasive missing data in traffic analysis due to sensor failures and gaps.
method Neural Canonical Polyadic Factorization (NCPF) integrating CP decomposition and deep learning.
result NCPF outperforms state-of-the-art baselines in urban traffic datasets.
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 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…
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-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 models. result Two-parameter models can learn targets with arbitrarily high success probability.
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 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.