論文の概要: How abundant are good interpolators?
- arxiv url: http://arxiv.org/abs/2606.06469v1
- Date: Thu, 04 Jun 2026 17:55:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-05 22:39:45.023163
- Title: How abundant are good interpolators?
- Title（参考訳）: 優れた補間器はどのくらい豊富ですか。
- Authors: August Y. Chen, Ahmed El Alaoui,
- Abstract要約: 補間分類器の指数的に小さな部分を除いて、この速度関数の特異な最大値によって与えられる一般化性能がほぼ同じであることを示す。
我々は、この最大化器を、勾配降下による経験的リスク最小化の性能と、自然な線形プログラムの性能とを数値的に比較する。
- 参考スコア（独自算出の注目度）: 1.6114012813668932
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Let $S$ be the set of unit norm linear classifiers $θ\in \mathbb{R}^d$ which correctly classify every point of a labeled dataset $(X_i,y_i)_{i=1}^n$, $X_i \in \mathbb{R}^d$, $y_i \in \{-1,+1\}$, with a possibly negative margin $κ$ fixed in advance. Under two natural data-generating distributions of the $(X,y)$ pairs -- a Gaussian mixture model and a logistic model with Gaussian features -- and in the proportional regime $n/d \to α$ with small enough $α$, we establish a large deviation principle on the event that a point $θ$ chosen uniformly at random from $S$ achieves a given generalization error, with high probability over the choice of the data. The associated large deviation rate function is deterministic and describes the proportion, at the exponential scale in $d$, of interpolating classifiers having a given desired performance. As a consequence, we establish the following concentration phenomenon: all but an exponentially small fraction of interpolating classifiers have approximately the same generalization performance given by the unique maximizer of this rate function. We numerically compare this maximizer to the performance of empirical risk minimization by gradient descent and to the performance of a natural linear program, both finding a point in $S$, and deduce that in the overparametrized regime of small $α$, these efficient procedures outperform the vast majority of interpolators, pointing to their nontrivial benign overfitting in this setting.
- Abstract（参考訳）: S$ を単位ノルム線型分類器の集合 $θ\in \mathbb{R}^d$ とし、これはラベル付きデータセット $(X_i,y_i)_{i=1}^n$, $X_i \in \mathbb{R}^d$, $y_i \in \{-1,+1\}$ のすべての点を正しく分類する。
ガウス的混合モデルとガウス的特徴を持つロジスティックモデルである$(X,y)$ペアの2つの自然なデータ生成分布の下では、比例的レギュレーション$n/d \to α$と小さな$α$とでは、$S$からランダムに選択された点$θ$が、データの選択よりも高い確率で与えられた一般化誤差を達成するという大きな偏差原理を確立する。
関連する大きな偏差率関数は決定論的であり、与えられた所望のパフォーマンスを持つ補間分類器の指数スケールで$d$の比率を記述する。
補間器の指数的に小さな分数を除いて、この速度関数の特異な最大値によって与えられる一般化性能はほぼ同じである。
この最大化器を、勾配降下による経験的リスク最小化の性能と自然線形プログラムの性能を比較して、S$の点を求めることと、α$の過度なパラメータ化状態において、これらの効率的な手順は補間器の大多数を上回り、その非自明な過度な過度な設定を指し示していると推定する。
関連論文リスト
- Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs [8.162867143465382]
我々はこの手法を利用して、平均ケースの複雑さにおいて広く信じられている予想の下で、いくつかの正準高次元統計モデルに対して、還元に基づく計算下界を確立する。
ガウス雑音を持つスパイクテンソルPCAの計算下界は、クラス内の他のガウス雑音分布にまで拡張可能であることを示す。
論文 参考訳（メタデータ） (2025-10-08T17:16:36Z) - Allocating Variance to Maximize Expectation [2.25491649634702]
ガウス確率変数の系列の上限を最大化するための効率的な近似アルゴリズムを設計する。
このような期待問題は、ユーティリティオークションから、定量的遺伝学の混合モデルを学ぶことまで、様々な応用で発生する。
論文 参考訳（メタデータ） (2025-02-25T18:59:46Z) - Universality of max-margin classifiers [10.797131009370219]
非ガウス的特徴に対する誤分類誤差の高次元普遍性と大域化写像の役割について検討する。
特に、オーバーパラメトリゼーションしきい値と一般化誤差はより単純なモデルで計算できる。
論文 参考訳（メタデータ） (2023-09-29T22:45:56Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。
特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
論文 参考訳（メタデータ） (2023-09-17T01:45:13Z) - $p$-Generalized Probit Regression and Scalable Maximum Likelihood
Estimation via Sketching and Coresets [74.37849422071206]
本稿では, 2次応答に対する一般化線形モデルである,$p$一般化プロビット回帰モデルについて検討する。
p$の一般化されたプロビット回帰に対する最大可能性推定器は、大容量データ上で$(1+varepsilon)$の係数まで効率的に近似できることを示す。
論文 参考訳（メタデータ） (2022-03-25T10:54:41Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文 参考訳（メタデータ） (2020-08-01T19:23:34Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - A Precise High-Dimensional Asymptotic Theory for Boosting and
Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。
統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。
また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
論文 参考訳（メタデータ） (2020-02-05T00:24:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。