論文の概要: Projection-free Adaptive Regret with Membership Oracles

• arxiv url: http://arxiv.org/abs/2211.12638v1
• Date: Tue, 22 Nov 2022 23:53:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-24 14:48:10.075084
• Title: Projection-free Adaptive Regret with Membership Oracles
• Title（参考訳）: 会員Oracleによるプロジェクションフリー適応レギュレーション
• Authors: Zhou Lu, Nataly Brukhim, Paula Gradu, Elad Hazan
• Abstract要約: ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。 GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。 我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
• 参考スコア（独自算出の注目度）: 31.422532403048738
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the framework of online convex optimization, most iterative algorithms require the computation of projections onto convex sets, which can be computationally expensive. To tackle this problem HK12 proposed the study of projection-free methods that replace projections with less expensive computations. The most common approach is based on the Frank-Wolfe method, that uses linear optimization computation in lieu of projections. Recent work by GK22 gave sublinear adaptive regret guarantees with projection free algorithms based on the Frank Wolfe approach. In this work we give projection-free algorithms that are based on a different technique, inspired by Mhammedi22, that replaces projections by set-membership computations. We propose a simple lazy gradient-based algorithm with a Minkowski regularization that attains near-optimal adaptive regret bounds. For general convex loss functions we improve previous adaptive regret bounds from $O(T^{3/4})$ to $O(\sqrt{T})$, and further to tight interval dependent bound $\tilde{O}(\sqrt{I})$ where $I$ denotes the interval length. For strongly convex functions we obtain the first poly-logarithmic adaptive regret bounds using a projection-free algorithm.
• Abstract（参考訳）: オンライン凸最適化の枠組みでは、ほとんどの反復アルゴリズムは凸集合上の射影の計算を必要とし、計算コストがかかる。 この問題に対処するため、HK12はプロジェクションをより安価な計算に置き換えるプロジェクションフリー手法の研究を提案した。 最も一般的なアプローチは、投影の代わりに線形最適化計算を使用するfrank-wolfe法に基づいている。 GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。 この研究では、mhammedi22にインスパイアされた別の手法に基づく投影自由アルゴリズムを、集合メンバー計算に置き換える。 我々はミンコフスキー正則化を用いた単純な遅延勾配に基づくアルゴリズムを提案する。 一般凸損失関数に対しては、以前の適応的後悔の限度を、$o(t^{3/4})$から$o(\sqrt{t})$に改善し、さらに、厳密な間隔依存境界 $\tilde{o}(\sqrt{i})$ ここで$i$は区間長を表す。 強凸関数に対しては、プロジェクションフリーアルゴリズムを用いて、最初の多対数適応的後悔境界を求める。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
  論文  参考訳（メタデータ） (2023-11-18T23:06:33Z)
• Improved Projection-free Online Continuous Submodular Maximization [35.324719857218014]
  単調かつ連続DR-サブモジュラー報酬関数を用いたオンライン学習の問題点について検討する。 従来の研究では、$O(T)$グラデーション評価を用いたMono-Frank-Wolfe (Mono-FW)と呼ばれる効率的なプロジェクションフリーアルゴリズムが提案されている。 同じ計算量を維持しつつ, 後悔を$O(T3/4)$に抑える改良されたプロジェクションフリーアルゴリズム(POBGA)を提案する。
  論文  参考訳（メタデータ） (2023-05-29T02:54:31Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes [7.734726150561089]
  離散的視点と連続的な視点の両方を用いて投影の計算を高速化するツールキットを開発した。 基数に基づく部分モジュラーポリトープの特別の場合、あるブレグマン射影の計算ランタイムを$Omega(n/log(n))$の係数で改善する。
  論文  参考訳（メタデータ） (2021-06-22T17:29:24Z)
• Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
  複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。 条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
  論文  参考訳（メタデータ） (2020-10-21T15:05:53Z)
• 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)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Faster Projection-free Online Learning [34.96927532439896]
  我々は、一般的なオンライン凸最適化に対してT2/3$の後悔を保証する効率的なプロジェクションフリーアルゴリズムを提案する。 提案手法はFollow-the-Perturbed-Leader法を用いて導出し,オンライン・プライマリ・デュアル・フレームワークを用いて解析する。
  論文  参考訳（メタデータ） (2020-01-30T21:18:39Z)

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

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