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.
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.
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.
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.
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.
Study learns linear utility functions from comparisons, showing learnability gaps between passive and active learning.
problem Learn linear utility functions from pairwise comparison queries.
method Analyzes passive and active learning settings, considering noise-free and noisy query responses.
result Efficient learnability of linear utilities in passive learning, but not for utility parameters without strong assumptions.
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.
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 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.
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.
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.
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.
Unified theory for representation learning using learnable functions.
problem Insufficient theoretical understanding of unsupervised and self-supervised learning.
method Discriminative theoretical framework for analyzing sample complexity.
result Learnable regularization functions can reduce the amount of labeled data needed.
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 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.
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.
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…
Efficiently clusters millions of data points with learnable subspace clustering.
problem Large-scale subspace clustering with high-dimensional data.
method Develops a learnable subspace clustering paradigm using a parametric function and RPCM.
result Outperforms state-of-the-art methods in efficiency and effectiveness.
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.
Recently, it has been shown that many functions on sets can be represented by sum decompositions. These decompositons easily lend themselves to neural approximations, extending the applicability of neural nets to set-valued inputs---Deep Set learning. This work investigates a core component of Deep Set architecture: ag…
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.
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.
Study analyzes learnability of RKHS under L∞ norm for kernel methods.
problem Understand performance of kernel methods and random feature models.
method Relate L∞ learnability to kernel spectrum decay and establish sample complexity bounds.
result Conditions for efficient L∞ learning of RKHS identified.
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.
New CFNN architecture approximates functions with machine accuracy.
problem Function approximation with high precision.
method Chebyshev Feature Neural Network (CFNN) with learnable frequencies.
result Achieves machine accuracy in function approximation.
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.
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…
GKAN extends KAN to graphs, improving graph-based learning.
problem Graph-based learning tasks, especially semi-supervised.
method Learnable spline-based functions applied to graph data.
result GKAN achieves higher accuracy in graph semi-supervised learning.
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.
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 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.
KANHedge improves hedging of high-dimensional options using learnable B-spline activation functions.
problem Challenges in high-dimensional option pricing and hedging due to the curse of dimensionality.
method Introduces KANHedge, a novel BSDE-based hedger leveraging Kolmogorov-Arnold Networks with learnable B-spline activation functions.
result KANHedge provides improved hedging performance, achieving significant reductions in hedging cost metrics.
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.
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…
This paper explores how boolean formulas can be learned by deep neural networks.
problem Understanding the learnability of boolean formulas by deep neural networks.
method Analysis of boolean formulas associated with model-sampling benchmarks, combinatorial optimization problems, and random 3-CNFs.
result Neural networks outperform rule-based systems and pure symbolic approaches in learning boolean formulas.
New method for directed graphs using learnable spectral positional encodings.
problem Challenges in magnetic Laplacians and unitary gauge invariance for directed graphs.
method Learnable spectral PEs of the form hθ(Aq)R, computed in Hermitian block Krylov subspace.
result Gauge-invariant and computationally efficient solution for directed graphs.
Study shows limitations and possibilities of learning quantum circuit output distributions.
problem Learnability of output distributions of local quantum circuits.
method Investigated within two oracle models: statistical query model and direct sample access model.
result Output distributions of super-logarithmic depth Clifford circuits are not efficiently learnable in the statistical query model.
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…
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.
Paper characterizes embeddability of function spaces into Lp-type RKBS via metric entropy.
problem Characterizing embeddability of function spaces into Lp-type RKBS. method Establishes a connection between metric entropy growth and embeddability.
result A bound on metric entropy growth allows embedding into Lp-type RKBS. Deep networks can approximate functions with fewer learnable parameters than previously thought.
problem High computational costs due to large number of parameters in deep neural networks.
method Theoretical design of ReLU networks with a few intrinsic parameters and numerical experiments.
result ReLU networks with a small number of intrinsic parameters can achieve good approximations of functions.
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.
Transformers tend to learn more symmetric functions in sequence data.
problem Understanding inductive bias in Transformers with infinitely over-parameterized models.
method Analyzing Transformers in the Gaussian process limit, using representation theory of the symmetric group.
result Transformers are biased towards more permutation symmetric functions, and this can be quantitatively predicted.
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…
New LCM aggregator improves GNN performance and efficiency.
problem Graph neural networks' sensitivity to aggregation function choice.
method Learnable commutative monoid for graph aggregation.
result LCM aggregator achieves performance competitive with recurrent aggregators.