Fugu-MT 論文翻訳(概要): Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation

論文の概要: Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation

arxiv url: http://arxiv.org/abs/2609.35177v1
Date: Mon, 28 Sep 2026 13:42:53 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-02 16:23:57.559144
Title: Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation
Title（参考訳）: 高次元ブラックボックス積分近似のためのサブグループランク1格子
Abstract要約: ブラックボックス関数の積分を、期待値やカーネルの平均埋め込みから自己アテンションにおけるソフトマックスカーネルまで推定することは、機械学習の基本的なサブグループである。我々は、Korobov 生成元 $(1,t,dots,td-1)$ が固定乗法次数 $m$ のスカラー $t$ を使用する部分群階数 1 格子について研究する。 $n$ in $mathbbQ(_m)$の分割を使って、$m-1$許容ジェネレータの平均化は、$(m)因子によって定数を改善する
参考スコア（独自算出の注目度）: 14.335646280851229
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: Estimating integrals of black-box, high-dimensional functions, from expectations and kernel mean embeddings to the softmax kernel in self-attention, is a basic subroutine in machine learning. Rank-1 lattice rules suit this setting: they query the integrand only at a fixed point set and need no gradients. When the $n$ points serve as a design matrix $X\in\mathbb{R}^{n\times d}$ for a feature map, however, computing $Ψ(X)^\top v$ or $Ψ(X)w$ for an elementwise nonlinearity $Ψ$ costs $O(nd)$ time and memory for any standard quasi-Monte Carlo point set. We study subgroup rank-1 lattices, whose Korobov generator $(1,t,\dots,t^{d-1})$ uses a scalar $t$ of fixed multiplicative order $m$. Splitting $\mathbb{F}_n^\times$ into cosets of $\langle t\rangle$ reduces both maps to short cyclic correlations evaluated by FFT, giving exact results for arbitrary $Ψ$ in $O(n\log m)$ time and $O(n)$ memory, without forming $X$. Since fixing $m$ falls outside classical component-by-component theory, we prove convergence directly: via resultants with the cyclotomic polynomial $Φ_m$, the squared worst-case error in the Korobov space decays as $O(n^{-(α-1)/(m-1)})$ for prime $m\ge d+1$, and this threshold is exact. Using the splitting of $n$ in $\mathbb{Q}(ζ_m)$, averaging over the $m-1$ admissible generators improves the constant by a factor $Θ(m-1)$. Empirically, the subgroup lattice beats Gaussian and orthogonal random features and scrambled Sobol' and Halton points in 49 of 54 synthetic kernel-estimation settings and all 45 softmax-attention settings on nine real datasets, and builds a sample set with $d=2048$, $n\approx4.1\times10^7$ in 2.3 ms.
Abstract（参考訳）: 予測からカーネル平均埋め込みまでのブラックボックスの高次元関数の積分を自己注意でソフトマックスカーネルに埋め込むことは、機械学習の基本的なサブルーチンである。ランク1格子規則はこの設定に適合する: 彼らは積分を定点集合でのみクエリし、勾配は不要である。しかし、ある特徴写像に対する設計行列 $X\in\mathbb{R}^{n\times d}$ として作用するとき、任意の標準準モンテカルロ点集合に対する時間とメモリに対して、元的に非線形であることに対して $n$$$$$$$$$$$$$$$$$O(nd)$$$$$ となる。我々は、Korobov 生成元 $(1,t,\dots,t^{d-1})$ が固定乗法次数 $m$ のスカラー $t$ を使用する部分群階数 1 格子について研究する。 $\langle t\rangle$ の余集合に $\mathbb{F}_n^\times$ を分割すると、両方の写像は FFT で評価された短い巡回相関に還元される。 m) 時間と$O (n)$メモリで、$X$を作らない。古典的成分-成分理論の外に$m$を固定すると、直接収束が証明される: シンクロトミック多項式 $ _m$ の帰結によって、コロボフ空間の2乗最悪のケース誤差は $O(n^{-(α-1)/(m-1)})$ として崩壊し、このしきい値は真である。 averaging over the $m-1$ admissible generators is improve the constant by a factor $(m-1)$。経験的に、サブグループ格子はガウス的および直交的ランダムな特徴を破り、54の合成カーネル推定設定のうち49のソボルとハルトンを、9つの実データセット上の45のソフトマックスアテンション設定のうち49の点でスクランブルし、2.3ミリ秒で$d=2048$, $n\approx4.1\times10^7$でサンプルセットを構築する。

論文の概要: Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation

関連論文リスト