論文の概要: Dirichlet Follow-the-Leader Closes the Gap in Simultaneous Multiclass U-Calibration

• arxiv url: http://arxiv.org/abs/2608.06656v1
• Date: Fri, 07 Aug 2026 00:02:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-10 16:21:25.305913
• Title: Dirichlet Follow-the-Leader Closes the Gap in Simultaneous Multiclass U-Calibration
• Title（参考訳）: Dirichlet Follow-the-Leader が同時多クラス U-Calibration でギャップを閉じる
• Abstract要約: 自己一致による摂動は、約$K5/4sqrtT$最悪の後悔を与える。 追加の$sqrtKlog K$を$-smooth損失で調達する。 両方のギャップを1行の予測器で埋めます。
• 参考スコア（独自算出の注目度）: 1.14219428942199
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Can one forecaster attain the optimal regret rate for every bounded proper loss and also adapt to every smooth proper loss? Recent work answered this up to a dimension gap. Its self-concordant perturbation gives roughly $K^{5/4}\sqrt{T}$ worst-case regret and incurs an additional $β\sqrt{K}\log K$ for $β$-smooth losses. We close both gaps with a one-line forecaster. After observing class counts $c_{t-1}$, draw the next prediction from $\operatorname{Dir}(c_{t-1})$, on the face of classes seen so far. This is a fresh Bayesian bootstrap of the outcomes. The analysis rests on an exact identity: averaging any bounded proper loss under $\operatorname{Dir}(α)$ equals a discrete derivative of its Dirichlet-averaged Bayes risk. The identity makes the be-the-perturbed-leader term telescope to a nonpositive Jensen gap. A one-count likelihood ratio then bounds stability by the inverse square root of that class's count. The resulting single, horizon-free algorithm satisfies $\sup_{\ell}\mathbb{E}\operatorname{Reg}_{\ell}\leq 4\sqrt{S_T T}\leq 4\sqrt{K T}$ and $\mathbb{E}\operatorname{Reg}_{\ell}\leq \frac{5}{2}β(1+\log T)$ for every $β$-smooth proper loss. Here $S_T$ is the number of observed classes. Known lower bounds show that both rates are optimal in their nontrivial regimes. The proof covers nondifferentiable losses and changes of the active simplex face.
• Abstract（参考訳）: ある予測者は、有界な適切な損失に対して最適な後悔率を達成でき、また、スムーズな適切な損失に対して適応できるだろうか? 最近の研究で、この答えは次元ギャップにまで達した。 その自己調和摂動は、およそ$K^{5/4}\sqrt{T}$最悪のケースの後悔を与え、さらに$β\sqrt{K}\log K$$$β$-smooth損失をもたらす。 両方のギャップを1行の予測器で埋めます。 クラスが$c_{t-1}$を数えたら、$\operatorname{Dir}(c_{t-1})$から次の予測を引き出す。 これはベイズ時代の新たなブートストラップである。 平均的な有界固有損失を $\operatorname{Dir}(α)$ で表すと、ディリクレ平均ベイズリスクの離散微分と等しい。 このアイデンティティは、望遠鏡を非正のジェンセンギャップへと誘導する。 一員数確率比は、そのクラスのカウントの逆二乗根によって安定性を束縛する。 結果として得られる1つの水平なアルゴリズムは、$\sup_{\ell}\mathbb{E}\operatorname{Reg}_{\ell}\leq 4\sqrt{S_T T}\leq 4\sqrt{K T}$と$\mathbb{E}\operatorname{Reg}_{\ell}\leq \frac{5}{2}β(1+\log T)$を、すべての$β$-smooth純損失に対して満足する。 ここで$S_T$は観測されたクラスの数です。 既知の下界は、どちらも非自明な状態において最適であることを示している。 この証明は、非微分不能な損失と活性単純面の変化をカバーしている。

関連論文リスト

• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Multiscale Reward Hedging from Correct Demonstrations [1.14219428942199]
  既存の報酬ヘッジ保証は、有限報酬クラスを仮定する。 鍵となるのは、あらゆる精度の尺度で寛容な最適性テストよりも、ひとつの共有投票でヘッジすることです。
  論文  参考訳（メタデータ） (2026-08-07T05:36:22Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• Solving Stochastic Fixed-Point Equations with High Probability [22.376855234542813]
  オラクルの不動点方程式 $mathbfT(mathbfx) = mathbfx$ をノルム空間上で研究する。 本稿では,2次スムーズなバナッハ空間に対する分散還元段階Halpern法であるVR-GHALを紹介する。
  論文  参考訳（メタデータ） (2026-07-10T04:59:20Z)
• Online Convex Optimization with Sublinear Noisy Probes [6.998574163422056]
  オンライン凸最適化(OCO)を凸集合として$Ksubseteq mathbb Rd$で検討する。 我々は最近の2つの作業の行を一般化する統一された探索モデルを導入する: 専門家設定におけるサブ線形ベストエキスパートクエリと、OCOの各ラウンドで利用できるペアワイズフィードバックである。 本研究の主目的は, サブリニアでノイズの多いプローブ予算であっても, OCO体制の完全なフィードバックにおける最悪の後悔を確実に改善できることである。
  論文  参考訳（メタデータ） (2026-06-12T17:05:08Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
  論文  参考訳（メタデータ） (2025-06-06T20:33:57Z)
• Omnipredictors for Regression and the Approximate Rank of Convex Functions [7.549720420141907]
  クラス $mathcal L$ の損失関数とクラス $mathcal C$ の損失予測器は、$mathcal L$ の損失毎に $mathcal C$ の最良の仮説よりも予想される損失が少ない予測器である。
  論文  参考訳（メタデータ） (2024-01-26T04:29:53Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• Differentially Private Generalized Linear Models Revisited [30.298342283075176]
  本研究では,凸損失のある線形予測器の差分学習における$(epsilon,delta)$-differentially private Learningの問題について検討する。 特に, $tildeOleft(fracVert w*Vertsqrtn + minleftfracVert w*Vert4/3(nepsilon)2/3, fracsqrtdVert w*Vertnepsilon の過剰集団リスクの低い境界を示す。
  論文  参考訳（メタデータ） (2022-05-06T05:01:02Z)
• 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)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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