Representing Piecewise-Linear Functions by Functions with Minimal Arity

• URL: http://arxiv.org/abs/2406.02421v1
• Date: Tue, 4 Jun 2024 15:39:08 GMT
• Title: Representing Piecewise-Linear Functions by Functions with Minimal Arity
• Authors: Christoph Koutschan, Anton Ponomarchuk, Josef Schicho,
• Abstract summary: We show that the tessellation of the input space $mathbbRn$ induced by the function $F$ has a direct connection to the number of arguments in the $max$ functions.
• Score: 0.5266869303483376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Any continuous piecewise-linear function $F\colon \mathbb{R}^{n}\to \mathbb{R}$ can be represented as a linear combination of $\max$ functions of at most $n+1$ affine-linear functions. In our previous paper [``Representing piecewise linear functions by functions with small arity'', AAECC, 2023], we showed that this upper bound of $n+1$ arguments is tight. In the present paper, we extend this result by establishing a correspondence between the function $F$ and the minimal number of arguments that are needed in any such decomposition. We show that the tessellation of the input space $\mathbb{R}^{n}$ induced by the function $F$ has a direct connection to the number of arguments in the $\max$ functions.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ under isotropic Gaussian data. We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ of arbitrary link function with a sample and runtime complexity of $n asymp T asymp C(q) cdot d
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• When does a bent concatenation not belong to the completed Maiorana-McFarland class? [47.2382573252527]
  When does a bent concatenation $f$ (not) belong to the completed Maiorana-McFarland class $mathcalM#$? We show how to specify bent functions outside $mathcalM#$.
  arXiv  Detail & Related papers  (2024-04-24T21:36:19Z)
• A Minimal Control Family of Dynamical Syetem for Universal Approximation [6.164223149261533]
  We show that a control family can generate flow maps that can approximate diffeomorphisms of $mathbbRd$ on any compact domain. Our result reveals an underlying connection between the approximation power of neural networks and control systems.
  arXiv  Detail & Related papers  (2023-12-20T10:36:55Z)
• Representing Piecewise Linear Functions by Functions with Small Arity [0.0]
  We show that for every piecewise linear function there exists a linear combination of $max$-functions with at most $n+1$ arguments. We also prove that the piecewise linear function $max(0, x_1, ldots, x_n)$ cannot be represented as a linear combination of maxima of less than $n+1$ affine-linear arguments.
  arXiv  Detail & Related papers  (2023-05-26T13:48:37Z)
• On minimal representations of shallow ReLU networks [0.0]
  We show that the minimal representation for $f$ uses either $n$, $n+1$ or $n+2$ neurons. In particular, where the input layer is one-dimensional, minimal representations always use at most $n+1$ neurons but in all higher dimensional settings there are functions for which $n+2$ neurons are needed.
  arXiv  Detail & Related papers  (2021-08-12T10:22:24Z)
• Submodular + Concave [53.208470310734825]
  It has been well established that first order optimization methods can converge to the maximal objective value of concave functions. In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$. This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
  arXiv  Detail & Related papers  (2021-06-09T01:59:55Z)
• Minimax Regret for Bandit Convex Optimisation of Ridge Functions [34.686687996497525]
  We analyse adversarial bandit convex optimisation with an adversary that is restricted to playing functions of the form $f(x) = g(langle x, thetarangle)$ for convex $g : mathbb R to mathbb R$ and $theta in mathbb Rd$. We provide a short information-theoretic proof that the minimax regret is at most $O(dsqrtn log(operatornamediammathcal K))$ where $n
  arXiv  Detail & Related papers  (2021-06-01T12:51:48Z)
• 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)
• Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev [31.57723436316983]
  One approach to sample from a high dimensional distribution matrix for some function is the Langevin Algorithm. Our work generalizes the results of [53] where $mathRn$ is defined on af$ rather than $bbRn$.
  arXiv  Detail & Related papers  (2020-10-11T15:02:12Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)

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.