PaperlayerView exact revision on arXiv

Source-linked AI summary

Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation

Yueming Lyu

arXiv:2609.35177v1cs.LG

TL;DR

High-dimensional black-box integration is common in machine learning, but direct feature-map evaluation on lattice points can be costly. The paper uses subgroup structure to compute these transforms efficiently and reports strong synthetic and real-dataset results against other feature-map constructions.

  • Problem

    High-dimensional black-box integration is common in machine learning, while direct evaluation of lattice-based feature maps incurs O(nm) work for elementwise transforms.

    Source: §1 · p. 1, §5.1 · p. 12

  • Method

    The method uses a fixed-order Korobov generator and coset-wise FFT cyclic correlations to compute feature-map transforms exactly without forming the design matrix.

    Source: §1 · p. 2

  • Results

    The subgroup lattice was most accurate among five feature-map constructions in 49 of 54 synthetic settings (up to 13.5× advantage) and all 45 softmax-attention settings on nine datasets (1.67× mean advantage).

    Source: §9 · p. 34

  • Takeaways & Limitations

    For prime m ≥ d+1, the fixed-order structure needed for fast transforms is compatible with convergence, while m ≤ d is the exact threshold below which squared worst-case error stays bounded below.

    Source: §1 · p. 3, §9 · p. 34

    The reported construction timings measure construction only, come from a single GPU, and do not measure applying the feature map to data.

    Source: §8.1.2 · p. 31

Abstract

