論文の概要: On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
- arxiv url: http://arxiv.org/abs/2407.05622v1
- Date: Mon, 8 Jul 2024 05:30:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-09 17:00:01.922810
- Title: On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
- Title（参考訳）: 統計的およびグラディエントなクエリによるスパース関数の複雑性について
- Authors: Nirmit Joshi, Theodor Misiakiewicz, Nathan Srebro,
- Abstract要約: 一般的な製品分布に対するスパース関数のサポートを学習するために,$mathsfDLQ$のクエリ複雑性を厳密に評価する。
正方形損失の場合、$mathsfDLQ$は、$mathsfSQ$よりも潜在的にずっと悪い相関統計クエリ$(mathsfCSQ)$-の複雑さと一致する。
また、$mathsfDLQ$が2層学習の複雑さを正確に記述することで、(確率的な)勾配勾配で学習をキャプチャできることを示す。
- 参考スコア（独自算出の注目度）: 25.03801392644285
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The goal of this paper is to investigate the complexity of gradient algorithms when learning sparse functions (juntas). We introduce a type of Statistical Queries ($\mathsf{SQ}$), which we call Differentiable Learning Queries ($\mathsf{DLQ}$), to model gradient queries on a specified loss with respect to an arbitrary model. We provide a tight characterization of the query complexity of $\mathsf{DLQ}$ for learning the support of a sparse function over generic product distributions. This complexity crucially depends on the loss function. For the squared loss, $\mathsf{DLQ}$ matches the complexity of Correlation Statistical Queries $(\mathsf{CSQ})$--potentially much worse than $\mathsf{SQ}$. But for other simple loss functions, including the $\ell_1$ loss, $\mathsf{DLQ}$ always achieves the same complexity as $\mathsf{SQ}$. We also provide evidence that $\mathsf{DLQ}$ can indeed capture learning with (stochastic) gradient descent by showing it correctly describes the complexity of learning with a two-layer neural network in the mean field regime and linear scaling.
- Abstract（参考訳）: 本研究の目的は,スパース関数(ユンタス)の学習における勾配アルゴリズムの複雑さを検討することである。
我々は、任意のモデルに対する特定の損失に対する勾配クエリをモデル化するために、微分可能な学習クエリ(\mathsf{DLQ}$)と呼ばれる統計クエリの種類を紹介します。
一般積分布上のスパース関数のサポートを学習するために,$\mathsf{DLQ}$のクエリ複雑性を厳密に評価する。
この複雑さは損失関数に大きく依存する。
平方損失に対して、$\mathsf{DLQ}$は相関統計量$(\mathsf{CSQ})$--ポテンシャル的に$\mathsf{SQ}$よりもはるかに悪い。
しかし、$\ell_1$損失を含む他の単純な損失関数の場合、$\mathsf{DLQ}$は常に$\mathsf{SQ}$と同じ複雑さを達成する。
また、$\mathsf{DLQ}$は、平均場状態と線形スケーリングにおける2層ニューラルネットワークによる学習の複雑さを正しく記述することにより、(確率的な)勾配勾配で学習をキャプチャできることを示す。
関連論文リスト
- 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_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
論文 参考訳（メタデータ） (2024-03-04T18:30:33Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳（メタデータ） (2023-11-23T02:19:32Z) - 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) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。