論文の概要: Agnostic Smoothed Online Regression with Adversarial Responses

• arxiv url: http://arxiv.org/abs/2609.32478v1
• Date: Sat, 26 Sep 2026 11:17:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-07 08:46:35.264899
• Title: Agnostic Smoothed Online Regression with Adversarial Responses
• Title（参考訳）: 逆応答を伴う無作為な平滑なオンライン回帰
• Abstract要約: 本研究は,オンラインのスムーズな予測手法について検討する。 我々は,有界擬似次元を持つ関数クラスに対して,サブ線形後悔$widetildeO(sqrttextPdim(mathcalF) textsfC_textsfcov T)$を実現する情報理論アルゴリズムであるtextscHedge-Coverを提案する。
• 参考スコア（独自算出の注目度）: 11.637139366403636
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study smoothed online prediction with bounded adversarial responses. This widely studied framework bridges i.i.d. sampling and adversarial covariate selection through a smoothness parameter $\textsf{C}_{\textsf{cov}}$, which bounds conditional covariate densities relative to a fixed, unknown base measure. We propose \textsc{Hedge-Cover}, an information-theoretic algorithm that achieves sublinear regret $\widetilde{O}(\sqrt{\text{Pdim}(\mathcal{F}) \textsf{C}_{\textsf{cov}} T})$ for function classes with bounded pseudo-dimension. The algorithm aggregates a carefully constructed family of experts using \textsc{Hedge}, with a prior that links regret to the number of disagreements between a consistent selector and a target function. We bound this number by exploiting covariate smoothness. This answers an open problem posed in \cite{blanchard2025agnostic} on the minimax optimal adaptive regret of the smoothed online regression problem. We establish a matching lower bound for the class of linear predictors. The main intricacy of the lower bound lies in explicitly constructing a challenging sequential covariate distribution supported on mutually orthogonal hyperplanes. This construction may be of independent technical interest. Finally, we revisit the well-specified setting and quantify the effect of response noise. For conditionally $ν^2$-subGaussian responses, we extend the existing lower bound under realizable responses by showing that the minimax expected regret is $Ω((1\vee ν)\sqrt{(\textsf{C}_{\textsf{cov}}-1)dT})$ for a function class of VC dimension $d$. A corresponding upper bound for ERM matches this dependence on $ν$.
• Abstract（参考訳）: 本研究は,オンラインのスムーズな予測手法について検討する。 この広く研究されたフレームワークブリッジ(すなわち、スムーズネスパラメータ$\textsf{C}_{\textsf{cov}}$)は、固定された未知の基底測度に対して条件付き共変量密度を束縛する。 我々は,有界擬似次元を持つ関数クラスに対して,サブ線形後悔$\widetilde{O}(\sqrt{\text{Pdim}(\mathcal{F}) \textsf{C}_{\textsf{cov}} T}) を実現する情報理論アルゴリズムである \textsc{Hedge-Cover} を提案する。 このアルゴリズムは、一貫したセレクタとターゲット関数の間の相違点の数に後悔する先行する、‘textsc{Hedge} を使って慎重に構築された専門家の族を集約する。 私たちは同変数の滑らかさを利用してこの数を束縛する。 このことは、スムーズなオンライン回帰問題に対する最小限の最適適応的後悔について \cite{blanchard2025agnostic} で提起されたオープンな問題に答える。 線形予測器のクラスに対して一致する下界を確立する。 下界の主な複雑さは、相互直交超平面上で支持される挑戦的な逐次共変分布を明示的に構成することにある。 この建設は独立した技術的関心事であるかもしれない。 最後に、よく特定された設定を再検討し、応答雑音の影響を定量化する。 条件付き$ν^2$-subGaussian反応に対しては、VC次元の関数クラス$d$に対して、ミニマックス期待の後悔が$Ω((1\vee ν)\sqrt{(\textsf{C}_{\textsf{cov}}-1)dT})$であることを示して、既存の下界を実現可能な応答の下で拡張する。 ERMの対応する上限は、$ν$への依存と一致する。

関連論文リスト

• Polyhedral Instability Governs Regret in Online Learning [23.46151626569377]
  このような問題における後悔は,活動領域の変化の回数という,多面的不安定性によって支配されることを示す。 合成および実問題に関する実験は、予測スケーリングを検証し、動作の明示的な列挙なしに、実際に低不安定が生じることを示す。
  論文  参考訳（メタデータ） (2026-05-13T15:45:44Z)
• A Gap Between Decision Trees and Neural Networks [2.4140387101794283]
  ここでは、解釈可能性の概念として用いられる決定境界の幾何学的単純さが、浅いニューラルネットワークによる軸整列決定木の正確な近似と矛盾する場合について検討する。 分類するために、有限$mathrmRmathrmTV$で滑らかな障壁スコア$S_A$を構築し、その固定しきい値$=1$がボックスを正確に回復する。 長方形の合成結合の実験は、結果として生じる精度-複雑さのトレードオフを示している。
  論文  参考訳（メタデータ） (2026-01-07T13:40:30Z)
• Agnostic Smoothed Online Learning without Knowledge of the Base Measure [5.167069404528051]
  本稿では,$mu$の事前知識を必要とせずに,オンライン学習を円滑に行うためのサブ線形後悔を保証するアルゴリズムを提案する。 R-Coverは、次元$d$を持つ関数クラスに対して、適応的後悔$tilde O(sqrtdT/sigma)$を持つ。
  論文  参考訳（メタデータ） (2024-10-07T15:25:21Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Smoothed Analysis with Adaptive Adversaries [28.940767013349408]
  オンライン問題に対する新しいアルゴリズムの保証を平滑化解析モデルで証明する。 このモデルでは、敵は各時間に一様分布の$tfrac1sigma$倍の密度関数を持つ入力分布を選択する。 本研究の結果は,アルゴリズムの決定と前回の時間ステップにおける入力の実現に基づいて,入力分布を選択可能な適応的敵に対して成り立っている。
  論文  参考訳（メタデータ） (2021-02-16T20:54:49Z)

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

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