論文の概要: Agnostic Online Learning and Excellent Sets

• arxiv url: http://arxiv.org/abs/2108.05569v1
• Date: Thu, 12 Aug 2021 07:33:33 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-13 14:20:30.539016
• Title: Agnostic Online Learning and Excellent Sets
• Title（参考訳）: Agnostic Online Learning and Excellent Sets
• Authors: Maryanthe Malliaris and Shay Moran
• Abstract要約: 我々は、$k$-edge 安定グラフにおける大きな可分集合の存在を証明した。 これらの証明のテーマは、測度から生じる2つの抽象的な多数派概念と、階数や次元から生じる相互作用である。
• 参考スコア（独自算出の注目度）: 21.87574015264402
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We revisit a key idea from the interaction of model theory and combinatorics, the existence of large ``indivisible'' sets, called ``$\epsilon$-excellent,'' in $k$-edge stable graphs (equivalently, Littlestone classes). Translating to the language of probability, we find a quite different existence proof for $\epsilon$-excellent sets in Littlestone classes, using regret bounds in online learning. This proof applies to any $\epsilon < {1}/{2}$, compared to $< {1}/{2^{2^k}}$ or so in the original proof. We include a second proof using closure properties and the VC theorem, with other advantages but weaker bounds. As a simple corollary, the Littlestone dimension remains finite under some natural modifications to the definition. A theme in these proofs is the interaction of two abstract notions of majority, arising from measure, and from rank or dimension; we prove that these densely often coincide and that this is characteristic of Littlestone (stable) classes. The last section lists several open problems.
• Abstract（参考訳）: 我々はモデル理論とコンビネータの相互作用、すなわち$k$-edge安定グラフ(つまりリトルストーンクラス)において ``$\epsilon$-excellent,''' と呼ばれる大きな ``indivisible'' 集合の存在から重要なアイデアを再検討する。 確率の言語に換算すると、Littlestoneクラスにおける$\epsilon$-excellent集合の存在証明は、オンライン学習における後悔すべき境界を用いて、かなり異なる。 この証明は、元の証明の$<{1}/{2^{2^k}}$ などと比較して、任意の$\epsilon < {1}/{2}$ に適用される。 閉包特性とVC定理を用いた第二の証明を含むが、その他の利点はあるがより弱い境界を持つ。 単純な系として、リトルストーン次元は定義に対する自然な修正の下で有限である。 これらの証明における1つのテーマは、測度と階数や次元から生じる2つの抽象的多数概念の相互作用である。 最後の節ではいくつかの未解決の問題を列挙している。

関連論文リスト

• Topological entanglement and number theory [0.0]
  3dチャーン・サイモンズ理論の文脈における位相的多界絡みの研究の最近の発展は、絡み合い測度と数論の間の強い相互作用を示唆している。 我々は、$k から infty$ の半古典的極限において、これらのエントロピーが有限値に収束することを示す。
  論文  参考訳（メタデータ） (2024-10-02T12:43:57Z)
• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
  論文  参考訳（メタデータ） (2024-09-17T23:09:25Z)
• A Trichotomy for Transductive Online Learning [32.03948071550447]
  我々は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。 この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされる一連のインスタンスを修正し、このシーケンスは学習者に知られている。
  論文  参考訳（メタデータ） (2023-11-10T23:27:23Z)
• Local Borsuk-Ulam, Stability, and Replicability [16.6959756920423]
  また,PAC設定では,リストリプリケータとグローバルな安定学習の両方が不可能であることを示す。 具体的には、有限類におけるリストの複製性と大域的安定性数に対する最適境界を確立する。
  論文  参考訳（メタデータ） (2023-11-02T21:10:16Z)
• Simple online learning with consistent oracle [55.43220407902113]
  オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
  論文  参考訳（メタデータ） (2023-08-15T21:50:40Z)
• Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions [33.49807210207286]
  新しい補助関数$xi$は、AdaGradsイテレーションの数値と分母の間の相関を扱う複雑さを取り除くのに役立つ。 AdaGradは,学習率がしきい値より低い限り,$(L_0)$smooth条件下での収束に成功していることを示す。
  論文  参考訳（メタデータ） (2023-05-29T09:33:04Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。 また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
  論文  参考訳（メタデータ） (2022-09-16T13:59:42Z)
• multiPRover: Generating Multiple Proofs for Improved Interpretability in Rule Reasoning [73.09791959325204]
  我々は、自然言語の事実と規則の形で明示的な知識を推論することを目的としている言語形式推論の一種に焦点を当てる。 PRoverという名前の最近の研究は、質問に答え、答えを説明する証明グラフを生成することによって、そのような推論を行う。 本研究では,自然言語規則ベースの推論のために複数の証明グラフを生成するという,新たな課題に対処する。
  論文  参考訳（メタデータ） (2021-06-02T17:58:35Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。 我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
  論文  参考訳（メタデータ） (2021-01-18T15:40:27Z)
• 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)

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

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