論文の概要: 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)を回復する。 我々の保証は、環境空間の次元が大きい場合のオフライン凸最適化設定でも有用である。

関連論文リスト

• Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
  我々は sPlicing itEration (SCOPE) を用いたスペーサリティ制約最適化アルゴリズムを開発した。 SCOPEはパラメータをチューニングせずに効率的に収束する。 SCOPEを用いて2次最適化を解き、スパース分類器を学習し、バイナリ変数のスパースマルコフネットワークを復元する。 C++実装に基づいたオープンソースのPythonパッケージskscopeがGitHubで公開されている。
  論文  参考訳（メタデータ） (2024-06-17T18:34:51Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
  論文  参考訳（メタデータ） (2023-11-18T23:06:33Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Projection-Free Online Convex Optimization via Efficient Newton Iterations [10.492474737007722]
  本稿では、凸領域$mathcalKサブセットmathbbRd$に対するオンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-19T18:48:53Z)
• Riemannian Projection-free Online Learning [5.918057694291832]
  プロジェクション操作は、オンライン勾配降下(OGD)のような最適化アルゴリズムにおける重要な要素である。 これは高次元の設定における計算上の制限や、不条件の制約セットを扱う際に悩まされる。 本稿では,曲面空間上でのオンライン測地線凸最適化において,線形後悔の保証を得る手法を提案する。
  論文  参考訳（メタデータ） (2023-05-30T18:22:09Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• 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)
• 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)

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

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