論文の概要: A Parameter-free Algorithm for Convex-concave Min-max Problems

• arxiv url: http://arxiv.org/abs/2103.00284v1
• Date: Sat, 27 Feb 2021 18:10:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-03 15:58:14.751336
• Title: A Parameter-free Algorithm for Convex-concave Min-max Problems
• Title（参考訳）: 凸凹最小問題に対するパラメータフリーアルゴリズム
• Authors: Mingrui Liu, Francesco Orabona
• Abstract要約: 洞窟なし最適化アルゴリズムは、学習速度を調整せずに初期点に対して収束率が最適であるアルゴリズムを指す。 副産物として,パラメータフリーなアルゴリズムを用いて,成長条件付きmin-max問題の高速速度を求める新しいアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 33.39558541452866
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Parameter-free optimization algorithms refer to algorithms whose convergence rate is optimal with respect to the initial point without any learning rate to tune. They are proposed and well-studied in the online convex optimization literature. However, all the existing parameter-free algorithms can only be used for convex minimization problems. It remains unclear how to design a parameter-free algorithm for convex-concave min-max problems. In fact, the best known convergence rates of the algorithms for solving these problems depend on the size of the domain, rather than on the distance between initial point and the optimal solution. In this paper, we provide the first parameter-free algorithm for several classes of convex-concave problems and establish corresponding state-of-the-art convergence rates, including strictly-convex-strictly-concave min-max problems and min-max problems with non-Euclidean geometry. As a by-product, we utilize the parameter-free algorithm as a subroutine to design a new algorithm, which obtains fast rates for min-max problems with a growth condition. Extensive experiments are conducted to verify our theoretical findings and demonstrate the effectiveness of the proposed algorithm.
• Abstract（参考訳）: パラメータフリー最適化アルゴリズムは、学習率を調整せずに初期点に対して収束率が最適であるアルゴリズムを指す。 オンライン凸最適化の文献において提案され、よく研究されている。 しかし、すべての既存のパラメータフリーアルゴリズムは凸最小化問題にのみ使用できる。 凸凹最大問題に対するパラメータフリーアルゴリズムの設計法は未だに不明である。 実際、これらの問題を解決するアルゴリズムの最もよく知られた収束率は、初期点と最適解の間の距離ではなく、領域の大きさに依存する。 本稿では,複数の凸凹問題に対して最初のパラメータフリーなアルゴリズムを提供し,厳密な凸凹問題と非ユークリッド幾何学によるmin-max問題を含む,最先端の収束率を確立する。 副産物として,パラメータフリーのアルゴリズムをサブルーチンとして利用して,成長条件付きmin-max問題に対する高速速度を求める新しいアルゴリズムを設計する。 理論的な知見を検証し,提案アルゴリズムの有効性を実証するために,広範な実験を行う。

関連論文リスト

• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• A proximal-proximal majorization-minimization algorithm for nonconvex tuning-free robust regression problems [4.261680642170457]
  非回帰問題に対する PMM (proximal-proximal majorization-minimization) アルゴリズムを提案する。 提案アルゴリズムは既存の最先端アルゴリズムよりも優れている。
  論文  参考訳（メタデータ） (2021-06-25T15:07:13Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Approximation Algorithms for Sparse Best Rank-1 Approximation to Higher-Order Tensors [1.827510863075184]
  スパーステンソル最高ランク1近似(英: Sparse tensor best rank-1 approximation, BR1Approx)は、密度テンソルBR1Approxの空間一般化である。 低計算量で容易に実装できる4つの近似アルゴリズムが提案されている。 提案手法の有効性を示すために,合成および実データに関する数値実験を行った。
  論文  参考訳（メタデータ） (2020-12-05T18:13:14Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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