論文の概要: Efficient Projection-Free Algorithms for Saddle Point Problems

• arxiv url: http://arxiv.org/abs/2010.11737v1
• Date: Wed, 21 Oct 2020 15:05:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-05 01:03:33.106643
• Title: Efficient Projection-Free Algorithms for Saddle Point Problems
• Title（参考訳）: サドルポイント問題に対する効率的な投影フリーアルゴリズム
• Authors: Cheng Chen, Luo Luo, Weinan Zhang, Yong Yu
• Abstract要約: 複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。 条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
• 参考スコア（独自算出の注目度）: 39.88460595129901
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Frank-Wolfe algorithm is a classic method for constrained optimization problems. It has recently been popular in many machine learning applications because its projection-free property leads to more efficient iterations. In this paper, we study projection-free algorithms for convex-strongly-concave saddle point problems with complicated constraints. Our method combines Conditional Gradient Sliding with Mirror-Prox and shows that it only requires $\tilde{O}(1/\sqrt{\epsilon})$ gradient evaluations and $\tilde{O}(1/\epsilon^2)$ linear optimizations in the batch setting. We also extend our method to the stochastic setting and propose first stochastic projection-free algorithms for saddle point problems. Experimental results demonstrate the effectiveness of our algorithms and verify our theoretical guarantees.
• Abstract（参考訳）: フランク=ウルフアルゴリズムは制約付き最適化問題の古典的な方法である。 最近、プロジェクションのない性質がより効率的なイテレーションをもたらすため、多くの機械学習アプリケーションで人気がある。 本稿では,複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。 条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$\tilde{O}(1/\sqrt{\epsilon})$勾配評価と$\tilde{O}(1/\epsilon^2)$線形最適化しか必要としないことを示す。 また,本手法を確率的設定にまで拡張し,サドル点問題に対する確率的プロジェクションフリーアルゴリズムを提案する。 実験により,アルゴリズムの有効性を実証し,理論的保証を検証する。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
  論文  参考訳（メタデータ） (2023-11-18T23:06:33Z)
• Projection-Free Online Convex Optimization via Efficient Newton Iterations [10.492474737007722]
  本稿では、凸領域$mathcalKサブセットmathbbRd$に対するオンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-19T18:48:53Z)
• Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
  ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。 GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。 我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
  論文  参考訳（メタデータ） (2022-11-22T23:53:06Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Towards an efficient approach for the nonconvex $\ell_p$ ball projection: algorithm and analysis [3.4693390973571594]
  本稿では, ベクトルのユークリッド射影を $pin(0,1)$ の $ell_p$ 球上に計算することに着目した。 我々は、再重み付けされた $ell_1$-ball 上の射影列を解いて定常点を計算する新しい数値的手法を開発した。 提案手法は穏やかな条件下で一意に収束し,最悪の場合$o(1/sqrtk)$収束率を持つ。
  論文  参考訳（メタデータ） (2021-01-05T04:51:12Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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