論文の概要: Projection-free Online Learning over Strongly Convex Sets

• arxiv url: http://arxiv.org/abs/2010.08177v2
• Date: Mon, 24 Jun 2024 03:35:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-27 20:13:23.348137
• Title: Projection-free Online Learning over Strongly Convex Sets
• Title（参考訳）: 強凸集合によるプロジェクションフリーオンライン学習
• Authors: Yuanyu Wan, Lijun Zhang,
• Abstract要約: 我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。 一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
• 参考スコア（独自算出の注目度）: 24.517908972536432
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To efficiently solve online problems with complicated constraints, projection-free algorithms including online frank-wolfe (OFW) and its variants have received significant interest recently. However, in the general case, existing efficient projection-free algorithms only achieved the regret bound of $O(T^{3/4})$, which is worse than the regret of projection-based algorithms, where $T$ is the number of decision rounds. In this paper, we study the special case of online learning over strongly convex sets, for which we first prove that OFW can enjoy a better regret bound of $O(T^{2/3})$ for general convex losses. The key idea is to refine the decaying step-size in the original OFW by a simple line search rule. Furthermore, for strongly convex losses, we propose a strongly convex variant of OFW by redefining the surrogate loss function in OFW. We show that it achieves a regret bound of $O(T^{2/3})$ over general convex sets and a better regret bound of $O(\sqrt{T})$ over strongly convex sets.
• Abstract（参考訳）: 複雑な制約で効率的にオンライン問題を解くために、オンライン・フランクウルフ(OFW)とその変種を含むプロジェクションフリーのアルゴリズムが近年大きな関心を集めている。 しかし、一般的な場合、既存の効率的なプロジェクションフリーアルゴリズムは、$O(T^{3/4})$の後悔境界を達成しただけで、これはプロジェクションベースアルゴリズムの後悔よりも悪い。 本稿では,強い凸集合上でのオンライン学習の特別な場合について検討し,OWが一般凸損失に対して$O(T^{2/3})$$の後悔を享受できることを最初に証明する。 鍵となる考え方は、単純な行探索規則によって元のOFWにおける崩壊するステップサイズを洗練させることである。 さらに、強い凸損失に対して、OFWにおける代理損失関数を再定義することにより、OFWの強い凸変種を提案する。 一般凸集合上では$O(T^{2/3})$の後悔境界、強凸集合上では$O(\sqrt{T})$の後悔境界が得られることを示す。

関連論文リスト

• Universal Online Convex Optimization with $1$ Projection per Round [31.16522982351235]
  我々は,複数種類の凸関数に対して同時にミニマックスレートを得るユニバーサルアルゴリズムを開発した。 我々は、単純なドメイン上で定義された代理損失を用いて、1ドルのプロジェクションしか必要としない普遍的なOCOアルゴリズムを開発する。 我々の分析は、サロゲート損失に新たな光を当て、元の損失の後悔とサロゲート損失の相違点の厳密な検証を容易にする。
  論文  参考訳（メタデータ） (2024-05-30T05:29:40Z)
• Second Order Methods for Bandit Optimization and Control [34.51425758864638]
  我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。 また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
  論文  参考訳（メタデータ） (2024-02-14T04:03:38Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime [74.52487417350221]
  オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。 そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-27T21:19:24Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
  ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。 GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。 我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
  論文  参考訳（メタデータ） (2022-11-22T23:53:06Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Projection-free Distributed Online Learning with Strongly Convex Losses [37.08975118221237]
  損失関数の強い凸性を利用して、後悔と通信の複雑さを改善する。 本アルゴリズムは多対数因子に縛られた$o(t2/3log t)$ regretを得るのにほぼ最適である。
  論文  参考訳（メタデータ） (2021-03-20T05:38:51Z)
• Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
  我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。 離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
  論文  参考訳（メタデータ） (2021-02-07T14:47:19Z)
• Online Learning with Imperfect Hints [72.4277628722419]
  オンライン学習において,不完全な方向ヒントを用いたアルゴリズムを開発し,ほぼ一致している。 我々のアルゴリズムはヒントの品質を損なうものであり、後悔の限界は常に相関するヒントの場合と隠れない場合とを補間する。
  論文  参考訳（メタデータ） (2020-02-11T23:06:09Z)

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

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