論文の概要: Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2511.19937v1
• Date: Tue, 25 Nov 2025 05:23:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-26 17:37:04.28663
• Title: Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization
• Title（参考訳）: 適応性と普遍性:オンライン凸最適化のための問題依存ユニバーサルレグレット
• Authors: Peng Zhao, Yu-Hu Yan, Hang Yu, Zhi-Hua Zhou,
• Abstract要約: 普遍性と適応性の両方を達成する新しいアプローチであるUniGradを紹介し、UniGrad.CorrectとUniGrad.Bregmanの2つの異なる実現法を提案する。 どちらのメソッドも勾配の変動に適応し、強い凸関数に対する $mathcalO(log V_T)$ regret とexp-concave関数に対する $mathcalO(d log V_T)$ regret を同時に達成する。
• 参考スコア（独自算出の注目度）: 64.88607416000376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Universal online learning aims to achieve optimal regret guarantees without requiring prior knowledge of the curvature of online functions. Existing methods have established minimax-optimal regret bounds for universal online learning, where a single algorithm can simultaneously attain $\mathcal{O}(\sqrt{T})$ regret for convex functions, $\mathcal{O}(d \log T)$ for exp-concave functions, and $\mathcal{O}(\log T)$ for strongly convex functions, where $T$ is the number of rounds and $d$ is the dimension of the feasible domain. However, these methods still lack problem-dependent adaptivity. In particular, no universal method provides regret bounds that scale with the gradient variation $V_T$, a key quantity that plays a crucial role in applications such as stochastic optimization and fast-rate convergence in games. In this work, we introduce UniGrad, a novel approach that achieves both universality and adaptivity, with two distinct realizations: UniGrad.Correct and UniGrad.Bregman. Both methods achieve universal regret guarantees that adapt to gradient variation, simultaneously attaining $\mathcal{O}(\log V_T)$ regret for strongly convex functions and $\mathcal{O}(d \log V_T)$ regret for exp-concave functions. For convex functions, the regret bounds differ: UniGrad.Correct achieves an $\mathcal{O}(\sqrt{V_T \log V_T})$ bound while preserving the RVU property that is crucial for fast convergence in online games, whereas UniGrad.Bregman achieves the optimal $\mathcal{O}(\sqrt{V_T})$ regret bound through a novel design. Both methods employ a meta algorithm with $\mathcal{O}(\log T)$ base learners, which naturally requires $\mathcal{O}(\log T)$ gradient queries per round. To enhance computational efficiency, we introduce UniGrad++, which retains the regret while reducing the gradient query to just $1$ per round via surrogate optimization. We further provide various implications.
• Abstract（参考訳）: ユニバーサルオンライン学習は、オンライン機能の曲率に関する事前知識を必要とせず、最適な後悔の保証を達成することを目的としている。 既存の手法は、万能オンライン学習のためのminimax-optimal regret boundsを確立しており、単一のアルゴリズムが同時に凸関数に対して $\mathcal{O}(\sqrt{T})$ regret、exp-concave 関数に対して $\mathcal{O}(d \log T)$、強凸関数に対して $\mathcal{O}(\log T)$、$T$ はラウンドの数であり、$d$ はファジブル領域の次元である。 しかし、これらの手法には問題に依存した適応性がない。 特に、普遍的な方法では、ゲームにおける確率的最適化や高速レート収束のようなアプリケーションにおいて重要な役割を果たす重要な量である勾配変動$V_T$でスケールする後悔境界は提供されない。 本稿では,UniGradとUniGrad.Bregmanの2つの異なる実現法を用いて,普遍性と適応性を両立する新しいアプローチであるUniGradを紹介する。 どちらの手法も勾配変動に適応する普遍的後悔保証を達成し、強い凸関数に対する後悔$\mathcal{O}(\log V_T)とexp-凹関数に対する後悔$\mathcal{O}(d \log V_T)を同時に達成する。 UniGrad.Correct は $\mathcal{O}(\sqrt{V_T \log V_T})$bound を達成し、オンラインゲームにおいて高速収束に不可欠な RVU プロパティを保存する一方で、UniGrad.Bregman は $\mathcal{O}(\sqrt{V_T})$ regret bound を新規設計を通じて達成する。 どちらの手法も、$\mathcal{O}(\log T)$base Learningersというメタアルゴリズムを採用しており、当然、ラウンド毎に$\mathcal{O}(\log T)$ gradient queryを必要とする。 計算効率を向上させるために、UniGrad++を導入し、これは、サロゲート最適化による1ラウンドあたりの勾配クエリをわずか1ドルに抑えながら、後悔を抑える。 私たちはさらに様々な意味を与えます。

関連論文リスト

• Sparsity-Based Interpolation of External, Internal and Swap Regret [4.753557469026313]
  本稿では,オンライン学習におけるエキスパート問題に焦点をあてる。 最適な$O(sqrtTlog d)$external regret bound when $dmathrmunif_phi=d$, the standard $tilde O(sqrtT)$ internal regret bound when $dmathrmself_phi=d-1$, and the optimal $tilde O(sqrtdT)$ swap regret bound in the worst case, we improve on existing algorithm in the intermediate regimes。
  論文  参考訳（メタデータ） (2025-02-06T22:47:52Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• 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)
• 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)

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

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