論文の概要: Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
- arxiv url: http://arxiv.org/abs/2503.15294v2
- Date: Fri, 28 Mar 2025 16:21:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-31 15:28:48.118365
- Title: Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
- Title（参考訳）: Borsuk-Ulamと大マルジン半空間の再現可能な学習
- Authors: Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak,
- Abstract要約: 我々は、$d$-dimensional $gamma$-margin half-spaces のリスト複製数が[ fracd2+1 le MathrmLR(Hd_gamma) le d, ] を満たすことを証明した。
部分類に対して、リストの複製性と大域的安定性は必ずしも有界リトルストーン次元から従わない。
- 参考スコア（独自算出の注目度）: 0.12815904071470702
- License:
- Abstract: Recent remarkable advances in learning theory have established that, for total concept classes, list replicability, global stability, differentially private (DP) learnability, and shared-randomness replicability all coincide with the finiteness of Littlestone dimension. Does this equivalence extend to partial concept classes? We answer this question by proving that the list replicability number of $d$-dimensional $\gamma$-margin half-spaces satisfies \[ \frac{d}{2}+1 \le \mathrm{LR}(H^d_\gamma) \le d, \] which grows with dimension. Consequently, for partial classes, list replicability and global stability do not necessarily follow from bounded Littlestone dimension, pure DP-learnability, or shared-randomness replicability. Applying our main theorem, we resolve several open problems: $\bullet$ Every disambiguation of infinite-dimensional large-margin half-spaces to a total concept class has unbounded Littlestone dimension, answering an open question of Alon, Hanneke, Holzman, and Moran (FOCS '21). $\bullet$ The maximum list-replicability number of any finite set of points and homogeneous half-spaces in $d$-dimensional Euclidean space is $d$, resolving a problem of Chase, Moran, and Yehudayoff (FOCS '23). $\bullet$ Every disambiguation of the Gap Hamming Distance problem in the large gap regime has unbounded public-coin randomized communication complexity. This answers an open question of Fang, G\"o\"os, Harms, and Hatami (STOC '25). Our lower bound follows from a topological argument based on the local Borsuk-Ulam theorem of Chase, Chornomaz, Moran, and Yehudayoff (STOC '24). For the upper bound, we construct a list-replicable learning rule using the generalization properties of SVMs.
- Abstract（参考訳）: 学習理論の最近の顕著な進歩は、全概念クラスにおいて、リストの複製性、大域的安定性、微分プライベート(DP)学習性、共有ランダムな複製性は、全てリトルストーン次元の有限性と一致することを証明している。
この同値性は部分的な概念クラスにまで拡張されますか?
この問題は、$d$-次元 $\gamma$-margin ハーフ空間のリストの複製数が、次元で成長する \[ \frac{d}{2}+1 \le \mathrm{LR}(H^d_\gamma) \le d, \] を満たすことを証明して、この質問に答える。
したがって、部分類の場合、リストの複製性や大域的安定性は、必ずしも境界のリトルストーン次元、純粋なDP-学習性、あるいは共有ランダムな複製性から従わない。
主定理を適用すると、いくつかの開問題を解決する: $\bullet$ 無限次元の大辺半空間の全体概念類へのすべての曖昧さは、リトルストーン次元を非有界にし、アロン、ハネケ、ホルツマン、モラン (FOCS '21) の開問題に答える。
$\bullet$ 任意の有限個の点と同次半空間の最大リスト-リプリケータビリティ数は$d$次元ユークリッド空間において$d$であり、チェイス、モラン、イェーダノフの問題を解く(FOCS '23)。
$\bullet$Gap Hamming Distance問題の大きなギャップ構造における曖昧さはすべて、パブリックコインのランダム化通信の複雑さを未然に抱えている。
これは、Fang, G\"o\"os, Harms, and Hatami (STOC '25) のオープンな疑問に答える。
我々の下界は、チェース、チョンマツ、モラン、イェーダホフ(STOC '24)の局所的なボルスク・ウラムの定理に基づく位相論から従う。
上界に対して、SVMの一般化特性を用いたリストレプリケーション可能な学習ルールを構築する。
関連論文リスト
- On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。
我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。
また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
論文 参考訳（メタデータ） (2024-11-16T12:09:37Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Improved Hardness Results for Learning Intersections of Halfspaces [2.1393480341554736]
不適切な設定でハーフ空間の弱学習交差点に対して、強い(そして驚くほど単純な)下界を示す。
我々は、$omega(log log N)$ halfspaces を$N$で学習しても超多項式時間を要することを示すことで、このギャップを著しく狭めている。
具体的には、次元$N$の任意の$k$ハーフスペースに対して、精度$N-Omega(k)$、指数関数的に多くのクエリが必要であることを示す。
論文 参考訳（メタデータ） (2024-02-25T05:26:35Z) - Local Borsuk-Ulam, Stability, and Replicability [16.6959756920423]
また,PAC設定では,リストリプリケータとグローバルな安定学習の両方が不可能であることを示す。
具体的には、有限類におけるリストの複製性と大域的安定性数に対する最適境界を確立する。
論文 参考訳（メタデータ） (2023-11-02T21:10:16Z) - Principle of minimal singularity for Green's functions [1.8855270809505869]
我々は、D$次元時空におけるダイソン=シュウィンガー方程式を下決定する2つのアプローチから着想を得た相関関数の新たな解析的連続性を考える。
我々は、エルミート四元数および非エルミート立方体理論に対して急速に収束する結果を得る。
論文 参考訳（メタデータ） (2023-09-05T13:06:57Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D
Shape Matching [69.14632473279651]
本稿では,3次元形状間の幾何学的一貫したマッピング空間をグローバルに最適化するスケーラブルなアルゴリズムを提案する。
従来の解法よりも数桁高速なラグランジュ双対問題と結合した新しい原始問題を提案する。
論文 参考訳（メタデータ） (2022-04-27T09:47:47Z) - Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable
Approach for Continuous Markov Random Fields [53.31927549039624]
断片的な離散化は既存の離散化問題と矛盾しないことを示す。
この理論を2つの画像のマッチング問題に適用する。
論文 参考訳（メタデータ） (2021-07-13T12:31:06Z) - From Geometry to Topology: Inverse Theorems for Distributed Persistence [0.0]
正しい不変量は、X の永続化図形ではなく、多くの小さな部分集合の永続化図形の集まりであることを示す。
この不変性は、私たちが"分散永続化"と呼んでいるもので、簡単に並列化可能で、外れ値に対してより安定です。
結果は、実際に分散持続性の使用を実証する2つの合成実験によって補完される。
論文 参考訳（メタデータ） (2021-01-28T21:36:45Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。
この結果は Bun et al の質問に答えます。
(FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
論文 参考訳（メタデータ） (2020-12-07T18:17:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。