論文の概要: Universal Online Convex Optimization Meets Second-order Bounds

• arxiv url: http://arxiv.org/abs/2105.03681v3
• Date: Wed, 20 Nov 2024 05:53:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-21 16:09:34.793161
• Title: Universal Online Convex Optimization Meets Second-order Bounds
• Title（参考訳）: Universal Online Convex Optimizationが2次境界に到達
• Authors: Lijun Zhang, Yibo Wang, Guanghui Wang, Jinfeng Yi, Tianbao Yang,
• Abstract要約: ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。 このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
• 参考スコア（独自算出の注目度）: 74.0120666722487
• License:
• Abstract: Recently, several universal methods have been proposed for online convex optimization, and attain minimax rates for multiple types of convex functions simultaneously. However, they need to design and optimize one surrogate loss for each type of functions, making it difficult to exploit the structure of the problem and utilize existing algorithms. In this paper, we propose a simple strategy for universal online convex optimization, which avoids these limitations. The key idea is to construct a set of experts to process the original online functions, and deploy a meta-algorithm over the linearized losses to aggregate predictions from experts. Specifically, the meta-algorithm is required to yield a second-order bound with excess losses, so that it can leverage strong convexity and exponential concavity to control the meta-regret. In this way, our strategy inherits the theoretical guarantee of any expert designed for strongly convex functions and exponentially concave functions, up to a double logarithmic factor. As a result, we can plug in off-the-shelf online solvers as black-box experts to deliver problem-dependent regret bounds. For general convex functions, it maintains the minimax optimality and also achieves a small-loss bound. Furthermore, we extend our universal strategy to online composite optimization, where the loss function comprises a time-varying function and a fixed regularizer. To deal with the composite loss functions, we employ a meta-algorithm based on the optimistic online learning framework, which not only possesses a second-order bound, but also can utilize estimations for upcoming loss functions. With appropriate configurations, we demonstrate that the additional regularizer does not contribute to the meta-regret, thus maintaining the universality in the composite setting.
• Abstract（参考訳）: 近年,オンライン凸最適化のための普遍的手法がいくつか提案されており,複数種類の凸関数に対して同時にミニマックスレートを実現することができる。 しかし、各種類の関数に対して1つのサロゲート損失を設計し、最適化する必要があるため、問題の構造を活用でき、既存のアルゴリズムを利用するのが困難である。 本稿では,これらの制約を回避するために,ユニバーサルなオンライン凸最適化のための簡単な戦略を提案する。 主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイし、専門家からの予測を集約することである。 具体的には、メタアルゴリズムは、強い凸性および指数的凸性を利用してメタレグレットを制御するために、過剰な損失で2階のバウンドを得る必要がある。 このようにして、我々の戦略は、強い凸関数や指数的凸関数のために設計された専門家の理論的保証を、二重対数係数まで継承する。 その結果、ブラックボックスの専門家として市販のオンラインソルバをプラグインして、問題依存の後悔の限界を提供することができます。 一般凸関数に対しては、ミニマックス最適性を維持し、また小さな空間境界を達成する。 さらに、損失関数は時間変化関数と固定正則化器を含むオンライン合成最適化に拡張する。 複合損失関数に対処するため,楽観的なオンライン学習フレームワークをベースとしたメタアルゴリズムを用いる。 適切な構成で、追加の正則化器がメタレグレットに寄与しないことを示し、コンポジット設定における普遍性を維持する。

関連論文リスト

• Universal Online Convex Optimization with $1$ Projection per Round [31.16522982351235]
  我々は,複数種類の凸関数に対して同時にミニマックスレートを得るユニバーサルアルゴリズムを開発した。 我々は、単純なドメイン上で定義された代理損失を用いて、1ドルのプロジェクションしか必要としない普遍的なOCOアルゴリズムを開発する。 我々の分析は、サロゲート損失に新たな光を当て、元の損失の後悔とサロゲート損失の相違点の厳密な検証を容易にする。
  論文  参考訳（メタデータ） (2024-05-30T05:29:40Z)
• Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization [8.225819874406238]
  Mualem citemualem23re は、この手法がダウンクローズド制約と非ダウンクローズド制約の間を滑らかにできないことを示す。 本研究では,物体を2つの異なる凸体に自然分解した新しいオフラインおよびオンラインアルゴリズムを提案する。 また、3つのオフラインおよび2つのオンラインアプリケーションにまたがる提案アルゴリズムの優位性を実証的に示す。
  論文  参考訳（メタデータ） (2024-01-17T14:56:42Z)
• 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)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (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)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Extracting Optimal Solution Manifolds using Constrained Neural Optimization [6.800113407368289]
  制約付き最適化解アルゴリズムは点ベース解に制限される。 最適集合を近似として抽出する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-13T15:37:44Z)

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

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