論文の概要: Finite Littlestone Dimension Implies Finite Information Complexity

• arxiv url: http://arxiv.org/abs/2206.13257v1
• Date: Mon, 27 Jun 2022 12:43:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-28 20:50:01.902740
• Title: Finite Littlestone Dimension Implies Finite Information Complexity
• Title（参考訳）: 有限小岩次元と有限情報複雑度
• Authors: Aditya Pradeep, Ido Nachum, Michael Gastpar
• Abstract要約: 我々は、Littlestone次元のあらゆるオンライン学習可能な関数のクラスが、有限情報複雑性を持つ学習アルゴリズムを認めることを証明した。 標準的なオンライン学習可能なクラスの場合、次元$d$のアフィン部分空間のインジケータ関数は、情報複雑性を$d$で対数的に上界化することができる。
• 参考スコア（独自算出の注目度）: 20.148961622211637
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that every online learnable class of functions of Littlestone dimension $d$ admits a learning algorithm with finite information complexity. Towards this end, we use the notion of a globally stable algorithm. Generally, the information complexity of such a globally stable algorithm is large yet finite, roughly exponential in $d$. We also show there is room for improvement; for a canonical online learnable class, indicator functions of affine subspaces of dimension $d$, the information complexity can be upper bounded logarithmically in $d$.
• Abstract（参考訳）: 我々は、Littlestone次元のあらゆるオンライン学習可能な関数のクラスが、有限情報複雑性を持つ学習アルゴリズムを認めることを証明した。 この目的のために、グローバルに安定なアルゴリズムという概念を用いる。 一般に、このようなグローバル安定アルゴリズムの情報複雑性は大きいが有限であり、概ね指数関数的に$d$である。 標準的なオンライン学習可能なクラスでは、次元$d$のアフィン部分空間のインジケータ関数は、情報複雑性を$d$で対数的に上界化することができる。

関連論文リスト

• 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)
• Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks [0.0]
  正準多面体のすべての次元の領域と面を決定する。 この全標準構造を計算するアルゴリズムを提案する。 得られたアルゴリズムは、中間ニューロンの数に時間とともに数値的に安定し、すべての次元にわたって正確な情報を得る。
  論文  参考訳（メタデータ） (2022-07-15T18:36:12Z)
• Learning Bayesian Networks in the Presence of Structural Side Information [22.734574764075226]
  本研究では,システムに関する構造的側面情報が得られる場合に,変数の集合のベイズネットワーク(BN)を学習する問題について検討する。 そこで我々は,そのような知識を学習プロセスに効率的に組み込むアルゴリズムを開発した。 我々の研究の結果、木幅の有界BNは複雑に学習できることが示されている。
  論文  参考訳（メタデータ） (2021-12-20T22:14:19Z)
• Provably efficient, succinct, and precise explanations [17.176431214060063]
  任意のブラックボックスモデルの予測を$f$で説明する問題を考える。 提案アルゴリズムは,提案アルゴリズムが返却する説明の簡潔さと正確さを保証し,効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-01T17:35:10Z)
• Provable Lifelong Learning of Representations [21.440845049501778]
  そこで本研究では,内部特徴表現を保守・洗練する,証明可能な生涯学習アルゴリズムを提案する。 すべてのタスクにおける任意の所望の精度に対して、表現の次元は、基礎となる表現の次元に近いままであることを示す。
  論文  参考訳（メタデータ） (2021-10-27T00:41:23Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。 この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
  論文  参考訳（メタデータ） (2020-07-30T04:18:51Z)
• 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)
• A Theory of Usable Information Under Computational Constraints [103.5901638681034]
  本稿では,複雑なシステムにおける情報推論のための新しいフレームワークを提案する。 我々の基礎はシャノンの情報理論の変分拡張に基づいている。 計算制約を組み込むことで,データから$mathcalV$-informationを確実に推定できることを示す。
  論文  参考訳（メタデータ） (2020-02-25T06:09:30Z)

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

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