Universal Approximation Under Constraints is Possible with Transformers

• URL: http://arxiv.org/abs/2110.03303v1
• Date: Thu, 7 Oct 2021 09:43:01 GMT
• Title: Universal Approximation Under Constraints is Possible with Transformers
• Abstract summary: Many practical problems need a machine learning model to satisfy a set of constraints, $K$. Our main result is a "deep neural version" of Berg's Theorem (1963).
• Score: 33.41613996903392
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many practical problems need the output of a machine learning model to satisfy a set of constraints, $K$. Nevertheless, there is no known guarantee that classical neural network architectures can exactly encode constraints while simultaneously achieving universality. We provide a quantitative constrained universal approximation theorem which guarantees that for any non-convex compact set $K$ and any continuous function $f:\mathbb{R}^n\rightarrow K$, there is a probabilistic transformer $\hat{F}$ whose randomized outputs all lie in $K$ and whose expected output uniformly approximates $f$. Our second main result is a "deep neural version" of Berge's Maximum Theorem (1963). The result guarantees that given an objective function $L$, a constraint set $K$, and a family of soft constraint sets, there is a probabilistic transformer $\hat{F}$ that approximately minimizes $L$ and whose outputs belong to $K$; moreover, $\hat{F}$ approximately satisfies the soft constraints. Our results imply the first universal approximation theorem for classical transformers with exact convex constraint satisfaction. They also yield that a chart-free universal approximation theorem for Riemannian manifold-valued functions subject to suitable geodesically convex constraints.

Related papers

• Constrained Learning with Universally Learnable Concept Classes [2.5998827435861633]
  We establish universal PACC learnability of the solutions of the solutions of dual algorithms.<n> Optimality is caught between universality, governed by convexity, and strong Lagrangian duality.
  arXiv  Detail & Related papers  (2026-08-09T02:13:57Z)
• Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unity [5.37133760455631]
  This paper investigates the learning theory of Transformer networks for regression tasks on the compact Euclidean domain $[0,1]d$.<n>We propose a novel constructive approximation framework for Transformers that builds local approximations of the target function and aggregates them into a global approximation.<n>We prove that a dense Transformer equipped with only two encoder blocks and standard single-hidden-layer point-wise feed-forward networks can achieve a uniform $varepsilon$-approximation error for $$-Hlder continuous functions.
  arXiv  Detail & Related papers  (2026-05-09T09:02:37Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry [0.0]
  We prove by a direct reduction from Hstad's theorem that no-time algorithm can exceed the randomassignment ratio $r/q$ by any constant.<n>This threshold coincides with the $ell/m to 0$ limit of the semicircle law governing decoded quantum interferometry.
  arXiv  Detail & Related papers  (2026-03-04T19:26:26Z)
• On finite-dimensional encoding/decoding theorems for neural operators [0.0]
  We show that a continuous mapping $f$ between function spaces $E$ and $F$ is approximated in the topology of uniform convergence on compacta.<n>We point out that the result needs no assumptions on $E,F$ whatsoever and remains true not only for all normed spaces, but for arbitrary locally convex spaces as well.<n>This analysis may be useful already because non-normable locally convex function spaces are common in the theory of differential equations.
  arXiv  Detail & Related papers  (2026-01-20T15:15:51Z)
• New advances in universal approximation with neural networks of minimal width [4.424170214926035]
  We show that autoencoders with leaky ReLU activations are universal approximators of $Lp$ functions. We broaden our results to show that smooth invertible neural networks can approximate $Lp(mathbbRd,mathbbRd)$ on compacta.
  arXiv  Detail & Related papers  (2024-11-13T16:17:16Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  We quantify the performance of the approximation with the Monge-Kantorovich $p$-cost. We may then reform the problem as minimizing a functional $mathscrJ_p(f)$ under a constraint on the Sobolev budget.
  arXiv  Detail & Related papers  (2024-09-25T01:30:16Z)
• On a Neural Implementation of Brenier's Polar Factorization [24.48716080522871]
  In 1991, Brenier proved a theorem that generalizes the polar decomposition for square matrices factored as PSD $times$ unitary -- to any vector field $F:mathbbRdright mathbbRdarrow. We propose a practical implementation of the polar factorization theorem, and explore possible uses within machine learning.
  arXiv  Detail & Related papers  (2024-03-05T15:59:54Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Toward $L_\infty$-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields [35.76184529520015]
  Many machine learning applications require learning a function with a small worst-case error over the entire input domain, that is, the $L_infty$-error. Most existing theoretical works only guarantee recovery in average errors such as the $L$-error. This paper makes some initial steps beyond the impossibility results by leveraging the randomness in the ground-truth functions.
  arXiv  Detail & Related papers  (2023-04-29T18:33:39Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• A general approximation lower bound in $L^p$ norm, with applications to feed-forward neural networks [0.0]
  We study the fundamental limits to the expressive power of neural networks. We first prove a general lower bound on how well functions in $F$ can be approximated in $Lp(mu)$ norm. We then instantiate this bound to the case where $G$ corresponds to a piecewise-polynomial feed-forward neural network.
  arXiv  Detail & Related papers  (2022-06-09T09:01:05Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
  We consider a standard distributed optimisation setting where $N$ machines aim to jointly minimise the sum of the functions $sum_i = 1N f_i (x)$. Our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the $N$ machines. We show that $Omega( Nd log d / Nvarepsilon)$ total bits need to be communicated between the machines to find an additive $epsilon$-approximation to the minimum of $sum_i = 1N
  arXiv  Detail & Related papers  (2020-10-16T08:10:02Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
  arXiv  Detail & Related papers  (2020-04-16T19:16:38Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.