論文の概要: Improved Dynamic Regret for Online Frank-Wolfe
- arxiv url: http://arxiv.org/abs/2302.05620v1
- Date: Sat, 11 Feb 2023 07:19:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 19:29:09.089545
- Title: Improved Dynamic Regret for Online Frank-Wolfe
- Title(参考訳): オンラインフランクウルフにおける動的レグレットの改善
- Authors: Yuanyu Wan and Lijun Zhang and Mingli Song
- Abstract要約: オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより、OFWの動的後悔境界を改善した。
- 参考スコア(独自算出の注目度): 52.709213334244495
- 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}(1+V_T+\sqrt{D_T}))$ 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(1+V_T)})$ for smooth functions. Second, we
achieve a better dynamic regret bound of $O((1+V_T)^{2/3}T^{1/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(1+V_T)$, 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}(1+V_T+\sqrt{D_T})$ の動的後悔境界を定めているだけで、$T$ はラウンド数、$V_T$ は関数変分、$D_T$ は勾配変分である。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界を改善する。
この拡張の鍵となるテクニックは、行探索ルールでOwのステップサイズを設定することである。
このようにして、まず、ofw の動的後悔境界は滑らかな関数に対して $o(\sqrt{t(1+v_t)})$ に改善できることを示した。
次に、関数が滑らかで強い凸であり、制約集合が強い凸であるときに、より優れた動的後悔値が$o((1+v_t)^{2/3}t^{1/3})$となる。
最後に、制約集合の内部に最小値を持つ滑らかで強い凸関数に対して、OWの動的後悔は$O(1+V_T)$に減少し、さらに$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 [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) - 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) - Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。
強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文 参考訳(メタデータ) (2021-03-21T11:43:35Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。