Non-negative L1-approximating polynomials for Gaussian distributions are proven for certain classes of sets.
problem Existence of non-negative L1-approximating polynomials for Gaussian distributions. method Proving the existence of degree-k non-negative polynomials that approximate indicator functions of sets with Gaussian surface area in L1-norm. result Proves the existence of non-negative L1-approximating polynomials for certain classes of sets with Gaussian surface area. This work improves polynomial approximations for functions with asymmetric behavior.
problem Efficiently approximating functions with asymmetric behavior, especially those growing unbounded on one side.
method Introduces weighted deep polynomial approximants that combine learnable deep polynomials with one-sided weights.
result Weighted deep polynomial approximants outperform existing methods in approximating functions with asymmetric behavior.
New algorithm speeds up polynomial kernel approximations.
problem Efficiently approximating polynomial kernels of high degree.
method Oblivious sketching combined with novel sampling.
result Polynomial factor slowdown removed in running time.
The paper shows neural networks can approximate functions over non-compact domains with non-polynomial activation.
problem Approximating functions over non-compact domains using neural networks.
method Using single-hidden-layer feedforward neural networks with non-polynomial activation functions over non-compact subsets of Euclidean spaces.
result Neural networks can approximate functions in weighted Ck-spaces and weighted Sobolev spaces over unbounded domains. The paper proves deep neural networks with analytic activation can approximate any function.
problem Approximating functions with neural networks using analytic activation functions.
method Elementary proofs for real and complex networks, Stone-Weierstrass theorem, Mergelyan's theorem.
result Closure of neural network classes equals space of polynomials for analytic activation.
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.
Approximates discounted moments for financial products using polynomial expansions.
problem Approximating discounted moments of stochastic processes for financial applications.
method High-order power series expansion of the infinitesimal generator.
result Error decreases to around 10 to 100 times machine precision for higher orders.
Unified approach to experimental design using interlacing polynomials.
problem Experimental design problems, especially D/A/E-design and E-design.
method Unified deterministic approach using interlacing polynomials.
result Improved approximation guarantees for various experimental design objectives.
New polynomial-time solutions found for training ReLU networks, mirroring Max-Cut complexity.
problem Training two-layer ReLU neural networks with weight decay regularization.
method Developed a convex formulation and randomized algorithm to find approximate global optimizers.
result First polynomial-time approximation guarantees and hardness of approximation results for regularized ReLU networks.
Paper develops polynomial approximations for complex probability densities.
problem Approximating high-dimensional concentrated probability densities.
method Tensor-product spectral polynomials and KR rearrangements.
result Efficient approximation of complex densities using composite maps.
The paper proves barriers to approximating functions with small weights and depth in neural networks.
problem Proving barriers to approximating functions with constant depth neural networks.
method Reduction to open problems and natural-proof barriers in circuit complexity, and a new approach to polynomially-bounded functions.
result There are fundamental barriers to proving results beyond depth 4 for constant-depth neural networks.
Polynomial sketch approximates functions of low-rank matrices efficiently.
problem Approximating element-wise functions of low-rank matrices without full access.
method Combining polynomial approximation and tensor sketch for monomials.
result Efficient algorithm with lower complexity than full matrix access.
Compact bilinear pooling approximates covariance features for faster training.
problem Efficiently approximating covariance features for faster training.
method Compact bilinear pooling extended to polynomial approximations of covariance features.
result The proposed method achieves comparable accuracy with fewer dimensions.
Analytic networks with bounded coefficients can't outperform polynomial approximations.
problem Approximation limits of neural networks with analytic activation functions under coefficient constraints.
method Deterministic analysis using comparison argument and Bernstein-type estimates.
result Networks with analytic activation functions and controlled coefficients cannot outperform classical polynomial approximation rates on non-analytic targets.
We find approximations by Vassiliev invariants for the coefficients of the Jones polynomial and all specializations of the HOMFLY and Kauffman polynomials. Consequently, we obtain approximations of some other link invariants arising from the homology of branched covers of links.
Tropical division approximates polynomial division for neural networks.
problem Approximating polynomial division in max-plus semiring.
method Approximating Newton Polytope of dividend by divisor, then applying to neural networks.
result Minimizes a two-layer fully connected network for binary classification.
SURF simplifies distribution estimation with simple, robust, and fast algorithms.
problem Efficient and accurate distribution estimation in statistics and machine learning.
method Piecewise polynomial approximation using empirical probability interpolation and divide-and-conquer merging.
result Surpassing state-of-the-art algorithms in efficiency and accuracy, SURF estimates distributions robustly and quickly.
Paper proposes a new vanishing ideal for noisy data with improved algebraic structure.
problem Extracting nonlinear structures of noisy data with better algebraic properties.
method Simultaneously finds polynomials and data points for which polynomials approximately vanish on input data and almost exactly on discovered points.
result Our method discovers much fewer and lower-degree polynomials than state-of-the-art methods, accelerating runtime without degrading accuracy.
Closed-form polynomial approximations replace MLPs in transformers, enabling new interpretability methods.
problem Replacing MLPs with polynomial approximations for transformer models.
method Theoretical derivation of closed-form least-squares approximations of MLPs and GLUs using polynomial functions.
result Polynomial approximations explain over 95% of MLP and GLU outputs' variance, enabling interpretability.
It is known that evaluating a certain approximation to the Jones polynomial for the plat closure of a braid is a BQP-complete problem. That is, this problem exactly captures the power of the quantum circuit model. The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maxim…
New algorithms improve approximation of matrix norms, with applications in statistics and machine learning.
problem Improving approximation of matrix norms for 2ightarrowq in polynomial time. method Polynomial-time multiplicative approximation algorithms for 2ightarrowq norm, leveraging sum-of-squares certificates. result Achieved polynomially improved approximation factors, notably d1/8 for q=4. New analysis shows neural networks and low-degree polynomials perform well on sparse latent structure problems.
problem Understanding the performance of neural networks and polynomial approximators on real-world sparse latent structure problems.
method Analysis of neural networks and polynomial kernels of bounded degree on a simple, natural inference problem with sparse latent structure.
result Almost-tight bounds on the performance of neural networks and low-degree polynomials for the problem, showing qualitative differences from worst-case settings.
Hard to approximate critical points for simple nonconvex functions.
problem Approximating critical points of nonconvex functions.
method Proving hardness results for polynomial-time approximation of critical points.
result Proving that approximating critical points is intractable for simple nonconvex functions.
Strongly polynomial algorithm for approximate Forster transforms and halfspace learning.
problem Computing approximate Forster transforms and halfspace learning.
method Strongly polynomial time algorithm for approximate Forster transforms and halfspace learning.
result First strongly polynomial time algorithm for distribution-free PAC learning of halfspaces.
We develop a polynomial method to optimize trading in markets with transaction costs.
problem Optimizing trading strategies in markets with proportional transaction costs.
method Polynomial approximation of the residual value function to determine optimal trading strategies.
result Identify the trade-off between trading frequency and trade sizes for satisfactory agreement with theoretically optimal strategies.
The paper shows how neural networks can approximate PDEs with polynomial scaling in dimension.
problem Understanding the complexity of approximating PDE solutions with neural networks.
method Developed a proof technique to simulate gradient descent using neural networks.
result Neural network parameters scale polynomially with input dimension for approximating PDE solutions.
NO approximates non-Markovian BSDEs with polynomial scaling in 1/ε.
problem Complexity of NO approximations for structured families of BSDEs.
method Identifying structured families of non-Markovian BSDEs, informing NO's inductive bias.
result Polynomial scaling in 1/ε for NO approximations of BSDE solution operators.
Quantifies polynomial approximation rates for smooth functions under various distributions.
problem Approximating smooth functions with polynomials under different distributional constraints.
method Develops a quantitative analogue of Carleman's theorem using complex analysis.
result Establishes superexponential rates of approximation for certain function classes over general distributions.
Study shows polynomial-width neural networks can closely approximate infinite-width networks in polynomial time.
problem Approximating dynamics of polynomial-width neural networks with infinite-width networks.
method Bounding approximation gap through a differential equation governed by mean-field dynamics, considering local Hessian.
result Polynomially many neurons are sufficient to closely approximate mean-field dynamics.
Proposes a novel approach for deep neural network initialization using polynomial approximations.
problem Improving deep neural network training from initialization.
method Uses polynomial-based approximations to initialize deep neural networks.
result Networks initialized with polynomial approximations are more likely to achieve a desirable local minimum during training.
Solves PCR with fewer calls to ridge regression.
problem Principal component regression (PCR) with high accuracy.
method Reduces PCR to ridge regression calls and develops stable recurrence for matrix Chebyshev polynomials.
result Achieves PCR with multiplicative accuracy up to 1+γ using fewer calls. Algorithm samples from Bingham distribution efficiently.
problem Sampling from the Bingham distribution on a sphere.
method Rejection sampling with polynomial approximation.
result Exact samples from Bingham distribution in polynomial time.
New algorithm speeds up knot polynomial calculations.
problem Computing Reshetikhin--Turaev knot polynomials efficiently.
method Fixed-parameter tractable computation via tensor networks.
result Knot polynomial computations are fixed-parameter tractable.
New insights into belief propagation and Bethe approximation for factor graphs.
problem Understanding the correctness and efficiency of belief propagation and its relation to partition functions.
method Viewing factor graphs through the lens of polynomials and reformulating Bethe approximation as a polynomial optimization problem.
result For bipartite normal factor graphs, the Bethe approximation is a lower bound to the partition function under certain analytic conditions.
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for appro…
The study approximates option prices using Hermite polynomials without assuming a specific distribution.
problem Approximating option prices without assuming a specific distribution of returns.
method Approximating the logarithmic return's density by a linear combination of rescaled Hermite polynomials.
result Empirical results suggest reasonable performance for options with moderate strike prices.
New algorithm improves polynomial chaos approximations using compressive sensing.
problem Improving the efficiency and accuracy of polynomial chaos expansions.
method Develops a two-step optimization procedure combining compressive sensing with basis adaptation.
result Optimal sparsity in polynomial chaos approximations with reduced dimensionality.
RationalNet improves graph convolutional networks by approximating jump discontinuities more efficiently.
problem Graph convolutional networks struggle with approximating jump discontinuities, leading to oscillations and high computational costs.
method RationalNet uses rational functions to approximate graph signals, avoiding oscillations and reducing computational complexity.
result RationalNet effectively characterizes jump discontinuities, outperforming other methods on both synthetic and real-world graphs.
Polynomial-time algorithm for optimal stopping with fixed accuracy.
problem High-dimensional path-dependent optimal stopping problems.
method Efficient simulator of underlying information process, polynomial-time algorithm based on novel expansion.
result Polynomial-time solution for epsilon-optimal stopping policies and values.
Efficiently finds sparse solutions to max-plus equations for convex regression.
problem Finding sparse solutions to max-plus equations for convex multivariate regression.
method Polynomial-time algorithm for sparse approximate solutions.
result Optimal piecewise-linear fitting with minimum number of regions.
This study shows the moment-SOS hierarchy converges in polynomial optimization over product of spheres.
problem Minimizing multihomogeneous polynomials over product of spheres.
method Moment-SOS hierarchy, local optimality conditions, differential geometry, Morse theory.
result The moment-SOS hierarchy has finite convergence for generic multihomogeneous objective functions.
Paper revisits graph-CNNs using Laplace-Beltrami spectral filters and polynomials.
problem Improving spectral graph convolutional neural networks (graph-CNNs).
method Developed Laplace-Beltrami CNN (LB-CNN) by replacing graph Laplacian with LB operator and approximating spectral filters using Chebyshev, Laguerre, and Hermite polynomials.
result Classification accuracy of LB-CNN is not dependent on the type of polynomials or operators.
Develops manifold calculus for simplicial complexes.
problem Approximating functors from simplicial complexes to topological spaces.
method Adapting manifold calculus to simplicial complexes and proving an approximation theorem.
result Functors can be approximated by polynomial functors under certain conditions.
A new formula approximates knot volume using Jones polynomial evaluations.
problem Approximating the hyperbolic volume of knots using a simple formula.
method Reversing a neural network trained on Jones polynomial evaluations.
result Average error of 2.86% on first 1.7 million knots.
In this paper we use Bernstein and Chebyshev polynomials to approximate the price of some basket options under a bivariate Black-Scholes model. The method consists in expanding the price of a univariate related contract after conditioning on the remaining underlying assets and calculating the mixed exponential-power mo…
Proposes polynomial neural networks for improved function approximation in various tasks.
problem Improving function approximation in various tasks like image generation, face verification, and 3D mesh representation learning.
method Introduces polynomial neural networks (Π-Nets) and three tensor decompositions to reduce parameter count and enhance expressiveness. result Demonstrates that Π-Nets can produce state-of-the-art results in challenging tasks without non-linear activation functions. Paper tackles spurious vanishing problem in approximate vanishing ideals.
problem Capturing nonlinear structure of perturbed data points leads to spurious vanishing problem.
method Proposes a general method integrating coefficient normalization and iterative basis construction.
result Proposed method overcomes spurious vanishing problem, resulting in shorter feature vectors.
Polynomial-time method approximates Shapley values for deep neural networks.
problem Lack of reliable attribution methods for deep neural networks.
method Polynomial-time approximation of Shapley values using uncertainty propagation.
result Our method produces significantly better approximations of Shapley values than existing methods.