MLPs can approximate any function in context, challenging the importance of in-context universality.
problem Understanding why transformers are more effective than classical models.
method Proved MLPs with trainable activation functions are universal in context.
result Transformer success is likely due to factors other than in-context universality.
Develops hierarchical reinforcement learning value function approximators.
problem Estimating long-term returns in reinforcement learning with multiple goals.
method Introduces hierarchical universal value function approximators (H-UVFAs) using the options framework.
result Demonstrates generalization and improved performance of H-UVFAs over UVFAs.
Universal MLPs with a single hidden layer can learn any function.
problem Learning on various data structures like sequences, images, sets, and graphs.
method Using group theory, the paper proves the universality of a broad class of equivariant MLPs with a single hidden layer.
result Having a hidden layer on which the group acts regularly is sufficient for universal equivariance (invariance).
Deep Sets approximates functions on sets with high-dimensional latent space.
problem Modeling functions of sets (permutation-invariant functions).
method Deep Sets, a method known to be a universal approximator for continuous set functions.
result Deep Sets' universal approximation property is only guaranteed with a sufficiently high-dimensional latent space.
Transformers enable in-context learning with guarantees for a wide range of tasks.
problem How to enable in-context learning with transformers for various tasks.
method Developed a universal approximation theory integrating Barron's function approximation with transformer capabilities.
result Transformers can approximate any target function with vanishingly small risk using a few in-context examples.
Develops a new approach to establish universality for any-dimensional machine learning models.
problem Understanding universality for models with inputs of varying sizes.
method Identifies any-dimensional functions with a unique function in an infinite-dimensional limit space, using symmetries and relations between inputs of different sizes.
result Establishes universality for several existing architectures and proposes modifications to restore it.
Framework for universal graph function approximators outperforms existing methods.
problem Graph classification and separation of graph classes.
method Inspired by persistent homology, dependency parsing, and multivalued functions, the framework constructs universal approximators on graph isomorphism classes.
result Achieves state-of-the-art performance on four graph datasets.
CF-INNs can approximate any invertible function, resolving a long-standing problem.
problem Whether CF-INNs can approximate any invertible function.
method Demonstrated CF-INNs are universal approximators for invertible functions by showing a convenient criterion.
result CF-INNs are universal approximators for invertible functions.
Reduces bounded loss learning to binary classification.
problem Universal consistency of non-i.i.d. processes with bounded loss.
method Constructive reduction to binary classification.
result Any bounded loss output setting can be reduced to binary classification.
Universal approximation for ODENet and ResNet with a single activation function.
problem Approximating complex dynamical systems with limited vector fields.
method Examined ODENet and ResNet with vector fields composed of a single activation function and affine mapping.
result ODENet and ResNet with restricted vector fields can uniformly approximate those with general vector fields.
A new Universal Activation Function improves performance across various machine learning tasks.
problem Achieving near optimal performance in different machine learning tasks.
method Optimization algorithms evolve the UAF's parameters to match the optimal activation function for each task.
result The UAF converges to near optimal performance in classification, quantification, and reinforcement learning tasks.
This paper explores the limits of deep learning in poly-time.
problem Characterizing function distributions that deep learning can or cannot learn efficiently.
method Analysis of SGD and GD-based deep learning approaches, proving universality and non-universality results.
result SGD-based deep learning is efficiently universal, while GD-based is not, especially with large batches.
Novel approach to universal online learning for bounded losses, closing open problems.
problem Characterizing processes for universal online learning under non-i.i.d. conditions.
method Characterization of processes admitting strong and weak universal learning, introduction of optimistically universal learning rule.
result Introduction of a novel 1NN algorithm that is optimistically universal for bounded losses.
OptFormer learns universal HPO from diverse datasets.
problem Learning HPO from experiments with different hyperparameters.
method Text-based Transformer framework for joint policy and function prediction.
result OptFormer can imitate multiple HPO algorithms and improve predictions.
A new machine learning model uses matrix exponentials for universal approximation.
problem Developing a robust and efficient machine learning model.
method Introduces a novel architecture using matrix exponentials as the only nonlinearity.
result The model achieves universal approximation properties and outperforms other models on benchmark tasks.
New method achieves both universality and adaptivity in online convex optimization.
problem Achieve optimal regret guarantees without prior knowledge of function curvature.
method Introduces UniGrad, a novel approach that achieves both universality and adaptivity.
result Achieves universal regret guarantees that adapt to gradient variation.
Paper characterizes and constructs universal approximators for neural networks.
problem Limited understanding of universal approximation in neural networks.
method Characterization, representation, construction method, existence result for any universal approximator.
result Improved capabilities of feed-forward architecture to approximate continuous functions.
New model closes gap in understanding equivariant set functions.
problem Understanding universality of equivariant set functions.
method Proves PointNet not equivariant universal and introduces PointNetST.
result PointNetST is the simplest permutation equivariant universal model.
This work initiates a general study of learning and generalization without the i.i.d. assumption, starting from first principles. While the traditional approach to statistical learning theory typically relies on standard assumptions from probability theory (e.g., i.i.d. or stationary ergodic), in this work we are inter…
Study proves deep narrow RNNs can approximate any function, with minimum width independent of data length.
problem Proving universality of deep narrow RNNs with bounded widths.
method Analyzing RNNs as dynamical systems, proving universality for deep narrow structures with specific widths.
result Minimum width for universality of deep narrow RNNs is independent of data length.
To deal with changing environments, a new performance measure -- adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, several algorithms have been successfully developed to minimize the adaptive regret. However, existi…
Paper proves GDL models can approximate any continuous function on non-Euclidean data.
problem Processing non-Euclidean data with universal feedforward models.
method Introduces geometric deep learning framework for differentiable manifold geometries.
result GDL models can uniformly approximate any continuous function on compact sets.
We prove Runge-type theorems and universality results for locally univalent holomorphic and meromorphic functions. Refining a result of M. Heins, we also show that there is a universal bounded locally univalent function on the unit disk. These results are used to prove that on any hyperbolic simply connected plane doma…
New findings on universal learning in contextual bandits with adversarial rewards.
problem Learning in contextual bandits with time-varying, adversarial rewards.
method Characterization of learnable processes and necessary/sufficient conditions for universal learning.
result Optimistic universal learning for contextual bandits with adversarial rewards is impossible in general.
HyperBO+ pre-trains a universal prior for Bayesian optimization across different domains.
problem Bayesian optimization requires domain-specific priors, limiting its applicability.
method Two-step pre-training method for hierarchical Gaussian processes.
result HyperBO+ achieves lower regrets on unseen search spaces.
UDENet and ResNet can approximate any function, with ODENet showing UAP for continuous functions.
problem Approximating any function using ODENet and ResNet.
method Proved UAP for ODENet and ResNet, derived gradient, and applied to various problems.
result UDENet and ResNet can approximate any function, with ODENet showing UAP for continuous functions.
The paper tightens bounds on distances between Reeb graphs.
problem Certifying quasi-universality of distances between Reeb graphs.
method Establishes tight bi-Lipschitz bounds for various distances.
result Proves strict universality of the functional contortion distance for contour trees and coincides with interleaving distance for merge trees.
In this paper, we study adaptive online convex optimization, and aim to design a universal algorithm that achieves optimal regret bounds for multiple common types of loss functions. Existing universal methods are limited in the sense that they are optimal for only a subclass of loss functions. To address this limitatio…
This research formalizes uncertainty quantification for Universal Differential Equations models.
problem Quantifying uncertainties in Universal Differential Equations models.
method Formalized uncertainty quantification methods for UDEs, including frequentist and Bayesian approaches.
result Evaluation of ensemble, variational inference, and MCMC sampling methods for UDEs.
Proposes a new neural network architecture combining MLP and basis functions.
problem Function approximation and operator learning in scientific machine learning.
method Combines robust MLP inner functions with flexible basis functions outer functions.
result KKAN outperforms MLPs and KANs in function approximation and operator learning tasks.
Paper explores universal rates of ERM in machine learning.
problem Understanding universal learning rates for ERM.
method Analyzes realizable concept classes and ERM principles.
result Four possible universal learning rates by ERM.
New conditions ensure deep neural networks can approximate any function on non-Euclidean spaces.
problem Understanding how to modify neural network architectures to approximate functions on non-Euclidean spaces.
method Developed conditions for feature and readout maps that preserve universal approximation capabilities.
result Modified architectures can deterministically approximate any classifier on non-Euclidean spaces.
UVU simplifies value uncertainty quantification in RL.
problem Estimating epistemic uncertainty in value functions for reinforcement learning.
method UVU uses squared prediction errors between an online learner and a fixed, randomly initialized target network, incorporating policy-conditional value uncertainty.
result UVU achieves equal performance to large ensembles on challenging offline RL settings, with computational savings.
USFs capture dynamics for faster RL task transfer.
problem Applying knowledge from one task to another.
method Proposed Universal Successor Features (USFs) for RL.
result USFs accelerate training and transfer knowledge.
A universal learner achieves best rates for all distributions.
problem Improving learning algorithm rates under various settings.
method Simple extension of Levin's universal search.
result Achieves best-possible rates for all distributions.
Unified framework proves neural networks' ability to mimic complex tasks.
problem Lack of a single constructive framework for neural network universality.
method Introduces neural network approximate identity (nAI) and proves it leads to universality.
result Any nAI activation function is universal.
Study presents a method to induce a generalized neural network from joint group invariant functions.
problem Encoding rule of neural network internal data representation.
method Systematic method using joint group invariant function on data-parameter domain.
result Induces a generalized neural network and its inverse operator (ridgelet transform).
The objective of transfer reinforcement learning is to generalize from a set of previous tasks to unseen new tasks. In this work, we focus on the transfer scenario where the dynamics among tasks are the same, but their goals differ. Although general value function (Sutton et al., 2011) has been shown to be useful for k…
MPE framework proves universal approximation for quantum data distribution.
problem Challenges in generating quantum data from underlying distributions.
method Many-body Projected Ensemble (MPE) framework for quantum state design.
result MPE can approximate any quantum distribution within 1-Wasserstein distance error.
Deep RBVFs improve continuous control in RL.
problem Challenges in finding optimal actions for continuous actions in RL.
method Introduced deep radial-basis value functions (RBVFs) for continuous control.
result RBF-DQN significantly outperforms value-function-only baselines and is competitive with actor-critic algorithms.
Minimum width for ReLU networks to approximate L^p functions is max(d_x+1, d_y).
problem Characterizing the minimum width for ReLU networks to approximate L^p functions.
method Analyzing networks with ReLU activation functions and proving the minimum width required.
result The minimum width required for the universal approximation of L^p functions is exactly max(d_x+1, d_y).
The study extends kernel universality to Riemannian symmetric spaces.
problem Understanding kernel universality in non-Euclidean domains.
method Harmonic analysis on Riemannian symmetric spaces.
result Proves universality of recent kernels on Riemannian symmetric spaces.
HDNNs can approximate any continuous function, proving their expressivity.
problem Lack of a comprehensive study on the expressivity of HDNNs.
method Discretization of Hamiltonian Neural Ordinary Differential Equations (HNN-ODEs).
result HDNNs can approximate any continuous function over a compact domain.
Kernel methods have been widely applied to machine learning and other questions of approximating an unknown function from its finite sample data. To ensure arbitrary accuracy of such approximation, various denseness conditions are imposed on the selected kernel. This note contributes to the study of universal, characte…
A fast method computes class-specific adversarial perturbations for deep networks.
problem Computing robust adversarial perturbations for deep networks.
method Linear function of weights, no training data, no hyper-parameters.
result Obtains 34% to 51% fooling rate on ImageNet, transfers across models.
We study the approximation properties of random ReLU features through their reproducing kernel Hilbert space (RKHS). We first prove a universality theorem for the RKHS induced by random features whose feature maps are of the form of nodes in neural networks. The universality result implies that the random ReLU features…
Echo state networks with random weights can approximate any continuous system.
problem Approximating continuous dynamical systems using echo state networks.
method Randomly generated internal weights and a sampling procedure for activation functions.
result Echo state networks with random weights can approximate any continuous casual time-invariant operators with high probability.
Complex-valued neural networks can approximate any continuous function.
problem Generalizing the universal approximation theorem to complex-valued networks.
method Characterizing activation functions for complex networks to approximate any continuous function.
result Different activation functions are required for deep vs shallow complex networks to achieve universal approximation.