論文の概要: Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate
- arxiv url: http://arxiv.org/abs/2610.13442v1
- Date: Fri, 09 Oct 2026 11:44:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-13 04:06:29.556714
- Title: Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate
- Title（参考訳）: 圧縮による学習:リスク推定値が大小算数の法則に達する
- Abstract要約: 固定信頼レベルが1-$であれば、リスクは少なくとも$$$1-$×$$ fracboldsymbolkN + Oleft(frac1sqrtNright),$$$$$は$boldsymbolkNの可能なすべての値に対して一様であることを示す。
また, 先行語である$boldsymbolk/N$は必要であり, 経験的リスクとの関係について検討する。
- 参考スコア（独自算出の注目度）: 5.901309581539199
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Compression schemes provide a general framework for deriving data-dependent risk bounds for learning algorithms. For learning rules based on preferent compression, existing results upper-bound the risk in terms of a sample-dependent complexity $\boldsymbol{k}$, defined as the cardinality of the compression augmented by the training examples on which the reconstructed hypothesis is inappropriate. These results, however, yield a margin of order $O(\sqrt{\ln N/N})$ above $\boldsymbol{k}/N$. In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed confidence level $1-δ$, the risk is bounded with probability at least $1-δ$ by $$ \frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right), $$ uniformly over all possible values of $\boldsymbol{k}$. Thus, risk estimates for learning algorithms based on preferent compression attain the same law-of-large-numbers rate as the empirical estimate of the probability of a fixed event. We also show that the leading term $\boldsymbol{k}/N$ is necessary and investigate its relation to the empirical risk. In particular, we identify regimes in which the empirical risk retains the $O(1/\sqrt{N})$ convergence rate, as well as regimes in which it converges more slowly or ceases to be consistent, while the complexity-based estimator preserves the $O(1/\sqrt{N})$ rate.
- Abstract（参考訳）: 圧縮スキームは、学習アルゴリズムのためのデータ依存リスク境界を導出するための一般的なフレームワークを提供する。
優先的な圧縮に基づく学習規則について、既存の結果は、再構成された仮説が不適切である訓練例によって強化された圧縮の基数として定義される、サンプル依存の複雑さ$\boldsymbol{k}$という観点でリスクを上限にしている。
しかし、これらの結果は位数$O(\sqrt{\ln N/N})$以上の$\boldsymbol{k}/N$のマージンを与える。
本稿では,対数係数が本質的でないことを示す。
固定信頼度 1-δ$ に対して、リスクは少なくとも 1-δ$ の確率で$$$ \frac {\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right),$$$\boldsymbol{k}$ のすべての可能な値に対して一様であることを示す。
このように、優先圧縮に基づく学習アルゴリズムのリスク推定は、固定事象の確率の実証的な推定値と同一数の法則を達成できる。
また、先頭項 $\boldsymbol{k}/N$ が必須であることを示し、経験的リスクとの関係について検討する。
特に、経験的リスクが$O(1/\sqrt{N})$収束率を保持するレジームと、よりゆっくり収束するか、一貫性が保たれるレジームを識別する一方、複雑性に基づく推定器は$O(1/\sqrt{N})$収束率を保持する。
関連論文リスト
- Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。
我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
論文 参考訳（メタデータ） (2026-08-06T19:49:48Z) - Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。
任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。
本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
論文 参考訳（メタデータ） (2026-02-19T17:21:15Z) - Risk reversal for least squares estimators under nested convex constraints [0.0]
制約付き最適化において、より厳密な実現可能な集合を課すことは、射影によって定義される推定器の統計的リスクをその集合に増加させないことを自然に期待する。
この直観は標準設定でも失敗する可能性があることを示す。
論文 参考訳（メタデータ） (2026-01-22T15:18:36Z) - Super-fast rates of convergence for Neural Networks Classifiers under the Hard Margin Condition [9.993044620455338]
DNNは二乗損失代理と$ell_p$ペナルティによる経験的リスクを最小限に抑えることができ、ハードマージン条件下では、任意の大きさの$alpha>0$に対して$mathcalOleft(n-alpharight)$の有限サンプル超過リスクを達成できることを示す。
この証明は、独立した利害関係にある可能性のある過剰リスクの新たな分解に依存している。
論文 参考訳（メタデータ） (2025-05-13T06:26:04Z) - Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。
逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。
これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z) - Stability and Risk Bounds of Iterative Hard Thresholding [41.082982732100696]
アルゴリズム安定性の概念の下でIHTの新しいスパース一般化理論を導入する。
スパースレベル$k$のIHTは、スパース過剰リスクにおける収束率を$mathcaltilde O(n-1/2sqrtlog(n)log(p))$で楽しむことを示す。
理論的予測を確認するための予備的な数値的証拠が提供される。
論文 参考訳（メタデータ） (2022-03-17T16:12:56Z) - Stability and Deviation Optimal Risk Bounds with Convergence Rate
$O(1/n)$ [4.1499725848998965]
経験的リスク最小化法で有効な強く凸およびLipschitz損失に対する$O(log n/n)$の確率に拘束される高い確率過剰リスクを示す。
O(log n/n)$ 高確率過剰リスク境界が、通常の滑らかさの仮定なしで強い凸やリプシッツ損失の場合の射影勾配降下に対してどのように可能かについて論じる。
論文 参考訳（メタデータ） (2021-03-22T17:28:40Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳（メタデータ） (2020-06-29T21:06:52Z) - Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff
in Regret [115.85354306623368]
本研究では,未知の遷移カーネルを持つマルコフ決定過程におけるリスク感応性強化学習について検討する。
確率的に効率的なモデルレスアルゴリズムとして、リスク感性価値反復(RSVI)とリスク感性Q-ラーニング(RSQ)を提案する。
RSVIが $tildeObig(lambda(|beta| H2) cdot sqrtH3 S2AT big) に達したことを証明しています。
論文 参考訳（メタデータ） (2020-06-22T19:28:26Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。