論文の概要: Margin in Abstract Spaces

• arxiv url: http://arxiv.org/abs/2603.07221v1
• Date: Sat, 07 Mar 2026 14:02:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-10 15:13:14.097009
• Title: Margin in Abstract Spaces
• Title（参考訳）: 抽象空間におけるマージン
• Authors: Yair Ashlagi, Roi Livni, Shay Moran, Tom Waknine,
• Abstract要約: 線形構造や解析構造を伴わずに, 学習容易性が三角形の不等式にのみ依存することを示す。 次に、線形空間への埋め込みを通して、マージンベースの学習可能性が常に説明できるかどうかを問う。
• 参考スコア（独自算出の注目度）: 31.970649402124547
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Margin-based learning, exemplified by linear and kernel methods, is one of the few classical settings where generalization guarantees are independent of the number of parameters. This makes it a central case study in modern highly over-parameterized learning. We ask what minimal mathematical structure underlies this phenomenon. We begin with a simple margin-based problem in arbitrary metric spaces: concepts are defined by a center point and classify points according to whether their distance lies below $r$ or above $R$. We show that whenever $R>3r$, this class is learnable in \emph{any} metric space. Thus, sufficiently large margins make learnability depend only on the triangle inequality, without any linear or analytic structure. Our first main result extends this phenomenon to concepts defined by bounded linear combinations of distance functions, and reveals a sharp threshold: there exists a universal constant $γ>0$ such that above this margin the class is learnable in every metric space, while below it there exist metric spaces where it is not learnable at all. We then ask whether margin-based learnability can always be explained via an embedding into a linear space -- that is, reduced to linear classification in some Banach space through a kernel-type construction. We answer this negatively by developing a structural taxonomy of Banach spaces: if a Banach space is learnable for some margin parameter $γ\geq 0$, then it is learnable for all such $γ$, and in infinite-dimensional spaces the sample complexity must scale polynomially in $1/γ$. Specifically, it must grow as $(1/γ)^p$ for some $p\ge 2$, and every such rate is attainable.
• Abstract（参考訳）: 線形およびカーネルメソッドで例示されるMarginベースの学習は、一般化保証がパラメータの数に依存しない数少ない古典的な設定の1つである。 これは現代の高度パラメータ学習における中心的なケーススタディである。 最小限の数学的構造がこの現象の根底にあるものは何なのかを問う。 概念は中心点によって定義され、それらの距離が$r$以下のか$R$以上のかに応じて点を分類する。 R>3r$ のときは常に、このクラスは \emph{any} 計量空間で学習可能であることを示す。 したがって、十分に大きなマージンは、線形構造や解析構造を持たず、三角形の不等式にのみ依存する。 最初の主要な結果は、この現象を距離関数の有界線型結合によって定義される概念にまで拡張し、鋭いしきい値(英語版)(シャープしきい値)を明らかにします。 次に、マージンベースの可学習性は常に線型空間への埋め込みを通して説明できるかどうかを問う。 バナッハ空間があるマージンパラメータ$γ\geq 0$に対して学習可能ならば、そのようなすべての$γ$に対して学習可能であり、無限次元空間ではサンプル複雑性は1/γ$で多項式的にスケールしなければならない。 具体的には、ある$p\ge 2$に対して$(1/γ)^p$として成長しなければならず、そのような速度は全て達成可能である。

関連論文リスト

• Learning with the $p$-adics [26.431600220740354]
  我々は、$mathbbR$, $mathbbQ_p$, $mathbbQ_p$の超測度および非アルキメデス空間の代替として、根本的に異なる分野の適合性について研究する。 p$-adicsの階層構造と無限文字列としての解釈は、コード理論と階層的表現学習にとって魅力的なツールである。
  論文  参考訳（メタデータ） (2025-12-27T19:40:42Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  制約付き部分空間近似のための一般的なフレームワークを導入する。 分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
  論文  参考訳（メタデータ） (2025-04-29T15:56:48Z)
• Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces [0.815557531820863]
  我々は、$d$-dimensional $gamma$-margin half-spaces のリスト複製数が[ fracd2+1 le MathrmLR(Hd_gamma) le d, ] を満たすことを証明した。
  論文  参考訳（メタデータ） (2025-03-19T15:17:13Z)
• A Theory of Interpretable Approximations [61.90216959710842]
  我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。 任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。 解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
  論文  参考訳（メタデータ） (2024-06-15T06:43:45Z)
• An Approximation Theory for Metric Space-Valued Functions With A View Towards Deep Learning [25.25903127886586]
  任意のポーランド計量空間 $mathcalX$ と $mathcalY$ の間の連続写像の普遍函数近似器を構築する。 特に、必要なディラック測度数は $mathcalX$ と $mathcalY$ の構造によって決定されることを示す。
  論文  参考訳（メタデータ） (2023-04-24T16:18:22Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
  線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。 特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。 提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
  論文  参考訳（メタデータ） (2020-11-02T14:59:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。