論文の概要: Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals
- arxiv url: http://arxiv.org/abs/2611.04344v1
- Date: Tue, 03 Nov 2026 05:27:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-10 02:09:34.585259
- Title: Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals
- Title（参考訳）: ログ・コンケーブ・マージナル下でのアフィン半空間の固有学習
- Abstract要約: 実次元対数対数辺辺のアフィン半空間に対して適切な定数要素学習器を与える。
任意のバイナリラベルに対して、アルゴリズムは独立ラベル付きサンプルを使用し、エラーで1つのアフィン半空間を返す。
この分析は、対数凹法則に対する四次二乗の総和モーメント境界と、バランスの取れたアフィン学習から均質な半空間学習への変換に基づく還元を組み合わせたものである。
- 参考スコア（独自算出の注目度）: 7.390615334369365
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give a proper constant-factor agnostic learner for affine halfspaces under full-dimensional log-concave marginals. For arbitrary binary labels, the algorithm uses independent labeled samples and returns a single affine halfspace with error at most $C\mathrm{OPT}+\varepsilon$. Its sample and real-arithmetic complexity are polynomial in dimension, inverse accuracy, and the logarithm of the reciprocal failure probability. The mean and covariance of the marginal need not be known, and the sample complexity can be made linear in this logarithmic confidence factor. The main geometric result compares global disagreement with disagreement on a balanced restriction: for a minority halfspace of mass $p$, global disagreement is within universal constant factors of $p$ times conditional disagreement, provided the latter is sufficiently small. To construct the restriction from noisy labels, we estimate the minority cap's mean and covariance robustly, approximately minimize the classical zonoid-depth dual objective, and expand a superlevel set to a marginal quantile. The disagreement comparison cancels the noise amplification caused by conditioning and allows the learned halfspace to be used on the entire space. The analysis combines degree-four sum-of-squares moment bounds for log-concave laws with a translation-based reduction from balanced affine learning to homogeneous halfspace learning.
- Abstract（参考訳）: 実次元対数対数辺辺のアフィン半空間に対して、正定要素非依存の学習者を与える。
任意のバイナリラベルに対して、アルゴリズムは独立ラベル付きサンプルを使用し、最大$C\mathrm{OPT}+\varepsilon$のエラーで1つのアフィン半空間を返す。
そのサンプルと実相対論的複雑性は、次元の多項式、逆精度、および相互失敗確率の対数である。
辺辺の平均と共分散は分かっておらず、この対数的信頼因子ではサンプルの複雑さを線形にすることができる。
主幾何学的結果は、大域的な不一致と均衡された制限についての不一致を比較する:大域的な不一致は、質量$p$の少数半空間に対して、後者が十分小さいならば、$p$の条件付き不一致の普遍定数要素の範囲内である。
ノイズラベルから制約を構築するため、マイノリティキャップの平均と共分散を頑健に推定し、古典的なゾノイド-深度双対目的をほぼ最小化し、超レベルセットを限界量子化に拡張する。
不一致比較は条件付けによる雑音増幅をキャンセルし、学習されたハーフスペースを全空間で使用できるようにする。
この分析は、対数凹法則に対する四次二乗の総和モーメント境界と、バランスの取れたアフィン学習から均質な半空間学習への変換に基づく還元を組み合わせたものである。
関連論文リスト
- Zero-Complement Extrapolation: Parameter Recovery and Classification in Severely Imbalanced Logistic Regression under Rank-Deficient Regimes [0.0]
本稿では,このパラダイムを少数派から多数派へとシフトさせる,新たなテキスト・キャリブレーションゼロ・コンプリメント推定器を提案する。
提案手法はパラメータのばらつきを防止し,高忠実度で超平面を復元し,F1スコアにおけるオラクルの回帰とSMOTEを著しく上回り,推定安定性を向上する。
論文 参考訳（メタデータ） (2026-10-29T02:15:44Z) - The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning [0.0]
ポイントワイドの再現性は、同じランダムシードを使用して、独立に訓練された2つの予測器が、高い確率でそれぞれの固定クエリに一致することを要求する。
有限および可算領域上で、その最適サンプル複雑性を決定する。
論文 参考訳（メタデータ） (2026-10-18T07:08:13Z) - Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness [0.0]
本研究では,未知の,未知の,未知の,未知の事例の残差に基づく実存可能なブール学習について検討する。
決定論的学習、任意の有限類に対する極小$$レギュレーション、VC 1 の有限類に対するすべての濃度-再現性レギュレーションを特徴付ける。
論文 参考訳（メタデータ） (2026-10-18T05:17:14Z) - Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation [51.56484100374058]
我々は、ハードレイヤーワイドリプシッツ予算の下で近似を研究する。
構成条件下では、対応するレイヤエラーをキャンセルする必要はないことを示す。
クラスのすべての作用素に対して、安定した深さ-$L$タワーが存在し、累積誤差の定数分を実現できる。
論文 参考訳（メタデータ） (2026-09-14T20:17:04Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube [26.777025730534756]
ハイパーキューブ上の一様分布に関して、ハーフスペースを学習するための最初のフルタイムアルゴリズムを与える。
誤り保証は$etaO(1)+epsilon$で、$eta$はノイズレートです。
より一般的に、我々のフレームワークは、個別分布に関する教師あり学習が以前考えられていたほど難しくないことを示している。
論文 参考訳（メタデータ） (2025-11-10T15:58:41Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins [92.7662890047311]
勾配降下は、分類誤差$tilde O(mathsfOPT1/2) + varepsilon$ in $mathrmpoly(d,1/varepsilon)$ time and sample complexity.
論文 参考訳（メタデータ） (2020-10-01T16:48:33Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。