論文の概要: Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent
- arxiv url: http://arxiv.org/abs/2404.12376v1
- Date: Thu, 18 Apr 2024 17:57:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-19 18:42:29.771364
- Title: Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent
- Title（参考訳）: 確率勾配変化を伴うkスパースパリティ問題に対する統計的問合せ下界のマッチング
- Authors: Yiwen Kou, Zixiang Chen, Quanquan Gu, Sham M. Kakade,
- Abstract要約: 勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
- 参考スコア（独自算出の注目度）: 83.85536329832722
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The $k$-parity problem is a classical problem in computational complexity and algorithmic theory, serving as a key benchmark for understanding computational classes. In this paper, we solve the $k$-parity problem with stochastic gradient descent (SGD) on two-layer fully-connected neural networks. We demonstrate that SGD can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube ($k\le O(\sqrt{d})$) with a sample complexity of $\tilde{O}(d^{k-1})$ using $2^{\Theta(k)}$ neurons, thus matching the established $\Omega(d^{k})$ lower bounds of Statistical Query (SQ) models. Our theoretical analysis begins by constructing a good neural network capable of correctly solving the $k$-parity problem. We then demonstrate how a trained neural network with SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors. Our theoretical results and findings are supported by empirical evidence, showcasing the efficiency and efficacy of our approach.
- Abstract（参考訳）: k$-parity問題($k$-parity problem)は計算複雑性とアルゴリズム理論における古典的な問題であり、計算クラスを理解するための重要なベンチマークとして機能する。
本稿では,2層完全連結ニューラルネットワーク上での確率勾配勾配(SGD)を用いた$k$-parity問題を解く。
我々は、SGDが$d$-dimensional hypercube$k\le O(\sqrt{d})$)上の$k$-sparseパリティ問題を、$\tilde{O}(d^{k-1})$$2^{\Theta(k)}$のニューロンで効率的に解くことができ、確立された$\Omega(d^{k})$low bounds of Statistical Query (SQ)モデルと一致することを示した。
私たちの理論的分析は、$k$-parityの問題を正しく解ける優れたニューラルネットワークを構築することから始まります。
次に、SGDを用いたトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
提案手法の有効性と有効性を示す実証的証拠により,本研究の理論的結果と結果が裏付けられる。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Collaborative non-parametric two-sample testing [55.98760097296213]
目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。
グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。
提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
論文 参考訳（メタデータ） (2024-02-08T14:43:56Z) - SGD Finds then Tunes Features in Two-Layer Neural Networks with
near-Optimal Sample Complexity: A Case Study in the XOR problem [1.3597551064547502]
本研究では,2層ニューラルネットワーク上でのミニバッチ降下勾配(SGD)の最適化過程について考察する。
二次 XOR' 関数 $y = -x_ix_j$ でラベル付けされた $d$-dimensional Boolean hypercube から得られるデータから、人口誤差 $o(1)$ と $d :textpolylog(d)$ のサンプルをトレーニングすることが可能であることを証明した。
論文 参考訳（メタデータ） (2023-09-26T17:57:44Z) - 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) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Generalization and Stability of Interpolating Neural Networks with
Minimal Width [37.908159361149835]
補間系における勾配によって訓練された浅層ニューラルネットワークの一般化と最適化について検討する。
トレーニング損失数は$m=Omega(log4 (n))$ニューロンとニューロンを最小化する。
m=Omega(log4 (n))$のニューロンと$Tapprox n$で、テスト損失のトレーニングを$tildeO (1/)$に制限します。
論文 参考訳（メタデータ） (2023-02-18T05:06:15Z) - Is Stochastic Gradient Descent Near Optimal? [0.0]
本研究では,多数のサンプルとクエリの総数を用いて,勾配勾配勾配の誤差が小さいことを示す。
このことは、SGDがJoen & Van Roy (arXiv:2203.00246) の情報理論的なサンプル複雑性境界を計算的に効率よく達成していることを示唆している。
論文 参考訳（メタデータ） (2022-09-18T18:26:43Z) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳（メタデータ） (2022-06-26T06:51:31Z) - High-Dimensional Inference over Networks: Linear Convergence and
Statistical Guarantees [20.701475313495884]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳（メタデータ） (2022-01-21T01:26:08Z) - An efficient projection neural network for $\ell_1$-regularized logistic
regression [10.517079029721257]
本稿では, $ell_$-regularized logistics regression のための単純な投影ニューラルネットワークを提案する。
提案したニューラルネットワークは、余分な補助変数や滑らかな近似を必要としない。
また、リアプノフ理論を用いて、提案したニューラルネットワークの収束について検討し、任意の初期値を持つ問題の解に収束することを示す。
論文 参考訳（メタデータ） (2021-05-12T06:13:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。