論文の概要: Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time

• arxiv url: http://arxiv.org/abs/2610.32940v1
• Date: Fri, 23 Oct 2026 17:34:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 01:38:06.623101
• Title: Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time
• Title（参考訳）: 完全多項式時間におけるReLUの正の線形結合の学習
• Abstract要約: この学習課題に対して,最初の完全多項式時間アルゴリズムを提案する。 我々のアルゴリズムは、$mathrmpoly(d, k, 1/)$サンプルを描画し、$mathrmpoly(d, k, 1/)$タイムで実行し、高い確率でターゲット概念に$-closeの仮説を出力する。
• 参考スコア（独自算出の注目度）: 56.773730898972225
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the fundamental problem of PAC learning positive linear combinations of $k$ arbitrary ReLU activations on $\mathbb{R}^d$ with respect to the Gaussian distribution, in $L_2$ loss. We give the first fully-polynomial time algorithm for this learning task. Specifically, our algorithm draws $\mathrm{poly}(d, k, 1/ε)$ samples, runs in $\mathrm{poly}(d, k, 1/ε)$ time, and outputs a hypothesis that is $ε$-close to the target concept with high probability. All prior algorithms for this problem require super-polynomial time in $k$ or $1/ε$, or leverage strong well-conditioned assumptions on the weight matrix. On a technical level, our approach develops a novel boosting procedure of a ``weak'' learner that recovers the hidden weight vectors to constant error, in a list-decodable manner. To develop this ``weak'' learning procedure, we leverage implicit tensor computation techniques to construct a low-degree filtering procedure based on Hermite tensors of the target function. This procedure amplifies separation among (clusters of) weight vectors to learn each of them to constant error. We then argue that the same procedure can be used for improving the estimation of hidden weight vectors, using gradient descent-like updates on the Euclidean sphere. A crucial ingredient of our algorithm is a pruning approach that ensures only relevant vectors that approximate the hidden weight vectors at target accuracy are maintained by the algorithm.
• Abstract（参考訳）: ガウス分布に関して、$k$任意のReLUアクティベーションを$\mathbb{R}^d$で学習するPAC学習正線形結合の基本的な問題を、$L_2$損失で研究する。 この学習課題に対して,最初の完全多項式時間アルゴリズムを提案する。 具体的には、我々のアルゴリズムは、$\mathrm{poly}(d, k, 1/ε)$サンプルを描画し、$\mathrm{poly}(d, k, 1/ε)$時間で実行し、高い確率でターゲット概念に$ε$閉じた仮説を出力する。 この問題の全ての前のアルゴリズムは、$k$または$/ε$の超多項式時間を必要とするか、あるいは重み行列上の強い条件付き仮定を利用する。 技術的レベルでは,隠れた重みベクトルを一定誤差に復元する‘weak'学習者の新規な促進手順を,リストデコタブルな方法で開発する。 この「弱」学習手法を開発するために、暗黙テンソル計算手法を活用し、ターゲット関数のHermiteテンソルに基づく低次フィルタリング手順を構築する。 この手順は、重みベクトル間の分離を増幅し、それぞれを一定の誤差で学習する。 そこで我々は、ユークリッド球面上の勾配降下のような更新を用いて、隠れ重みベクトルの推定を改善するために、同じ手順を使うことができると論じる。 本アルゴリズムの重要な要素は,対象精度で隠れた重みベクトルを近似する関係ベクトルのみをアルゴリズムで維持するプルーニング手法である。

関連論文リスト

• Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
  我々は,暗黙のモーメントテンソル複雑性を表わす汎用的アルゴリズムを開発した。 暗黙のモーメント推定アルゴリズムを利用して、以下のモデルに対して最初の$mathrmpoly(d, k, 1/epsilon)$-time学習アルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-11-23T23:13:24Z)
• 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)
• Learning Narrow One-Hidden-Layer ReLU Networks [30.63086568341548]
  最初のアルゴリズムは$k$が定数であるときに成功する。 我々は、十分に近接したニューロンを一緒に崩壊させることができると主張するために、マルチスケール分析を用いる。
  論文  参考訳（メタデータ） (2023-04-20T17:53:09Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)

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

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