from arXiv · show

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 $\Psi(X)^\top v$ or $\Psi(X)w$ for an elementwise nonlinearity $\Psi$ 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 $\Psi$ 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 $\Phi_m$, the squared worst-case error in the Korobov space decays as $O(n^{-(\alpha-1)/(m-1)})$ for prime $m\ge d+1$, and this threshold is exact. Using the splitting of $n$ in $\mathbb{Q}(\zeta_m)$, averaging over the $m-1$ admissible generators improves the constant by a factor $\Theta(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.

1 Introduction

High-dimensional feature-map evaluation makes the usual O(nd) cost of applying an elementwise nonlinearity a bottleneck, even when the point set itself is suitable for black-box integration. The paper uses fixed-order subgroup rank-1 lattices to accelerate these operations and proves convergence under an exact dimension threshold, alongside empirical comparisons.

1 Introduction

  • Standard point sets require O(nd) time and memory for Ψ(X)ᵀv or Ψ(X)w, which is prohibitive when both n and d are large.At d = 2048 and n ≈ 4.1 × 10^7, X would contain about 8.4 × 10^10 entries, or roughly 670 GB in double precision.Source: §1 · p. 2
  • The construction fixes a scalar t of small multiplicative order m in the Korobov power-form generator z(t) = (1, t, …, t^(d−1)) mod n.The admissible generator pool remains fixed in size as n grows, so classical CBC averaging arguments do not apply.Source: §1 · p. 2

1.1 Contributions

  • Coset-based length-m FFT correlations compute both feature-map operations exactly for arbitrary Ψ in O(n log m) time and O(n) memory, without forming X.The transform uses n evaluations of Ψ rather than the O(nd) evaluations required by direct evaluation.Source: §1 · p. 2, §1.1 · p. 3
  • For prime m ≥ d + 1, squared worst-case error is O(n^-(α-1)/(m-1)); for m ≤ d it is bounded below by 2, making the threshold exact.The convergence bound applies to every admissible generator for sufficiently large primes n ≡ 1 (mod m).Source: §1.1 · p. 3
  • Averaging over the m − 1 admissible generators improves the average squared worst-case-error bound by a factor Θ(m − 1) at the same exponent.At least one generator attains the sharper bound.Source: §1.1 · pp. 3–4
  • 49 of 54 synthetic kernel-estimation settings and all 45 softmax-attention settings favor the subgroup lattice as most accurate, with reported advantages up to 13.5× and mean 1.67×, respectively.The comparisons use five feature-map constructions and nine real embedding datasets for attention.Source: §1.1 · p. 4

2 Related Work

The paper situates its method among lattice rules, digital nets, random features, and fast structured feature maps. Its distinction is to accelerate use of a fixed structured lattice, rather than generator search or function reconstruction.

2 Related Work

  • CBC selects lattice generators by minimizing worst-case error, with classical bounds based on averaging over candidate pools that grow with n.The subgroup construction instead uses a fixed-size pool and requires a different convergence argument.Source: §2 · pp. 4–5
  • Halton, Sobol’, and other digital-net constructions do not relate coordinates in a way that accelerates applying an elementwise nonlinearity, leaving an O(nd) cost.Scrambled Sobol’ and Halton points are among the paper’s experimental baselines.Source: §2 · p. 5
  • Fast CBC uses FFTs to accelerate searching for a generic generator, whereas this method uses length-m FFTs on subgroup orbits to apply Ψ to the resulting point set.Other lattice FFT methods recover functions from samples along the point index rather than applying a nonlinearity to the point set.Source: §2 · p. 5
  • Fastfood and structured orthogonal random features reach O(n log d) through randomized matrix factorizations, while the subgroup lattice uses deterministic lattice algebra and retains worst-case error guarantees.The transform applies to arbitrary nonlinearities Ψ.Source: §2 · p. 5
  • The convergence and averaging analyses use resultants with Φm and the complete splitting of n in Q(ζm), tools the authors report as new to QMC convergence-rate proofs.The method addresses the elementwise-map cost, which the cited high-dimensional QMC techniques for dimension control do not target.Source: §2 · p. 6

3 Preliminaries

The preliminaries establish the paper’s error measure and lattice-rule framework, then specialize to rank-1 rules generated by a single vector. They define the power-form coordinates used in the later subgroup construction.

3.1 The Korobov space and worst-case error

  • The quadrature error is assessed by worst-case error over the unit ball of the Korobov space of smoothness α.The paper fixes dimension d and smoothness α > 1.Source: §3 · p. 6, §3.1 · p. 7

3.2 Integration lattices and generator matrices

  • An integration lattice contains Z^d and has index N = |det B|^-1; its lattice rule averages a function over N representatives in the unit cube.The cube points represent the cosets of Z^d in the lattice.Source: §3.2 · p. 8

3.3 Rank-1 lattice rules and the power-form generator

  • A rank-1 rule uses the n points x_l = {lz/n} for l = 0, …, n − 1, and its aliasing frequencies satisfy k · z ≡ 0 (mod n).The aliasing identity is the basis for the later convergence analysis.Source: §3.3 · p. 9
  • The power-form generator sets z(t) = (1, t, t^2, …, t^(d−1)) mod n, so its coordinates are consecutive powers of one scalar.This is the structured generating-vector construction used throughout the paper.Source: §3.3 · p. 9

4 Subgroup rank-1 lattice

The subgroup rank-1 lattice fixes the multiplicative order of the scalar in a power-form generator. Its induced cosets support the fast transform, while the restriction leaves a fixed-size generator pool whose convergence requires separate analysis.

4 Subgroup rank-1 lattice

  • Fixing t’s multiplicative order m independently of n defines the subgroup rank-1 lattice, whose structure is used for fast computation and convergence analysis.The construction requires m ≥ d + 1 for the stated convergence result.Source: §4 · p. 9, §4.1 · p. 10

4.1 Fixed-order power-form generators

  • For prime n with m | n − 1, the generator uses t of order exactly m; only φ(m) such generators are available as n grows.The construction imposes m ≥ d + 1, the exact threshold for the paper’s convergence result.Source: §4.1 · pp. 9–10

4.2 The coset decomposition of F× n induced by H

  • Multiplication by t partitions F_n^× into q = (n − 1)/m cosets of H = ⟨t⟩, each an m-cycle under that multiplication.This cyclic ordering supplies the structure used by the coset-FFT transform.Source: §4.2 · p. 11

4.3 Scope of the restriction

  • The admissible generator pool stays fixed at φ(m) as n grows, and the resulting proven convergence exponent is weaker than the one CBC certifies.The paper describes its polynomial rate as explicit but not provably tight.Source: §4.3 · pp. 11–12

5 A fast O(n log d) algorithm for the elementwise lattice transform

A fixed-order power-form generator lets coset structure turn both elementwise lattice transforms into short cyclic correlations, computed exactly without assumptions on Ψ. The same approach accelerates aggregation and expansion, with experiments confirming floating-point-level agreement and speedups over direct evaluation.

5.1 Setting

  • For any scalar Ψ, the two target maps are Ψ(X)⊤v and Ψ(X)w; the argument assumes no continuity, linearity, monotonicity, or Ψ(0) = 0.Direct evaluation costs O(nm) arithmetic operations and nm evaluations of Ψ.Source: §5.1 · p. 12

5.2 Main result: a coset-FFT decomposition

  • Both aggregation and expansion are exact in O(n log m) arithmetic operations plus n evaluations of Ψ, or O(n log d) arithmetic when m = Θ(d).Direct evaluation costs O(nm) arithmetic operations plus nm evaluations of Ψ.Source: §5.2 · p. 12, §5.1 · p. 12, §5.4 · pp. 15–16
  • Partitioning nonzero residues into order-m cosets turns each coset’s contribution into a length-m cyclic correlation evaluated by FFT.Aggregation sums across cosets and adds the r = 0 correction; expansion computes each coset’s outputs without cross-coset summation.Source: §5.2 · p. 13, §5.4 · p. 15

5.3 The advantage of the fast transform

  • The improvement over O(nd) direct evaluation relies on the fixed-order power-form generator and gives no general acceleration recipe for arbitrary generating vectors.The coset construction reduces the work to length-m FFT pairs.Source: §5.3 · pp. 13–14

5.4 The transpose direction: fast computation of Ψ(X)w

  • The transpose map expands m coefficients to n outputs, using one correlation per coset and a Ψ(0) correction at the zero row.Unlike aggregation, expansion needs no summation across cosets.Source: §5.4 · pp. 15–16

5.5 Numerical experiments

  • At n = 1,500,007, coset-FFT was ~13× faster for Y, and both fast transforms matched direct evaluation at floating-point level across tested Ψ.For u, speedups grew from ~9× / ~20× to ~17× / ~35× for id / nonlinear Ψ.Source: §5.5 · pp. 17–18, Table 2 · p. 17

6 Convergence rate for a fixed subgroup-order generator

Fixing the subgroup order leaves only a fixed pool of generators, outside the growing candidate pools used in classical convergence arguments. The paper uses cyclotomic polynomials and resultants to establish convergence and identify the exact dimension threshold.

6.1 Setting

  • With fixed subgroup order, the generator pool has only φ(m) members and does not grow with n, so classical CBC averaging over a growing pool is unavailable.The setting takes prime m, prime n ≡ 1 (mod m), and generators of exact order m.Source: §6 · p. 18, §6.1 · p. 18

6 Convergence rate for a fixed subgroup-order generator

  • The result addresses whether full n-point lattices still converge when the power-form generator’s order is fixed independently of n.The convergence analysis considers the Korobov-space worst-case error.Source: §6 · p. 18, §6.1 · p. 18, §6.3 · p. 20

6.2 Algebraic tools: cyclotomic polynomials and resultants

  • A lattice alias implies n divides the integer resultant of the frequency polynomial and Φm; the resultant is nonzero when d ≤ m−1.The proof identifies the alias condition with a polynomial root at an order-m element modulo n.Source: §6.2 · p. 19

6.3 Main convergence theorem

  • Theorem 17 addresses a convergence rate for fixed prime subgroup order when m is prime, 2 ≤ d ≤ m−1, and α > 1; Figure 1 compares empirical decay with the predicted upper-bound exponent at m = 5 and α = 2.Source: §6.3 · p. 20, Figure 1 · p. 21

6.4 Sharpness of the dimension restriction

  • The threshold is exact: convergence holds when m ≥ d+1, while m ≤ d gives an n-independent error floor and failure to converge.The stated floor is e2(Qn, z(t)) ≥ 2.Source: §6.4 · p. 21

7 A sharper constant via averaging over the candidate pool

Averaging over the fixed pool of order-m generators yields a sharper worst-case error constant. The argument links shared aliasing to higher resultant divisibility, then uses a log-weighted tail bound to establish the average.

7 A sharper constant via averaging over the candidate pool

  • The uniform convergence bound applies to every order-m generator, but averaging over the fixed candidate pool may yield a sharper constant for at least one.A naive bound on how many candidates share a bad frequency does not combine with the size-dependent threshold to give decay in n.Source: §7 · p. 22

7.1 Complete splitting and the resultant as a field norm

  • If a frequency aliases for Nh generators, then n^Nh divides its resultant, strengthening the single-factor divisibility bound.The proof identifies the generators with distinct prime ideals above n in the cyclotomic integer ring.Source: §7.1 · pp. 22–23

7.2 A sharper average, via a log-weighted tail bound

  • A log-weighted tail bound tracks aliasing multiplicity and converts the resultant divisibility control into an average-error bound.The multiplicity is controlled logarithmically, so the argument requires a tail bound that includes a logarithmic weight.Source: §7.2 · pp. 23–24

7.3 Existence of a sharper-constant generator

  • At least one of the m−1 order-m generators has a squared worst-case error at most the average, improving the uniform bound’s constant by a factor Θ(m−1).The selected generator may depend on n.Source: §7.3 · p. 24

8 Experiments

The experiments compare subgroup rank-1 lattices with four standard feature-map constructions on synthetic kernel estimation and real-data softmax attention, selecting and caching a generator from the admissible pool for each configuration. Across both tasks, the subgroup lattice is usually the most accurate, while its sample-set construction is especially fast at large dimensions.

8 Experiments

  • All five methods use the same elementwise nonlinearity, so the accuracy comparison attributes differences to the point set.The synthetic task estimates exp(x⊤y); the real-data task estimates self-normalized softmax attention.Source: §8 · pp. 24–25

8.3 Discussion

  • The experiments use the best generator selected on a held-out batch and cached, but that exhaustive search adds a one-time cost for each (d, m, n) configuration.The search evaluates all m −1 candidates and is dominated by FFT work.Source: §8 · p. 25, §8.3 · p. 33

8.1.1 Empirical Error Evaluation

  • The five synthetic exceptions were cases where a QMC baseline won; four occurred at small dimensions and the largest tested ratios, while d = 1024 was a 1.5% near-tie.The authors suggest the small candidate pool may limit adaptivity in the small-dimension cases.Source: Table 5 · p. 26, §8.1.1 · pp. 26–27
  • At the largest tested n for d ≥32, its advantage over the best baseline ranged from 2.0× to 5.5×, reaching 5.5× at d = 2048.At d = 2048 and n ≈4.1 × 10^7, mean relative error was 8.95 × 10^-8 versus 4.92 × 10^-7 for Halton.Source: §8.1.1 · pp. 26–27, Table 6 · p. 27, Figure 2 · p. 28

8.1.2 Sample set construction time comparison

  • For d ≥512, the subgroup lattice was fastest at every tested configuration; at d = 2048 and n ≈4.1×10^7, construction took 2.29 ms.The timings isolate construction of the sample set, not application to data.Source: §8.1.2 · pp. 28–29, Table 7 · p. 29, Figure 3 · p. 30

8.2 Real-data softmax-attention approximation

  • On real-data attention, the mean advantage across 45 configurations ranged from 1.13× to 3.37×, and Sobol was the closest baseline in 22 of 45.The subgroup lattice’s curve was the lowest-error and tightest-banded in all nine dataset panels.Source: §8.2 · pp. 31–32, Table 9 · p. 32, Figure 4 · p. 33

8.3 Discussion

  • The subgroup lattice was most accurate in 49 of 54 synthetic settings and all 45 real-data attention settings, with the narrowest repeat bands across datasets.The attention experiments report a mean advantage of 1.67× across configurations.Source: §8.1.1 · p. 26, Figure 2 · p. 28, §8.2 · p. 31

9 Conclusion

The paper trades generic freedom in rank-1 lattice generators for fixed-order algebraic structure, yielding faster feature-map transforms, direct convergence guarantees, and strong empirical accuracy. The conclusion also identifies generator selection cost and the assumption that n and m are prime as practical boundaries.

Computational contribution

  • Both feature-map transforms are computed exactly in O(n log m) arithmetic operations and O(n) memory for arbitrary scalar maps, without storing X.The coset-FFT transform matched direct evaluation to floating-point precision and built n ≈4.1 × 10^7 points at d = 2048 in 2.3 ms.Source: §9 · p. 34

Theoretical contribution

  • For prime m ≥ d + 1, every admissible generator has squared worst-case error O(n^−(α−1)/(m−1)); for m ≤ d, it is bounded below by 2.The paper derives these bounds directly because the fixed candidate pool does not support classical average-case arguments.Source: §9 · p. 34
  • Averaging over the admissible generators improves the average worst-case error by a factor Θ(m −1).The argument uses complete splitting of n in Q(ζ_m).Source: §9 · p. 34

Empirical contribution

  • The subgroup lattice was most accurate in 49 of 54 synthetic kernel-estimation settings and all 45 real-data softmax-attention settings, with a mean advantage of 1.67× on attention.The best of m −1 admissible generators was selected once on a held-out batch and cached.Source: §9 · p. 34

Limitations

  • Generator selection costs up to about five GPU hours for the largest configuration, and the theory assumes both n and m are prime.Selection is paid once per (d, m, n) and reused; the method was least competitive at small d with very large n.Source: §9 · p. 34

Related papers

This paper cites

Loading 2609.35177v1…