論文の概要: Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions

• arxiv url: http://arxiv.org/abs/2501.12365v1
• Date: Tue, 21 Jan 2025 18:45:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-22 14:19:25.877361
• Title: Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions
• Title（参考訳）: 一般化q-ary関数のスパースフーリエ変換の効率的なアルゴリズム
• Authors: Darin Tsui, Kunal Talreja, Amirali Aghazadeh,
• Abstract要約: GFastは,f:mathbbZ_qnrightarrow mathbbR$のスパースフーリエ変換を計算するアルゴリズムである。 GFastは、ニューラルネットワークの予測的相互作用を、既存のアルゴリズムと比較して25%$より小さな正規化平均二乗誤差で説明する。
• 参考スコア（独自算出の注目度）: 0.3004066195320147
• License:
• Abstract: Computing the Fourier transform of a $q$-ary function $f:\mathbb{Z}_{q}^n\rightarrow \mathbb{R}$, which maps $q$-ary sequences to real numbers, is an important problem in mathematics with wide-ranging applications in biology, signal processing, and machine learning. Previous studies have shown that, under the sparsity assumption, the Fourier transform can be computed efficiently using fast and sample-efficient algorithms. However, in many practical settings, the function is defined over a more general space -- the space of generalized $q$-ary sequences $\mathbb{Z}_{q_1} \times \mathbb{Z}_{q_2} \times \cdots \times \mathbb{Z}_{q_n}$ -- where each $\mathbb{Z}_{q_i}$ corresponds to integers modulo $q_i$. A naive approach involves setting $q=\max_i{q_i}$ and treating the function as $q$-ary, which results in heavy computational overheads. Herein, we develop GFast, an algorithm that computes the $S$-sparse Fourier transform of $f$ with a sample complexity of $O(Sn)$, computational complexity of $O(Sn \log N)$, and a failure probability that approaches zero as $N=\prod_{i=1}^n q_i \rightarrow \infty$ with $S = N^\delta$ for some $0 \leq \delta < 1$. In the presence of noise, we further demonstrate that a robust version of GFast computes the transform with a sample complexity of $O(Sn^2)$ and computational complexity of $O(Sn^2 \log N)$ under the same high probability guarantees. Using large-scale synthetic experiments, we demonstrate that GFast computes the sparse Fourier transform of generalized $q$-ary functions using $16\times$ fewer samples and running $8\times$ faster than existing algorithms. In real-world protein fitness datasets, GFast explains the predictive interactions of a neural network with $>25\%$ smaller normalized mean-squared error compared to existing algorithms.
• Abstract（参考訳）: q$-ary 関数 $f:\mathbb{Z}_{q}^n\rightarrow \mathbb{R}$ のフーリエ変換を計算し、$q$-ary 列を実数に写し、生物学、信号処理、機械学習の幅広い応用を持つ数学において重要な問題である。 従来の研究では、疎性仮定の下で、フーリエ変換は高速でサンプル効率のよいアルゴリズムを用いて効率的に計算できることが示されている。 一般化された$q$-ary Sequences $\mathbb{Z}_{q_1} \times \mathbb{Z}_{q_2} \times \cdots \mathbb{Z}_{q_n}$ -- ここで、各$\mathbb{Z}_{q_i}$は整数 modulo $q_i$ に対応する。 単純なアプローチでは、$q=\max_i{q_i}$を設定し、関数を$q$-aryとして扱う。 ここで、GFastは、$S$スパースフーリエ変換を$f$で計算し、$O(Sn)$、$O(Sn \log N)$の計算複雑性を計算し、$N=\prod_{i=1}^n q_i \rightarrow \infty$を$S = N^\delta$ for some $0 \leq \delta < 1$としてゼロに近づく失敗確率を求める。 ノイズの存在下では、GFastの頑健なバージョンは、同じ高い確率保証の下で、$O(Sn^2)$と$O(Sn^2 \log N)$の計算複雑性で変換を計算することをさらに実証する。 大規模な合成実験を用いて、GFast は、より少ないサンプルと既存のアルゴリズムよりも高速な 8 倍の時間で、一般化された$q$-ary 関数のスパースフーリエ変換を計算することを実証した。 実世界のタンパク質の適合性データセットでは、GFastはニューラルネットワークの予測的相互作用を、既存のアルゴリズムと比較して25\%$より小さい正規化平均二乗誤差で説明する。

関連論文リスト

• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
  シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。 適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
  論文  参考訳（メタデータ） (2024-11-08T17:10:38Z)
• 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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Efficiently Computing Sparse Fourier Transforms of $q$-ary Functions [12.522202946750157]
  長さ$n$シーケンスの$q$-ary関数に特化してスパースフーリエ変換アルゴリズムを開発する。 固定$q$の場合、$q$-SFTのロバストバージョンはサンプル複雑性が$O(Sn2)$であり、計算複雑性が$O(Sn3)$と同じ保証を持つことを示す。
  論文  参考訳（メタデータ） (2023-01-15T22:04:53Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• Convergence of Sparse Variational Inference in Gaussian Processes Regression [29.636483122130027]
  計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
  論文  参考訳（メタデータ） (2020-08-01T19:23:34Z)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。 我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-11T00:55:35Z)

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

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