論文の概要: Dynamic Regret of Convex and Smooth Functions
- arxiv url: http://arxiv.org/abs/2007.03479v2
- Date: Sat, 28 Nov 2020 08:52:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 18:58:02.378338
- Title: Dynamic Regret of Convex and Smooth Functions
- Title（参考訳）: 凸関数と滑らか関数の動的回帰
- Authors: Peng Zhao, Yu-Jie Zhang, Lijun Zhang, Zhi-Hua Zhou
- Abstract要約: 非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
- 参考スコア（独自算出の注目度）: 93.71361250701075
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate online convex optimization in non-stationary environments and
choose the 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 dynamic regret by
exploiting the smoothness condition. Specifically, we propose novel online
algorithms that are capable of leveraging smoothness and replace the dependence
on $T$ in the dynamic regret by 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.
- Abstract（参考訳）: 非定常環境におけるオンライン凸最適化について検討し、オンラインアルゴリズムが生み出す累積損失と実行可能なコンパレータシーケンスとの差として定義される性能指標として動的後悔を選択する。
T$を時間軸とし、$P_T$を環境の非定常性を本質的に反映するパス長とし、最先端の動的後悔は$\mathcal{O}(\sqrt{T(1+P_T)})$とする。
この境界は凸関数に対してミニマックス最適であることが証明されているが、本論文では滑らか性条件を利用して動的後悔をさらに高めることができることを示す。
具体的には, 損失関数の勾配の変動, コンパレータシーケンスの累積損失, 前の2項の最小化という問題依存量によって, 滑らかさを生かし, 動的後悔のT$への依存を置き換える新しいオンラインアルゴリズムを提案する。
これらの量は少なくとも$\mathcal{O}(T)$であるが、良質な環境ではずっと小さい。
したがって,本研究の結果は,既往の結果よりも厳密であり,かつ最悪の場合において同じ確率を保証できるため,本問題の本質的な難易度に適応する。
関連論文リスト
- An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。
R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-06-03T17:54:58Z) - 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) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - 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) - Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex
Cost Functions [30.412826613009518]
リプシッツ連続性も均一な滑らか性も存在しない場合でも、動的後悔を束縛することは可能であることを示す。
次に、相対的に強い凸性の付加条件により、動的後悔は経路長と勾配変化によって境界付けられることを示す。
論文 参考訳（メタデータ） (2022-02-25T17:35:07Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Dynamic Regret for Strongly Adaptive Methods and Optimality of Online
KRR [13.165557713537389]
我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。
我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
論文 参考訳（メタデータ） (2021-11-22T21:52:47Z) - A closer look at temporal variability in dynamic online learning [19.468067110814808]
この作品は、完全な情報でオンライン学習の文脈でダイナミックな後悔の設定に焦点を当てています。
損失関数の列は時間とともに大きく変化しないと仮定することにより、既存の結果と比較して改善された後悔境界を導き出すことが可能であることを示す。
論文 参考訳（メタデータ） (2021-02-15T16:50:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。