論文の概要: Non-stationary Projection-free Online Learning with Dynamic and Adaptive
Regret Guarantees
- arxiv url: http://arxiv.org/abs/2305.11726v1
- Date: Fri, 19 May 2023 15:02:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 13:59:41.840362
- Title: Non-stationary Projection-free Online Learning with Dynamic and Adaptive
Regret Guarantees
- Title（参考訳）: 動的および適応的後悔を保証した非定常プロジェクションフリーオンライン学習
- Authors: Yibo Wang, Wenhao Yang, Wei Jiang, Shiyin Lu, Bing Wang, Haihong Tang,
Yuanyu Wan, Lijun Zhang
- Abstract要約: 本研究では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価を行った。
我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、既存の$mathcalO(T3/4)$static regretを復元することができる。
本稿では,$tildemathcalO(tau3/4)$ アダプティブリフレッシュバウンドを長さ$tauの任意の間隔で達成するためのプロジェクションフリーな手法を提案する。
- 参考スコア（独自算出の注目度）: 36.746745619968024
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Projection-free online learning has drawn increasing interest due to its
efficiency in solving high-dimensional problems with complicated constraints.
However, most existing projection-free online methods focus on minimizing the
static regret, which unfortunately fails to capture the challenge of changing
environments. In this paper, we investigate non-stationary projection-free
online learning, and choose dynamic regret and adaptive regret to measure the
performance. Specifically, we first provide a novel dynamic regret analysis for
an existing projection-free method named $\text{BOGD}_\text{IP}$, and establish
an $\mathcal{O}(T^{3/4}(1+P_T))$ dynamic regret bound, where $P_T$ denotes the
path-length of the comparator sequence. Then, we improve the upper bound to
$\mathcal{O}(T^{3/4}(1+P_T)^{1/4})$ by running multiple $\text{BOGD}_\text{IP}$
algorithms with different step sizes in parallel, and tracking the best one on
the fly. Our results are the first general-case dynamic regret bounds for
projection-free online learning, and can recover the existing
$\mathcal{O}(T^{3/4})$ static regret by setting $P_T = 0$. Furthermore, we
propose a projection-free method to attain an $\tilde{\mathcal{O}}(\tau^{3/4})$
adaptive regret bound for any interval with length $\tau$, which nearly matches
the static regret over that interval. The essential idea is to maintain a set
of $\text{BOGD}_\text{IP}$ algorithms dynamically, and combine them by a meta
algorithm. Moreover, we demonstrate that it is also equipped with an
$\mathcal{O}(T^{3/4}(1+P_T)^{1/4})$ dynamic regret bound. Finally, empirical
studies verify our theoretical findings.
- Abstract（参考訳）: 投影のないオンライン学習は、複雑な制約を伴う高次元問題の解法における効率性から、関心が増している。
しかし、既存のプロジェクションフリーなオンラインメソッドの多くは、静的な後悔を最小限に抑えることに重点を置いている。
本稿では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価する。
具体的には、まず、既存のプロジェクションフリーなメソッドである$\text{BOGD}_\text{IP}$に対して新しい動的後悔解析を行い、$\mathcal{O}(T^{3/4)(1+P_T))$ dynamic regret boundを設定し、$P_T$はコンパレータシーケンスのパス長を表す。
次に、ステップサイズが異なる複数の$\text{bogd}_\text{ip}$アルゴリズムを並列に実行し、オンザフライで最高のアルゴリズムを追跡することで、上限を$\mathcal{o}(t^{3/4}(1+p_t)^{1/4})$に改善する。
我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、$P_T = 0$を設定して既存の$\mathcal{O}(T^{3/4})$静的後悔を取り戻すことができる。
さらに,長さ$\tau$の任意の区間に拘束された$\tilde{\mathcal{o}}(\tau^{3/4})$適応的後悔を,その区間で静的な後悔とほぼ一致するような投影不要な方法を提案する。
基本的な考え方は、$\text{BOGD}_\text{IP}$アルゴリズムを動的に維持し、それらをメタアルゴリズムで組み合わせることである。
さらに、$\mathcal{O}(T^{3/4)(1+P_T)^{1/4})$ dynamic regret boundも備えていることを示す。
最後に、実証研究は理論的な結果を検証する。
関連論文リスト
- Online Convex Optimization with a Separation Oracle [10.225358400539719]
本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
論文 参考訳（メタデータ） (2024-10-03T13:35:08Z) - An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。
R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-06-03T17:54:58Z) - Improved Projection-free Online Continuous Submodular Maximization [35.324719857218014]
単調かつ連続DR-サブモジュラー報酬関数を用いたオンライン学習の問題点について検討する。
従来の研究では、$O(T)$グラデーション評価を用いたMono-Frank-Wolfe (Mono-FW)と呼ばれる効率的なプロジェクションフリーアルゴリズムが提案されている。
同じ計算量を維持しつつ, 後悔を$O(T3/4)$に抑える改良されたプロジェクションフリーアルゴリズム(POBGA)を提案する。
論文 参考訳（メタデータ） (2023-05-29T02:54:31Z) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - 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) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - Improved Analysis for Dynamic Regret of Strongly Convex and Smooth
Functions [24.445848532264307]
OMGDの動的な後悔は、少なくとも$mathcalO(minmathcalP_T,mathcalS_T)$であり、$mathcalP_T$と$mathcalS_T$はパス長と2乗パス長である。
我々は、改良された解析により、OMGDの動的後悔を$mathcalO(minmathcalP_T,mathcalS_T,mathcalに改善できることを実証した。
論文 参考訳（メタデータ） (2020-06-10T15:01:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。