論文の概要: Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for
Mixable/Exp-Concave Losses
- arxiv url: http://arxiv.org/abs/2109.13786v1
- Date: Tue, 28 Sep 2021 15:06:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-29 14:51:01.297551
- Title: Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for
Mixable/Exp-Concave Losses
- Title（参考訳）: 近対数レギュレット・パー・スイッチを用いた混合・露光損失に対するニア線形時間アルゴリズム
- Authors: Kaan Gokcesu, Hakan Gokcesu
- Abstract要約: 動的環境における対数的静的後悔を伴う混合損失関数のオンライン最適化について検討する。
文献では,スイッチ1回あたりのほぼ対数的後悔を1時間あたりのポリノミカルな複雑さで達成できることが確認できた。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of online learning, which has gained significant
attention in recent years due to its applicability in a wide range of fields
from machine learning to game theory. Specifically, we study the online
optimization of mixable loss functions with logarithmic static regret in a
dynamic environment. The best dynamic estimation sequence that we compete
against is selected in hindsight with full observation of the loss functions
and is allowed to select different optimal estimations in different time
intervals (segments). We propose an online mixture framework that uses these
static solvers as the base algorithm. We show that with the suitable selection
of hyper-expert creations and weighting strategies, we can achieve logarithmic
and squared logarithmic regret per switch in quadratic and linearithmic
computational complexity, respectively. For the first time in literature, we
show that it is also possible to achieve near-logarithmic regret per switch
with sub-polynomial complexity per time. Our results are guaranteed to hold in
a strong deterministic sense in an individual sequence manner.
- Abstract（参考訳）: 近年,機械学習からゲーム理論まで幅広い分野に適用可能であることから,オンライン学習の課題が注目されている。
具体的には,動的環境における混合損失関数と対数的静的後悔のオンライン最適化について検討する。
我々が競う最良の動的推定列は、損失関数の完全な観察とともに後から選択され、異なる時間間隔(セグメント)で異なる最適推定を選択できる。
静的解法をベースアルゴリズムとして利用するオンライン混合フレームワークを提案する。
重み付け戦略を適当に選択することで,二次計算複雑性と線形計算複雑性において,スイッチ毎の対数的および二乗対数的後悔をそれぞれ達成できることを示す。
文献では,スイッチ1回あたりのほぼ対数的後悔を1時間あたりのポリノミカルな複雑さで達成できることが確認できた。
私たちの結果は、個々のシーケンスで強い決定論的意味を持つことが保証されます。
関連論文リスト
- Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。
インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。
これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
論文 参考訳（メタデータ） (2023-09-27T21:54:52Z) - Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making [73.48977854003697]
この研究は、複雑性という新しい概念、一般化ブラケット数を導入し、空間の大きさに対する敵の制約を結婚させる。
次に、オンライン予測や断片的連続関数の計画など、関心のあるいくつかの問題で境界をインスタンス化する。
論文 参考訳（メタデータ） (2023-02-10T18:45:52Z) - Efficient and Near-Optimal Smoothed Online Learning for Generalized
Linear Functions [28.30744223973527]
我々は,K-wise線形分類において,統計学的に最適なログ(T/sigma)の後悔を初めて楽しむ計算効率のよいアルゴリズムを提案する。
一般化線形分類器によって誘導される不一致領域の幾何学の新たな特徴付けを開発する。
論文 参考訳（メタデータ） (2022-05-25T21:31:36Z) - Damped Online Newton Step for Portfolio Selection [96.0297968061824]
古典的なオンラインポートフォリオ選択の問題を再考し、各ラウンドで学習者がポートフォリオの集合上の分布を選択し、その富を割り当てる。
この問題に対する対数的後悔を達成する既存のアルゴリズムは、ラウンドの総数とスケールする時間と空間の複雑さがある。
対数的後悔を伴う最初の実用的オンラインポートフォリオ選択アルゴリズムを提示し、その時間と空間の複雑さは水平線上で対数的にのみ依存する。
論文 参考訳（メタデータ） (2022-02-15T17:01:55Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2022-02-09T19:22:34Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:10:48Z) - Optimal and Efficient Algorithms for General Mixable Losses against
Switching Oracles [0.0]
動的環境における混合損失関数のオンライン最適化について検討する。
我々の結果は、個々のシーケンス方式で強い決定論的意味を持つことが保証されている。
論文 参考訳（メタデータ） (2021-08-13T21:48:55Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。
提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。
本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
論文 参考訳（メタデータ） (2020-02-20T11:11:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。