Fugu-MT 論文翻訳(概要): Online Convex Optimization with a Separation Oracle

論文の概要: Online Convex Optimization with a Separation Oracle

arxiv url: http://arxiv.org/abs/2410.02476v1
Date: Mon, 7 Oct 2024 17:15:37 GMT
ステータス: 処理完了
システム内更新日: 2024-11-04 03:01:18.884533
Title: Online Convex Optimization with a Separation Oracle
Title（参考訳）: 分離されたOracleによるオンライン凸最適化
Authors: Zakaria Mhammedi,
Abstract要約: 本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。我々のアルゴリズムは、$tildeO(sqrtdT + kappa d)$の後悔のバウンダリを達成します。
参考スコア（独自算出の注目度）: 10.225358400539719
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: In this paper, we introduce a new projection-free algorithm for Online Convex Optimization (OCO) with a state-of-the-art regret guarantee among separation-based algorithms. Existing projection-free methods based on the classical Frank-Wolfe algorithm achieve a suboptimal regret bound of $O(T^{3/4})$, while more recent separation-based approaches guarantee a regret bound of $O(\kappa \sqrt{T})$, where $\kappa$ denotes the asphericity of the feasible set, defined as the ratio of the radii of the containing and contained balls. However, for ill-conditioned sets, $\kappa$ can be arbitrarily large, potentially leading to poor performance. Our algorithm achieves a regret bound of $\tilde{O}(\sqrt{dT} + \kappa d)$, while requiring only $\tilde{O}(1)$ calls to a separation oracle per round. Crucially, the main term in the bound, $\tilde{O}(\sqrt{d T})$, is independent of $\kappa$, addressing the limitations of previous methods. Additionally, as a by-product of our analysis, we recover the $O(\kappa \sqrt{T})$ regret bound of existing OCO algorithms with a more straightforward analysis and improve the regret bound for projection-free online exp-concave optimization. Finally, for constrained stochastic convex optimization, we achieve a state-of-the-art convergence rate of $\tilde{O}(\sigma/\sqrt{T} + \kappa d/T)$, where $\sigma$ represents the noise in the stochastic gradients, while requiring only $\tilde{O}(1)$ calls to a separation oracle per iteration.
Abstract（参考訳）: 本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。古典的フランク=ウルフアルゴリズムに基づく既存の射影自由法は、$O(T^{3/4})$の最適的後悔境界を達成する一方、より最近の分離に基づくアプローチは、$O(\kappa \sqrt{T})$の後悔境界を保証する。しかし、不条件集合の場合、$\kappa$は任意に大きくなり、性能が低下する可能性がある。我々のアルゴリズムは、$\tilde{O}(\sqrt{dT} + \kappa d)$の後悔境界を達成できるが、ラウンドごとの分離オラクルへの呼び出しは$\tilde{O}(1)$のみである。重要なことに、境界の主項である$\tilde{O}(\sqrt{d T})$は$\kappa$とは独立であり、以前のメソッドの制限に対処する。さらに、分析の副産物として、既存のOCOアルゴリズムの後悔境界をより簡単な分析で復元し、プロジェクションフリーのオンラインexp-concave最適化における後悔境界を改善する。最後に、制約付き確率凸最適化では、$\tilde{O}(\sigma/\sqrt{T} + \kappa d/T)$の最先端収束率を達成する。

関連論文リスト

Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文参考訳（メタデータ） (2024-02-14T13:44:16Z)
Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文参考訳（メタデータ） (2024-02-14T07:52:00Z)
Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文参考訳（メタデータ） (2023-06-30T20:36:44Z)
Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文参考訳（メタデータ） (2023-02-09T18:58:05Z)
Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning [8.461907111368628]
我々はオンライン凸最適化(OCO)のための新しい効率的なプロジェクションフリーアルゴリズムを開発した。我々は,LOOracleを1ラウンドに2回呼び出すOCOアルゴリズムを開発し,ほぼ最適の$widetildeO(sqrtT)を後悔する。また, 一般凸集合に対して, 1ラウンド当たりのO(d)$ LO Oracleへのコール数を$widetilde O(d)$に設定するアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-05-23T17:13:46Z)
The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
本稿では,スムーズで強靭なミニマックス最適化問題を再考する。既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
論文参考訳（メタデータ） (2022-05-11T17:33:07Z)
Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime [17.60502131429094]
本稿では,条件数関数としてスペーサー解を復元する反復型ハードしきい値決定アルゴリズムの簡単な修正を提案する。提案するアルゴリズムである正規化IHTは、疎度$O(skappa)$の解を返す。我々のアルゴリズムはARHTよりも大幅に改善され、またスパーシティ$O(skappa)$の解も見つかる。
論文参考訳（メタデータ） (2022-04-11T19:33:15Z)
New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees [21.30065439295409]
オンライン凸最適化(OCO)のための効率的なテキストプロジェクションフリーアルゴリズムを提案する。提案アルゴリズムは,テキストインファシブルプロジェクション(textitinfeasible projections)と呼ばれる新しい,効率的なアプローチによるテクスタイトライン勾配降下アルゴリズムに基づいている。我々は、全体として$O(T)$コールを使用して分離オラクルを呼び出し、$O(sqrtT)$アダプティブな後悔と$O(T3/4)$アダプティブな期待された後悔を保証します。
論文参考訳（メタデータ） (2022-02-09T20:56:16Z)
Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文参考訳（メタデータ） (2021-03-02T06:53:44Z)
Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文参考訳（メタデータ） (2021-02-15T08:16:51Z)

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

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