論文の概要: Robust testing of low-dimensional functions

• arxiv url: http://arxiv.org/abs/2004.11642v2
• Date: Tue, 12 Jan 2021 22:59:17 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-10 04:26:39.357924
• Title: Robust testing of low-dimensional functions
• Title（参考訳）: 低次元関数のロバストテスト
• Authors: Anindya De, Elchanan Mossel and Joe Neeman
• Abstract要約: 著者たちの最近の研究は、線型$k$-juntasがテスト可能であることを示した。 耐雑音性試験への関心が高まった後, 本論文では, 耐雑音性(あるいは頑健性)バージョンを実証する。 クエリ複雑性が$kO(mathsfpoly(log k/epsilon))$,$k$-halfspacesの交叉のクラスに対して完全耐雑音試験器を得る。
• 参考スコア（独自算出の注目度）: 8.927163098772589
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. A recent work of the authors showed that linear $k$-juntas are testable. Thus there exists an algorithm to distinguish between: 1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ which is a linear $k$-junta with surface area $s$, 2. $f$ is $\epsilon$-far from any linear $k$-junta with surface area $(1+\epsilon)s$, where the query complexity of the algorithm is independent of the ambient dimension $n$. Following the surge of interest in noise-tolerant property testing, in this paper we prove a noise-tolerant (or robust) version of this result. Namely, we give an algorithm which given any $c>0$, $\epsilon>0$, distinguishes between 1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ has correlation at least $c$ with some linear $k$-junta with surface area $s$. 2. $f$ has correlation at most $c-\epsilon$ with any linear $k$-junta with surface area at most $s$. The query complexity of our tester is $k^{\mathsf{poly}(s/\epsilon)}$. Using our techniques, we also obtain a fully noise tolerant tester with the same query complexity for any class $\mathcal{C}$ of linear $k$-juntas with surface area bounded by $s$. As a consequence, we obtain a fully noise tolerant tester with query complexity $k^{O(\mathsf{poly}(\log k/\epsilon))}$ for the class of intersection of $k$-halfspaces (for constant $k$) over the Gaussian space. Our query complexity is independent of the ambient dimension $n$. Previously, no non-trivial noise tolerant testers were known even for a single halfspace.
• Abstract（参考訳）: 高次元推論における自然問題は、分類器 $f:\mathbb{R}^n \rightarrow \{-1,1\}$ がその入力データの少数の線形方向に依存するかどうかを決定することである。 関数 $g: \mathbb{r}^n \rightarrow \{-1,1\}$、入力空間の$k$-次元部分空間によって完全に決定される場合、線型 $k$-junta と呼ぶ。 著者たちの最近の研究は、線型$k$-juntasがテスト可能であることを示した。 したがって、次のように区別するアルゴリズムが存在する。 1.$f: \mathbb{R}^n \rightarrow \{-1,1\}$ これは表面積が$s$の線型$k$-juntaである。 2.$f$ is $\epsilon$-far from any linear $k$-junta with surface area $(1+\epsilon)s$ ここでアルゴリズムのクエリの複雑さは周囲の次元$n$とは独立である。 耐雑音性試験への関心が高まった後, 本論文では, 耐雑音性(あるいは頑健性)の検証を行った。 すなわち、任意の$c>0$,$\epsilon>0$を与えられたアルゴリズムを区別する。 1.$f: \mathbb{R}^n \rightarrow \{-1,1\}$は、少なくとも$c$と、表面積が$s$の線型$k$-juntaとの相関を持つ。 2.$f$ は、最大 $c-\epsilon$ と、表面積が最大 $s$ の線形 $k$-junta との相関を持つ。 テスト担当者のクエリの複雑さは$k^{\mathsf{poly}(s/\epsilon)}$である。 この手法を用いることで、任意のクラス$\mathcal{C}$ of linear $k$-juntas with surface area with $s$に対して同じクエリ複雑性を持つ完全耐雑音試験器も得られる。 その結果、クエリ複雑性が$k^{O(\mathsf{poly}(\log k/\epsilon))} である完全雑音耐性試験器を、ガウス空間上の$k$-半空間(定数$k$)の交叉のクラスに対して得られる。 私たちのクエリの複雑さは、周囲の次元$n$とは独立です。 以前は、1つのハーフスペースでさえ、非自明なノイズ耐性テスターは知られていない。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
  本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。 この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
  論文  参考訳（メタデータ） (2023-02-07T10:39:44Z)
• 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)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Ridgeless Interpolation with Shallow ReLU Networks in $1D$ is Nearest Neighbor Curvature Extrapolation and Provably Generalizes on Lipschitz Functions [16.75218291152252]
  一層のReLUネットワークの正確な幾何学的記述を1つの線形単位を持つ$z(x;theta)$で証明する。 我々はこれらをリッジレスReLU補間剤と呼ぶ。 この結果から,リッジレスReLU補間器は1d$リプシッツ関数の学習に最適な一般化を実現することがわかった。
  論文  参考訳（メタデータ） (2021-09-27T11:32:24Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• 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)

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

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