論文の概要: Decomposition Polyhedra of Piecewise Linear Functions

• arxiv url: http://arxiv.org/abs/2410.04907v1
• Date: Mon, 7 Oct 2024 10:48:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-02 01:27:55.619537
• Title: Decomposition Polyhedra of Piecewise Linear Functions
• Title（参考訳）: 線形関数の分解多面体
• Authors: Marie-Charlotte Brandenburg, Moritz Grillo, Christoph Hertrich,
• Abstract要約: 本稿では,連続ピースワイド線形関数(CPWL)を凸CPWL関数に分解する方法について,よく研究されている問題に寄与する。 すべての CPWL 関数は無限分解を持つが、差分 2 個の凸 CPWL 関数を持つ。 できるだけ少ない線形部分で分解を見つけるために、我々のフレームワークを適用します。
• 参考スコア（独自算出の注目度）: 4.594829845106234
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we contribute to the frequently studied question of how to decompose a continuous piecewise linear (CPWL) function into a difference of two convex CPWL functions. Every CPWL function has infinitely many such decompositions, but for applications in optimization and neural network theory, it is crucial to find decompositions with as few linear pieces as possible. This is a highly challenging problem, as we further demonstrate by disproving a recently proposed approach by Tran and Wang [Minimal representations of tropical rational functions. Algebraic Statistics, 15(1):27-59, 2024]. To make the problem more tractable, we propose to fix an underlying polyhedral complex determining the possible locus of nonlinearity. Under this assumption, we prove that the set of decompositions forms a polyhedron that arises as intersection of two translated cones. We prove that irreducible decompositions correspond to the bounded faces of this polyhedron and minimal solutions must be vertices. We then identify cases with a unique minimal decomposition, and illustrate how our insights have consequences in the theory of submodular functions. Finally, we improve upon previous constructions of neural networks for a given convex CPWL function and apply our framework to obtain results in the nonconvex case.
• Abstract（参考訳）: 本稿では,連続ピースワイド線形関数(CPWL)を2つの凸CPWL関数の差分に分解する方法について,よく研究されている問題に寄与する。 すべてのCPWL関数は無限に多くの分解を持つが、最適化やニューラルネットワーク理論の応用においては、できるだけ少数の線形部分で分解を見つけることが重要である。 これは、トランとワンによる最近提案されたアプローチ(熱帯有理関数の最小表現,代数統計学,15(1):27-59,2024)を否定することで、非常に難しい問題である。 問題をより難解にするために、非線形性の可能性の軌跡を決定する基礎となる多面体複体を固定することを提案する。 この仮定の下では、分解の集合が2つの翻訳された円錐の交叉として生じる多面体を形成することを証明している。 我々は、既約分解がこの多面体の有界面に対応することを証明し、最小解は頂点でなければならない。 次に、一意の最小分解を持つケースを特定し、劣モジュラ函数の理論において我々の洞察がどのように結果をもたらすかを説明する。 最後に、与えられた凸CPWL関数に対するニューラルネットワークの以前の構成を改善し、このフレームワークを適用して非凸の場合の結果を得る。

関連論文リスト

• The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank [0.6963971634605796]
  我々は、凸体上の関数を制約に最適化する問題に対して、外部近似の収束族を構築する。 階層の3段階の数値的な実装は、この問題に対して非常に厳密な近似をもたらすことが示されている。
  論文  参考訳（メタデータ） (2024-06-13T18:00:09Z)
• Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization [8.225819874406238]
  Mualem citemualem23re は、この手法がダウンクローズド制約と非ダウンクローズド制約の間を滑らかにできないことを示す。 本研究では,物体を2つの異なる凸体に自然分解した新しいオフラインおよびオンラインアルゴリズムを提案する。 また、3つのオフラインおよび2つのオンラインアプリケーションにまたがる提案アルゴリズムの優位性を実証的に示す。
  論文  参考訳（メタデータ） (2024-01-17T14:56:42Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  本研究では,2次損失を持つ1層多変量ReLUネットワークをトレーニングする際に,勾配勾配勾配が収束する解のタイプについて検討する。 我々は、浅いReLUネットワークが普遍近似器であるにもかかわらず、安定した浅層ネットワークは存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-06-30T09:17:39Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions [23.96475985648844]
  修正線形単位を用いたディープニューラルネットワークは、連続的ピースワイド線形関数(CPWL)を表す。 最近の研究では、任意のCPWL関数を正確に表すために必要なニューロンの数は、ピースの数と指数関数的に増加するか、あるいは異なる線形成分の数の因子として指数関数的に増加すると推定されている。 本稿では、より厳密な境界を提案し、任意のCPWL関数に対してこれらの境界を満たすネットワークを見つけるための時間アルゴリズムを確立する。
  論文  参考訳（メタデータ） (2022-10-13T17:58:41Z)
• Sparsest Univariate Learning Models Under Lipschitz Constraint [31.28451181040038]
  一次元回帰問題に対する連続領域定式化を提案する。 リプシッツ定数をユーザ定義上界を用いて明示的に制御する。 いずれの問題も、連続的かつ断片的線形なグローバル最小化を許容していることが示される。
  論文  参考訳（メタデータ） (2021-12-27T07:03:43Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。 このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
  論文  参考訳（メタデータ） (2021-05-08T11:43:49Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Ideal formulations for constrained convex optimization problems with indicator variables [2.578242050187029]
  本研究では,指標変数と指標に対する制約を用いた凸最適化問題のクラスを凸化することを検討した。 スパース回帰問題の凸化に関する従来の研究とは異なり、非線形非分離対象、指標変数、制約を同時に検討する。 階層性,多行性,空間性制約といった問題に対する理想的な凸化を導出する。
  論文  参考訳（メタデータ） (2020-06-30T21:07:10Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。 正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。 高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
  論文  参考訳（メタデータ） (2020-02-25T23:05:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。