論文の概要: On Riemannian Projection-free Online Learning
- arxiv url: http://arxiv.org/abs/2305.19349v1
- Date: Tue, 30 May 2023 18:22:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 19:56:00.790620
- Title: On Riemannian Projection-free Online Learning
- Title（参考訳）: Riemannian Projection-free Online Learningについて
- Authors: Zihao Hu, Guanghui Wang and Jacob Abernethy
- Abstract要約: プロジェクション操作は、オンライン勾配降下(OGD)のような最適化アルゴリズムにおける重要な要素である。
これは高次元の設定における計算上の制限や、不条件の制約セットを扱う際に悩まされる。
本稿では, 曲面領域上での空間的凸最適化において, 線形後悔の保証を得る手法を提案する。
- 参考スコア（独自算出の注目度）: 20.353993251916982
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The projection operation is a critical component in a wide range of
optimization algorithms, such as online gradient descent (OGD), for enforcing
constraints and achieving optimal regret bounds. However, it suffers from
computational complexity limitations in high-dimensional settings or when
dealing with ill-conditioned constraint sets. Projection-free algorithms
address this issue by replacing the projection oracle with more efficient
optimization subroutines. But to date, these methods have been developed
primarily in the Euclidean setting, and while there has been growing interest
in optimization on Riemannian manifolds, there has been essentially no work in
trying to utilize projection-free tools here. An apparent issue is that
non-trivial affine functions are generally non-convex in such domains. In this
paper, we present methods for obtaining sub-linear regret guarantees in online
geodesically convex optimization on curved spaces for two scenarios: when we
have access to (a) a separation oracle or (b) a linear optimization oracle. For
geodesically convex losses, and when a separation oracle is available, our
algorithms achieve $O(T^{1/2}\:)$ and $O(T^{3/4}\;)$ adaptive regret guarantees
in the full information setting and the bandit setting, respectively. When a
linear optimization oracle is available, we obtain regret rates of
$O(T^{3/4}\;)$ for geodesically convex losses and $O(T^{2/3}\; log T )$ for
strongly geodesically convex losses
- Abstract（参考訳）: プロジェクション演算は、制約を強制し、最適後悔境界を達成するために、オンライン勾配降下(OGD)のような幅広い最適化アルゴリズムにおいて重要な要素である。
しかし、高次元の設定や不条件制約集合を扱う場合、計算複雑性の制限に苦しむ。
プロジェクションフリーアルゴリズムは、プロジェクションオラクルをより効率的な最適化サブルーチンに置き換えることでこの問題に対処する。
しかし、今日までこれらの手法は主にユークリッド空間で開発されており、リーマン多様体の最適化に対する関心は高まっているが、ここでは射影のないツールを使おうとする試みは本質的に行われていない。
明らかな問題は、非自明なアフィン函数がそのような領域では一般に非凸であることである。
本稿では,2つのシナリオに対して,曲面空間上での空間的凸最適化において,サブ線形後悔保証を得る方法を提案する。
(a)分離神託又は
(b)線形最適化オラクル。
地理的に凸な損失に対して、そして分離オラクルが利用可能になったとき、我々のアルゴリズムは、それぞれ完全な情報設定とbandit設定において、$o(t^{1/2}\:)$と$o(t^{3/4}\;)$を保証します。
線形最適化 oracle が利用可能であれば、地理的凸損失に対して $o(t^{3/4}\;)$ と、強立体凸損失に対して $o(t^{2/3}\; log t )$ が得られる。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Second Order Methods for Bandit Optimization and Control [34.51425758864638]
我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
論文 参考訳（メタデータ） (2024-02-14T04:03:38Z) - 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) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。
GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。
我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
論文 参考訳（メタデータ） (2022-11-22T23:53:06Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - 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) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。
このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。
本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
論文 参考訳（メタデータ） (2020-08-13T08:56:24Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。