論文の概要: A Simple yet Universal Strategy for Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2105.03681v1
- Date: Sat, 8 May 2021 11:43:49 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-11 14:33:39.481473
- Title: A Simple yet Universal Strategy for Online Convex Optimization
- Title（参考訳）: オンライン凸最適化のための単純かつ普遍的な戦略
- Authors: Lijun Zhang, Guanghui Wang, Jinfeng Yi, Tianbao Yang
- Abstract要約: ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。
鍵となるアイデアは、元のオンライン機能を処理する専門家のセットを構築し、emphlinearized lossの上にメタアゴリタムを配置することだ。
我々の戦略は、強い凸関数と指数関数のために設計された専門家の理論的保証を継承する。
- 参考スコア（独自算出の注目度）: 97.64589722655612
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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, which makes it difficult to exploit the structure
of the problem and utilize the vast amount of 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
\emph{linearized} losses to aggregate predictions from experts. Specifically,
we choose Adapt-ML-Prod to track the best expert, because it has a second-order
bound and can be used to leverage strong convexity and exponential concavity.
In this way, we can plug in off-the-shelf online solvers as black-box experts
to deliver problem-dependent regret bounds. Furthermore, our strategy inherits
the theoretical guarantee of any expert designed for strongly convex functions
and exponentially concave functions, up to a double logarithmic factor. For
general convex functions, it maintains the minimax optimality and also achieves
a small-loss bound.
- Abstract（参考訳）: 近年,オンライン凸最適化のための普遍的手法がいくつか提案され,複数種類の凸関数のミニマックス率を同時に達成する手法が提案されている。
しかし、各種類の関数に対して1つのサロゲート損失を設計および最適化する必要があるため、問題の構造を活用し、既存の膨大なアルゴリズムを活用することは困難である。
本稿では,これらの制約を回避するために,ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。
重要なアイデアは、元のオンライン機能を処理する専門家のセットを構築し、専門家からの予測を集約するために \emph{linearized} 損失の上にメタアルゴリズムを配置することだ。
具体的には、最適な専門家を追跡するためにAdapt-ML-Prodを選択します。
このようにして、ブラックボックスの専門家として市販のオンラインソルバをプラグインして、問題に依存した後悔の束縛を提供することができます。
さらに, この戦略は, 強凸関数および指数凸関数のために設計された任意の専門家の理論的保証を, 二重対数因子まで受け継いでいる。
一般凸函数に対しては、ミニマックスの最適性を維持し、小さな損失境界も達成する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。