論文の概要: Non-Stationary Online Structured Prediction with Surrogate Losses

• arxiv url: http://arxiv.org/abs/2510.07086v1
• Date: Wed, 08 Oct 2025 14:43:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.568098
• Title: Non-Stationary Online Structured Prediction with Surrogate Losses
• Title（参考訳）: 代理損失を考慮した非定常オンライン構造化予測
• Authors: Shinsaku Sakaue, Han Bao, Yuzhou Cao,
• Abstract要約: 累積目標損失に対して$F_T + C (1 + P_T)$という形の有界性を証明する。 我々の中核となる考え方は、勾配オンライン降下(OGD)の動的後悔境界を代理ギャップを利用する手法で合成することである。 我々はまた、OGDのための新しいPolyakスタイルの学習率にも光を当てています。
• 参考スコア（独自算出の注目度）: 22.848052937383244
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online structured prediction, including online classification as a special case, is the task of sequentially predicting labels from input features. Therein the surrogate regret -- the cumulative excess of the target loss (e.g., 0-1 loss) over the surrogate loss (e.g., logistic loss) of the fixed best estimator -- has gained attention, particularly because it often admits a finite bound independent of the time horizon $T$. However, such guarantees break down in non-stationary environments, where every fixed estimator may incur the surrogate loss growing linearly with $T$. We address this by proving a bound of the form $F_T + C(1 + P_T)$ on the cumulative target loss, where $F_T$ is the cumulative surrogate loss of any comparator sequence, $P_T$ is its path length, and $C > 0$ is some constant. This bound depends on $T$ only through $F_T$ and $P_T$, often yielding much stronger guarantees in non-stationary environments. Our core idea is to synthesize the dynamic regret bound of the online gradient descent (OGD) with the technique of exploiting the surrogate gap. Our analysis also sheds light on a new Polyak-style learning rate for OGD, which systematically offers target-loss guarantees and exhibits promising empirical performance. We further extend our approach to a broader class of problems via the convolutional Fenchel--Young loss. Finally, we prove a lower bound showing that the dependence on $F_T$ and $P_T$ is tight.
• Abstract（参考訳）: オンライン分類を含むオンライン構造化予測は、入力特徴からラベルを逐次予測するタスクである。 ここでは、固定ベスト推定器のサロゲート損失(例えば、ロジスティック損失)に対する目標損失(例えば、0-1損失)の累積超過が注目されている。 しかし、そのような保証は、固定推定器が全て$T$で線形に増加するような非定常環境において破られる。 ここでは、累積的目標損失に対して$F_T + C(1 + P_T)$という形式の有界を証明し、そこでは$F_T$は任意のコンパレータ列の累積的代理損失であり、$P_T$はその経路長であり、$C > 0$は一定である。 このバウンダリは$F_T$と$P_T$を通してのみ$T$に依存しており、しばしば非定常環境においてより強い保証をもたらす。 我々の中核となる考え方は、代理ギャップを利用したオンライン勾配降下(OGD)の動的後悔境界を合成することである。 我々はまた、OGDのための新しいPolyakスタイルの学習率にも光を当てています。 我々はさらに、Fenchel-Young損失を通じて、より広範な問題にアプローチを拡張します。 最後に、$F_T$と$P_T$への依存が厳密であることを証明する。

関連論文リスト

• Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification [27.33243506775655]
  分離線形分類のための非正規化手法の一般化性能について検討する。 収束速度は損失テンプレートの幾何に大きく影響されていることを示す。
  論文  参考訳（メタデータ） (2025-05-28T13:39:14Z)
• Any-stepsize Gradient Descent for Separable Data under Fenchel--Young Losses [17.835960292396255]
  emphFenchel-Young損失の枠組みに基づく一般損失関数に対して任意のステップの勾配収束を示す。 我々は、自己有界性の代わりに損失関数の分岐マージンによって、これらのより良いレートが可能であると論じる。
  論文  参考訳（メタデータ） (2025-02-07T12:52:12Z)
• Revisiting Projection-Free Online Learning with Time-Varying Constraints [35.573654458435854]
  我々は制約付きオンライン凸最適化について検討し、そこでは決定は固定的で典型的には複雑な領域に属する必要がある。 いくつかのプロジェクションフリーな手法が$mathcalO(T3/4 sqrtlog T)$ regret boundと$mathcalO(T3/4 sqrtlog T)$ cumulative constraint violation (CCV) bound for general convex lossで提案されている。 本稿では,損失関数が強凸である場合に,この結果を改善し,さらにテクスチノーベルの後悔とCCV境界を確立する。
  論文  参考訳（メタデータ） (2025-01-27T13:38:51Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  逆制約を伴うオンライン凸最適化(OCO)について検討する。 本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。 以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
  論文  参考訳（メタデータ） (2024-12-11T03:06:42Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Realizable $H$-Consistent and Bayes-Consistent Loss Functions for Learning to Defer [30.389055604165222]
  非増加関数の$Psi$によってパラメータ化され、穏やかな条件下で実現可能な$H$一貫性を確立する。 分類誤差に基づくコスト関数の場合、これらの損失は仮説集合が対称かつ完全であるときに$H$一貫性境界を持つことを示す。
  論文  参考訳（メタデータ） (2024-07-18T17:35:03Z)
• 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)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• The Adversarial Consistency of Surrogate Risks for Binary Classification [20.03511985572199]
  逆行訓練は、各例が小さなボール内で悪質に破損する可能性がある場合に、予想される0$-$1$損失を最小限にすることを目指している。 我々は、一貫した代理損失関数の集合の単純かつ完全な特徴づけを与える。 本結果から, 逆一貫したサロゲートのクラスは, 標準設定よりもかなり小さいことが明らかとなった。
  論文  参考訳（メタデータ） (2023-05-17T05:27:40Z)

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

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