論文の概要: Universal Online Convex Optimization with $1$ Projection per Round

• arxiv url: http://arxiv.org/abs/2405.19705v1
• Date: Thu, 30 May 2024 05:29:40 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-31 17:57:08.518994
• Title: Universal Online Convex Optimization with $1$ Projection per Round
• Title（参考訳）: Universal Online Convex Optimization: ラウンド当たり1ドルプロジェクション
• Authors: Wenhao Yang, Yibo Wang, Peng Zhao, Lijun Zhang,
• Abstract要約: 我々は,複数種類の凸関数に対して同時にミニマックスレートを得るユニバーサルアルゴリズムを開発した。 我々は、単純なドメイン上で定義された代理損失を用いて、1ドルのプロジェクションしか必要としない普遍的なOCOアルゴリズムを開発する。 我々の分析は、サロゲート損失に新たな光を当て、元の損失の後悔とサロゲート損失の相違点の厳密な検証を容易にする。
• 参考スコア（独自算出の注目度）: 31.16522982351235
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To address the uncertainty in function types, recent progress in online convex optimization (OCO) has spurred the development of universal algorithms that simultaneously attain minimax rates for multiple types of convex functions. However, for a $T$-round online problem, state-of-the-art methods typically conduct $O(\log T)$ projections onto the domain in each round, a process potentially time-consuming with complicated feasible sets. In this paper, inspired by the black-box reduction of Cutkosky and Orabona (2018), we employ a surrogate loss defined over simpler domains to develop universal OCO algorithms that only require $1$ projection. Embracing the framework of prediction with expert advice, we maintain a set of experts for each type of functions and aggregate their predictions via a meta-algorithm. The crux of our approach lies in a uniquely designed expert-loss for strongly convex functions, stemming from an innovative decomposition of the regret into the meta-regret and the expert-regret. Our analysis sheds new light on the surrogate loss, facilitating a rigorous examination of the discrepancy between the regret of the original loss and that of the surrogate loss, and carefully controlling meta-regret under the strong convexity condition. In this way, with only $1$ projection per round, we establish optimal regret bounds for general convex, exponentially concave, and strongly convex functions simultaneously. Furthermore, we enhance the expert-loss to exploit the smoothness property, and demonstrate that our algorithm can attain small-loss regret for multiple types of convex and smooth functions.
• Abstract（参考訳）: 関数型の不確実性に対処するため、オンライン凸最適化(OCO)の最近の進歩は、複数の種類の凸関数に対して同時に極小レートを達成するユニバーサルアルゴリズムの開発を刺激している。 しかし、$T$ラウンドのオンライン問題の場合、最先端の手法は通常、各ラウンドのドメインに$O(\log T)$プロジェクションを実行する。 この論文は、Cutkosky and Orabona (2018) のブラックボックス削減にインスパイアされ、単純なドメイン上で定義された代理損失を用いて、1ドルプロジェクションしか必要としないユニバーサルOCOアルゴリズムを開発する。 専門家の助言で予測の枠組みを取り入れた上で,機能の種類ごとに専門家の集合を維持し,メタアルゴリズムを用いて予測を集約する。 私たちのアプローチの要点は、メタレグレットとエキスパート-レグレットへの後悔の革新的な分解から生まれた、強い凸関数のためのユニークな設計のエキスパート-ロスにあります。 本分析では,サロゲート損失に新たな光を当て,元の損失の後悔とサロゲート損失の相違点の厳密な検証と,強い凸条件下でのメタレグレトを慎重に制御することを可能にした。 このように、1ラウンドあたりの射影はわずか1ドルであり、一般凸、指数的凸、強凸関数を同時に最適に残す境界を確立する。 さらに,スムーズ性を活用するためにエキスパートロスを向上し,複数種類の凸関数と滑らか関数に対して,アルゴリズムが小さめの後悔を達成できることを実証した。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• 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)
• Adaptive Bandit Convex Optimization with Heterogeneous Curvature [40.368893108265056]
  本研究では,学習者が決定を下すと,各関数が独自の曲率を持つ異種環境について検討する。 我々は, 高速で曲率に適応できる効率的なアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-02-12T21:55:42Z)
• Lazy Lagrangians with Predictions for Online Learning [24.18464455081512]
  オンライン凸最適化における時間的差分制約による一般的な問題について考察する。 Follow-The-Regularized-Leaderイテレーションと予測適応動的ステップを組み合わせることで、新しい原始双対アルゴリズムを設計する。 我々の研究は、この制約されたOCO設定のためのFTRLフレームワークを拡張し、各最先端のグレディベースのソリューションより優れています。
  論文  参考訳（メタデータ） (2022-01-08T21:49:10Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。 このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
  論文  参考訳（メタデータ） (2021-05-08T11:43:49Z)
• Projection-free Online Learning over Strongly Convex Sets [24.517908972536432]
  我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。 一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2020-10-16T05:42:50Z)

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

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