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.
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.
The paper approximates Levi-Civita connection and curvature on 2D manifolds using finite elements.
problem Approximating Levi-Civita connection and curvature on 2D manifolds with finite elements.
method Using Regge finite elements, piecewise polynomial symmetric (0,2)-tensor fields, and distributional sense for non-regular tensors.
result Distributional quantities converge to their smooth counterparts under refinement of triangulation.
Unified method for estimating properties of large domain distributions efficiently.
problem Estimating properties of distributions over large domains efficiently.
method Piecewise-polynomial approximation technique for constructing sample- and time-efficient estimators.
result Near-linear-time computable estimators with optimal and highly-concentrated approximation values.
The paper approximates Einstein tensor using finite elements.
problem Approximating Einstein tensor for piecewise polynomial metrics.
method Finite element method applied to Riemannian metrics.
result Convergence rate of O(hr+1) in H−2(Ω)-norm. We give a highly efficient "semi-agnostic" algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions. Let p be an arbitrary distribution over an interval I which is τ-close (in total variation distance) to an unknown probability distribution $…
Piecewise polynomial interpolation-based gradient descent reduces oracle complexity for smooth loss functions.
problem Optimizing empirical risk minimization loss functions
method Piecewise polynomial interpolation-based gradient descent
result Oracle complexity is reduced for smooth loss functions
Paper studies efficient function approximation in high-dimensional spaces with low-dimensional structures.
problem Regression of functions varying along a central subspace in high-dimensional spaces.
method Generalized Contour Regression (GCR) algorithm for estimating the central subspace using piecewise polynomials.
result GCR leads to a mean squared estimation error of O(n−1) for the central subspace, improving the mean squared regression error of f to $O(n^{- rac{2s}{2s+d}})$. Estimates piecewise polynomials and bounded variation functions using optimal decision trees.
problem Estimating piecewise smooth functions in general dimensions.
method Dyadic CART and Optimal Regression Tree (ORT) estimators for piecewise polynomials and bounded variation functions.
result Oracle inequalities and risk bounds for ORT estimators, demonstrating adaptivity and optimality.
New algorithm reduces dynamic regret for noisy gradient feedback with piecewise polynomial comparators.
problem Online estimation of piecewise polynomial trends with noisy feedback.
method Introduces variational constraint for piecewise polynomial comparators, designs adaptive algorithm.
result Achieves nearly optimal dynamic regret of $ ilde{O}(n^{ rac{1}{2k+3}}C_n^{ rac{2}{2k+3}})$.
POUnets combine partitions of unity and monomials for efficient deep learning.
problem Efficiently approximating functions with deep neural networks in high dimensions.
method Integrates partitions of unity and monomials into neural network architecture.
result POUnets achieve hp-convergence for smooth functions and outperform MLPs for discontinuous functions.
Neural networks with ReLU^k approximate Sobolev functions efficiently via Radon transform.
problem Approximating functions from Sobolev spaces using shallow ReLU^k neural networks.
method Utilizing the Radon transform and discrepancy theory, we provide nearly optimal approximation rates.
result Optimal approximation rates for smoothness up to order s = k + (d+1)/2.
This paper introduces a novel mixture model-based approach for simultaneous clustering and optimal segmentation of functional data which are curves presenting regime changes. The proposed model consists in a finite mixture of piecewise polynomial regression models. Each piecewise polynomial regression model is associat…
In this note we consider setups in which variational objectives for Bayesian neural networks can be computed in closed form. In particular we focus on single-layer networks in which the activation function is piecewise polynomial (e.g. ReLU). In this case we show that for a Normal likelihood and structured Normal varia…
For any positive integer k, there exist neural networks with Θ(k3) layers, Θ(1) nodes per layer, and Θ(1) distinct parameters which can not be approximated by networks with O(k) layers unless they are exponentially large --- they must possess Ω(2k) nodes. This result is proved here for a class o…
We consider Bayesian analysis of a class of multiple changepoint models. While there are a variety of efficient ways to analyse these models if the parameters associated with each segment are independent, there are few general approaches for models where the parameters are dependent. Under the assumption that the depen…
The paper analyzes a simple neural network model with algebraic methods.
problem Finding minima of a ridge-regularized mean squared error for ReLU perceptrons.
method Developed a Divide-Enumerate-Merge strategy using computational algebra.
result Identifies both isolated and connected minima of the RR-MSE.
General lower bounds on neural network approximation in L^p norm.
problem Fundamental limits of neural network expressivity.
method General lower bound proof on approximation in L^p norm, applied to feed-forward neural networks.
result Neural networks can't approximate certain functions as well as previously thought.
Finite element method approximates scalar curvature in arbitrary dimensions.
problem Approximating scalar curvature using finite elements in arbitrary dimensions.
method Piecewise polynomial interpolants of a smooth Riemannian metric on a triangulated polyhedral domain.
result Finite element interpolants converge to scalar curvature with rate O(hr+1) in H−2(Ω) norm. Constructs finite element spaces for (p,q)-forms, excluding one subspace.
problem Constructing finite element spaces for (p,q)-forms. method Piecewise polynomial finite element spaces for all natural subspaces of (p,q)-forms, excluding one subspace. result Recovers known finite element spaces and introduces new ones.
This paper uses linear rational splines for invertible modeling, offering a simpler inverse and similar costs.
problem Creating expressive invertible models with tractable Jacobian determinants.
method Replacing affine transformations with linear rational splines in coupling layers.
result Linear rational splines offer a simpler inverse and similar costs for inference and generation.
Extends gradient-based optimization to spline functions.
problem Limitations of standard differentiable programming methods.
method Derives Jacobian of spline functions and uses it in predictive models.
result Improved performance in various applications.
This note is an addendum to our earlier work \cite{humi}. In \cite{humi}, we studied a Hamiltonian action for a generalized Calabi-Yau manifold and showed that the Duistermaat-Heckman theorem holds. The purpose of this note is to show that the density function of the Duistermaa-Heckman measure is a piecewise polynomial…
While all kinds of mixed data -from personal data, over panel and scientific data, to public and commercial data- are collected and stored, building probabilistic graphical models for these hybrid domains becomes more difficult. Users spend significant amounts of time in identifying the parametric form of the random va…
New algorithm predicts piecewise regular functions online.
problem Online prediction of piecewise regular functions.
method Modified sleeping experts aggregation algorithm.
result Oracle risk bounds for all local regions.
Let G be a connected compact Lie group acting on a manifold M and let D be a transversally elliptic operator on M. The multiplicity of the index of D is a function on the set of irreducible representations of G. Let T be a maximal torus of G with Lie algebra Lie(T). We construct a finite number of piecewise polynomial …
New method for robust learning from batches, even adversarial ones.
problem Learning from batches that may be corrupt or adversarial.
method General framework for robust learning, derived from optimal robust algorithms.
result First robust agnostic learning algorithms for various distributions.
Study extends GNN VC dimension bounds to Pfaffian activation functions.
problem Bounding GNN VC dimension for new activation functions.
method Pfaffian function theory applied to GNNs with sigmoid and hyperbolic tangent activations.
result Bounds on GNN VC dimension for various architectures and graph properties.
Paper proposes algorithms to accurately identify breakpoints in piecewise regression.
problem Identifying accurate breakpoints in piecewise regression for better data fitting.
method Proposes novel greedy algorithms to minimize error and determine optimal breakpoints.
result The proposed algorithms outperform existing methods in accuracy and efficiency.
Unified analysis of kernel-based and locally adaptive bandit optimization methods.
problem Performance of bandit optimization algorithms in RKHS functions.
method Investigates the relationship between kernel regularity and algorithmic performance, characterizing spectral properties of various kernels.
result Unified framework for analyzing kernel-based and locally adaptive bandit algorithms, deriving explicit regret bounds.
Efficiently learns mixtures of Gaussians without separation assumptions.
problem Learning mixtures of Gaussian distributions without assuming separation.
method Reduction to score matching and use of diffusion models.
result Constructs a sampler for the target mixture with polynomial runtime and sample complexity.
Probabilistic representations, such as Bayesian and Markov networks, are fundamental to much of statistical machine learning. Thus, learning probabilistic representations directly from data is a deep challenge, the main computational bottleneck being inference that is intractable. Tractable learning is a powerful new p…
Sampling logconcave functions arising in statistics and machine learning has been a subject of intensive study. Recent developments include analyses for Langevin dynamics and Hamiltonian Monte Carlo (HMC). While both approaches have dimension-independent bounds for the underlying continuous processes under s…
The field of statistical relational learning aims at unifying logic and probability to reason and learn from data. Perhaps the most successful paradigm in the field is probabilistic logic programming: the enabling of stochastic primitives in logic programming, which is now increasingly seen to provide a declarative bac…
Method estimates observation functions in state-space models without supervision.
problem Unsupervised learning of non-invertible observation functions in nonlinear state-space models.
method Nonparametric generalized moment method using constrained regression.
result Estimates function space of identifiability from state process.
This work interprets GELU and related activations via a first-order loss function.
problem Understanding and optimizing activation functions in neural networks.
method Complementary interpretation using the Gaussian first-order loss function.
result Calibrated or learned uniform-threshold gates are competitive and often outperform GELU, ReLU, and SiLU/Swish.
This paper studies the problem of estimating the grahpon model - the underlying generating mechanism of a network. Graphon estimation arises in many applications such as predicting missing links in networks and learning user preferences in recommender systems. The graphon model deals with a random graph of n vertices…
PolyLUT uses polynomials to reduce FPGA latency.
problem Reducing latency in FPGA-based neural network inference.
method Training neural networks using multivariate polynomials as basic building blocks.
result Achieved significant latency and area improvements.
The paper calculates volumes of moduli spaces of flat metrics on spheres with specific angles.
problem Calculating volumes of moduli spaces of flat metrics on spheres with prescribed angles.
method Recursive formula and application of Kontsevich's formula.
result The volume of moduli spaces of flat metrics on spheres is a continuous piecewise polynomial function of the angles.
We provide a differentially private algorithm for hypothesis selection. Given samples from an unknown probability distribution P and a set of m probability distributions H, the goal is to output, in a ε-differentially private manner, a distribution from H whose total variation di…
We propose to use deep neural networks for generating samples in Monte Carlo integration. Our work is based on non-linear independent components estimation (NICE), which we extend in numerous ways to improve performance and enable its application to integration problems. First, we introduce piecewise-polynomial couplin…
We study additive models built with trend filtering, i.e., additive models whose components are each regularized by the (discrete) total variation of their kth (discrete) derivative, for a chosen integer k≥0. This results in kth degree piecewise polynomial components, (e.g., k=0 gives piecewise constant co…
Algorithm learns mixtures of Gaussians efficiently using diffusion models.
problem Learning mixtures of Gaussians with identity covariance.
method Analytic approach using diffusion models to learn score functions.
result Quasi-polynomial time and sample complexity for learning mixtures.
Kronecker trend filtering improves lattice data smoothing.
problem Estimating smooth functions on lattice data.
method Penalized least squares with Kronecker products of univariate trend filtering penalties.
result Kronecker trend filtering outperforms linear smoothers in high dimensions.
We study trend filtering, a recently proposed tool of Kim et al. [SIAM Rev. 51 (2009) 339-360] for nonparametric regression. The trend filtering estimate is defined as the minimizer of a penalized least squares criterion, in which the penalty term sums the absolute kth order discrete derivatives over the input points…
The study provides conditions for approximating Riemannian manifolds with polyhedral metrics.
problem Approximating Riemannian manifolds with polyhedral metrics.
method Conditions on curvature tensors for Lipschitz and local polyhedral approximations.
result Conditions are sufficient for local polyhedral approximations, conjectured to be sufficient for global approximations.
Geometric Gaussian approximations capture any distribution.
problem Approximating complex probability distributions.
method Geometric Gaussian approximations through diffeomorphisms or exponential maps.
result Geometric Gaussian approximations are universal, capturing any distribution.
Deep learning networks are approximated using dynamical systems theory.
problem Understanding the approximation capabilities of deep learning networks.
method Modeling deep residual networks as continuous-time dynamical systems and using approximation theories in Lp. result Established general sufficient conditions for universal approximation of deep residual networks.