Piecewise Polynomial Regression of Tame Functions via Integer Programming

• URL: http://arxiv.org/abs/2311.13544v3
• Date: Tue, 4 Jun 2024 09:38:39 GMT
• Title: Piecewise Polynomial Regression of Tame Functions via Integer Programming
• Authors: Gilles Bareilles, Johannes Aspman, Jiri Nemecek, Jakub Marecek,
• Abstract summary: We consider tame functions, nonsmooth functions with all common activations, value functions of mixed-integer programs, or wave functions of small molecules.
• Score: 2.2499166814992435
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tame functions are a class of nonsmooth, nonconvex functions, which feature in a wide range of applications: functions encountered in the training of deep neural networks with all common activations, value functions of mixed-integer programs, or wave functions of small molecules. We consider approximating tame functions with piecewise polynomial functions. We bound the quality of approximation of a tame function by a piecewise polynomial function with a given number of segments on any full-dimensional cube. We also present the first mixed-integer programming formulation of piecewise polynomial regression. Together, these can be used to estimate tame functions. We demonstrate promising computational results.

Related papers

• Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection [50.14730810124592]
  Submodular functions and variants, through their ability to characterize diversity and coverage, have emerged as a key tool for data selection and summarization. We propose FLEXSUBNET, a family of flexible neural models for both monotone and non-monotone submodular functions.
  arXiv  Detail & Related papers  (2022-10-20T06:00:45Z)
• Sparsification of Decomposable Submodular Functions [27.070004659301162]
  Submodular functions are at the core of many machine learning and data mining tasks. The number of underlying submodular functions in the original function is so large that we need large amount of time to process it and/or it does not even fit in the main memory. We introduce the notion of sparsification for decomposable submodular functions whose objective is to obtain an accurate approximation of the original function is a (weighted) sum of only a few submodular functions.
  arXiv  Detail & Related papers  (2022-01-18T20:05:25Z)
• Neural Network Approximation of Refinable Functions [8.323468006516018]
  We show that refinable functions are approximated by the outputs of deep ReLU networks with a fixed width and increasing depth with accuracy exponential. Our results apply to functions used in the standard construction of wavelets as well as to functions constructed via subdivision algorithms in Computer Aided Geometric Design.
  arXiv  Detail & Related papers  (2021-07-28T06:45:36Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Learning Aggregation Functions [78.47770735205134]
  We introduce LAF (Learning Aggregation Functions), a learnable aggregator for sets of arbitrary cardinality. We report experiments on semi-synthetic and real data showing that LAF outperforms state-of-the-art sum- (max-) decomposition architectures.
  arXiv  Detail & Related papers  (2020-12-15T18:28:53Z)
• On Polynomial Approximations for Privacy-Preserving and Verifiable ReLU Networks [6.130998208629276]
  We propose a degree-2 activation function with a first order term and empirically show that it can lead to much better models. Our proposed function improves the test accuracy by up to 10.4% compared to the square function.
  arXiv  Detail & Related papers  (2020-11-11T03:32:22Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Estimating Multiplicative Relations in Neural Networks [0.0]
  We will use properties of logarithmic functions to propose a pair of activation functions which can translate products into linear expression and learn using backpropagation. We will try to generalize this approach for some complex arithmetic functions and test the accuracy on a disjoint distribution with the training set.
  arXiv  Detail & Related papers  (2020-10-28T14:28:24Z)
• UNIPoint: Universally Approximating Point Processes Intensities [125.08205865536577]
  We provide a proof that a class of learnable functions can universally approximate any valid intensity function. We implement UNIPoint, a novel neural point process model, using recurrent neural networks to parameterise sums of basis function upon each event.
  arXiv  Detail & Related papers  (2020-07-28T09:31:56Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  Submodular functions have been studied extensively in machine learning and data mining. In this work, we propose a continuous DR-submodular extension for integer submodular functions. We formulate a new probabilistic model which is defined through integer submodular functions.
  arXiv  Detail & Related papers  (2020-06-01T22:20:45Z)

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.