論文の概要: Improved Dynamic Regret for Online Frank-Wolfe
- arxiv url: http://arxiv.org/abs/2302.05620v2
- Date: Mon, 24 Jun 2024 13:11:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-26 05:28:15.937863
- Title: Improved Dynamic Regret for Online Frank-Wolfe
- Title（参考訳）: オンラインFrank-Wolfeにおける動的レグレットの改善
- Authors: Yuanyu Wan, Lijun Zhang, Mingli Song,
- Abstract要約: オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
- 参考スコア（独自算出の注目度）: 54.690867216880356
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: To deal with non-stationary online problems with complex constraints, we investigate the dynamic regret of online Frank-Wolfe (OFW), which is an efficient projection-free algorithm for online convex optimization. It is well-known that in the setting of offline optimization, the smoothness of functions and the strong convexity of functions accompanying specific properties of constraint sets can be utilized to achieve fast convergence rates for the Frank-Wolfe (FW) algorithm. However, for OFW, previous studies only establish a dynamic regret bound of $O(\sqrt{T}(V_T+\sqrt{D_T}+1))$ by utilizing the convexity of problems, where $T$ is the number of rounds, $V_T$ is the function variation, and $D_T$ is the gradient variation. In this paper, we derive improved dynamic regret bounds for OFW by extending the fast convergence rates of FW from offline optimization to online optimization. The key technique for this extension is to set the step size of OFW with a line search rule. In this way, we first show that the dynamic regret bound of OFW can be improved to $O(\sqrt{T(V_T+1)})$ for smooth functions. Second, we achieve a better dynamic regret bound of $O(T^{1/3}(V_T+1)^{2/3})$ when functions are smooth and strongly convex, and the constraint set is strongly convex. Finally, for smooth and strongly convex functions with minimizers in the interior of the constraint set, we demonstrate that the dynamic regret of OFW reduces to $O(V_T+1)$, and can be further strengthened to $O(\min\{P_T^\ast,S_T^\ast,V_T\}+1)$ by performing a constant number of FW iterations per round, where $P_T^\ast$ and $S_T^\ast$ denote the path length and squared path length of minimizers, respectively.
- Abstract（参考訳）: 複雑な制約を伴う非定常オンライン問題に対処するため、オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるオンラインフランクウルフ(OFW)の動的後悔について検討する。
オフライン最適化の設定において、関数の滑らかさと制約セットの特定の性質に付随する関数の強い凸性を利用して、フランク・ウルフ(FW)アルゴリズムの高速収束率を達成することはよく知られている。
しかし、OW の場合、以前の研究は、問題の凸性を利用して、$O(\sqrt{T}(V_T+\sqrt{D_T}+1)$の動的後悔境界を定めているだけで、$T$ はラウンド数、$V_T$ は関数変分、$D_T$ は勾配変分である。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
この拡張の鍵となるテクニックは、行探索ルールでOwのステップサイズを設定することである。
このようにして、OW の動的後悔境界が滑らかな函数に対して$O(\sqrt{T(V_T+1)})$に改善できることを最初に示す。
第二に、函数が滑らかで強凸であり、制約集合が強凸であるとき、$O(T^{1/3}(V_T+1)^{2/3})$のより動的な後悔境界を達成する。
最後に、制約集合の内部に最小値を持つ滑らかで強い凸関数に対して、OWの動的後悔は$O(V_T+1)$に減少し、さらに$O(\min\{P_T^\ast,S_T^\ast,V_T\}+1)$に拡張できることを示す。
関連論文リスト
- Fast Rates in Online Convex Optimization by Exploiting the Curvature of
Feasible Sets [42.37773914630974]
オンライン線形最適化では、損失関数の平均勾配が特定の値よりも大きい場合、実現可能な集合の曲率を利用することができる。
本稿では、損失関数の曲率に適応したアルゴリズムが、実現可能な集合の曲率を活用できることを明らかにする。
論文 参考訳（メタデータ） (2024-02-20T09:59:33Z) - 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) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe
Algorithm under Parallelization [9.166498349629157]
2つの凸関数の和を最小化する問題を考える。
1つはリプシッツ連続勾配を持ち、オークルを介してアクセスでき、もう1つは「単純」である。
我々は、$tildeO (1/ sqrtepsilon)$ iterationsで$epsilon$prialdual gap(期待して)を達成することができることを示す。
論文 参考訳（メタデータ） (2022-05-25T13:01:09Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z) - Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly
Convex and Smooth Problems [14.924672048447334]
本稿では,関数列の第1次および第2次情報が予測可能である場合に,楽観的なニュートン法を提案する。
OGD に対して多重勾配を用いることで、後悔の時に$O(minC*_2,T,V_T) の上限を達成できる。
論文 参考訳（メタデータ） (2020-06-06T16:37:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。