論文の概要: 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問題を解く方法を示す。
提案手法の有効性と有効性を示す実証的証拠により,本研究の理論的結果と結果が裏付けられる。
関連論文リスト
- Learning High-Degree Parities: The Crucial Role of the Initialization [15.527103574584663]
本稿では,通常のニューラルネットワーク上での勾配勾配降下に対して,学習性は初期重み分布に依存することを示す。
ほぼ完全なパリティの正の値は$sigma=O(d-1)$とされ、よりシャープなしきい値現象に関する疑問が指摘される。
論文 参考訳（メタデータ） (2024-12-06T10:05:10Z) - Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations [40.77319247558742]
目的関数 $f_*:mathbbRdtomathbbR$ を加法構造で学習する際の計算複雑性について検討する。
2層ニューラルネットワークの勾配学習により,$f_*$の大規模なサブセットを効率的に学習できることを実証した。
論文 参考訳（メタデータ） (2024-06-17T17:59:17Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。
SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - 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) - 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) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳（メタデータ） (2022-06-26T06:51:31Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees [23.256961881716595]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳（メタデータ） (2022-01-21T01:26:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。