Fugu-MT 論文翻訳(概要): The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

論文の概要: The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

arxiv url: http://arxiv.org/abs/2608.04686v1
Date: Wed, 05 Aug 2026 10:53:13 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-06 14:48:43.831219
Title: The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences
Title（参考訳）: クレッシー下の分散ロバストPAC学習のサンプル複雑さ--読解の多様性-
Authors: Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss,
Abstract要約: 我々は,データ分布の逆摂動が Cressie-Read divergence of order $k>1$ and radius $geq 0$ で制約されるような$0$--1$-lossのPAC学習について検討した。 VC次元が$d$の仮説クラスに対して、実現可能かつ非依存的なサンプル-複雑性は定数および対数的因子に密接な境界を定めている。
参考スコア（独自算出の注目度）: 4.588028371034407
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study distributionally robust PAC learning for the $0$--$1$-loss, where adversarial perturbations of the data distribution are constrained by a Cressie--Read divergence of order $k>1$ and radius $ρ\geq 0$. For hypothesis classes with VC dimension $d$, we establish realizable and agnostic sample-complexity bounds tight up to constant and logarithmic factors, respectively; ordinary empirical risk minimization attains both rates up to logarithmic factors. For target accuracy $\varepsilon\in(0,1)$ and confidence $δ\in(0,1)$, their respective orders are \[ \max\!\left\{\frac{1}{\varepsilon}, \frac{ρ^{\frac 1{k-1}}}{\varepsilon^{k_\star}} \right\}\cdot(d+\log δ^{-1}) \qquad\text{and}\qquad \max\!\left\{\frac{1}{\varepsilon^2}, \frac{ρ^{\frac1{k-1}}}{\varepsilon^{k_\star\vee 2}} \right\}\cdot(d+\log δ^{-1}), \] where $k_\star={k}/{(k-1)}$. For every fixed $ρ>0$, robustness changes the realizable $\varepsilon$-dependence from $\varepsilon^{-1}$ to $\varepsilon^{-k_\star}$ as $\varepsilon\downarrow0$. In the agnostic case, for $1<k<2$, robustness changes the $\varepsilon$-dependence from $\varepsilon^{-2}$ to $\varepsilon^{-k_\star}$, whereas for $k\geq2$ the exponent remains the classical $2$, with nontrivial $ρ$-dependence. Building on the known scalar reduction of robust $0$--$1$ risk to ordinary classification error, our analysis reveals a scale-sensitive interaction between the statistical estimation of classification error and its amplification by robustness, sharply explaining the transition in the agnostic rate. We extend the previously studied $χ^2$-divergence case to every Cressie--Read order $k>1$, close its upper--lower gaps, and recover standard PAC learning rates as $ρ\to0$, unlike previous bounds that fail to interpolate correctly in this limit.
Abstract（参考訳）: 本研究では,データ分布の逆摂動が Cressie-Read divergence of order $k>1$ and radius $ρ\geq 0$ で制約されるような,0$--1$-lossの分散ロバストなPAC学習について検討する。 VC次元が$d$の仮説クラスでは、実効性および非特異なサンプル-複雑度はそれぞれ、定数および対数的要因に密接な境界を定め、通常の経験的リスク最小化は、対数的要因までの両方の速度を達成できる。目標精度$\varepsilon\in(0,1)$と信頼$δ\in(0,1)$に対して、それぞれの順序は \[ \max\! \left\{\frac{1}{\varepsilon}, \frac{ρ^{\frac 1{k-1}}}{\varepsilon^{k_\star}} \right\}\cdot(d+\log δ^{-1}) \qquad\text{and}\qquad \max\! \left\{\frac{1}{\varepsilon^2}, \frac{ρ^{\frac1{k-1}}}{\varepsilon^{k_\star\vee 2}} \right\}\cdot(d+\log δ^{-1}), \] ここで$k_\star={k}/{(k-1)}$。すべての固定された$ρ>0$に対して、ロバストネスは実現可能な$\varepsilon$-dependenceを$\varepsilon^{-1}$から$\varepsilon^{-k_\star}$へ変更する。 1<k<2$の場合、ロバストネスは$\varepsilon$-dependenceを$\varepsilon^{-2}$から$\varepsilon^{-k_\star}$に変更する。通常の分類誤差に対する0$--1$リスクのスカラー化が知られていることから, 分類誤差の統計的推定とロバスト性による増幅とのスケール敏感な相互作用が明らかとなり, 不可知率の推移を強く説明できる。我々は、以前に研究された$ ^2$-divergence ケースをすべての Cressie--Read order $k>1$ に拡張し、その上から下へのギャップを閉じ、標準の PAC 学習率を $ρ\to0$ に回復する。

論文の概要: The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

関連論文リスト