論文の概要: Representing Piecewise Linear Functions by Functions with Small Arity
- arxiv url: http://arxiv.org/abs/2305.16933v1
- Date: Fri, 26 May 2023 13:48:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-29 14:46:44.881850
- Title: Representing Piecewise Linear Functions by Functions with Small Arity
- Title（参考訳）: アーリティーが小さい関数による区分線形関数の表現
- Authors: Christoph Koutschan, Bernhard Moser, Anton Ponomarchuk, Josef Schicho
- Abstract要約: すべてのピースワイズ線型函数に対して、少なくとも$n+1$引数を持つ$max$-函数の線型結合が存在することを示す。
また、ピースワイズ線型関数 $max(0, x_1, ldots, x_n)$ が、$n+1$ Affine-linear arguments 以下の最大値の線型結合として表現できないことも証明した。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: ピースワイズ線型函数は異なる形式で記述できる:$\min$- と$\max$-函数の任意の入れ子式として、2つの凸なピースワイズ線型函数の差として、またはアフィン線型関数の最大和の線型結合として。
本稿では、まず、各ピースワイド線型関数に対して、少なくとも$n+1$の引数を持つ$\max$-functionsの線形結合が存在し、その計算にアルゴリズムを与えることを示す。
さらに、これらの引数は、ある開集合における与えられた函数と一致するアフィン線型函数の有限集合に含まれる。
第二に、区分線型函数 $\max(0, x_{1}, \ldots, x_{n})$ は、最大値が $n+1$ アフィン線形引数の線形結合として表現できないことを証明する。
これは2005年にwang と sun によって、極大の線型結合としての区分線型関数の表現に関する論文で予想された。
関連論文リスト
- Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach [4.895675355301809]
凸凹型双線型サドル点問題 $min_x max_y f(x) + ytop Ax - g(y)$ について検討する。
この問題の解決策は多くの機械学習タスクの中核にある。
論文 参考訳（メタデータ） (2024-10-18T16:43:10Z) - Constructions of Efficiently Implementable Boolean functions Possessing High Nonlinearity and Good Resistance to Algebraic Attacks [28.8640336189986]
低計算複雑性、非線形性および(高速)代数免疫の間の最もよく知られたトレードオフを提供する関数の2つの新しいクラスを記述する。
2つの新しいクラスから適切に選択された関数は、ストリーム暗号の非線形フィルタモデルで使用されるフィルタ関数を設計する問題に対する優れた解を提供する。
論文 参考訳（メタデータ） (2024-08-21T12:46:50Z) - Representing Piecewise-Linear Functions by Functions with Minimal Arity [0.5266869303483376]
入力空間 $mathbbRn$ の関数 $F$ によるテッセルレーションは、$max$ 関数の引数の数に直結することを示す。
論文 参考訳（メタデータ） (2024-06-04T15:39:08Z) - A Minimal Control Family of Dynamical Syetem for Universal Approximation [6.164223149261533]
制御族は任意のコンパクト領域上で$mathbbRd$の微分同相を近似できるフロー写像を生成することができることを示す。
この結果から,ニューラルネットワークと制御系の近似パワーの基盤となる関係が明らかとなった。
論文 参考訳（メタデータ） (2023-12-20T10:36:55Z) - Combinatory Adjoints and Differentiation [0.0]
機能解析におけるカテゴリー構造に基づく自動的および記号的微分のための構成的アプローチを開発する。
本稿では,線形関数を生成する微分計算を用いて,記号的および自動微分が可能であることを示す。
また、行列を使わずに微分の随伴を記号的に計算する計算も提供する。
論文 参考訳（メタデータ） (2022-07-02T14:34:54Z) - Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave
Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
論文 参考訳（メタデータ） (2021-12-30T20:31:46Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Nearly Minimax Optimal Regret for Learning Infinite-horizon
Average-reward MDPs with Linear Function Approximation [95.80683238546499]
本論文では, 線形関数近似を用いた UCRL2 アルゴリズムの拡張として見ることのできる新しいアルゴリズム UCRL2-VTR を提案する。
Bernstein 型ボーナス付き UCRL2-VTR は $tildeO(dsqrtDT)$ の後悔を達成でき、$d$ は特徴写像の次元である。
また、一致した下界$tildeOmega(dsqrtDT)$を証明し、提案したUCRL2-VTRが対数係数の最小値であることを示す。
論文 参考訳（メタデータ） (2021-02-15T02:08:39Z) - Piecewise Linear Regression via a Difference of Convex Functions [50.89452535187813]
本稿では,データに対する凸関数(DC関数)の差を利用した線形回帰手法を提案する。
実際に実装可能であることを示すとともに,実世界のデータセット上で既存の回帰/分類手法に匹敵する性能を有することを実証的に検証した。
論文 参考訳（メタデータ） (2020-07-05T18:58:47Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。