論文の概要: Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

• arxiv url: http://arxiv.org/abs/2407.11832v1
• Date: Tue, 16 Jul 2024 15:20:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-17 14:13:22.156693
• Title: Approximating the Number of Relevant Variables in a Parity Implies Proper Learning
• Title（参考訳）: 親の学習に影響を及ぼす関係変数数の近似
• Authors: Nader H. Bshouty, George Haddad,
• Abstract要約: パリティ関数の関連変数数を近似することはパリティを適切に学習するのと同じくらい難しいことを示す。 2つ目の結果では、任意の$T(n)$-timeアルゴリズムから、任意のパリティ$f$に対して、関連する変数の数を$gamma$-approximation($d(f)$ of $f$)を返すことを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities. More specifically, let $\gamma:{\mathbb R}^+\to {\mathbb R}^+$, where $\gamma(x) \ge x$, be any strictly increasing function. In our first result, we show that from any polynomial-time algorithm that returns a $\gamma$-approximation, $D$ (i.e., $\gamma^{-1}(d(f)) \leq D \leq \gamma(d(f))$), of the number of relevant variables~$d(f)$ for any parity $f$, we can, in polynomial time, construct a solution to the long-standing open problem of polynomial-time learning $k(n)$-sparse parities (parities with $k(n)\le n$ relevant variables), where $k(n) = \omega_n(1)$. In our second result, we show that from any $T(n)$-time algorithm that, for any parity $f$, returns a $\gamma$-approximation of the number of relevant variables $d(f)$ of $f$, we can, in polynomial time, construct a $poly(\Gamma(n))T(\Gamma(n)^2)$-time algorithm that properly learns parities, where $\Gamma(x)=\gamma(\gamma(x))$. If $T(\Gamma(n)^2)=\exp({o(n/\log n)})$, this would resolve another long-standing open problem of properly learning parities in the presence of random classification noise in time $\exp({o(n/\log n)})$.
• Abstract（参考訳）: ランダムな分類ノイズの存在下で、ランダムな一様ラベル付き例を通してパリティ関数にアクセスできるモデルを考える。 本稿では,パリティ関数における関連する変数の数を近似することはパリティ関数を適切に学習するのと同じくらい難しいことを示す。 具体的には、$\gamma:{\mathbb R}^+\to {\mathbb R}^+$ とする。 最初の結果から、$\gamma$-approximation, $D$ (i., $\gamma^{-1}(d(f)) \leq D \leq \gamma(d(f))$), of the number of relevant variables~$d(f)$ for any parity $f$, the polynomial time can construct a solution to a long-standing open problem of polynomial-time learning $k(n)$-sparse parities (parities with $k(n)\le n$ relevant variables), where $k(n) = \omega_n(1)$。 第二の結果として、任意のパリティ$f$に対して$\gamma$-approximation of the number of relevant variables $d(f)$ of $f$, we can be constructed a $poly(\Gamma(n))T(\Gamma(n)^2)$-time algorithm that $\Gamma(x)=\gamma(\gamma(x))$。 もし$T(\Gamma(n)^2)=\exp({o(n/\log n)})$なら、これは時間$\exp({o(n/\log n)})$におけるランダムな分類ノイズの存在下でパリティを適切に学習するもう一つの長年のオープンな問題を解決する。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• A Multivariate Complexity Analysis of Qualitative Reasoning Problems [9.594432031144716]
  我々は、それぞれ$f(k) cdot 2O(n)$, $f(k)n$, timeで解ける問題のクラス FPE と XE を紹介する。 有効幅$k$の部分順序時間問題は16kn$時間で解決可能であり,XEに含まれることを示す。 また、アレンの区間代数のネットワーク整合性問題は、$k$以上と重複しないが、$(2nk)2k cdot 2n$ timeで解決可能であり、その中に含まれることを示す。
  論文  参考訳（メタデータ） (2022-09-30T07:29:53Z)
• List-Decodable Covariance Estimation [1.9290392443571387]
  共分散推定アルゴリズムを初めて提案する。 この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
  論文  参考訳（メタデータ） (2022-06-22T09:38:06Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
  我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。 また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
  論文  参考訳（メタデータ） (2022-02-11T23:53:43Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• 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 Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
  グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。 これは高速多重極法について証明された最初の公式な制限である。
  論文  参考訳（メタデータ） (2020-11-04T18:35:02Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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