論文の概要: Hardness of Learning Fixed Parities with Neural Networks

• arxiv url: http://arxiv.org/abs/2501.00817v1
• Date: Wed, 01 Jan 2025 12:04:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-05 17:16:37.588920
• Title: Hardness of Learning Fixed Parities with Neural Networks
• Title（参考訳）: ニューラルネットワークを用いた固定親の学習の難しさ
• Authors: Itamar Shoshani, Ohad Shamir,
• Abstract要約: パリティ関数の学習は、学習理論における標準的な問題である。 ある最小サイズの固定パリティでは、それをターゲット関数として使用して、一層型ReLUネットワークをトレーニングしても意味のあるものは発生しない。
• 参考スコア（独自算出の注目度）: 33.84710024813985
• License:
• Abstract: Learning parity functions is a canonical problem in learning theory, which although computationally tractable, is not amenable to standard learning algorithms such as gradient-based methods. This hardness is usually explained via statistical query lower bounds [Kearns, 1998]. However, these bounds only imply that for any given algorithm, there is some worst-case parity function that will be hard to learn. Thus, they do not explain why fixed parities - say, the full parity function over all coordinates - are difficult to learn in practice, at least with standard predictors and gradient-based methods [Abbe and Boix-Adsera, 2022]. In this paper, we address this open problem, by showing that for any fixed parity of some minimal size, using it as a target function to train one-hidden-layer ReLU networks with perturbed gradient descent will fail to produce anything meaningful. To establish this, we prove a new result about the decay of the Fourier coefficients of linear threshold (or weighted majority) functions, which may be of independent interest.
• Abstract（参考訳）: 学習パリティ関数は学習理論における標準的な問題であり、計算的に抽出可能であるが、勾配法のような標準的な学習アルゴリズムには適用できない。 この硬さは通常、統計的クエリの下界 [Kearns, 1998] を通して説明される。 しかし、これらの境界は任意のアルゴリズムに対して、学習が難しい最悪のパーティ関数が存在することを暗示しているだけである。 したがって、固定パリティ(例えば、すべての座標上の完全パリティ関数)が、少なくとも標準的な予測器や勾配に基づく手法(Abbe と Boix-Adsera, 2022)で、実際に学習することが難しい理由を説明できない。 本稿では,最小サイズの任意の固定パリティに対して,摂動勾配勾配の1層ReLUネットワークを目標関数として用いると,何の意味も生み出すことができないことを示すことで,この問題に対処する。 これを確立するために、線形しきい値(あるいは重み付き多数)関数のフーリエ係数の崩壊に関する新たな結果が証明される。

関連論文リスト

• Robustly Learning Single-Index Models via Alignment Sharpness [40.886706402941435]
  単行数モデル学習の問題点を,無知モデルにおける損失$L2$で検討する。 最適損失に対する定数係数近似を達成し,効率的な学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-27T18:48:07Z)
• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。 いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
  論文  参考訳（メタデータ） (2023-02-13T15:13:22Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Learning Globally Smooth Functions on Manifolds [94.22412028413102]
  スムーズな関数の学習は、線形モデルやカーネルモデルなどの単純なケースを除いて、一般的に難しい。 本研究は,半無限制約学習と多様体正規化の技法を組み合わせることで,これらの障害を克服することを提案する。 軽度条件下では、この手法は解のリプシッツ定数を推定し、副生成物として大域的に滑らかな解を学ぶ。
  論文  参考訳（メタデータ） (2022-10-01T15:45:35Z)
• A Unified Framework for Implicit Sinkhorn Differentiation [58.56866763433335]
  暗黙の微分によってシンクホーン層の解析勾配を求めるアルゴリズムを提案する。 特にGPUメモリなどのリソースが不足している場合には,計算効率が向上する。
  論文  参考訳（メタデータ） (2022-05-13T14:45:31Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Multi-task Supervised Learning via Cross-learning [102.64082402388192]
  我々は,様々なタスクを解くことを目的とした回帰関数の集合を適合させることで,マルチタスク学習と呼ばれる問題を考える。 我々の新しい定式化では、これらの関数のパラメータを2つに分けて、互いに近づきながらタスク固有のドメインで学習する。 これにより、異なるドメインにまたがって収集されたデータが、互いのタスクにおける学習パフォーマンスを改善するのに役立つ、クロス・ファーティライズが促進される。
  論文  参考訳（メタデータ） (2020-10-24T21:35:57Z)
• When Hardness of Approximation Meets Hardness of Learning [35.39956227364153]
  線形クラスと浅層ネットワークを用いた近似の硬さと,相関クエリと勾配差を用いた学習の硬さを両立させる単一の硬さ特性を示す。 これにより、パリティ関数、DNF式および$AC0$回路の近似の硬さと学習性に関する新たな結果が得られる。
  論文  参考訳（メタデータ） (2020-08-18T17:41:28Z)

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

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