The paper shows how to avoid the trivial representation in IB by choosing the right β.
problem Lack of theoretical guidance for choosing β in the IB method.
method Identifying a phase transition between learnable and unlearnable representations based on β.
result IB-Learnability is defined by the largest confident, typical, and imbalanced subset of examples.
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.
Paper proposes learnable topological features for efficient phylogenetic inference.
problem Finding appropriate topological structures for phylogenetic inference tasks requires significant design effort and domain expertise.
method Combines raw node features with graph neural networks to automatically adapt to different tasks.
result Demonstrates effectiveness and efficiency on simulated and real data phylogenetic inference tasks.
End-to-end learnable network for safer self-driving with interpretable intermediate representations.
problem Safe motion planning for self-driving vehicles.
method Differentiable semantic occupancy representation for cost calculation in motion planning.
result Significantly outperforms state-of-the-art planners in imitating human behaviors and producing safer trajectories.
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.
MoleculeNet benchmarks molecular machine learning algorithms.
problem Lack of a standard benchmark for molecular machine learning.
method Curated multiple public datasets, established evaluation metrics, released open-source implementations.
result Learnable representations offer the best performance in molecular machine learning.
A new autoencoder combines deep learning with SVD to reduce model complexity.
problem Overcoming the Kolmogorov barrier in high-dimensional systems.
method Learnable weighted hybrid autoencoder combining SVD and deep learning.
result Empirically, the model exhibits a sharpness thousands of times smaller than other models.
Study on learnability of Schatten--von Neumann operators in learning theory.
problem Learnability of Schatten--von Neumann operators in infinite-dimensional settings.
method Adapted representer theorem to convert infinite-dimensional optimization to convex finite-dimensional problem.
result Schatten--von Neumann operators are probably approximately correct (PAC)-learnable via practical convex program for any p<∞. Deep networks struggle to learn efficient representations of simple functions.
problem Can deep learning methods find efficient representations of simple functions?
method Trained deep neural networks on the parity function and fast Fourier transform, using gradient-based optimization.
result Deep networks require initialization close to exact solutions to learn efficient representations of simple functions.
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.
A hierarchy of GNNs based on learnable local features is proposed.
problem Limited understanding of GNN architectures and their systematic construction.
method A hierarchy of GNNs based on aggregation regions is derived, and theoretical results are provided.
result Simple GNN architecture exceeds Weisfeiler-Lehman graph isomorphism test.
New fair PCA method using streaming algorithms with statistical guarantees.
problem Perform PCA while ensuring fair projected distributions.
method Formulated new notion PAFO learnability, proposed fair noisy power method (FNPM) for memory efficiency.
result First statistical guarantee for fair PCA in streaming setting.
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 interpretation of RNN forget gate improves learnability for long-term sequential data.
problem Improving learnability of recurrent neural networks for long-term temporal dependencies.
method Generalized theory of gated RNNs, focusing on gradient behavior over time.
result Existing RNNs satisfy the gradient condition for initial training, suggesting validity of forget gate interpretation.
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.
Machine learning accelerates Lie algebra computations.
problem Computing tensor products and branching rules of Lie algebras.
method Machine learning for Lie algebra computations.
result Achieves significant speed-ups in Lie algebra computations.
This paper shows neural networks can learn non-linear sparse parities.
problem The challenge of learning non-linear models with neural networks.
method Gradient descent on depth-two neural networks.
result Sparse parities are learnable by neural networks but not by linear methods.
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.
TACOMA improves cancer biomarker validation by incorporating deep features.
problem Improving accuracy and repeatability in TMA image scoring.
method Incorporating deep learning representations learned through unsupervised clustering and recursive space partitioning.
result Reduced error rate by about 6% on breast cancer TMA images.
New model separates object attributes for better perceptual grouping.
problem Perceptual grouping of complex visual scenes.
method Spatial mixture models with learnable priors.
result Outperforms state-of-the-art methods in perceptual grouping.
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 learnability of deep random networks, showing practical limitations with depth.
problem Learnability of deep random networks with sign activation.
method Theoretical and practical analysis of random deep networks with sign activation.
result Learnability of random deep networks drops exponentially with depth.
Graph networks predict and control physical systems with strong generalization.
problem Accurately predicting and controlling complex physical systems.
method Graph networks as learnable models for object- and relation-centric representations.
result Strong generalization across various physical systems.
Measures sample learnability across DNNs, showing consistency.
problem Estimating the learnability of each sample in a training set.
method Train DNN on training set, aggregate hits and misses over epochs.
result Sample-wise learnability measure is highly correlated across DNN models.
New learnability concept shown independent of ZFC axioms.
problem Learnability of finite subsets on [0,1] interval is undecidable.
method Set-theoretic techniques to prove independence of ZFC.
result EMX learnability of finite subsets on [0,1] is independent of ZFC.
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.
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.
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 graph convolution captures local features on non-Euclidean grids.
problem Capturing local features on irregular, coarse non-Euclidean grids.
method Low-rank learnable local filters in graph convolutions.
result Proves more expressive than previous spectral graph convolution methods.
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.
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.
The study analyzes neural network predictions of knot invariants and finds that braid representations work best.
problem Understanding and predicting knot invariants using neural networks.
method Investigated different knot representations and invariants, proposed a cosine similarity score.
result Braid representations are best for predicting knot invariants, and some invariants are easier to learn than others.
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.
Deep models learn to parse complex language structures from local data patterns.
problem Understanding how deep models parse and represent language structures.
method Introduced tunable probabilistic context-free grammars and a learning algorithm inspired by deep networks.
result Data correlations across scales enable hierarchical language representations.
UNIPoint universally approximates point process intensities.
problem How to precisely describe the flexibility of point process models.
method Proof using Stone-Weierstrass Theorem, transfer functions, and recurrent neural networks.
result UNIPoint performs better than other models on synthetic and real-world datasets.
Adding supplementary axes improves neural network learnability and accuracy.
problem Overfitting and computational cost in deep neural networks.
method Analysis of a simple MLP model and comparison with and without supplementary information.
result Neural networks with supplementary axes show more robust and accurate training results.
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.
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…
We develop a mean-field theory for multi-component ICA in high dimensions.
problem Understanding multi-component ICA in high-dimensional settings.
method Asymptotically exact mean-field theory for multi-component online ICA.
result Explicit learnability boundaries and competition conditions linking step size, data moments, and initialization.
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.
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.
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.
A new KAN variant uses sinusoidal activations to approximate functions.
problem Approximating multivariable functions using neural networks.
method Replacing inner and outer functions in Kolmogorov-Arnold representation with weighted sinusoidal functions.
result The new KAN variant outperforms fixed-frequency Fourier transform and achieves comparable performance to MLPs.
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.