論文の概要: Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2112.14368v1
- Date: Wed, 29 Dec 2021 02:42:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-30 15:44:35.091843
- Title: Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization
- Title（参考訳）: 適応性と非定常性:オンライン凸最適化における問題依存動的後悔
- Authors: Peng Zhao, Yu-Jie Zhang, Lijun Zhang, Zhi-Hua Zhou
- Abstract要約: 非定常環境におけるオンライン凸最適化について検討する。
エンファンダイナミックな後悔をパフォーマンス指標として選びます。
本研究では,スムーズさを生かし,動的後悔の中で$T$に依存する新しいオンラインアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 93.14387921542709
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate online convex optimization in non-stationary environments and
choose the \emph{dynamic regret} as the performance measure, defined as the
difference between cumulative loss incurred by the online algorithm and that of
any feasible comparator sequence. Let $T$ be the time horizon and $P_T$ be the
path-length that essentially reflects the non-stationarity of environments, the
state-of-the-art dynamic regret is $\mathcal{O}(\sqrt{T(1+P_T)})$. Although
this bound is proved to be minimax optimal for convex functions, in this paper,
we demonstrate that it is possible to further enhance the guarantee for some
easy problem instances, particularly when online functions are smooth.
Specifically, we propose novel online algorithms that can leverage smoothness
and replace the dependence on $T$ in the dynamic regret by
\emph{problem-dependent} quantities: the variation in gradients of loss
functions, the cumulative loss of the comparator sequence, and the minimum of
the previous two terms. These quantities are at most $\mathcal{O}(T)$ while
could be much smaller in benign environments. Therefore, our results are
adaptive to the intrinsic difficulty of the problem, since the bounds are
tighter than existing results for easy problems and meanwhile guarantee the
same rate in the worst case. Notably, our algorithm requires only \emph{one}
gradient per iteration, which shares the same gradient query complexity with
the methods developed for optimizing the static regret. As a further
application, we extend the results from the full-information setting to bandit
convex optimization with two-point feedback and thereby attain the first
problem-dependent dynamic regret for such bandit tasks.
- Abstract（参考訳）: 非定常環境におけるオンライン凸最適化について検討し,オンラインアルゴリズムが生み出す累積損失と,実現可能なコンパレータシーケンスとの差として定義した性能指標として, 'emph{dynamic regret} を選択する。
T$を時間軸とし、$P_T$を環境の非定常性を本質的に反映するパス長とし、最先端の動的後悔は$\mathcal{O}(\sqrt{T(1+P_T)})$とする。
この境界は凸関数に対してミニマックス最適であることが証明されているが,本稿では,簡単な問題,特にオンライン関数が滑らかである場合の保証をさらに強化できることを実証する。
具体的には, 損失関数の勾配の変動, コンパレータ列の累積損失, および前2項の最小値によって, 滑らかさを生かして, 動的後悔における$t$への依存を<emph{problem-dependent} 量に置き換える, オンラインアルゴリズムを提案する。
これらの量は少なくとも$\mathcal{O}(T)$であるが、良質な環境ではずっと小さい。
したがって,本研究の結果は,既往の結果よりも厳密であり,かつ最悪の場合において同じ確率を保証できるため,本問題の本質的な難易度に適応する。
このアルゴリズムは静的な後悔を最適化するために開発された手法と同じ勾配クエリの複雑さを共有する。
さらなる応用として、全情報設定から2点フィードバックによる包絡最適化までの結果を拡張し、そのような包絡タスクに対する最初の問題依存動的後悔を実現する。
関連論文リスト
- Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
非強凸設定における最小二乗回帰問題の近似を考察する。
本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-03-03T14:39:33Z) - Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex
Cost Functions [30.412826613009518]
リプシッツ連続性も均一な滑らか性も存在しない場合でも、動的後悔を束縛することは可能であることを示す。
次に、相対的に強い凸性の付加条件により、動的後悔は経路長と勾配変化によって境界付けられることを示す。
論文 参考訳（メタデータ） (2022-02-25T17:35:07Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳（メタデータ） (2021-06-29T09:48:46Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Adaptive Importance Sampling for Finite-Sum Optimization and Sampling
with Decreasing Step-Sizes [4.355567556995855]
ステップサイズを小さくした有限サム最適化とサンプリングのための適応的重要度サンプリングのための簡易かつ効率的なアルゴリズムであるavareを提案する。
標準的な技術的条件下では、$mathcalO(T2/3)$と$mathcalO(T5/6)$の動的後悔をそれぞれ、$mathcalO(T5/6)$のステップサイズで実行するときに達成している。
論文 参考訳（メタデータ） (2021-03-23T00:28:15Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。