論文の概要: Tight list replicability bounds via a novel sphere covering theorem
- arxiv url: http://arxiv.org/abs/2606.06148v1
- Date: Thu, 04 Jun 2026 13:24:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-05 22:39:44.81483
- Title: Tight list replicability bounds via a novel sphere covering theorem
- Title（参考訳）: 新規球面被覆定理によるタイトリストの再現性境界
- Authors: Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak,
- Abstract要約: 大域半空間に対して、マージンが大きすぎると、最適リストサイズは周囲次元に等しいことを示す。
また、大マージン半空間の場合、マージンが大きすぎると、最適リストサイズは周囲次元に等しいことを示す。
- 参考スコア（独自算出の注目度）: 0.815557531820863
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In recent years, list replicability has emerged as a framework for formalizing reproducibility in learning theory. A central question is how the required list size relates to the accuracy parameter and natural complexity measures of the hypothesis class. To achieve sharp bounds on list replicability, we prove a novel topological sphere covering theorem, derived from the Borsuk-Ulam theorem. Specifically, if the $d$-sphere is covered by open sets, each of which lies in an open hemisphere, then $d+1$ of these sets must have a common intersection. Using this result, we obtain a sharp bound on the relationship between list size and accuracy for VC classes. We also show that for large-margin half-spaces, provided the margin is not too large, the optimal list size equals the ambient dimension. However, when the margin is taken to be very large, we devise a replicable algorithm achieving the minimal list size of $\lceil d/2 \rceil + 1$.
- Abstract（参考訳）: 近年, 学習理論における再現性を形式化する枠組みとして, リスト複製能力が出現している。
中心的な疑問は、要求リストのサイズが仮説クラスの精度パラメータと自然複雑性尺度にどのように関係しているかである。
リストの複製性に関する鋭い境界を達成するために、ボルスク・ウラムの定理から導かれた新しい位相球被覆定理を証明した。
具体的には、$d$-球面が開集合で、それぞれが開半球にあるなら、これらの集合の$d+1$は共通交叉を持つ必要がある。
この結果から,VCクラスにおけるリストサイズと精度の関係を鋭く把握する。
また、大マージン半空間の場合、マージンが大きすぎると、最適リストサイズは周囲次元に等しいことを示す。
しかし、マージンが非常に大きいとすると、最小リストサイズを$\lceil d/2 \rceil + 1$ とするレプリカブルアルゴリズムを考案する。
関連論文リスト
- Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval [59.859592671274704]
$dtimes d$ リニアメモリストアはいくつのキー値アソシエーションが可能ですか?
この答えは、メモリマトリックスの$d2$自由度だけでなく、検索基準にも依存する。
論文 参考訳（メタデータ） (2026-05-06T17:53:20Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - 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) - Local Borsuk-Ulam, Stability, and Replicability [16.6959756920423]
また,PAC設定では,リストリプリケータとグローバルな安定学習の両方が不可能であることを示す。
具体的には、有限類におけるリストの複製性と大域的安定性数に対する最適境界を確立する。
論文 参考訳（メタデータ） (2023-11-02T21:10:16Z) - 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) - A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。
我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
論文 参考訳（メタデータ） (2021-01-18T15:40:27Z) - Average-case Complexity of Teaching Convex Polytopes via Halfspace
Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。
我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文 参考訳（メタデータ） (2020-06-25T19:59:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。