論文の概要: Dual Adaptivity: Universal Algorithms for Minimizing the Adaptive Regret of Convex Functions

• arxiv url: http://arxiv.org/abs/2508.00392v1
• Date: Fri, 01 Aug 2025 07:42:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-04 18:08:53.776745
• Title: Dual Adaptivity: Universal Algorithms for Minimizing the Adaptive Regret of Convex Functions
• Title（参考訳）: 二重適応性:凸関数の適応回帰を最小化する普遍的アルゴリズム
• Authors: Lijun Zhang, Wenhao Yang, Guanghui Wang, Wei Jiang, Zhi-Hua Zhou,
• Abstract要約: オンライン学習において、新たなパフォーマンス指標、適応的後悔(adaptive regret)が提案された。 適応的後悔を最小限に抑えるために、いくつかのアルゴリズムが開発されている。 既存のアルゴリズムは1種類の凸関数しか扱えないという意味で普遍性を欠いている。
• 参考スコア（独自算出の注目度）: 61.393184339405465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To deal with changing environments, a new performance measure -- adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, several algorithms have been successfully developed to minimize the adaptive regret. However, existing algorithms lack universality in the sense that they can only handle one type of convex functions and need apriori knowledge of parameters, which hinders their application in real-world scenarios. To address this limitation, this paper investigates universal algorithms with dual adaptivity, which automatically adapt to the property of functions (convex, exponentially concave, or strongly convex), as well as the nature of environments (stationary or changing). Specifically, we propose a meta-expert framework for dual adaptive algorithms, where multiple experts are created dynamically and aggregated by a meta-algorithm. The meta-algorithm is required to yield a second-order bound, which can accommodate unknown function types. We further incorporate the technique of sleeping experts to capture the changing environments. For the construction of experts, we introduce two strategies (increasing the number of experts or enhancing the capabilities of experts) to achieve universality. Theoretical analysis shows that our algorithms are able to minimize the adaptive regret for multiple types of convex functions simultaneously, and also allow the type of functions to switch between rounds. Moreover, we extend our meta-expert framework to online composite optimization, and develop a universal algorithm for minimizing the adaptive regret of composite functions.
• Abstract（参考訳）: 環境の変化に対処するため、オンライン学習において、あらゆる間隔で最大の静的な後悔と定義される、適応的後悔という新たなパフォーマンス指標が提案された。 オンライン凸最適化の設定の下で、適応的後悔を最小限に抑えるためにいくつかのアルゴリズムが開発されている。 しかし、既存のアルゴリズムは1種類の凸関数しか扱えないという意味で普遍性を欠き、パラメータのプリオリ知識が必要であり、現実のシナリオでの応用を妨げる。 この制限に対処するために,関数の性質(凸,指数的凹,強凸)と環境の性質(定常あるいは変化)に自動的に適応する双対適応性をもつ普遍アルゴリズムについて検討する。 具体的には、複数の専門家が動的に作成され、メタアルゴリズムによって集約される、二重適応アルゴリズムのためのメタエキスパートフレームワークを提案する。 メタアルゴリズムは未知の関数型に対応する2階のバウンドを生成するために必要である。 さらに、睡眠専門家の技法を取り入れて、環境の変化を捉えます。 専門家の構築には,専門家の数を増やすか,専門家の能力を高めるための2つの戦略を導入する。 理論的解析により,複数種類の凸関数に対する適応的後悔を同時に最小化することができ,また,関数の型がラウンド間で切替できることが示唆された。 さらに,我々のメタエキスパートフレームワークをオンライン複合最適化に拡張し,複合関数の適応的後悔を最小化するための普遍的アルゴリズムを開発した。

関連論文リスト

• Universal Online Convex Optimization with $1$ Projection per Round [31.16522982351235]
  我々は,複数種類の凸関数に対して同時にミニマックスレートを得るユニバーサルアルゴリズムを開発した。 我々は、単純なドメイン上で定義された代理損失を用いて、1ドルのプロジェクションしか必要としない普遍的なOCOアルゴリズムを開発する。 我々の分析は、サロゲート損失に新たな光を当て、元の損失の後悔とサロゲート損失の相違点の厳密な検証を容易にする。
  論文  参考訳（メタデータ） (2024-05-30T05:29:40Z)
• Universal Online Optimization in Dynamic Environments via Uniclass Prediction [0.0]
  動的環境におけるユニバーサルオンライン最適化のための新しい直感的なフレームワークを提案する。 私たちの戦略は、専門家のセットと付随するメタアルゴリズムの構築に依存していません。 これは、一般凸コスト関数に対しても、最先端の動的後悔保証を伴う普遍的アプローチを提案する最初の論文である。
  論文  参考訳（メタデータ） (2023-02-13T03:00:45Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients [99.13839450032408]
  一般的な問題を解決するための適応アルゴリズムのための普遍的な枠組みを設計することが望まれる。 特に,本フレームワークは,非収束的設定支援の下で適応的手法を提供する。
  論文  参考訳（メタデータ） (2021-06-15T15:16:28Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。 このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
  論文  参考訳（メタデータ） (2021-05-08T11:43:49Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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