論文の概要: Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise

• arxiv url: http://arxiv.org/abs/2502.11413v1
• Date: Mon, 17 Feb 2025 03:54:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-18 14:15:36.657964
• Title: Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
• Title（参考訳）: ランダム分類雑音を用いた複数クラス線形分類の統計的検索困難性
• Authors: Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, Christos Tzamos,
• Abstract要約: ランダム分類ノイズ(RCN)を用いた分布自由PACモデルにおけるMLC(Multiclass Linear Classification)の課題について検討する。 本研究の主な貢献として,3つ以上のラベルが存在する場合,RCN との MLC の複雑性が著しく異なることを示す。
• 参考スコア（独自算出の注目度）: 41.23222309589753
• License:
• Abstract: We study the task of Multiclass Linear Classification (MLC) in the distribution-free PAC model with Random Classification Noise (RCN). Specifically, the learner is given a set of labeled examples $(x, y)$, where $x$ is drawn from an unknown distribution on $R^d$ and the labels are generated by a multiclass linear classifier corrupted with RCN. That is, the label $y$ is flipped from $i$ to $j$ with probability $H_{ij}$ according to a known noise matrix $H$ with non-negative separation $\sigma: = \min_{i \neq j} H_{ii}-H_{ij}$. The goal is to compute a hypothesis with small 0-1 error. For the special case of two labels, prior work has given polynomial-time algorithms achieving the optimal error. Surprisingly, little is known about the complexity of this task even for three labels. As our main contribution, we show that the complexity of MLC with RCN becomes drastically different in the presence of three or more labels. Specifically, we prove super-polynomial Statistical Query (SQ) lower bounds for this problem. In more detail, even for three labels and constant separation, we give a super-polynomial lower bound on the complexity of any SQ algorithm achieving optimal error. For a larger number of labels and smaller separation, we show a super-polynomial SQ lower bound even for the weaker goal of achieving any constant factor approximation to the optimal loss or even beating the trivial hypothesis.
• Abstract（参考訳）: ランダム分類ノイズ(RCN)を用いた分布自由PACモデルにおけるMLC(Multiclass Linear Classification)の課題について検討する。 具体的には、学習者はラベル付き例のセットである$(x, y)$を与えられるが、$x$は未知の分布から$R^d$で引き出され、ラベルはRCNで劣化した多クラス線形分類器によって生成される。 すなわち、ラベル$y$は、非負分離$\sigma: = \min_{i \neq j} H_{ii}-H_{ij}$を持つ既知のノイズ行列$H$に従って、確率$H_{ij}$で$i$から$j$に反転する。 目標は、0-1の小さな誤差で仮説を計算することである。 2つのラベルの特別な場合、先行研究は多項式時間アルゴリズムに最適な誤差を与える。 驚くべきことに、3つのラベルでさえ、このタスクの複雑さについてはほとんど分かっていない。 本研究の主な貢献として,3つ以上のラベルが存在する場合,RCN との MLC の複雑性が著しく異なることを示す。 具体的には、この問題に対して超多項式統計クエリ(SQ)の下位境界を証明している。 より詳しくは、3つのラベルと一定の分離であっても、最適誤差を達成する任意のSQアルゴリズムの複雑さに超多項式的な下限を与える。 ラベルの数が多く、分離が小さい場合には、最適損失に対する定数係数近似を達成したり、自明な仮説を破ったりするという、より弱い目標であっても、超ポリノミカルなSQ境界を示す。

関連論文リスト

• Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
  非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。 本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
  論文  参考訳（メタデータ） (2024-10-28T18:19:13Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。 本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。 我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
  論文  参考訳（メタデータ） (2024-08-27T18:28:31Z)
• Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity [6.812247730094931]
  任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。 また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
  論文  参考訳（メタデータ） (2023-09-25T09:50:15Z)
• 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)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• A Multiclass Classification Approach to Label Ranking [2.6905021039717987]
  マルチクラスの分類において、目標は、$mathcalY=1,; ldots,; K $ with $Kgeq 3$で値を値するランダムラベル$Y$の予測方法を学ぶことである。 本稿では,多クラス分類と後続確率推定の中間点である,この統計的学習問題の解析に焦点をあてる。
  論文  参考訳（メタデータ） (2020-02-21T17:12:43Z)

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

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