論文の概要: Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces

• arxiv url: http://arxiv.org/abs/2503.15294v3
• Date: Sun, 27 Apr 2025 14:17:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-29 18:43:11.256414
• 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: http://creativecommons.org/licenses/by/4.0/
• 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 et al. (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 et al. (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 et al. (STOC '25). $\bullet$ There exists a partial concept class with Littlestone dimension $1$ such that all its disambiguations have infinite Littlestone dimension. This answers a question of Cheung et al. (ICALP '23). 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$ 無限次元の大マルジン半空間の全体概念類への曖昧さは、リトルストーン次元を非有界にし、Alon et al (FOCS '21) の開問題に答える。 $d$-次元ユークリッド空間における任意の有限個の点と同質半空間の最大リスト-複製可能性数は$d$であり、Chase et al (FOCS '23) の問題を解く。 $\bullet$Gap Hamming Distance問題の大きなギャップ構造における曖昧さはすべて、パブリックコインのランダム化通信の複雑さを未然に抱えている。 これは Fang et al (STOC '25) のオープンな疑問に答える。 $\bullet$ リトルストーン次元が 1 ドルある部分概念クラスが存在し、すべての曖昧さが無限のリトルストーン次元を持つ。 これは Cheung et al (ICALP '23) の質問に答える。 我々の下界は、チェース、チョンマツ、モラン、イェーダホフ(STOC '24)の局所的なボルスク・ウラムの定理に基づく位相論から従う。 上界に対して、SVMの一般化特性を用いたリストレプリケーション可能な学習ルールを構築する。

関連論文リスト

• On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
  多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。 我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。 また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
  論文  参考訳（メタデータ） (2024-11-16T12:09:37Z)
• Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity [8.28720658988688]
  最適関数近似器であり,統計的に良好であるReLU多層認識(MLP)のクラスを同定する。 我々は、小さなスパイクに頼って犠牲になる最適なReLU近似器を構築するための標準的なアプローチを避けることで、これを実現する。
  論文  参考訳（メタデータ） (2024-09-18T22:05:07Z)
• Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem [26.292576184028924]
  この研究は、差分プライベート(DP)とオンライン学習との関係について研究を続けている。 一般分類タスクにおいては,DP学習性はオンライン学習性を意味することを示す。
  論文  参考訳（メタデータ） (2024-07-10T15:43:30Z)
• 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)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• 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)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)

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

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