Improved neural network depth-width trade-offs via dynamical systems.
problem Expressivity of neural networks in terms of depth and width.
method Connection with dynamical systems, focusing on periodic points and Lipschitz constants.
result Sharper width lower bounds for neural networks, yielding exponential depth-width separations.
Understanding the representational power of Deep Neural Networks (DNNs) and how their structural properties (e.g., depth, width, type of activation unit) affect the functions they can compute, has been an important yet challenging question in deep learning and approximation theory. In a seminal paper, Telgarsky highlig…
Bayesian linear networks reveal optimal depth and width trade-offs.
problem Understanding how depth, width, and dataset size affect model quality in linear networks.
method Zero noise Bayesian inference with Gaussian weight priors and mean squared error.
result Optimal predictions at infinite depth and maximized Bayesian model evidence at infinite depth.
WGANs improve probability distribution approximation with depth and width trade-offs.
problem Approximating complex probability distributions accurately.
method Wasserstein GANs with GroupSort discriminators, quantified generalization bound.
result High-capacity discriminators are crucial for WGANs' performance.
Deep forests enhance expressiveness exponentially with depth, not width or tree size.
problem Understanding the role of depth, width, and tree size in deep forest performance.
method Provided upper and lower bounds on deep forest approximation complexity.
result Depth exponentially enhances deep forest expressiveness.
Self-attention models benefit equally from width and depth, but beyond a certain point, depth becomes less efficient.
problem Understanding the optimal balance between depth and width in self-attention models.
method Theoretical predictions and empirical ablations on networks of varying depths and widths.
result An optimal width of 30K is recommended for a 1-Trillion parameter network, marking a significant width for self-attention models.
Convolutional Neural Networks (ConvNets) are commonly developed at a fixed resource budget, and then scaled up for better accuracy if more resources are available. In this paper, we systematically study model scaling and identify that carefully balancing network depth, width, and resolution can lead to better performan…
Deep neural networks near edge of chaos show universal scaling laws.
problem Understanding the behavior of deep neural networks near critical points.
method Analogy to absorbing phase transitions in statistical mechanics, deterministic propagation dynamics, mean-field and directed percolation universality classes.
result Deep neural networks exhibit universal scaling laws near the edge of chaos.
This work generalizes bounds on the number of linear regions in CPWL NNs.
problem Determining the number of linear regions in CPWL neural networks is challenging.
method Generalized bounds on the maximal number of linear regions for arbitrary CPWL activation functions.
result Depth significantly increases the number of linear regions, but not exponentially.
We provide several new depth-based separation results for feed-forward neural networks, proving that various types of simple and natural functions can be better approximated using deeper networks than shallower ones, even if the shallower networks are much larger. This includes indicators of balls and ellipses; non-lin…
This paper improves neural network approximation for analytic functions with adjustable depth and width.
problem Approximating analytic functions using neural networks with depth and width parameters.
method Characterizes approximation rates as a joint function of width (N) and depth (L) for ReLU networks.
result Establishes upper bounds for analytic function approximation rates of O(N^(-CL^τ)) with τ influenced by N and L.
Deep neural networks with piecewise-polynomial activations can approximate smooth functions and their derivatives.
problem Approximating smooth functions and their derivatives with neural networks.
method Derives the depth, width, and sparsity required for approximation in Hölder norms.
result Deep neural networks with bounded weights can approximate Hölder smooth functions and their derivatives.
Deep neural networks have been used in various machine learning applications and achieved tremendous empirical successes. However, training deep neural networks is a challenging task. Many alternatives have been proposed in place of end-to-end back-propagation. Layer-wise training is one of them, which trains a single …
There has been a growing interest in expressivity of deep neural networks. However, most of the existing work about this topic focuses only on the specific activation function such as ReLU or sigmoid. In this paper, we investigate the approximation ability of deep neural networks with a broad class of activation functi…
This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attributes, and layer expressiveness. Second, it is discovered that GNNm…
Deep neural networks with specific parameter sets can approximate smooth functions efficiently.
problem Approximating smooth functions with deep neural networks.
method Deep neural networks with ReLU activation and specific parameter sets {0,±21,±1,2} are used to approximate Cβ-smooth functions. result The constructed networks can approximate Cβ-smooth functions with parameters {0,±21,±1,2} efficiently, achieving the same convergence rate as sparse networks with parameters in [−1,1]. Pruned neural networks' error scales predictably with architecture and task.
problem Understanding the predictability of pruning across different scales and architectures.
method Functionally approximated the error of pruned networks, showing it is predictable in terms of invariant tying width, depth, and pruning level.
result The error of pruned networks follows a scaling law with interpretable coefficients that depend on architecture and task.
The paper bounds the excess risk of deep neural networks for weakly dependent processes.
problem Learning with weakly dependent data using deep neural networks.
method Approximation of smooth functions by deep neural networks and a bound on excess risk.
result The excess risk bound for deep learning under weak dependence is close to O(n−1/2) for sufficiently smooth functions. New method selects neural network architectures without needing data.
problem Choosing efficient deep neural network architectures.
method Developed the deep frame potential to quantify network capacity.
result Deep frame potential correlates with generalization error.
Spike-and-Slab Deep Learning (SS-DL) is a fully Bayesian alternative to Dropout for improving generalizability of deep ReLU networks. This new type of regularization enables provable recovery of smooth input-output maps with unknown levels of smoothness. Indeed, we show that the posterior distribution concentrates at t…
The classical Universal Approximation Theorem holds for neural networks of arbitrary width and bounded depth. Here we consider the natural `dual' scenario for networks of bounded width and arbitrary depth. Precisely, let n be the number of inputs neurons, m be the number of output neurons, and let ρ be any nonaff…
Study shows neural operators can efficiently solve complex reaction-diffusion systems.
problem Efficiently solving nonlinear reaction-diffusion systems using neural operators.
method Laplacian-based neural operators applied to a generalized Gierer-Meinhardt system.
result Explicit approximation error bounds established for neural operators in terms of network parameters.
We provide a general framework for characterizing the trade-off between accuracy and robustness in supervised learning. We propose a method and define quantities to characterize the trade-off between accuracy and robustness for a given architecture, and provide theoretical insight into the trade-off. Specifically we in…
A new algorithm speeds up neural network derivative calculations.
problem Exponential runtime of autodifferentiation for high-order derivatives in neural networks.
method n-TangentProp, a quasilinear algorithm for computing higher-order derivatives.
result Computes exact derivatives in quasilinear time, not exponential.
A new framework enables real-time task trade-off control.
problem Conflict between multiple related tasks in a fixed model capacity.
method Formulates MTL as a preference-conditioned multiobjective optimization problem; uses a hypernetwork-based neural network.
result A single model can handle different trade-off preferences among multiple tasks.
Paper proves higher-order flow matching preserves optimality in generative modeling.
problem Theoretical guarantees for higher-order flow matching in generative modeling.
method Neural network approximations with controlled depth, width, and sparsity.
result Proves worst case optimality for second-order flow matching.
New trade-off found between accuracy and adversarial robustness in regression.
problem Finding a balance between accuracy and robustness in regression models.
method Deriving a fundamental trade-off between standard and adversarial risk in regression with polynomial ridge functions.
result A necessary condition for achieving adversarial robustness without significant accuracy loss.
Paper explores robust regression methods and their bias-variance trade-off.
problem Understanding the trade-off between robust estimation and optimization methods.
method Examines traditional outlier-resistant robust estimation and robust optimization.
result Both methods follow converse strategies due to a bias-variance trade-off.
This paper studies trade-offs in private prediction methods.
problem Leakage of training data information in machine learning predictions.
method Private training and private prediction methods with trade-offs.
result Private training methods outperform private prediction methods in various settings.
Efficiently approximates fairness-accuracy trade-offs for diverse datasets.
problem Inherent trade-off between fairness and accuracy in machine learning models.
method You-Only-Train-Once (YOTO) framework for computationally efficient approximation.
result Robust methodology for auditing model fairness with statistical guarantees.
Batch normalization makes deep neural networks' representations increasingly orthogonal.
problem Orthogonality of deep neural network representations.
method Random linear transformations in successive batch-normalizations.
result Orthogonality of representations improves SGD performance.
New insights into convergence and accuracy trade-offs in federated and meta-learning.
problem Understanding the trade-offs between convergence and accuracy in federated and meta-learning.
method Generalized local update methods, proving equivalence to first-order optimization on a surrogate loss.
result Novel convergence rates and insights into the importance of algorithmic choices in communication-limited settings.
We empirically investigate the best trade-off between sparse and uniformly-weighted multiple kernel learning (MKL) using the elastic-net regularization on real and simulated datasets. We find that the best trade-off parameter depends not only on the sparsity of the true kernel-weight spectrum but also on the linear dep…
There have been different strategies to improve the performance of a machine learning model, e.g., increasing the depth, width, and/or nonlinearity of the model, and using ensemble learning to aggregate multiple base/weak learners in parallel or in series. This paper proposes a novel strategy called patch learning (PL)…
Proposes FACT, a diagnostic for understanding group fairness trade-offs.
problem Group fairness notions often conflict with each other, requiring a cost in model performance.
method Characterizes trade-offs via the fairness-confusion tensor and optimizes accuracy and fairness objectives.
result Demonstrates the use of FACT on synthetic and real datasets to understand accuracy-fairness trade-offs.
Study shows exponential error reduction in multiclass classification without bias-variance trade-off.
problem Multiclass classification with margin conditions.
method Analysis of classification error under hard-margin conditions.
result Exponential decrease in classification error without bias-variance trade-off.
A trade-off between accuracy and fairness is almost taken as a given in the existing literature on fairness in machine learning. Yet, it is not preordained that accuracy should decrease with increased fairness. Novel to this work, we examine fair classification through the lens of mismatched hypothesis testing: trying …
Vecchia approximations provide the best accuracy-runtime trade-off for Gaussian process approximations.
problem High computational cost of Gaussian processes for large data sets.
method Systematic comparison of different Gaussian process approximations.
result Vecchia approximations consistently provide the best accuracy-runtime trade-off.
The paper explores the trade-off between bias and variance in high-dimensional models.
problem Understanding the unavoidable trade-off between bias and variance in high-dimensional statistical models.
method Proposes a general strategy to obtain lower bounds on the variance of estimators with a specified bias, and applies it to various statistical models.
result Shows the extent to which the bias-variance trade-off is unavoidable and quantifies the performance loss for methods that do not balance it.
Mixtures of neural operators reduce active complexity in operator learning.
problem Reduction of active complexity in operator learning models.
method Constructive comparison between routed mixtures of neural operators (MoNOs) and a fixed single-neural-operator construction.
result Every scalar uniformly continuous nonlinear operator can be approximated by a MoNO whose active expert has smaller depth, width, and rank scaling.
The statistical complexity of quantum circuits is studied using Rademacher complexity.
problem Measuring the richness of quantum hypothesis spaces.
method Applying Rademacher complexity to quantum circuits, investigating dependencies on resources, depth, width, and input/output registers.
result Bounds on the capacity of quantum neural networks constrained by circuit depth, width, and resource measures.
Study on the geometric Dyson Brownian motion of non-square matrix products.
problem Understanding the spectrum of a product of non-square random matrices.
method Proportional depth-width limit followed by mean-field limit, solving Burgers equation.
result Free log-normal law is obtained in the identity-start case.
New insights into how depth and width affect in-context learning in deep models.
problem Understanding how various resources impact in-context learning in deep models.
method Analyzed linear regression in a deep linear self-attention model, varying resources like depth, width, context length, and training steps.
result Increasing depth improves in-context learning even at infinite context length, contrary to previous findings.
Fine-tuning LLMs improves capability but harms safety, study finds.
problem Balancing capability and safety in LLM fine-tuning.
method Theoretical framework and numerical experiments for two safety-aware fine-tuning strategies.
result Characterization of fundamental limits of safety-capability trade-off in LLM fine-tuning.
This paper analyzes the trade-off between accuracy and communication in personalized federated learning.
problem The accuracy-communication trade-off in personalized federated learning.
method The paper provides a quantitative characterization of the personalization degree on the trade-off, establishing minimax optimality.
result The paper offers theoretical insights for choosing the personalization degree and validates the results on synthetic and real-world datasets.
NeuroMAS treats multi-agent systems as neural networks for scalable, trainable coordination.
problem Designing multi-agent systems as hand-designed workflows is inefficient and inflexible.
method NeuroMAS treats multi-agent systems as a neural network architecture with reinforcement learning for scalable coordination.
result NeuroMAS improves significantly over multi-agent baselines and can be scaled progressively.
SCORE resolves the robustness vs accuracy trade-off by redefining robust error.
problem The inherent trade-off between robustness and accuracy in adversarial training.
method SCORE defines local equivariance as the ideal robust behavior, leading to a new robust error metric.
result SCORE reconciles robustness and accuracy, improving model performance on RobustBench.
Two Fisher information matrix estimators are analyzed for neural networks, focusing on their variances and trade-offs.
problem Estimating the Fisher information matrix in neural networks due to its high computational cost.
method Examined two popular diagonal Fisher information matrix estimators and their variances in neural networks for regression and classification.
result The variances of the estimators depend on the non-linearity with respect to different parameter groups and should not be neglected.