論文の概要: Sharp margin-based generalization bounds for realizable SVM
- arxiv url: http://arxiv.org/abs/2609.17845v1
- Date: Tue, 15 Sep 2026 21:03:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-20 08:55:53.545429
- Title: Sharp margin-based generalization bounds for realizable SVM
- Title（参考訳）: シャープマージンに基づく実現可能なSVMの一般化境界
- Abstract要約: Ppleft( _m>0,quad Risk(u_m)> fracCm left(K_m+logfrac1 right) le であるような普遍的な数値定数 (C) が存在することを証明している。
- 参考スコア（独自算出の注目度）: 43.31446644314209
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Let the exact homogeneous hard-margin support vector machine be trained on \(m\) independent observations from a Borel probability law on a real Hilbert space. We prove that, with score zero counted as an error, there is a universal numerical constant \(C\) such that \[ \Pp\left( γ_m>0,\quad \Risk(u_m)> \frac{C}{m} \left( K_m+\log\frac1δ \right) \right) \le δ. \] Here \(γ_m\) is the empirical homogeneous margin, \(u_m\) is the exact minimum-norm unit-margin separator, \(r_m\) is the largest training radius, and \(K_m:=r_m^2\norm{u_m}^2=r_m^2/γ_m^2\) on \(\{γ_m>0\}\). The proof is driven by a deterministic deletion problem. Given vectors \(x_1,\ldots,x_n\) in the unit ball, delete a set \(B\) of constraints and let \(u_B\) be the closest point to the origin that satisfies every retained unit-margin constraint. Suppose that \(\norm{u_B}^2\le k\) and that every deleted vector has nonpositive score under \(u_B\). We prove that a family of such deletion sets of cardinality \(q\) has size at most \(\exp(8k+2q)\). The conceptual step is an exact identity obtained from the KKT representation of \(u_B\). For a random deletion set, the identity converts the mean squared spread of the separators into a weighted sum of score deficits. It therefore forces a coordinate whose deletion status separates the two conditional means by a quantitatively large amount. Revealing that coordinate decreases the conditional separator variance enough to control the binary entropy of the split. An entropy induction gives the deletion count, and an exact factorial ghost-sample identity converts that count into the stated high-probability SVM bound.
- Abstract（参考訳）: 実ヒルベルト空間上のボレル確率法則から独立な観測で、正確な同質なハードマージン支持ベクトルマシンを訓練する。
スコアゼロを誤差としてカウントすると、普遍数値定数 \(C\) が存在して、 \[ \Pp\left( γ_m>0,\quad \Risk(u_m)> \frac{C}{m} \left(K_m+\log\frac1δ \right) \le δ となる。
\] ここで、(γ_m\) は経験的同質マージン、(u_m\) は正確な最小ノルム単位マージンセパレータ、(r_m\) は最大のトレーニング半径、(K_m:=r_m^2\norm{u_m}^2=r_m^2/γ_m^2\) は \(\{γ_m>0\}\) である。
この証明は決定論的削除問題によって引き起こされる。
単位球のベクトル \(x_1,\ldots,x_n\) が与えられたとき、制約の集合 \(B\) を削除し、(u_B\) を元の最も近い点とし、保持されたすべての単位辺の制約を満たす。
\(\norm{u_B}^2\le k\) とすると、すべての削除されたベクトルは \(u_B\) の下で非正のスコアを持つ。
そのような基数の削除集合の族 \(q\) が少なくとも \(\exp(8k+2q)\) の大きさを持つことを示す。
概念ステップは \(u_B\) の KKT 表現から得られる正確な恒等式である。
ランダムな削除セットに対して、IDはセパレータの平均2乗拡散をスコア損失の重み付け和に変換する。
したがって、削除状態が2つの条件付き手段を定量的に大量に分離する座標を強制する。
この座標は、分割のバイナリエントロピーを制御するのに十分な条件分離器の分散を減少させる。
エントロピー帰納法は削除数を与え、正確な因数的なゴーストサンプルの同一性は、そのカウントを高確率のSVM境界に変換する。
関連論文リスト
- Uniformly Stable Minimal Weyl--Heisenberg Measurements Approaching the SIC Benchmark [2.5735476569508995]
情報完全性(IC)は、逆が存在することを保証する。
最小ランク1のワイル=ハイゼンベルク測度に対して、共分散は非恒等射影-グラムスペクトルをフィデューシャルの曖昧性強度に比例させる。
バランスの取れた1座標摂動は、立方体オールトップ状態のゼロアンビグニティ軸を修復し、到達した床を正の定数で一様に束縛し、非同一性スペクトル全体を(U_q/L_qto1)で([L_q,U_q])に閉じ込める。
論文 参考訳（メタデータ） (2026-08-12T09:41:26Z) - Conditionally Resampled Sliding-Window Count Kernels: Spectral-Gap Bounds and Poincaré Inequalities [8.412659799221698]
定常有限状態可逆マルコフ連鎖の窓の長さn$窓の実験的数について検討する。
有限状態空間上のすべての固定された正の可逆核 (P) に対して、誘導されたカウント核 $tP_n$ of length $n$ に対してポアンカレ不等式を示す。
結果として得られる数空間のポアンカレ不等式は、有限ウィンドウ数統計量に対して局所-グロバル分散をもたらす。
論文 参考訳（メタデータ） (2026-08-09T12:48:30Z) - Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$を符号、空間性、正方性制限なしで証明する。
純粋な$varepsilon$-DP行列力学クラスでは、最適化された最大誤差と平均二乗誤差の両方が$(varepsilon-2log3(n+1))$である。
論文 参考訳（メタデータ） (2026-07-30T14:41:34Z) - Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
不変学習は、構造が統計的に識別可能であっても失敗することがある。
ブラックボックスサンプリング可能な教師付きスパースリカバリプリミティブの下では、実証可能な多次元環境が存在する。
合成および実際のデータセットは、予測されたギャップと遷移を示し、単純な多様性診断を動機付ける。
論文 参考訳（メタデータ） (2026-06-11T05:49:43Z) - Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression [65.82017723631897]
自己正規化マルティンガレのスケール不変上界が可能であることを示す。
通常の正規化ペナルティを含まない自己正規化濃度不等式を導出する。
論文 参考訳（メタデータ） (2026-05-02T22:39:00Z) - Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。
我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文 参考訳（メタデータ） (2026-03-20T01:53:44Z) - Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Multivariate mean estimation with direction-dependent accuracy [8.147652597876862]
独立な同一分布観測に基づくランダムベクトルの平均を推定する問題を考察する。
確率ベクトルの1次元辺の分散があまり小さくない全ての方向において、ほぼ最適誤差を持つ推定器を証明した。
論文 参考訳（メタデータ） (2020-10-22T17:52:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。