論文の概要: 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を選択します。
このようにして、ブラックボックスの専門家として市販のオンラインソルバをプラグインして、問題に依存した後悔の束縛を提供することができます。
さらに, この戦略は, 強凸関数および指数凸関数のために設計された任意の専門家の理論的保証を, 二重対数因子まで受け継いでいる。
一般凸函数に対しては、ミニマックスの最適性を維持し、小さな損失境界も達成する。
関連論文リスト
- 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) - Nonsmooth Projection-Free Optimization with Functional Constraints [14.413404128420352]
本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。
提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。
決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
論文 参考訳(メタデータ) (2023-11-18T23:06:33Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online
Ensemble Approach [65.10444843694003]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $widehatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳(メタデータ) (2023-07-17T09:55:35Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - Efficient First-order Methods for Convex Optimization with Strongly
Convex Function Constraints [3.667453772837954]
強い凸関数制約を受ける凸関数を最小化する方法を示す。
有限個の結果に独立な意味を持つような空間パターンを同定する。
論文 参考訳(メタデータ) (2022-12-21T16:04:53Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。
最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文 参考訳(メタデータ) (2022-06-22T23:57:40Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳(メタデータ) (2022-03-01T18:20:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。