論文の概要: On Approximate Computation of Critical Points

• arxiv url: http://arxiv.org/abs/2601.21917v1
• Date: Thu, 29 Jan 2026 16:08:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-30 16:22:49.974656
• Title: On Approximate Computation of Critical Points
• Title（参考訳）: 臨界点の近似計算について
• Authors: Amir Ali Ahmadi, Georgina Hall,
• Abstract要約: 臨界点の非常に近似的な計算は、非時間関数の難解な単純なクラスであることを示す。 また,臨界点の存在が保証されるような構造的条件下での臨界点の近似も証明する。
• 参考スコア（独自算出の注目度）: 0.6015898117103068
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a polynomial-time algorithm that takes as input a polynomial in $n$ variables of constant degree (as low as three) and outputs a point whose gradient has Euclidean norm at most $2^n$ whenever the polynomial has a critical point, then P=NP. The algorithm is permitted to return an arbitrary point when no critical point exists. We also prove hardness results for approximate computation of critical points under additional structural assumptions, including settings in which existence and uniqueness of a critical point are guaranteed, the function is lower bounded, and approximation is measured in terms of distance to a critical point. Overall, our results stand in contrast to the commonly-held belief that, in nonconvex optimization, approximate computation of critical points is a tractable task.
• Abstract（参考訳）: 非凸関数の単純なクラスに対して、臨界点の非常に粗い近似が導出可能であることを示す。 より具体的には、もし多項式時アルゴリズムが定数次数$n$変数の入力として (3 に対して低い) あり、多項式が臨界点を持つたびに、勾配がユークリッドノルムが 2^n$ であるような点を出力するなら、P=NP である。 このアルゴリズムは臨界点が存在しない場合には任意の点を返すことができる。 また, 臨界点の存在と特異性が保証され, 関数の境界が低く, 臨界点までの距離で近似が測定されるような設定を含む, 付加的な構造仮定の下で臨界点の近似計算の硬度結果も証明する。 全体として、我々の結果は、非凸最適化において臨界点の近似計算は難解な作業である、という一般的な信念とは対照的である。

関連論文リスト

• Approximating Fixpoints of Approximated Functions [0.31457219084519]
  正確には知られていないが、それらに収束する近似関数列で表される関数の最小固定点を近似する方法を示す。 この結果は,確率的誤差境界で関心関数を近似できるシステムに対して,最小の固定点にほぼ確実に反復することができる。
  論文  参考訳（メタデータ） (2025-01-15T16:52:21Z)
• Mathematical Programming Algorithms for Convex Hull Approximation with a Hyperplane Budget [0.0]
  我々は、すべての正の点と負の点を含む、ほとんどのK面を持つ凸多面体を探索する。 この問題は純粋凸多面体近似の文献で知られている。 私たちの関心は、制約学習の応用の可能性に起因しています。
  論文  参考訳（メタデータ） (2024-07-24T15:08:52Z)
• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
  論文  参考訳（メタデータ） (2023-10-13T14:52:46Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Deep Point-to-Plane Registration by Efficient Backpropagation for Error Minimizing Function [0.0]
  点集合登録の伝統的なアルゴリズムは、点から点までの距離を最小化するアルゴリズムよりも、剛性変換をより正確に推定する。 近年の深層学習に基づく手法はポイント・ツー・ポイント距離を最小化している。 本論文は,平面間登録における深層学習に基づく最初のアプローチを提案する。
  論文  参考訳（メタデータ） (2022-07-14T05:18:20Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Social Distancing is Good for Points too! [91.3755431537592]
  点が近すぎるとFCNNの動作が悪くなることを示す。 そして、そのようなケースを避けるためにアルゴリズムの修正に成功した。 この修正はアルゴリズムの近似保証とともに有用な上界を証明するのに十分である。
  論文  参考訳（メタデータ） (2020-06-28T16:49:59Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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