論文の概要: Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses

• arxiv url: http://arxiv.org/abs/2605.10219v1
• Date: Mon, 11 May 2026 08:59:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.672618
• Title: Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses
• Title（参考訳）: ピスワイズアフィン関数と浅部CNN損失に対する定常試験のパラメータ化複雑性
• Authors: Yuhan Ye,
• Abstract要約: 本研究は, 連続片方向アフィン関数の所定点における近似一階定常性試験のパラメータ化複雑性について検討する。 Tian と So による最近の研究は、PA 関数に対する近似定常性の概念のテストは、最悪の場合、計算的に難解であることを示している。 我々は、トレーニング可能な重量空間で定常性試験を行い、難易度をReLU CNN訓練損失の浅い家族に拡張する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the parameterized complexity of testing approximate first-order stationarity at a prescribed point for continuous piecewise-affine (PA) functions, a basic task in nonsmooth optimization. PA functions form a canonical model for nonsmooth stationarity testing and capture the local polyhedral geometry that appears in ReLU-type training losses. Recent work by Tian and So (SODA 2025) shows that testing approximate stationarity notions for PA functions is computationally intractable in the worst case, and identifies fixed-dimensional tractability as an open direction. We address this direction from the viewpoint of parameterized complexity, with the ambient dimension $d$ as the parameter. In this paper, we give XP algorithms in fixed dimension for the tractable sides, and prove W[1]-hardness for the complementary sides. Moreover, lower bounds under the Exponential Time Hypothesis rule out algorithms running in time $ρ(d)\size^{o(d)}$ for any computable function $ρ$, where $\size$ denotes the total binary encoding length of the stationarity-testing instance. As a further consequence, our results yield the corresponding parameterized complexity picture for testing local minimality of continuous PA functions. We further extend our hardness results to a family of shallow ReLU CNN training losses, with stationarity tested in the trainable weight space. Thus, the same parameterized-complexity picture also appears for simple CNN training losses.
• Abstract（参考訳）: 非滑らかな最適化における基本課題である連続ピースワイズアフィン関数(PA)の所定点における近似一階定常性試験のパラメータ化複雑性について検討した。 PA関数は、ReLU型トレーニング損失に現れる局所多面体形状を捉え、非滑らかな定常試験のための標準モデルを形成する。 Tian and So (SODA 2025) による最近の研究は、PA関数に対する近似定常性の概念のテストは、最悪の場合、計算可能であり、固定次元のトラクタビリティをオープンな方向として識別することを示している。 パラメータ化複雑性の観点から、周辺次元をパラメータとして$d$とすることで、この方向性に対処する。 本稿では, トラクタブル側に対して, XP アルゴリズムを固定次元で与え, 相補側に対して W[1] 硬さを証明した。 さらに、指数時間仮説の下限は、任意の計算可能な関数に対して$ρ(d)\size^{o(d)}$で実行されるアルゴリズムを規定する。 その結果,連続的なPA関数の局所最小性をテストするためのパラメータ化複雑性図が得られた。 我々はさらに、トレーニング可能な重量空間で定常性試験を行い、より浅いReLU CNN訓練損失の家族に、我々の硬度結果をさらに拡張する。 このように、パラメータ化・複雑度図は単純なCNNトレーニングの損失にも現れる。

関連論文リスト

• A parametric algorithm is optimal for non-parametric regression of smooth functions [44.32603181895527]
  PADUAは、この設定に最適なサンプル複雑性を持つ最初のパラメトリックアルゴリズムである。 PADUAは最先端の手法に匹敵する性能を示すが,計算時間はごくわずかである。
  論文  参考訳（メタデータ） (2024-12-19T11:22:52Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。 i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。 その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
  論文  参考訳（メタデータ） (2024-04-18T16:46:08Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
  コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近複雑性を導出する。 数値実験では, 既存の再起動バージョンよりも改善が見られた。
  論文  参考訳（メタデータ） (2021-08-10T07:15:07Z)
• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality [8.940054309023525]
  トレーニングデータの寸法$d$が計算の複雑さに与える影響を分析します。 既知のブルートフォース戦略が本質的に最適であることを示す。 特に、一定の$d$ と凸損失関数に対する既知の時間アルゴリズムを、より一般的な損失関数のクラスに拡張する。
  論文  参考訳（メタデータ） (2021-05-18T17:05:26Z)

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

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