論文の概要: Optimal Multiclass U-Calibration Error and Beyond

• arxiv url: http://arxiv.org/abs/2405.19374v1
• Date: Tue, 28 May 2024 20:33:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-31 19:35:57.055493
• Title: Optimal Multiclass U-Calibration Error and Beyond
• Title（参考訳）: 最適マルチクラスU-キャリブレーション誤差とそれを超えるもの
• Authors: Haipeng Luo, Spandan Senapati, Vatsal Sharan,
• Abstract要約: オンラインマルチクラス境界U-キャリブレーションの問題は、予測器がU-キャリブレーション誤差の低いクラスをK$で逐次分布予測することを目的としている。 最適U校正誤差は$Theta(sqrtKT)$である。
• 参考スコア（独自算出の注目度）: 31.959887895880765
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of online multiclass U-calibration, where a forecaster aims to make sequential distributional predictions over $K$ classes with low U-calibration error, that is, low regret with respect to all bounded proper losses simultaneously. Kleinberg et al. (2023) developed an algorithm with U-calibration error $O(K\sqrt{T})$ after $T$ rounds and raised the open question of what the optimal bound is. We resolve this question by showing that the optimal U-calibration error is $\Theta(\sqrt{KT})$ -- we start with a simple observation that the Follow-the-Perturbed-Leader algorithm of Daskalakis and Syrgkanis (2016) achieves this upper bound, followed by a matching lower bound constructed with a specific proper loss (which, as a side result, also proves the optimality of the algorithm of Daskalakis and Syrgkanis (2016) in the context of online learning against an adversary with finite choices). We also strengthen our results under natural assumptions on the loss functions, including $\Theta(\log T)$ U-calibration error for Lipschitz proper losses, $O(\log T)$ U-calibration error for a certain class of decomposable proper losses, U-calibration error bounds for proper losses with a low covering number, and others.
• Abstract（参考訳）: オンラインマルチクラスU-キャリブレーションの問題を考えると、予測者はU-キャリブレーション誤差が低いクラスに対して連続的な分布予測を行うことを目標としている。 Kleinberg et al (2023) は U-calibration error $O(K\sqrt{T})$ after $T$ rounds というアルゴリズムを開発した。 我々は、最適U校正誤差が$\Theta(\sqrt{KT})$ -- まず、ダスカラキスとシルグカニスのFollow-the-Perturbed-Leaderアルゴリズム(2016)がこの上限を達成し、その後、特定の適切な損失で構築された一致した下限が続くという単純な観察から始める。 また、損失関数に関する自然な仮定では、Lipschitz の固有損失に対して $\Theta(\log T)$ U-calibration error, $O(\log T)$ U-calibration error for a certain class of decomposable proper loss, U-calibration error bounds for proper loss with a low covered number などである。

関連論文リスト

• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
  敵は、学習者に未知の任意の数kの損失関数を破損させることで、外れ値を導入することができる。 我々は,任意の数kで損失関数を破損させることで,敵が外乱を発生させることができる,頑健なオンラインラウンド最適化フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-12T17:08:31Z)
• Deep learning from strongly mixing observations: Sparse-penalized regularization and minimax optimality [0.0]
  ディープニューラルネットワーク予測器のスパースペナル化正規化について検討する。 正方形と幅広い損失関数を扱う。
  論文  参考訳（メタデータ） (2024-06-12T15:21:51Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• 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)
• Asymptotic Characterisation of Robust Empirical Risk Minimisation Performance in the Presence of Outliers [18.455890316339595]
  我々は,次元$d$とデータ点数$n$が固定比$alpha=n/d$で分岐した場合,高次元の線形回帰について検討し,出力率を含むデータモデルについて検討する。 我々は、$ell$-regularized $ell$, $ell_$, Huber損失を用いて、経験的リスク最小化(ERM)のパフォーマンスの正確性を提供する。
  論文  参考訳（メタデータ） (2023-05-30T12:18:39Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Black-Box Generalization [31.80268332522017]
  微分一般化によるブラックボックス学習のための最初の誤り解析を行う。 どちらの一般化も独立$d$,$K$であり、適切な選択の下では学習率がわずかに低下していることを示す。
  論文  参考訳（メタデータ） (2022-02-14T17:14:48Z)
• Scale-free Unconstrained Online Learning for Curved Losses [1.5147172044848798]
  コンパレータのノルム$U$と勾配の最大ノルム$G$に同時に適応する可能性を検討する。 意外なことに、最近の研究では1ドル=Lipschitz損失の特定のケースにおいて、適応性に対するそのような価格が不要であることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T14:10:35Z)
• Localization, Convexity, and Star Aggregation [0.0]
  オフセットラデマッハ複体は、正方形損失に対する鋭く線形依存的な上界を示すことが示されている。 統計的設定では、オフセット境界は一定の均一な凸性を満たす任意の損失に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-19T00:47:59Z)

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

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