論文の概要: Local Borsuk-Ulam, Stability, and Replicability

• arxiv url: http://arxiv.org/abs/2311.01599v1
• Date: Thu, 2 Nov 2023 21:10:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-06 15:48:03.036937
• Title: Local Borsuk-Ulam, Stability, and Replicability
• Title（参考訳）: 局所ボルスク・ウラム, 安定性, 再現性
• Authors: Zachary Chase, Bogdan Chornomaz, Shay Moran, Amir Yehudayoff
• Abstract要約: また,PAC設定では,リストリプリケータとグローバルな安定学習の両方が不可能であることを示す。 具体的には、有限類におけるリストの複製性と大域的安定性数に対する最適境界を確立する。
• 参考スコア（独自算出の注目度）: 16.6959756920423
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We use and adapt the Borsuk-Ulam Theorem from topology to derive limitations on list-replicable and globally stable learning algorithms. We further demonstrate the applicability of our methods in combinatorics and topology. We show that, besides trivial cases, both list-replicable and globally stable learning are impossible in the agnostic PAC setting. This is in contrast with the realizable case where it is known that any class with a finite Littlestone dimension can be learned by such algorithms. In the realizable PAC setting, we sharpen previous impossibility results and broaden their scope. Specifically, we establish optimal bounds for list replicability and global stability numbers in finite classes. This provides an exponential improvement over previous works and implies an exponential separation from the Littlestone dimension. We further introduce lower bounds for weak learners, i.e., learners that are only marginally better than random guessing. Lower bounds from previous works apply only to stronger learners. To offer a broader and more comprehensive view of our topological approach, we prove a local variant of the Borsuk-Ulam theorem in topology and a result in combinatorics concerning Kneser colorings. In combinatorics, we prove that if $c$ is a coloring of all non-empty subsets of $[n]$ such that disjoint sets have different colors, then there is a chain of subsets that receives at least $1+ \lfloor n/2\rfloor$ colors (this bound is sharp). In topology, we prove e.g. that for any open antipodal-free cover of the $d$-dimensional sphere, there is a point $x$ that belongs to at least $t=\lceil\frac{d+3}{2}\rceil$ sets.
• Abstract（参考訳）: 我々はボルスク・ウラムの定理をトポロジーから適用し、リスト複製とグローバルに安定な学習アルゴリズムの限界を導出する。 さらに, コンビネータ・トポロジーにおける手法の適用性を示す。 自明なケースの他に,PAC設定ではリスト再現性やグローバルな安定学習は不可能であることを示す。 これは、有限小石次元を持つ任意のクラスがそのようなアルゴリズムによって学習できることが知られているような実現可能な場合とは対照的である。 実現可能なPAC設定では、従来の不可能な結果をシャープにし、スコープを広げる。 具体的には,有限クラスにおけるリスト再現性と大域的安定性数に対する最適境界を定式化する。 これは以前の作品よりも指数関数的に改善され、リトルストーン次元から指数関数的な分離を意味する。 さらに,弱い学習者,すなわちランダムな推測よりもわずかによい学習者に対して,下限を導入する。 以前の作品の下位境界は、より強い学習者にのみ適用される。 位相的アプローチをより広く包括的に見るために、トポロジーにおいてボルスク・ウラムの定理の局所的変種を証明し、クネーサー彩色に関する組合せ論の結果を得る。 組合せ論において、$c$ が$[n]$ の空でないすべての部分集合の色付けであり、不連結集合が異なる色を持つならば、少なくとも 1+ \lfloor n/2\rfloor$ 色を受け取る部分集合の連鎖が存在する(この境界はシャープである)。 例えば、$d$-次元球面の任意の開反ポッドフリー被覆に対して、少なくとも$t=\lceil\frac{d+3}{2}\rceil$集合に属する点$x$が存在することを証明している。

関連論文リスト

• 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)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions [39.97534972432276]
  本稿では,$[0,1]$-valued関数のクラスを学習するための新しい汎用アルゴリズムを提案する。 このアルゴリズムの絶対誤差の一般上界を証明した。 本研究は, 学習の複雑さに関する一般化された一般境界を得るために, 両方のパッキングバウンドをどう適用するかを示す。
  論文  参考訳（メタデータ） (2023-04-21T15:51:35Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。 巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。 我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
  論文  参考訳（メタデータ） (2023-01-04T04:15:40Z)
• Agnostic Online Learning and Excellent Sets [21.87574015264402]
  我々は、$k$-edge 安定グラフにおける大きな可分集合の存在を証明した。 これらの証明のテーマは、測度から生じる2つの抽象的な多数派概念と、階数や次元から生じる相互作用である。
  論文  参考訳（メタデータ） (2021-08-12T07:33:33Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。 我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
  論文  参考訳（メタデータ） (2021-01-18T15:40:27Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)

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

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