論文の概要: Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds

• arxiv url: http://arxiv.org/abs/2610.24370v1
• Date: Sat, 17 Oct 2026 01:50:08 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-20 11:46:32.026456
• Title: Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds
• Title（参考訳）: スムーズなオンライン学習の再考:競争率、切り替えコストによる動的レグレット、両世界のベスト
• Abstract要約: 競争率の向上, スイッチングコストによる最適な動的後悔, および両世界のベスト・オブ・ワールド保証を備えたアルゴリズムを開発した。 コンベックスの$$$quadratic成長のヒットコストでは、ヒットと正方形の$ell$-normスイッチングコストの適切な重み付けを最小化すれば、競争率は1+frac2sqrt$になる。 $ell$-normスイッチングコストによる動的後悔に対して、標準オンライン凸において最適な$O(sqrtT(1+P_T))$レートを達成するSmoothed Aderを開発する。
• 参考スコア（独自算出の注目度）: 18.8014726084153
• License:
• Abstract: We revisit smoothed online learning and develop algorithms with improved competitive ratios, optimal dynamic regret with switching cost, and best-of-both-worlds guarantees. Surprisingly, minimizing the hitting cost alone is $\max(1,\frac{2}α)$-competitive for $α$-polyhedral functions under the $\ell_2$-norm switching cost and $1+\frac{4}λ$-competitive for $λ$-quadratic growth functions under the squared $\ell_2$-norm switching cost, significantly improving existing guarantees. The polyhedral bound is tight for this naive algorithm, and we establish a matching lower bound for $α\geq1$. For convex $λ$-quadratic growth hitting costs, minimizing a suitably weighted sum of hitting and squared $\ell_2$-norm switching costs yields a competitive ratio of $1+\frac{2}{\sqrtλ}$. For dynamic regret with the $\ell_2$-norm switching cost, we develop Smoothed Ader (SAder), which achieves the optimal $O(\sqrt{T(1+P_T)})$ rate in the standard online convex optimization setting, where $P_T$ is the comparator's path-length. Its lookahead version removes the bounded-gradient assumption, and a matching lower bound establishes optimality in this setting. Finally, for convex hitting costs on a bounded convex domain, we develop UDNP to aggregate any two experts in the lookahead setting under both switching costs. Its additional cumulative cost is at most $O(1)$ relative to the first expert and $O(\sqrt{T\log T})$ relative to the second, yielding best-of-both-worlds guarantees without bounded gradients.
• Abstract（参考訳）: オンライン学習を円滑にし、競争率の向上、コストの切り替えによる動的後悔の最適化、両世界のベスト・オブ・ワールド保証といったアルゴリズムを開発しました。 驚いたことに、ヒットコストを最小化するのは$\max(1,\frac{2}α)$-competitive for $α$-polyhedral function under the $\ell_2$-norm switch cost と $1+\frac{4}λ$-competitive for $λ$-quadratic growth function under the squared $\ell_2$-norm switch cost である。 多面体境界はこの単純アルゴリズムに対して厳密であり、一致する下界を$α\geq1$とする。 convex $λ$-quadratic growth hit cost を最小にすると、$\ell_2$-norm switch cost は 1+\frac{2}{\sqrtλ}$ となる。 In the dynamic regret with the $\ell_2$-norm switch cost, we developed Smoothed Ader (SAder) which achieves the optimal $O(\sqrt{T(1+P_T)})$ rate in the standard online convex optimization set, where $P_T$ is the conparator's path-length。 そのルックアヘッドバージョンは有界次数的仮定を排除し、一致する下界はこの設定において最適性を確立する。 最後に,有界凸領域における凸打つコストに対して,両切替コストの下でのルックアヘッド設定における2つの専門家を集約するUDNPを開発する。 その追加累積コストは、第一の専門家と比較して$O(1)$、第二の専門家に対して$O(\sqrt{T\log T})$である。

関連論文リスト

• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Efficient Online Inverse Optimization with $O(d)$ Regret [26.77597743186513]
  オンライン逆線形最適化のための決定論的アルゴリズムを,残差$O(d)$,地平線一様,ラウンド毎の$O(d2)$時間で提供する。 この順序の境界は最近Dewasurendraによって得られたが、全てのスケールでカバーを列挙する不適切な規則により、1ラウンド当たり$T(d)の費用がかかる。
  論文  参考訳（メタデータ） (2026-09-11T18:55:31Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets [0.0]
  ネストした縮小可能な領域を2つの設定でオンライン最適化する。 懸念されている最小限の試験と累積余剰試験は、後悔の保証を保っている。 決定論的リセット可能なネスト付き凸体チェッカーは運動を制限する。
  論文  参考訳（メタデータ） (2026-08-29T06:01:56Z)
• Convex Optimization with Nested Evolving Feasible Sets [4.67724003380452]
  両ケースに対して$o(T)$ regretのオンラインアルゴリズムが$(logT)$の移動コストを持ち、Frugalの最適性を証明していることを示す。 また、$o(T)$ regretのオンラインアルゴリズムは、両方のケースに対して$(logT)$の移動コストを持ち、Frugalの最適性を証明することも示している。
  論文  参考訳（メタデータ） (2026-05-08T07:42:15Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。