Fugu-MT 論文翻訳(概要): The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS

論文の概要: The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS

arxiv url: http://arxiv.org/abs/2011.01929v3
Date: Tue, 13 Apr 2021 14:51:12 GMT
ステータス: 処理完了
システム内更新日: 2022-09-30 06:28:52.428552
Title: The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS
Title（参考訳）: 勾配降下の複雑さ:cls = ppad $\cap$ pls
Authors: John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani
Abstract要約: 本研究では,有界凸多面体領域上でグラディエントDescentを実行することで解くことができる探索問題について検討する。このクラスは、PPAD と PLS の2つのよく知られたクラスの交叉に等しいことを示す。
参考スコア（独自算出の注目度）: 68.419966284392
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain and show that this class is equal to the intersection of two well-known classes: PPAD and PLS. As our main underlying technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a continuously differentiable function over the domain $[0,1]^2$ is PPAD $\cap$ PLS-complete. This is the first natural problem to be shown complete for this class. Our results also imply that the class CLS (Continuous Local Search) - which was defined by Daskalakis and Papadimitriou as a more "natural" counterpart to PPAD $\cap$ PLS and contains many interesting problems - is itself equal to PPAD $\cap$ PLS.
Abstract（参考訳）: 有界凸多面体領域上で勾配降下を行うことで解くことができる探索問題を考察し、このクラスが2つのよく知られたクラス ppad と pls の交叉と等しいことを示した。主な技術的貢献として、KKT(Karush-Kuhn-Tucker)ポイントの計算がドメイン上で連続的に微分可能な関数であることを示す[0,1]^2$ is PPAD $\cap$ PLS-complete。これはこのクラスで完結した最初の自然問題である。我々の結果は、ダスカラキスとパパディミトリオによって定義されたクラス CLS (Continuous Local Search) が、PPAD $\cap$ PLSとより"自然な"ものと定義され、多くの興味深い問題を含んでいることを示唆している。

関連論文リスト

Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions [41.43895948769255]
非滑らかな非漸近公正問題のクラスを$min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$の形で示す。本稿では,これらの問題を解く最初の方法であるエンベロープ近似勾配SMAGを提案する。
論文参考訳（メタデータ） (2024-05-28T20:52:46Z)
On the complexity of PAC learning in Hilbert spaces [0.0]
ヒルベルト空間における凸多面体学習の観点から二項分類の問題を考察する。本稿では,分布の少なくとも1-varepsilon$を正しく分類する多面体学習アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-03-03T16:16:11Z)
Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文参考訳（メタデータ） (2023-02-13T22:51:07Z)
Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文参考訳（メタデータ） (2022-05-30T14:28:02Z)
Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
線形関数近似を用いた強化学習における最短経路 (SSP) 問題について検討し, 遷移カーネルを未知モデルの線形混合として表現する。本稿では,線形混合SSPを学習するための新しいアルゴリズムを提案し,このアルゴリズムにより,$tilde O(d B_star1.5sqrtK/c_min)$ regretを実現する。
論文参考訳（メタデータ） (2021-10-25T08:34:00Z)
On Agnostic PAC Learning using $\mathcal{L}_2$-polynomial Regression and Fourier-based Algorithms [10.66048003460524]
構造的性質を持つPAC学習問題を解析するためのプロキシとしてヒルベルト空間を用いたフレームワークを開発する。 0-1の損失を持つPAC学習はヒルベルト空間領域における最適化と同値であることを示す。
論文参考訳（メタデータ） (2021-02-11T21:28:55Z)
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文参考訳（メタデータ） (2020-12-14T18:14:08Z)
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文参考訳（メタデータ） (2020-06-22T17:53:54Z)

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

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