論文の概要: Efficient Projection-Free Online Convex Optimization with Membership Oracle

• arxiv url: http://arxiv.org/abs/2111.05818v1
• Date: Wed, 10 Nov 2021 17:22:29 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-11 15:23:54.003085
• Title: Efficient Projection-Free Online Convex Optimization with Membership Oracle
• Title（参考訳）: メンバーシップオラクルによる効率的なプロジェクションフリーオンライン凸最適化
• Authors: Zakaria Mhammedi
• Abstract要約: ユークリッド球上で定義された任意のアルゴリズムAを、球に含まれる制約付き集合 C 上のアルゴリズムに変換する新しい還元法を提案する。 我々の削減には、O(T log T) を T ラウンド後に C 上で Oracle に呼び出しる必要があり、C 上の線形最適化は不要である。
• 参考スコア（独自算出の注目度）: 11.745866777357566
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In constrained convex optimization, existing methods based on the ellipsoid or cutting plane method do not scale well with the dimension of the ambient space. Alternative approaches such as Projected Gradient Descent only provide a computational benefit for simple convex sets such as Euclidean balls, where Euclidean projections can be performed efficiently. For other sets, the cost of the projections can be too high. To circumvent these issues, alternative methods based on the famous Frank-Wolfe algorithm have been studied and used. Such methods use a Linear Optimization Oracle at each iteration instead of Euclidean projections; the former can often be performed efficiently. Such methods have also been extended to the online and stochastic optimization settings. However, the Frank-Wolfe algorithm and its variants do not achieve the optimal performance, in terms of regret or rate, for general convex sets. What is more, the Linear Optimization Oracle they use can still be computationally expensive in some cases. In this paper, we move away from Frank-Wolfe style algorithms and present a new reduction that turns any algorithm A defined on a Euclidean ball (where projections are cheap) to an algorithm on a constrained set C contained within the ball, without sacrificing the performance of the original algorithm A by much. Our reduction requires O(T log T) calls to a Membership Oracle on C after T rounds, and no linear optimization on C is needed. Using our reduction, we recover optimal regret bounds [resp. rates], in terms of the number of iterations, in online [resp. stochastic] convex optimization. Our guarantees are also useful in the offline convex optimization setting when the dimension of the ambient space is large.
• Abstract（参考訳）: 制約付き凸最適化では、楕円体法や切断平面法に基づく既存の手法は周囲空間の次元とよく一致しない。 射影勾配 Descent のような別のアプローチはユークリッド球のような単純な凸集合に対してのみ計算上の利点を与え、ユークリッド射影を効率的に行うことができる。 他の集合の場合、投影のコストは高すぎる可能性がある。 これらの問題を回避すべく、有名なフランク・ウルフアルゴリズムに基づく代替手法が研究され、使用されている。 このようなメソッドはユークリッド射影の代わりに各イテレーションで線形最適化Oracleを使用し、前者は効率的に実行できる。 このような手法は、オンラインおよび確率最適化設定にも拡張されている。 しかし、フランク・ウルフアルゴリズムとその変種は、一般的な凸集合に対する後悔やレートの観点からは最適性能を達成できない。 さらに、彼らが使用しているLinear Optimization Oracleは、場合によっては計算コストも高い。 本稿では,frank-wolfe 型のアルゴリズムから離れ,ユークリッド球上の任意のアルゴリズム a を,元のアルゴリズム a の性能を犠牲にすることなく,球に含まれる制約付き集合 c 上のアルゴリズムに変換する新しい還元法を提案する。 我々の削減には、O(T log T) を T ラウンド後に C 上で Oracle に呼び出しる必要があり、C 上の線形最適化は不要である。 減算を用いて, オンライン凸最適化において, 繰り返し回数の観点から, 最適後悔境界(resp. rate)を回復する。 我々の保証は、環境空間の次元が大きい場合のオフライン凸最適化設定でも有用である。

関連論文リスト

• Accelerated First-Order Optimization under Nonlinear Constraints [97.16266088683061]
  制約付きFrankWolf-e-eに対して,高速化された1次アルゴリズムの新たなクラスを設計する。 これらのアルゴリズムの重要な性質は制約の数である。 我々は,非制約を効率的に扱えるとともに,最先端のパフォーマンスを$ellp1$で回復できることを示す。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
  ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。 GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。 我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
  論文  参考訳（メタデータ） (2022-11-22T23:53:06Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
  複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。 条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
  論文  参考訳（メタデータ） (2020-10-21T15:05:53Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)
• Faster Projection-free Online Learning [34.96927532439896]
  我々は、一般的なオンライン凸最適化に対してT2/3$の後悔を保証する効率的なプロジェクションフリーアルゴリズムを提案する。 提案手法はFollow-the-Perturbed-Leader法を用いて導出し,オンライン・プライマリ・デュアル・フレームワークを用いて解析する。
  論文  参考訳（メタデータ） (2020-01-30T21:18:39Z)

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

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