論文の概要: Faster Projection-free Online Learning

• arxiv url: http://arxiv.org/abs/2001.11568v2
• Date: Fri, 14 Feb 2020 17:36:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-05 12:03:35.810942
• Title: Faster Projection-free Online Learning
• Title（参考訳）: 高速なプロジェクションフリーオンライン学習
• Authors: Elad Hazan and Edgar Minasyan
• Abstract要約: 我々は、一般的なオンライン凸最適化に対してT2/3$の後悔を保証する効率的なプロジェクションフリーアルゴリズムを提案する。 提案手法はFollow-the-Perturbed-Leader法を用いて導出し,オンライン・プライマリ・デュアル・フレームワークを用いて解析する。
• 参考スコア（独自算出の注目度）: 34.96927532439896
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many online learning problems the computational bottleneck for gradient-based methods is the projection operation. For this reason, in many problems the most efficient algorithms are based on the Frank-Wolfe method, which replaces projections by linear optimization. In the general case, however, online projection-free methods require more iterations than projection-based methods: the best known regret bound scales as $T^{3/4}$. Despite significant work on various variants of the Frank-Wolfe method, this bound has remained unchanged for a decade. In this paper we give an efficient projection-free algorithm that guarantees $T^{2/3}$ regret for general online convex optimization with smooth cost functions and one linear optimization computation per iteration. As opposed to previous Frank-Wolfe approaches, our algorithm is derived using the Follow-the-Perturbed-Leader method and is analyzed using an online primal-dual framework.
• Abstract（参考訳）: 多くのオンライン学習問題において、勾配に基づく方法の計算ボトルネックは投影演算である。 このため、多くの問題において最も効率的なアルゴリズムは、射影を線形最適化によって置き換えるフランク=ウルフ法に基づいている。 しかし、一般的な場合、オンライン射影自由法は射影法よりも多くの反復を必要とする:最もよく知られた後悔境界スケールは$T^{3/4}$である。 フランク=ウルフ法の様々な変種に関する研究にもかかわらず、この境界は10年間変わっていない。 本稿では, オンライン凸最適化に$t^{2/3}$を保証し, 円滑なコスト関数と1イテレーション当たりの線形最適化計算を実現した, 効率的なプロジェクションフリーアルゴリズムを提案する。 従来のFrank-Wolfe手法とは対照的に,本アルゴリズムはFollow-the-Perturbed-Leader法を用いて導出され,オンラインプライマリ・デュアル・フレームワークを用いて解析される。

関連論文リスト

• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [79.39965431772626]
  Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。 有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
  論文  参考訳（メタデータ） (2023-04-23T20:05:09Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [56.92236659731376]
  本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。 決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
  論文  参考訳（メタデータ） (2023-02-07T22:09:20Z)
• Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
  ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。 GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。 我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
  論文  参考訳（メタデータ） (2022-11-22T23:53:06Z)
• Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization [1.4504054468850665]
  In Empirical Minimization -- Minimization -- We present a novel computer step-size approach to we have compute guarantees。 提案手法は実世界のバイナリデータセットに非常に重要な問題を示す。 また、計算の保証を得るための新しい適応的なステップサイズアプローチを提案する。
  論文  参考訳（メタデータ） (2022-08-30T00:08:37Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。 そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。 後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
  論文  参考訳（メタデータ） (2022-03-19T13:39:49Z)
• Efficient Projection-Free Online Convex Optimization with Membership Oracle [11.745866777357566]
  ユークリッド球上で定義された任意のアルゴリズムAを、球に含まれる制約付き集合 C 上のアルゴリズムに変換する新しい還元法を提案する。 我々の削減には、O(T log T) を T ラウンド後に C 上で Oracle に呼び出しる必要があり、C 上の線形最適化は不要である。
  論文  参考訳（メタデータ） (2021-11-10T17:22:29Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• Boosting for Online Convex Optimization [64.15578413206715]
  多数の専門家とオンライン凸最適化の意思決定フレームワークを検討します。 弱学習アルゴリズムは、基本クラスの専門家に対するおよその後悔を保証するメカニズムとして定義します。 ベースクラスの凸船体に対するほぼ最適の後悔を保証する効率的なブースティングアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-02-18T12:30:49Z)
• Complexity of Linear Minimization and Projection on Some Sets [33.53609344219565]
  Frank-Wolfeアルゴリズムは、プロジェクションではなく線形最小化に依存する制約付き最適化の手法である。 本稿では、最適化によく用いられる複数の集合上の両タスクの複雑性境界について検討する。
  論文  参考訳（メタデータ） (2021-01-25T12:14:34Z)
• Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
  複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。 条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
  論文  参考訳（メタデータ） (2020-10-21T15:05:53Z)

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

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