論文の概要: Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
- arxiv url: http://arxiv.org/abs/2503.15294v1
- Date: Wed, 19 Mar 2025 15:17:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-20 15:22:39.214842
- 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要約: 我々は、リトルストーン次元が有界で、純粋にDP学習可能で高次元においても共有ランダム性は複製可能である大マージン半空間クラスについて研究する。
リストの複製性とグローバルな安定性は、境界のリトルストーン次元、DP-学習性、共有ランダムな複製性から従わない。
- 参考スコア（独自算出の注目度）: 0.12815904071470702
- License:
- Abstract: Recent advances in learning theory have established that, for total concepts, list replicability, global stability, differentially private (DP) learnability, and shared-randomness replicability coincide precisely with the finiteness of the Littlestone dimension. Does the same hold for partial concept classes? We answer this question by studying the large-margin half-spaces class, which has bounded Littlestone dimension and is purely DP-learnable and shared-randomness replicable even in high dimensions. We prove that the list replicability number of $\gamma$-margin half-spaces satisfies \[ \frac{d}{2} + 1 \le \mathrm{LR}(H_{\gamma}^d) \le d, \] which increases with the dimension $d$. This reveals a surprising separation for partial concepts: list replicability and global stability do not follow from bounded Littlestone dimension, DP-learnability, or shared-randomness replicability. By applying our main theorem, we also answer the following open problems. - We prove that any disambiguation of an infinite-dimensional large-margin half-space to a total concept class has unbounded Littlestone dimension, answering an open question of Alon et al. (FOCS '21). - We prove that 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 et al. (FOCS '23). - We prove that any disambiguation of the Gap Hamming Distance problem in the large gap regime has unbounded public-coin randomized communication complexity. This answers an open problem of Fang et al. (STOC '25). We prove the lower bound via a topological argument involving the local Borsuk-Ulam theorem of Chase et al. (STOC '24). For the upper bound, we design a learning rule that relies on certain triangulations of the cross-polytope and recent results on the generalization properties of SVM.
- Abstract（参考訳）: 学習理論の最近の進歩は、全体概念において、リストの複製性、大域的安定性、微分プライベート(DP)学習性、共有ランダムネス複製性は、リトルストーン次元の有限性と正確に一致することを証明している。
同じことが部分概念クラスにも当てはまりますか?
この問題は、Littlestone次元が有界で純粋にDP学習可能で、高次元においても共有ランダム性は複製可能である大マージン半空間クラスを研究することで解決する。
我々は、$\gamma$-margin 半空間のリストの再現性数は、次元$d$で増加する \[ \frac{d}{2} + 1 \le \mathrm{LR}(H_{\gamma}^d) \le d, \] を満たすことを証明している。
リストの複製性とグローバルな安定性は、境界のリトルストーン次元、DP-学習性、共有ランダムな複製性から従わない。
主定理を適用することにより、以下の開問題にも答える。
- 無限次元の大辺半空間の全体概念類への曖昧さは、リトルストーン次元が非有界であることを示し、Alon et al (FOCS '21) の開問題に答える。
- ユークリッド空間の任意の *有限* 個の点と等質半空間の最大リスト-可逆性数は$d$-次元ユークリッド空間が$d$であることを示し、Chase et al (FOCS '23) の問題を解く。
-大きなギャップ構造におけるギャップハミング距離問題の曖昧さは、公開コインランダム化通信の複雑さを未然に防ぐことができる。
これは Fang et al (STOC '25) の開問題に答える。
局所的なボルスク・ウラムの定理(英語版)(Chase et al (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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。