Representing Piecewise Linear Functions by Functions with Small Arity

• URL: http://arxiv.org/abs/2305.16933v1
• Date: Fri, 26 May 2023 13:48:37 GMT
• Title: Representing Piecewise Linear Functions by Functions with Small Arity
• Authors: Christoph Koutschan, Bernhard Moser, Anton Ponomarchuk, Josef Schicho
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A piecewise linear function can be described in different forms: as an arbitrarily nested expression of $\min$- and $\max$-functions, as a difference of two convex piecewise linear functions, or as a linear combination of maxima of affine-linear functions. In this paper, we provide two main results: first, we show that for every piecewise linear function there exists a linear combination of $\max$-functions with at most $n+1$ arguments, and give an algorithm for its computation. Moreover, these arguments are contained in the finite set of affine-linear functions that coincide with the given function in some open set. Second, we 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. This was conjectured by Wang and Sun in 2005 in a paper on representations of piecewise linear functions as linear combination of maxima.

Related papers

• Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach [4.895675355301809]
  We study the convex-concave bilinear saddle-point problem $min_x max_y f(x) + ytop Ax - g(y)$, where both, only one, or none of the functions $f$ and $g$ are strongly convex. The solution of this problem is at the core of many machine learning tasks.
  arXiv  Detail & Related papers  (2024-10-18T16:43:10Z)
• Constructions of Efficiently Implementable Boolean functions Possessing High Nonlinearity and Good Resistance to Algebraic Attacks [28.8640336189986]
  We describe two new classes of functions which provide the best known trade-offs between low computational complexity, nonlinearity and (fast) algebraic immunity. Appropriately chosen functions from the two new classes provide excellent solutions to the problem of designing filtering functions for use in the nonlinear filter model of stream ciphers.
  arXiv  Detail & Related papers  (2024-08-21T12:46:50Z)
• Representing Piecewise-Linear Functions by Functions with Minimal Arity [0.5266869303483376]
  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.
  arXiv  Detail & Related papers  (2024-06-04T15:39:08Z)
• 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)
• Combinatory Adjoints and Differentiation [0.0]
  We develop a compositional approach for automatic and symbolic differentiation based on categorical constructions in functional analysis. We show that both symbolic and automatic differentiation can be performed using a differential calculus for generating linear functions. We also provide a calculus for symbolically computing the adjoint of a derivative without using matrices.
  arXiv  Detail & Related papers  (2022-07-02T14:34:54Z)
• Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
  We study a linear convex-concave saddle-point problem $min_xmax_y f(x) ytopmathbfA x - g(y)
  arXiv  Detail & Related papers  (2021-12-30T20:31:46Z)
• 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)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  We study the reinforcement learning for finite-horizon episodic Markov decision processes with adversarial reward and full information feedback. We show that it can achieve $tildeO(dHsqrtT)$ regret, where $H$ is the length of the episode. We also prove a matching lower bound of $tildeOmega(dHsqrtT)$ up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-02-17T18:54:08Z)
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [95.80683238546499]
  We propose a new algorithm UCRL2-VTR, which can be seen as an extension of the UCRL2 algorithm with linear function approximation. We show that UCRL2-VTR with Bernstein-type bonus can achieve a regret of $tildeO(dsqrtDT)$, where $d$ is the dimension of the feature mapping. We also prove a matching lower bound $tildeOmega(dsqrtDT)$, which suggests that the proposed UCRL2-VTR is minimax optimal up to logarithmic factors
  arXiv  Detail & Related papers  (2021-02-15T02:08:39Z)
• Piecewise Linear Regression via a Difference of Convex Functions [50.89452535187813]
  We present a new piecewise linear regression methodology that utilizes fitting a difference of convex functions (DC functions) to the data. We empirically validate the method, showing it to be practically implementable, and to have comparable performance to existing regression/classification methods on real-world datasets.
  arXiv  Detail & Related papers  (2020-07-05T18:58:47Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)

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.