論文の概要: Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise

• arxiv url: http://arxiv.org/abs/2607.27073v1
• Date: Wed, 29 Jul 2026 15:58:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-30 21:06:25.73351
• Title: Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise
• Title（参考訳）: 重音下におけるオンライン凸最適化のためのパラメータフリーダイナミックレグレット
• Abstract要約: 重音下での非定常環境におけるオンライン凸最適化(OCO)について検討した。 ブロック長の幾何プール上に再起動したAdaGrad専門家を組み合わせたパラメータフリーアルゴリズムである textbfHT-PAder を提案する。 有限分散(p=2$)の特別な場合であっても、HT-パダーはパラメータフリーのミニマックスの普遍的後悔保証を提供する。
• 参考スコア（独自算出の注目度）: 55.29259818039367
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online convex optimization (OCO) in non-stationary environments under heavy-tailed noise, where the stochastic gradient oracle admits only a finite $p$-th central moment for some $p \in (1, 2]$. While static regret is well-understood, achieving universal dynamic regret in a parameter-free manner remains an open challenge. We resolve this by proposing \textbf{HT-PAder}, a parameter-free algorithm combining restarted AdaGrad experts over a geometric pool of block lengths with a pathwise meta-algorithm, \textbf{AdaGrad-Hedge}, which requires no moment conditions on meta-losses. For a domain of diameter $D$, Lipschitz constant $G$, noise level $σ$, and comparator path length $P_T$, HT-PAder achieves an expected universal dynamic regret of \[ \widetilde O\left( GD\sqrt{T(1+P_T/D)} + σD T^{1/p}(1+P_T/D)^{(p-1)/p} \right). \] The algorithm does not require prior knowledge of any of these problem parameters. Even in the special case of finite variance ($p=2$), HT-PAder provides the first parameter-free minimax universal dynamic regret guarantee. We also prove a matching lower bound, establishing the optimality of the path-length exponent.
• Abstract（参考訳）: 重み付き雑音下でのオンライン凸最適化 (OCO) について検討し, 確率勾配オラクルは, 約1, 2]$に対して, 有限$p$-th中心モーメントのみを許容する。 静的な後悔はよく理解されているが、パラメータのない方法で普遍的な動的後悔を達成することは、未解決の課題である。 本稿では,メタロスのモーメント条件を必要としないブロック長の幾何学的プール上に,再起動したAdaGrad専門家を併用したパラメータフリーアルゴリズムである \textbf{HT-PAder} を提案する。 直径$D$, Lipschitz constant $G$, noise level $σ$, and comparator path length $P_T$, HT-PAder は \[ \widetilde O\left(GD\sqrt{T(1+P_T/D)} + σD T^{1/p}(1+P_T/D)^{(p-1)/p} \right の普遍的動的後悔を達成する。 \] このアルゴリズムはこれらの問題のパラメータの事前の知識を必要としない。 有限分散(p=2$)の特別な場合であっても、HT-パダーはパラメータフリーのミニマックスの普遍的後悔保証を提供する。 また、一致した下界を証明し、経路長指数の最適性を確立する。

関連論文リスト

• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• PAC global optimization for VQE in low-curvature geometric regimes [0.3553493344868413]
  変分量子固有解法における大域的な$varepsilon$-optimalityのノイズロスト保証 Morse--Bott 部分多様体は座標整列な埋め込みフラットに対してファイバー正則性を満たす。
  論文  参考訳（メタデータ） (2025-11-18T16:18:26Z)
• Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
  拡張逆数(SEA)モデルの既存のアプローチは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識を必要とする。 パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。
  論文  参考訳（メタデータ） (2025-10-06T10:53:37Z)
• Dynamic Regret Reduces to Kernelized Static Regret [63.36965242404415]
  本研究では,オンライン凸最適化において,任意のベンチマークシーケンスに対して低累積損失を達成することを目的とした動的後悔について検討する。 再生ケルネルヒルベルト空間 (RKHS) の形で適切な関数空間を構築することにより、最適$R_T(u_1,ldots,u_T) = MathcalO(sqrtsum_t|u_t-u_t-1|T)$ dynamic regret guarantee。
  論文  参考訳（メタデータ） (2025-07-07T21:09:33Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。 そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
  論文  参考訳（メタデータ） (2022-11-03T14:41:46Z)

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

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