Proposes a method to learn representations of higher-dimensional simplicial complexes.
problem Lack of methods for representing entire simplicial complexes.
method Geometric message passing schemes for end-to-end learning of simplicial complex representations.
result First method for learning representations of entire simplicial complexes.
CAP-BM learns complex-valued data's amplitude and phase distributions.
problem Learning from complex-valued data with amplitude variation.
method Complex Amplitude-Phase Boltzmann machine (CAP-BM) with Gibbs sampling.
result Necessity of amplitude-amplitude coupling term in CAP-BM.
New findings show Rademacher complexities are not crucial for learning complexities.
problem Understanding the sample complexity of learning with squared loss in convex classes.
method Novel learning procedure combining mean estimation and Talagrand's generic chaining method.
result Sample complexity is determined by the limiting Gaussian process, not Rademacher complexities.
Proposes Neural Complexity (NC) for predicting and explaining generalization in deep neural networks.
problem Challenges in specifying a suitable complexity measure for deep neural networks to predict and explain generalization.
method A meta-learning framework that learns a scalar complexity measure through interactions with many heterogeneous tasks.
result Trained NC model can be added to standard training loss to regularize any task learner.
CVRL tackles complex visual observations in reinforcement learning.
problem Complex visual observations in natural environments.
method Contrastive Variational Reinforcement Learning (CVRL) learns a contrastive variational model by maximizing mutual information between latent states and observations.
result CVRL achieves comparable performance with state-of-the-art model-based DRL methods and significantly outperforms them on tasks with complex observations.
Transductive learning considers situations when a learner observes m labelled training points and u unlabelled test points with the final goal of giving correct answers for the test points. This paper introduces a new complexity measure for transductive learning called Permutational Rademacher Complexity (PRC) and …
Quantum learning complexity reviewed using information theory.
problem Learning properties of quantum systems or processing data via quantum computing.
method Information-theoretic techniques focusing on data, copy, and model complexity.
result Copy complexity due to irreversible quantum measurements limits information extraction.
New framework minimizes model complexity for improved few-shot learning.
problem Empirical benefits of pre-training scale with data size but lack theoretical explanation.
method Complexity Minimization framework for meta-representation learning.
result Theoretical analysis shows error rate improves with more meta-training data.
We consider the problems of robust PAC learning from distributed and streaming data, which may contain malicious errors and outliers, and analyze their fundamental complexity questions. In particular, we establish lower bounds on the communication complexity for distributed robust learning performed on multiple machine…
Diffusion models learn simple statistics before complex ones, revealing a sample complexity exponent.
problem Understanding the learning dynamics of diffusion models.
method Empirical observations and theoretical analysis of diffusion models and denoisers.
result Diffusion models learn simple statistics (pair-wise correlations) at linear sample complexity, while higher-order statistics (e.g., fourth cumulant) require cubic sample complexity.
First proper learning algorithm for Gaussian halfspaces with matching sample and computational complexity.
problem Agnostically learning halfspaces under Gaussian distribution.
method First proper learning algorithm with matching sample and computational complexity.
result First proper learning algorithm for agnostically learning halfspaces under Gaussian distribution with matching sample and computational complexity.
New algorithm reduces sample and communication complexities in federated Q-learning.
problem Optimal Q-function learning in federated Q-learning with limited communication.
method Introduced Fed-DVR-Q algorithm for order-optimal sample and communication complexities.
result Complete characterization of sample-communication complexity trade-off.
A new deep learning framework for topological data.
problem Developing models for data on complex topological domains.
method Introducing combinatorial complexes and developing attention-based CCNNs.
result CCNNs outperform existing models in tasks involving mesh shape analysis and graph learning.
New algorithm trains neural nets on simple skills to learn complex tasks faster.
problem Learning complex tasks through simple imitation.
method Train neural networks on simple, easy-to-learn skills to accelerate learning of complex, hard-to-learn tasks.
result Consistently outperforms state-of-the-art baseline in training speed and performance.
New analysis shows transfer learning can significantly reduce sample size for complex models.
problem Reducing sample size needed for complex models like large language models.
method Optimal transport viewpoint applied to analyze transfer learning efficiency.
result Transfer learning can achieve better sample efficiency for complex models.
Paper settles sample complexity for learning from multiple distributions.
problem Learning from multiple data distributions with a hypothesis class of bounded VC dimension.
method Introduced an algorithm with sample complexity of O((d+k)ε^-2)·(k/ε)^o(1).
result Algorithm matches lower bound up to sub-polynomial factor.
This work establishes distribution-free upper and lower bounds on the minimax label complexity of active learning with general hypothesis classes, under various noise models. The results reveal a number of surprising facts. In particular, under the noise model of Tsybakov (2004), the minimax label complexity of active …
The paper introduces optimal transport kernels for comparing cell complexes.
problem Lack of machine learning methods for CW complexes.
method Derives explicit expression for Wasserstein distance, extends Fused Gromov-Wasserstein, introduces novel kernels.
result Introduced novel kernels for comparing probability measures on CW complexes.
Paper provides label complexity guarantees for deep active learning.
problem Lack of rigorous label complexity guarantees for deep active learning.
method Studied deep active learning from nonparametric classification perspective.
result Proved near-optimal label complexity guarantees for deep active learning.
Optimal sample complexity for contrastive learning of distances.
problem Minimum labeled tuples needed for high accuracy in learning distances.
method Analyzes sample complexity in various distance settings, proving tight bounds.
result Almost optimal bound on sample complexity for learning ℓp distances. Majorizing measures control sequential complexities for online learning.
problem Extending classical empirical processes theory to sequential cases.
method Generic chaining, majorizing measures, fractional covering numbers.
result Sharp control of worst-case sequential Rademacher complexity.
Introduces LLC, a new complexity measure for DNNs based on SLT.
problem Lack of effective complexity measures for DNNs.
method Uses Singular Learning Theory to define LLC and proposes scalable estimator.
result Empirical evidence shows LLC provides valuable insights into DNN complexity.
New RL method reduces sample complexity for large state-action spaces.
problem Handling large state-action spaces in RL with general Q-functions.
method Nonparametric Q-learning using kernel ridge regression.
result Sample complexity is order optimal with respect to ε and kernel complexity.
New measure shows various training techniques control model complexity.
problem Understanding how to control model complexity in deep learning.
method Developed geometric complexity measure and demonstrated its effectiveness.
result Many training techniques control geometric complexity, providing a unified framework.
Develops neural networks for learning physics of complex systems by enforcing thermodynamics principles.
problem Learning physics of complex systems from incomplete experimental data.
method Integrates port-metriplectic formalism with neural networks to enforce thermodynamics principles.
result Neural networks can learn physics of complex systems by parts, reducing learning burden.
SCAFFLSA reduces communication complexity for federated learning with heterogeneous clients.
problem Quantifying and reducing communication complexity in federated learning with heterogeneous clients.
method Proposes SCAFFLSA, a variant of FedLSA using control variates to correct for client drift.
result SCAFFLSA achieves logarithmic communication complexity for statistically heterogeneous agents, scaling with the inverse of the desired accuracy.
Paper shows pre-training and transfer learning reduce sample complexity for neural networks.
problem Training high-dimensional supervised learning with limited labeled data.
method Study of single-layer neural networks via online stochastic gradient descent, considering concept shift.
result Pre-training and transfer learning reduce sample complexity by polynomial factors under general assumptions.
Study batch reinforcement learning methods for personalized medical treatments.
problem Batch reinforcement learning for personalized medical treatments.
method Direct policy learning and model-based learning approaches.
result Model-based learning is impossible with finite model classes but feasible with relaxed conditions.
New research determines the optimal sample complexity for multiclass and list learning.
problem Determining the optimal sample complexity for multiclass classification.
method Algebraic characterization of multiclass hypothesis classes in terms of their DS dimension.
result Proves a longstanding conjecture and determines the optimal dependence of sample complexity on DS dimension.
Study on teaching reinforcement learning with Q-learning, reducing sample complexity.
problem Reducing sample complexity in reinforcement learning.
method Characterized teaching dimension for Q-learning under different teacher control, presented optimal teaching algorithms.
result Minimum number of samples needed for reinforcement learning is characterized.
This work improves Q-learning for average-reward MDPs, reducing sample and communication complexities in federated settings.
problem Improving sample complexity of Q-learning for average-reward MDPs.
method Simple Q-learning algorithm with carefully chosen parameters for both single-agent and federated scenarios.
result Established first federated Q-learning algorithm for average-reward MDPs with provable efficiency in sample and communication complexities.
New algorithm reduces worst-case sample complexity for learning best arm.
problem Identifying a best arm with confidence in multi-armed bandit settings.
method Proposed a new (ε,δ)-PAC learning algorithm for multi-armed bandits. result Algorithm achieves optimal sample complexity for (ε,δ)-learning. We propose reinforcement learning on simple networks consisting of random connections of spiking neurons (both recurrent and feed-forward) that can learn complex tasks with very little trainable parameters. Such sparse and randomly interconnected recurrent spiking networks exhibit highly non-linear dynamics that transf…
Improved TD learning with neural nets reduces sample complexity and overparameterization.
problem Temporal difference learning with neural networks in large state spaces.
method Projection-free and max-norm regularized Neural TD learning, with Lyapunov drift analysis.
result Max-norm regularization significantly improves TD learning's sample complexity and overparameterization.
NeurIPS 2020 competition seeks to predict deep learning generalization.
problem Understanding and predicting generalization in deep learning models.
method Propose complexity measures to accurately predict generalization performance.
result A robust complexity measure could improve deep learning reliability.
Survey of complex-valued neural networks for improved performance.
problem Lack of complex-valued neural networks in machine learning frameworks.
method Literature review of CVNNs.
result Advantages of CVNNs over real-valued neural networks.
Algorithm extsc{Pedel} learns near-optimal policies efficiently on specific problems.
problem Learning near-optimal policies in linear MDPs with minimal samples.
method Online experiment design to focus exploration on relevant directions.
result Achieves instance-dependent complexity, outperforming minimax-optimal algorithms.
No free lunch theorems suggest inductive biases are needed, but we show neural networks prefer low-complexity data.
problem The need for inductive biases in machine learning.
method Analysis of Kolmogorov complexity and neural network behavior on various datasets.
result Neural networks prefer low-complexity data, suggesting inductive biases are not always necessary.
Active learning method balances bias and variance under class imbalance.
problem Active learning under label shift when class proportions differ.
method Mediated Active Learning under Label Shift (MALLS) using a 'medial distribution'.
result MALLS reduces asymptotic sample complexity under arbitrary label shift.
SGD learns neural networks with a complexity measure called leap.
problem Time complexity of SGD learning on neural networks.
method Introduced a complexity measure called leap, proved conjecture for Gaussian data, and showed saddle-to-saddle dynamics.
result Proved a conjecture about the time complexity of learning functions with low-dimensional support.
This paper improves learning complex functions with CoT supervision, reducing sample complexity.
problem Learning complex functions with multi-step reasoning.
method Develops a statistical theory linking CoT risk and end-to-end risk, using CoT information measure.
result CoT supervision can achieve significantly faster learning rates compared to standard E2E supervision.
Deep learning improves analysis of complex natural processes.
problem Simplistic dynamics in regression analyses of complex natural processes.
method Flexible function approximation using deep learning, relaxing standard assumptions.
result Substantial improvements in behavioral and neuroimaging data.
New complexity measure for interactive learning reduces regret to near-optimal levels.
problem Challenges in sample-efficient, adaptive learning algorithms for interactive decision making.
method Introduces the Decision-Estimation Coefficient and the Estimation-to-Decisions (E2D) principle.
result Unified algorithm design principle E2D achieves optimal sample-efficient learning.
PAC learning sample complexity is decidable with finite support bounds.
problem Determining the exact sample complexity for PAC learning concepts.
method Observation and proof of decidability with a-priori bounds.
result Sample complexity can be exactly determined for various concepts with finite support bounds.
The paper generalizes offset Rademacher complexities to convex and non-convex problems.
problem Improper learning and convexity in statistical learning.
method Generalization of offset Rademacher complexities to convex and non-convex problems.
result The offset complexity provides versatile analytic tools for both convex and non-convex learning.
New algorithm learns halfspaces with noise using Forster decomposition.
problem Learning halfspaces in noisy data.
method Forster decomposition and efficient mixture of distributions.
result First polynomial-time algorithm with strongly polynomial sample complexity.
Efficient active learning with abstention reduces label complexity exponentially.
problem Achieving high accuracy with minimal labels.
method Developed a computationally efficient active learning algorithm with abstention.
result Achieves polylog(1/ε) label complexity, reducing by an exponential factor.
While deep learning has received a surge of interest in a variety of fields in recent years, major deep learning models barely use complex numbers. However, speech, signal and audio data are naturally complex-valued after Fourier Transform, and studies have shown a potentially richer representation of complex nets. In …