July 10, 2026
We show that every weighted hypergraph on \(n\) vertices admits a spectral \(\varepsilon\)-sparsifier with \(O(n\log n/\varepsilon^2)\) hyperedges, strengthening the independent STOC 2023 works of Lee and Jambulapati–Liu–Sidford by removing their rank dependence and answering Lee’s open question on whether this loss is inherent. The key idea is global-dictionary chaining: after choosing clique edge weights with balanced effective resistances, every hyperedge seminorm is Lipschitz with respect to the same global-dictionary norm generated by normalized vertex-pair directions; the local rank complexity is thereby replaced by the Gaussian width of this common dictionary. Since these STOC 2023 works have become standard analytic primitives across a broad subsequent literature on spectral hypergraph sparsification and its variants, our rank-independent theorem sharpens many later guarantees that inherit their sampling bounds.
Spectral sparsification is a central paradigm for compressing large weighted graphs while preserving the associated Laplacian quadratic form uniformly over all vertex potentials. For graphs, this paradigm admits sparsifiers with \(O(n/\varepsilon^2)\) edges [1], building on a long line of work [2], [3]. In hypergraphs, the corresponding object is a natural nonlinear Laplacian energy. For a weighted hypergraph \(H=(V,E,w)\) whose hyperedges have size at least two, the spectral energy is \[\label{eq:intro-energy} Q_H(x)=\sum_{e\in E} w_e\max_{\{u,v\}\subseteq e}(x_u-x_v)^2, \qquad x\in\mathbb{R}^V .\tag{1}\] When every hyperedge has size two, this is exactly the graph Laplacian energy. For general hypergraphs, the contribution of a hyperedge is the squared diameter of the vertex potential restricted to that hyperedge, so \(Q_H\) is a weighted sum of squared range seminorms.
A weighted subhypergraph \(\widetilde{H}=(V,\widetilde{E},\widetilde{w})\) with \(\widetilde{E}\subseteq E\) is a spectral \(\varepsilon\)-sparsifier of \(H\) if \[\label{eq:intro-sparsifier-def} \lvert Q_{\widetilde{H}}(x)-Q_H(x) \rvert\leq \varepsilon Q_H(x) \qquad \forall x\in\mathbb{R}^V .\tag{2}\] This guarantee is algorithmically meaningful because the hypergraph energy simultaneously captures several primitives. On indicator vectors it is exactly the hypergraph cut function, which has a separate near-linear-size sparsification theory [4], while on arbitrary vertex potentials it is the nonlinear Laplacian energy underlying spectral methods for hypergraphs. Thus a spectral sparsifier gives a sparse subhypergraph that preserves both cut values and nonlinear-Laplacian quantities, including eigenvalue-type parameters and Laplacian-based semi-supervised learning objectives [5]. These motivations have led to substantial recent activity, including spectral hypergraph sparsification in online, streaming, sliding-window, linear-sketching, fully dynamic, directed, and quantum models [6]–[13].
Soma and Yoshida [5] initiated spectral hypergraph sparsification and proved that every \(n\)-vertex hypergraph has a spectral \(\varepsilon\)-sparsifier with \(\widetilde{O}(n^3/\varepsilon^2)\) hyperedges. Bansal, Svensson, and Trevisan [14] improved the size to \(\widetilde{O}(nr^3/\varepsilon^2)\) hyperedges in terms of the rank \(r\). Kapralov, Krauthgamer, Tardos, and Yoshida reduced this further to \(\widetilde{O}(nr/\varepsilon^{O(1)})\) hyperedges [15], and then obtained rank-independent sparsifiers with \(n(\varepsilon^{-1}\log n)^{O(1)}\) hyperedges [16]. Thus, before the 2023 chaining works, the known nearly linear bounds either retained rank dependence or lost the optimal \(\varepsilon^{-2}\) dependence. The independent STOC 2023 works of Lee [17] and Jambulapati–Liu–Sidford [18] introduced chaining methods and showed that every \(n\)-vertex rank-\(r\) hypergraph has a spectral sparsifier with \(O(n\log n\log r/\varepsilon^2)\) hyperedges. Here \(r=\max_{e\in E}|e|\) is the rank of the hypergraph. Their analyses brought the size to nearly linear for all ranks, but left an additional logarithmic dependence on the rank. This left open a question highlighted by Lee [17]:
Can the logarithmic dependence on the rank be removed?
In this work, we study this question and answer it affirmatively.
Theorem 1 (Main theorem). For every \(n\)-vertex weighted hypergraph \(H=(V,E,w)\) and every \(\varepsilon\in(0,1)\), there exists a spectral \(\varepsilon\)-sparsifier \(\widetilde{H}=(V,\widetilde{E},\widetilde{w})\) of \(H\) with \(|\widetilde{E}|=O(n\log n/\varepsilon^2)\).
The theorem follows the STOC 2023 sampling framework [17], [18]. An underlying graph supplies hyperedge leverage overestimates, and hyperedges are sampled according to these overestimates. Our main contribution is a rank-independent estimate for the Rademacher process controlling the sampled hyperedge energies, eliminating the local \(\log r\) loss in the previous chaining analyses. Since \(Q_H(\mathbf{1}_S)\) is exactly the weight of the hyperedges cut by \(S\), spectral sparsification subsumes hypergraph cut sparsification; thus Theorem 1 recovers the \(O(n\log n/\varepsilon^2)\) size bound of Chen–Khanna–Nagda [4], whose cut-only proof constructs a balanced assignment on an auxiliary clique graph so that hyperedge sampling can be analyzed through Benczúr–Karger graph-strength sampling. Within this sampling framework, the remaining \(\log n\) factor is the global uniform-convergence cost. Whether one can obtain \(O(n/\varepsilon^2)\)-size spectral hypergraph sparsifiers, matching the graph theorem of Batson–Spielman–Srivastava [1], remains an interesting and challenging open question.
The extra \(\log r\) in the STOC 2023 bounds comes from analyzing each hyperedge through its own local pair dictionary. After passing to the resistance-normalized coordinates of an underlying graph, the normalized contribution of a hyperedge \(e\) can be viewed, up to the normalizations made precise below, as \[N_e(y)=\max_{p\subseteq e}\beta_{e,p}\lvert \left\langle u_p,y \right\rangle \rvert, \qquad 0\leq\beta_{e,p}\leq1,\] where \(u_p\) is the resistance-normalized direction of the pair \(p\) in the underlying graph, and \(\beta_{e,p}\) collects the remaining resistance and leverage factors. A hyperedge-by-hyperedge chaining argument sees the dictionary \(\{u_p:p\subseteq e\}\), whose Gaussian width is of order \(\sqrt{\log |e|}\) in the worst case. Through the symmetrized sampling and self-bounding step, this local width becomes the additional \(\log r\) factor.
The point of the present proof is that the pair directions need not be treated locally. The same underlying graph defines a single normalized direction \(u_p\) for every pair \(p\in\binom V2\), and hence a common dictionary \(\mathcal{R}=\{u_p:p\in\binom V2\}\). The metric \[\rho(h)=\max_{u\in\mathcal{R}}\lvert \left\langle u,h \right\rangle \rvert,\] measures the largest change in any normalized pair coordinate, and every normalized hyperedge seminorm \(N_e\) is \(1\)-Lipschitz with respect to it. Consequently the symmetrized sampling process can be chained once in the metric \(\rho\), whose complexity is controlled by the Gaussian width of the common dictionary: \[\gamma_2(B_2^{n-1},\rho) \lesssim \mathbb{E}_g\max_{u\in\mathcal{R}}\lvert \left\langle u,g \right\rangle \rvert \lesssim \sqrt{\log n}.\] Here the first inequality is the Gaussian ellipsoid estimate used later, and the second follows from a union bound over \(|\mathcal{R}|\leq\binom n2\) unit directions. Thus we keep the underlying-graph leverage-overestimate framework of Lee [17] and Jambulapati–Liu–Sidford [18], but replace the local chaining step by a global-dictionary chaining bound that is independent of the rank.
The proof is a hypergraph analogue of effective-resistance sampling for graphs. In a graph, an edge is sampled according to its leverage score, namely its weight times its effective resistance, and the sum of these scores is linear in the number of vertices. A hyperedge has no single canonical resistance: its energy is the largest squared difference among all vertex pairs it contains. We therefore first choose an underlying graph by distributing the weight \(w_e\) of each hyperedge over the clique on \(e\). Thus, for each unordered pair \(p=\{a,b\}\subseteq e\), we choose a nonnegative clique weight \(c_{e,p}\); here \(b_p=\mathbf{1}_a-\mathbf{1}_b\) is the signed incidence vector of the pair. The resulting graph Laplacian is \[L=\sum_{e\in E}\sum_{p\subseteq e}c_{e,p}b_pb_p^\top .\] The balancing results of Lee [17] and Jambulapati–Liu–Sidford [18] give numbers \(\tau_e\) such that \[w_e\max_{p\subseteq e}(b_p^\top x)^2\leq \tau_e\,x^\top Lx \qquad\text{for every vertex potential }x,\] and \(\Lambda:=\sum_e\tau_e\lesssim n\). Thus \(\tau_e\) is a leverage overestimate, equivalently a sensitivity upper bound, for hyperedge \(e\) relative to the reference graph \(L\); the linear bound on \(\Lambda\) is the source of the near-linear sampling budget.
The next step is to express the hypergraph energy in the geometry of this reference graph. Write \(x=L^{+/2}y\), where \(L^{+/2}\) is the positive square root of the pseudoinverse \(L^+\) and \(y\) lies in the subspace \(\mathbf{1}^\perp\) orthogonal to the all-ones vector. The underlying graph is a minorant of the hypergraph, meaning that \(x^\top Lx\leq Q_H(x)\) for every \(x\). Since \(x^\top Lx=\left\lVert y \right\rVert_2^2\) in these coordinates, this minorization becomes the lower bound \(F(y)\geq\left\lVert y \right\rVert_2^2\). Moreover, the same coordinates decompose the hypergraph energy as \[F(y):=Q_H(L^{+/2}y)=\sum_{e\in E}\tau_eN_e(y)^2,\] where each \(N_e\) is a normalized version of the maximum pair difference inside \(e\). Sampling \(M\) independent hyperedges \(e_1,\ldots,e_M\) with probabilities \(p_e=\tau_e/\Lambda\) gives the unbiased estimator \(\widehat F(y)=\Lambda M^{-1}\sum_{i=1}^M N_{e_i}(y)^2\) for \(F(y)\). By degree-two homogeneity, it suffices to prove an additive approximation on the unit energy body \(K=\{y\in\mathbf{1}^\perp:F(y)\leq1\}\); this rescales to a relative approximation everywhere.
After this reduction, the remaining task is a uniform concentration bound for the sampled functions \(N_e^2\) on \(K\). Symmetrization reduces it to bounding the Rademacher process \(X_y=\sum_i\sigma_iN_{e_i}(y)^2\), where the \(\sigma_i\) are independent random signs. The normalization above is designed so that every \(N_e\) is \(1\)-Lipschitz with respect to the same global-dictionary metric \[\rho(h)=\max_{p\in\binom V2}\lvert \left\langle u_p,h \right\rangle \rvert,\] where \(u_p=L^{+/2}b_p/\sqrt{b_p^\top L^+b_p}\) is the resistance-normalized direction of the pair \(p\). The rank-independent chaining estimate then gives the required Rademacher bound. Namely, for a fixed sample, if \(S^2=\sup_{y\in K}\sum_iN_{e_i}(y)^2\), the common Lipschitz bound controls the increments by \(2S\rho\), while the complexity of \(\rho\) on \(K\) is \(O(\sqrt{\log n})\); hence \[\mathbb{E}_\sigma\sup_{y\in K}\lvert X_y \rvert\lesssim S\sqrt{\log n}.\] This is the sole place where the chaining estimate is used in the sampling argument.
It remains to control the random radius \(S\). Let \(\Delta=\sup_{y\in K}\lvert \widehat F(y)-F(y) \rvert\). Since \(F(y)\leq1\) on \(K\) and \(\widehat F\) is the sampled energy, \(S^2\leq (M/\Lambda)(1+\Delta)\). Combining this self-bounding relation with symmetrization and the Rademacher bound yields \[\mathbb{E}\Delta \lesssim \sqrt{\frac{\Lambda\log n}{M}}\sqrt{1+\mathbb{E}\Delta}.\] Using \(\Lambda\lesssim n\), the choice \(M\gtrsim n\log n/\varepsilon^2\) makes \(\mathbb{E}\Delta\leq\varepsilon\), and hence some sampled reweighted subhypergraph gives the desired spectral \(\varepsilon\)-sparsifier.
The STOC 2023 sparsification theorems of Lee and Jambulapati–Liu–Sidford [17], [18] now serve as a sampling primitive across several subsequent settings, including directed sparsification, online and streaming algorithms, sketching and dynamic data structures, and quantum algorithms. These works supply the reductions, data structures, recovery procedures, and access mechanisms needed in their respective models. In those applications, our rank-independent estimate removes the local-chaining \(\log r\) factor from the sampling analysis. [tab:consequence-summary] records the resulting quantitative changes; in some applications the affected quantity is an intermediate sampling or recovery parameter rather than the final sparsifier size. Details are given below.
| Quantity | Previous bound | Consequence of our result |
|---|---|---|
| sparsifier size [10] | \(O(\varepsilon^{-2}n^2\log^3(n/\varepsilon))\) | \(O(\varepsilon^{-2}n^2\log n)\) |
| sparsifier via lift [11] | \(O(\varepsilon^{-2}n^2\log^2 n)\) | \(O(\varepsilon^{-2}n^2\log n)\) |
| sampling term [6] | \(O(\varepsilon^{-2}n\log n\log r)\) | \(O(\varepsilon^{-2}n\log n)\) |
| algorithm output size [13] | \(O(\varepsilon^{-2}n\log n\log r)\) | \(O(\varepsilon^{-2}n\log n)\) |
| sample size [7] | \(O(\varepsilon^{-2}n\log n\log m\log r)\) | \(O(\varepsilon^{-2}n\log n\log m)\) |
| streaming space [7] | \(O(\varepsilon^{-2}nr\log^2 n\log r\,\mathrm{poly}(\log\log m))\) | \(O(\varepsilon^{-2}nr\log^2 n\,\mathrm{poly}(\log\log m))\) |
| recovery framework [8] | \(O(\varepsilon^{-2}\log n\log^3 m)\) | \(O(\varepsilon^{-2}\log n\log^2 m)\) |
| sparsifier size [12] | \(O(\varepsilon^{-2}n^2\log^7 m)\) | \(O(\varepsilon^{-2}n^2\log^5 m)\) |
Directed spectral hypergraphs give the cleanest transfer of the rank-independent sampling bound. Oko–Sakaue–Tanigawa [10] gave \(O(\varepsilon^{-2}n^2\log^3(n/\varepsilon))\)-size spectral sparsifiers for directed hypergraphs. Khanna–Putterman–Sudan [11] subsequently introduced an ordered-pair lift from an \(n\)-vertex directed instance to an undirected hypergraph on \(n^2+1\) vertices, where a directed hyperedge of size at most \(r\) becomes an undirected hyperedge of size at most \(r^2\). Using the undirected Lee [17] and Jambulapati–Liu–Sidford [18] sparsifier on the lifted instance gives \(O(\varepsilon^{-2}n^2\log n\log r)\) directed hyperedges, and hence \(O(\varepsilon^{-2}n^2\log^2 n)\) in the worst case. Replacing this undirected input by Theorem 1 removes the inherited \(\log r\) factor and gives \(O(\varepsilon^{-2}n^2\log n)\) directed hyperedges. The remaining \(n^2\) factor is the cost of the ordered-pair lift.
Soma–Tung–Yoshida [6] study online \((\varepsilon,\delta)\)-spectral sparsification, where \(\delta\) is the additive error parameter. Their Algorithm 1 maintains a reweighted graph chosen by a log-determinant potential, following the reweighting framework of Lee [17], and samples an arriving hyperedge with probability proportional to a ridged effective-resistance overestimate, using sampling coefficient \(c=O(\varepsilon^{-2}\log n\log r)\). This yields the high-probability size bound \(O(\varepsilon^{-2}n\log n\log r\cdot\log(1+\varepsilon W/(\delta n)))\), where \(W=\sum_{e\in E}w_e\) in their notation. The \(\log r\) term comes from the chaining estimate of Lee [17] used in the sampling analysis. Replacing that step by the global-dictionary estimate removes the \(\log r\) factor from the sampling coefficient, while the additive-error factor \(\log(1+\varepsilon W/(\delta n))\) and the online-model overheads remain unchanged.
Liu–Gao–Ji–Ying [13] develop a quantum algorithm for spectral hypergraph sparsification. Their algorithm constructs query access to an \(O(n)\)-total hyperedge leverage-score overestimate and samples from the induced distribution using quantum primitives. Their sparsification theorem [13] gives \(O(\varepsilon^{-2}n\log n\log r)\) hyperedges; the \(\log r\) factor in this bound comes from the chaining estimate of Lee [17] used in the correctness proof. Replacing that estimate by Theorem 1 changes the sample count in the analysis to \(O(\varepsilon^{-2}n\log n)\).
Cohen-Addad et al. [7] obtain insertion-only spectral streaming algorithms by combining online sampling with merge-and-reduce, and the sampling bounds of Lee and Jambulapati–Liu–Sidford enter at two points. In their online sampling theorem [7], the analysis invokes the Jambulapati–Liu–Sidford theorem [18] with sampling coefficient \(O(\varepsilon^{-2}\log m\log r)\); replacing only the chaining estimate, while keeping the same \(1/\operatorname{poly}(m)\) failure probability, changes the online sample-size bound of Cohen-Addad et al. [7] from \(O(\varepsilon^{-2}n\log n\log m\log r)\) to \(O(\varepsilon^{-2}n\log n\log m)\), and the same deletion of the explicit \(\log r\) factor propagates through their sliding-window framework. The merge step uses their offline subroutine [7], with size \(O(\varepsilon^{-2}n\log n\log r)\) from Lee [17] and Jambulapati–Liu–Sidford [18]. Our bound gives \(O(\varepsilon^{-2}n\log n)\). Consequently, in the low-space branch of Cohen-Addad et al. [7], the stored-hyperedge bound loses the displayed \(\log r\) factor and becomes \(O(\varepsilon^{-2}n\log n)\cdot\mathrm{poly}(\log\log m)\); the same offline replacement removes the outer merge \(\log r\) in the polynomial-update and robust variants.
For Khanna–Li–Putterman [8], the improvement occurs inside the recovery threshold used by their linear-sketching, online, and fully dynamic implementations. At one recovery level with error parameter \(\eta\), their analysis invokes the Jambulapati–Liu–Sidford sampling theorem [18] with coefficient proportional to \(\eta^{-2}\log n\log m\) times the maximum pair effective resistance inside the hyperedge, measured in the corresponding witnessing weighted clique graph [8]. Replacing that step by our rank-independent estimate changes the one-level coefficient to \(O(\eta^{-2}\log n)\). Since their sparsifier composes \(O(\log m)\) half-sampling levels and sets \(\eta=\Theta(\varepsilon/\log m)\), this contribution changes from \(O(\varepsilon^{-2}\log n\log^3 m)\) to \(O(\varepsilon^{-2}\log n\log^2 m)\).
The fully dynamic directed application requires replacing a one-step sampling routine, not only the final sparsifier bound. Forster–Goranci–Momeni [12] use the Oko–Sakaue–Tanigawa coreset-and-sampling step: for every ordered pair \((u,v)\), keep the \(\lambda\) heaviest still-unselected hyperedges with \(u\) in the tail and \(v\) in the head, and sample the residual hyperedges with probability \(1/2\). These ordered-pair sets are also the dynamic invariant: after deleting a kept edge chosen for \((u,v)\), the data structure replaces it by the next eligible edge from the same set. Thus the Khanna–Putterman–Sudan lift [11] gives a final directed sparsifier bound, but not the ordered-pair subroutine needed here. Proposition 6 supplies this rank-independent one-step guarantee. In the Forster–Goranci–Momeni recurrence, it reduces the one-step parameter from \(O(\eta^{-2}\log^3 m)\) to \(O(\eta^{-2}\log m)\) under the same \(m^{-O(1)}\) failure probability, improving the fully dynamic size bound from \(O(\varepsilon^{-2}n^2\log^7 m)\) to \(O(\varepsilon^{-2}n^2\log^5 m)\) for \(m\geq n\); see Subsection 3.3.
We close by noting several related settings where the present argument does not directly apply. The fully dynamic undirected algorithm of Goranci–Momeni [9] maintains bundles of hyperspanners, so its rank dependence comes from a dynamic spanner construction rather than the sampling bounds of Lee and Jambulapati–Liu–Sidford. The cut-streaming and cut-sketching results [19]–[21] preserve cut values and are driven by strength-based sampling, contractions, adaptive robustness, or linear-sketch recovery. Submodular cut sparsifiers [11], spectral CSP sparsification [22], and sparsification of sums of norms [23] concern richer objective classes in which the common vertex-pair dictionary used here is no longer available in this form. Whether analogous rank-independent improvements are possible in these settings remains an interesting direction.
We identify \(\mathbb{R}^V\) with vectors indexed by a finite vertex set \(V\) and write \(\mathbf{1}\) for the all-ones vector and \(\mathbf{1}^\perp=\{x\in\mathbb{R}^V:\left\langle x,\mathbf{1} \right\rangle=0\}\). For an unordered pair \(p=\{a,b\}\), fix an arbitrary orientation and set \(b_p=\mathbf{1}_a-\mathbf{1}_b\); every quantity below is invariant under reversing this orientation. For \(S\subseteq V\), we write \(\binom S2\) for the set of unordered pairs contained in \(S\).
A weighted hypergraph is denoted by \(H=(V,E,w)\), where \(w_e>0\) and \(|e|\geq2\) for every \(e\in E\). The rank is \(r=\max_{e\in E}|e|\). A hypergraph is connected if the graph obtained by replacing every hyperedge by a clique is connected. If \(L\) is the Laplacian of a connected weighted graph on \(V\), then \(L^+\) denotes its Moore–Penrose pseudoinverse and \(L^{+/2}\) its positive semidefinite square root. On \(\mathbf{1}^\perp\) we have \(L^{+/2}LL^{+/2}=I\).
All implicit constants are universal. We write \(A\lesssim B\) to mean \(A\leq CB\) for a universal constant \(C\), and \(A\gtrsim B\) to mean \(B\lesssim A\). All logarithms are natural.
We use Talagrand’s \(\gamma_2\) functional for a metric or semimetric space \((T,d)\). An admissible sequence is a sequence of partitions \((\mathcal{A}_k)_{k\geq0}\) of \(T\) with \(|\mathcal{A}_0|=1\) and \(|\mathcal{A}_k|\leq 2^{2^k}\) for \(k\geq1\), and \[\gamma_2(T,d) = \inf_{(\mathcal{A}_k)} \sup_{t\in T}\sum_{k\geq0}2^{k/2} \operatorname{diam}_d(\mathcal{A}_k(t)),\] where \(\mathcal{A}_k(t)\) denotes the atom containing \(t\); see Talagrand [24]. We use the following subgaussian-process upper bound, stated in the absolute-value form needed in the proof. It follows from the one-sided estimate by applying it to both \((X_t)_{t\in T}\) and \((-X_t)_{t\in T}\); see [24].
Theorem 2 (Subgaussian chaining). Let \((T,d)\) be a separable semimetric space, and let \((X_t)_{t\in T}\) be a separable stochastic process with \(X_{t_0}=0\) for some \(t_0\in T\). Suppose that for all \(s,t\in T\) and all \(\lambda\in\mathbb{R}\), \[\mathbb{E}\exp\{\lambda(X_t-X_s)\} \leq \exp\!\left(\frac{\lambda^2d(s,t)^2}{2}\right).\] If the supremum is measurable, then \[\mathbb{E}\sup_{t\in T}|X_t|\lesssim \gamma_2(T,d).\]
The second chaining input is the Gaussian ellipsoid bound: the \(\gamma_2\) complexity of a Euclidean ball measured in an arbitrary seminorm is controlled by the Gaussian average of that seminorm. This is the standard ellipsoid form of Talagrand’s comparison between majorizing measures and Gaussian averages; see Ledoux–Talagrand [25] and Talagrand [24].
Theorem 3 (Gaussian ellipsoid bound). Let \(\alpha\) be a seminorm on \(\mathbb{R}^d\), and let \(d_\alpha(x,y)=\alpha(x-y)\). If \(g\) is a standard Gaussian vector in \(\mathbb{R}^d\), then \[\gamma_2(B_2^d,d_\alpha)\lesssim \mathbb{E}\alpha(g).\]
We use the Rademacher symmetrization inequality; see Ledoux–Talagrand [25]. All applications below are to continuous function classes on compact finite-dimensional parameter spaces, so the measurability and integrability assumptions are automatic.
Lemma 1 (Rademacher symmetrization). Let \(\xi_1,\ldots,\xi_M\) be independent samples from a distribution \(\mu\), and let \(\{f_t:t\in T\}\) be a separable class of real-valued measurable functions. Assume that the suprema below are measurable and integrable. If \(\sigma_1,\ldots,\sigma_M\) are independent Rademacher signs, then \[\mathbb{E}\sup_{t\in T} \lvert \sum_{i=1}^M\left( f_t(\xi_i)-\mathbb{E}_\mu f_t \right) \rvert \leq 2\mathbb{E}\mathbb{E}_\sigma\sup_{t\in T} \lvert \sum_{i=1}^M\sigma_i f_t(\xi_i) \rvert .\]
Proof. Let \(\xi_1',\ldots,\xi_M'\) be an independent ghost sample. Jensen’s inequality gives \[\mathbb{E}\sup_t \lvert \sum_i\left( f_t(\xi_i)-\mathbb{E}_\mu f_t \right) \rvert \leq \mathbb{E}\mathbb{E}'\sup_t \lvert \sum_i\left( f_t(\xi_i)-f_t(\xi_i') \right) \rvert .\] The joint distribution of \(\left( f_t(\xi_i)-f_t(\xi_i') \right)_{i=1}^M\) is invariant under multiplying each difference by an independent sign \(\sigma_i\). Therefore the last display is at most \[\begin{align} \mathbb{E}\mathbb{E}'\mathbb{E}_\sigma\sup_t \lvert \sum_i\sigma_i\left( f_t(\xi_i)-f_t(\xi_i') \right) \rvert &\leq \mathbb{E}\mathbb{E}_\sigma\sup_t\lvert \sum_i\sigma_i f_t(\xi_i) \rvert +\mathbb{E}'\mathbb{E}_\sigma\sup_t\lvert \sum_i\sigma_i f_t(\xi_i') \rvert \\ &=2\mathbb{E}\mathbb{E}_\sigma\sup_t\lvert \sum_i\sigma_i f_t(\xi_i) \rvert . \end{align}\] ◻
This section proves Theorem 1. The guiding idea is to choose, before sampling, an underlying graph that puts all vertex pairs on a common effective-resistance scale. In these coordinates, each normalized hyperedge seminorm is a maximum over unit pair directions, so all hyperedges are Lipschitz with respect to the same global-dictionary metric. The sampling error is therefore controlled by one symmetrized process and chained once over this dictionary, instead of being analyzed separately inside each hyperedge. The section ends with the analogous one-step estimate for directed ordered-pair coresets, where the coreset lower bound supplies the reference geometry.
Since \(Q_H\) decomposes over connected components of the clique graph, we may assume \(H\) is connected; for component sizes \(n_i\), the resulting sparsifier sizes sum to \(\sum_i O(n_i\log n_i/\varepsilon^2)\leq O(n\log n/\varepsilon^2)\).
The first step is to attach a scalar sampling weight to each hyperedge. In an ordinary weighted graph, the effective-resistance sampling weight of an edge is its weight times its effective resistance. For a hyperedge there is no canonical pair: its energy is the maximum squared difference over all pairs it contains. Thus the effective-resistance viewpoint becomes meaningful only after choosing an underlying graph, obtained by distributing each hyperedge weight \(w_e\) over the clique on \(e\).
Concretely, for each \(p\in\binom e2\) choose weights \(c_{e,p}\geq0\) with \(\sum_{p\subseteq e}c_{e,p}=w_e\), and let \(L=\sum_{e,p\subseteq e}c_{e,p}b_pb_p^\top\). This graph serves as a reference quadratic form: always \(x^\top Lx\leq Q_H(x)\). If \(L\) is connected, it also defines effective resistances \(R_p=b_p^\top L^+b_p\) and hyperedge leverage \(w_eR_e\), where \(R_e=\max_{p\subseteq e}R_p\). The structural task is to choose the clique weights so that these quantities have overestimates \(\tau_e\geq w_eR_e\) with total mass \(\lesssim n\); this is the hypergraph analogue of effective-resistance sampling in graphs.
Lee [17] realizes this program by maximizing the spanning-tree potential, equivalently the log determinant of \(L\) restricted to \(\mathbf{1}^\perp\), over all clique decompositions of the hyperedge weights. The KKT conditions balance the active pair resistances within each hyperedge, and Foster’s theorem gives \(\sum_e w_e\max_{p\subseteq e} b_p^\top L^+b_p\leq n-1\). Jambulapati–Liu–Sidford [18] isolate the weaker condition needed for sampling: it is enough to have a one-sided domination bound for every pair in a hyperedge, together with a linear bound on the total overestimate. Applying their graphical-hypergraph group-leverage overestimate theorem to the groups \(\{\sqrt{w_e}\,b_p:p\in\binom e2\}\) yields the following form.
Lemma 2 (Underlying graph with bounded hyperedge leverage). Let \(H=(V,E,w)\) be connected, and assume that \(|e|\geq2\) for every \(e\in E\). For every unordered pair \(p=\{a,b\}\), let \(b_p=\mathbf{1}_a-\mathbf{1}_b\) under an arbitrary orientation of \(p\); all expressions below are invariant under reversing this orientation. There are clique weights \(c_{e,p}\geq0\), indexed by \(e\in E\) and \(p\in\binom e2\), and numbers \(\tau_e>0\) such that, for every \(e\in E\), \[\sum_{p\subseteq e}c_{e,p}=w_e .\] Let \[L=\sum_{e\in E}\sum_{p\subseteq e}c_{e,p}b_pb_p^\top .\] Then \(L\) is the Laplacian of a connected graph, and the following hold.
Hyperedge leverage domination. For every hyperedge \(e\) and every \(x\in\mathbb{R}^V\), \[\label{eq:one-sided-hyperedge-leverage} w_e\max_{p\subseteq e}(b_p^\top x)^2\leq \tau_e\,x^\top Lx ;\tag{3}\]
Linear total mass. \[\label{eq:tau-total} \Lambda:=\sum_{e\in E}\tau_e\lesssim n ;\tag{4}\]
Quadratic minorization. \[\label{eq:L-minorizes-QH} x^\top Lx\leq Q_H(x)\qquad\forall x\in\mathbb{R}^V .\tag{5}\]
Consequently, if \(R_p=b_p^\top L^+b_p\) and \(R_e=\max_{p\subseteq e}R_p\), then \[\label{eq:hyperedge-resistance-overestimate} w_eR_e\leq \tau_e \qquad\forall e\in E .\tag{6}\]
Proof. Apply the graphical-hypergraph group-leverage overestimate theorem of Jambulapati–Liu–Sidford [18] to the matrix hypergraph whose group corresponding to \(e\) consists of the row vectors \(\{(\sqrt{w_e}\,b_p)^\top:p\in\binom e2\}\). It gives group weights \(\alpha_{e,p}\geq0\) with \(\sum_{p\subseteq e}\alpha_{e,p}=1\) and \(O(n)\)-bounded group-leverage overestimates \(\tau_e\) in the sense of [18]. Set \(c_{e,p}=w_e\alpha_{e,p}\). The one-sided domination property of these overestimates [18] implies 3 for \(L=\sum_{e,p}c_{e,p}b_pb_p^\top\), and the total-mass bound in the definition gives 4 .
The domination inequality also forces \(L\) to be connected. Otherwise there is a nonconstant vector \(x\) that is constant on every connected component of the graph supporting \(L\), and hence \(x^\top Lx=0\). Since the clique graph of \(H\) is connected, some hyperedge contains a pair whose endpoints have different \(x\)-values, contradicting 3 .
The minorization 5 follows from the weight normalization: for all \(x\), \[x^\top Lx =\sum_{e\in E}\sum_{p\subseteq e}c_{e,p}(b_p^\top x)^2 \leq\sum_{e\in E} w_e\max_{p\subseteq e}(b_p^\top x)^2 =Q_H(x).\] Finally, since \(L\) is connected, the variational characterization of effective resistance gives \[R_p=\sup_{x\notin\ker L}\frac{(b_p^\top x)^2}{x^\top Lx} .\] Applying 3 to each \(p\subseteq e\) yields \(w_eR_p\leq\tau_e\), and taking the maximum over \(p\subseteq e\) gives 6 . ◻
These properties are used in complementary ways. Leverage domination makes each normalized hyperedge contribution a contraction of a common pair-dictionary norm. The total mass bound is the sampling budget, while the minorization puts the hypergraph unit-energy body inside the Euclidean ball after the change of coordinates below. Connectedness makes the effective resistances and normalized coordinates well-defined on \(\mathbf{1}^\perp\).
Fix the objects given by Lemma 2. We identify \(\mathbf{1}^\perp\) with a Euclidean space of dimension \(d=n-1\).
The change of variables \(x=L^{+/2}y\), with \(y\in\mathbf{1}^\perp\), is the point at which the underlying graph becomes the reference geometry. In these coordinates, \(y^\top L^{+/2}LL^{+/2}y=\left\lVert y \right\rVert_2^2\), so the graph minorant is the Euclidean quadratic form. At the same time, every pair difference is measured in units of its effective resistance, so pair directions are compared on the natural scale of the graph metric rather than on their raw coordinate scale. For every vertex pair \(p\in\binom V2\), define \[R_p=b_p^\top L^+b_p, \qquad u_p=\frac{L^{+/2}b_p}{\sqrt{R_p}}\in\mathbf{1}^\perp .\] Connectedness of \(L\) gives \(R_p>0\) and \(\left\lVert u_p \right\rVert_2=1\). Let \[\mathcal{R}=\left\{u_p:p\in\binom V2\right\}, \qquad |\mathcal{R}|\leq\binom n2 .\] For each hyperedge \(e\), set \(R_e=\max_{p\subseteq e}R_p>0\). Define \[\label{eq:Ne-definition} N_e(y)= \sqrt{\frac{w_eR_e}{\tau_e}} \max_{p\subseteq e}\sqrt{\frac{R_p}{R_e}}\,\left\lvert \left\langle u_p,y \right\rangle \right\rvert, \qquad y\in\mathbf{1}^\perp .\tag{7}\] Both normalization factors in 7 are at most one by the definition of \(R_e\) and by 6 . The normalization is useful precisely because, after rescaling, each local hyperedge maximum is built from unit pair directions and has no larger Lipschitz constant than the ambient pair dictionary.
Lemma 3 (Normalized energy representation). In the connected setting of this subsection, let \(L\) and \(\tau_e\) be as in Lemma 2, let \(N_e\) be the seminorm in 7 , and set \(F(y)=Q_H(L^{+/2}y)\) for \(y\in\mathbf{1}^\perp\). Then \[F(y)=\sum_{e\in E}\tau_eN_e(y)^2 \qquad\text{and}\qquad F(y)\geq\left\lVert y \right\rVert_2^2 .\]
Proof. For each pair \(p\), we have \(b_p^\top L^{+/2}y=\sqrt{R_p}\,\left\langle u_p,y \right\rangle\). Therefore \[\begin{align} Q_H(L^{+/2}y) &=\sum_{e\in E}w_e\max_{p\subseteq e}R_p\left\langle u_p,y \right\rangle^2 \\ &=\sum_{e\in E}\tau_e \frac{w_eR_e}{\tau_e} \max_{p\subseteq e}\frac{R_p}{R_e}\left\langle u_p,y \right\rangle^2 \\ &=\sum_{e\in E}\tau_eN_e(y)^2 . \end{align}\] For the lower bound, apply 5 to \(x=L^{+/2}y\). Since \(y\in\mathbf{1}^\perp\), \[F(y)=Q_H(L^{+/2}y) \geq y^\top L^{+/2}LL^{+/2}y =\left\lVert y \right\rVert_2^2 .\] ◻
Let \[\label{eq:K-definition} K=\{y\in\mathbf{1}^\perp:F(y)\leq1\}.\tag{8}\] By Lemma 3, \(K\subseteq B_2^d\). Since \(F\) is continuous, \(K\) is closed; hence \(K\) is compact. All suprema over \(K\) below are therefore measurable maxima.
The metric used for chaining should measure how much any normalized pair coordinate can change. A local analysis would use, for every hyperedge \(e\), the dictionary \(\{u_p:p\subseteq e\}\) and would therefore see the rank of \(e\). We instead use the complete pair dictionary once and for all: \[\label{eq:global-rho} \rho(h)=\max_{u\in\mathcal{R}}\lvert \left\langle u,h \right\rangle \rvert, \qquad h\in\mathbf{1}^\perp .\tag{9}\] This is the global-dictionary metric. It is global because the same metric controls all hyperedges simultaneously, and it is a norm on \(\mathbf{1}^\perp\). If \(\rho(h)=0\), then \(b_p^\top L^{+/2}h=0\) for every pair \(p\), so \(L^{+/2}h\) is constant on \(V\). Since \(L^{+/2}h\in\mathbf{1}^\perp\), this constant vector is zero, and invertibility of \(L^{+/2}\) on \(\mathbf{1}^\perp\) gives \(h=0\).
Every hyperedge seminorm is \(1\)-Lipschitz in this same norm: \[\label{eq:Ne-lipschitz} \lvert N_e(y)-N_e(z) \rvert\leq \rho(y-z) \qquad \forall y,z\in\mathbf{1}^\perp .\tag{10}\] Indeed, the reverse triangle inequality for a weighted maximum norm and the two normalizations in 7 give \[\begin{align} \lvert N_e(y)-N_e(z) \rvert &\leq \sqrt{\frac{w_eR_e}{\tau_e}} \max_{p\subseteq e}\sqrt{\frac{R_p}{R_e}}\, \lvert \left\langle u_p,y-z \right\rangle \rvert \\ &\leq \rho(y-z). \end{align}\] This is the structural step that removes the rank dependence: the same metric \(\rho\) controls all hyperedges, and the dictionary defining \(\rho\) has size at most \(\binom n2\), independent of the size of any individual hyperedge.
The next lemma is the only quantitative estimate needed for this global-dictionary metric. It is stated for a general finite dictionary because the directed coreset argument uses the same form. In that generality \(\rho_{\mathcal{U}}\) may be only a seminorm, meaning that it can vanish in directions not spanned by \(\mathcal{U}\); this is harmless because the induced semimetric is all that enters the \(\gamma_2\) functional.
Lemma 4 (Global-dictionary chaining). Let \(\mathcal{U}\subseteq S^{d-1}\) be nonempty and finite, and define \[\rho_{\mathcal{U}}(h)=\max_{u\in\mathcal{U}}\lvert \left\langle u,h \right\rangle \rvert, \qquad h\in\mathbb{R}^d .\] Then \[\gamma_2(B_2^d,\rho_{\mathcal{U}}) \lesssim \sqrt{\log(2|\mathcal{U}|)} .\]
Proof. Let \(T:\mathbb{R}^d\to\mathbb{R}^{\mathcal{U}}\) be the linear map \(Th=(\left\langle u,h \right\rangle)_{u\in\mathcal{U}}\). Then \(\rho_{\mathcal{U}}(h-h')=\max_{u\in\mathcal{U}}|(T(h-h'))_u|\). By Theorem 3, applied to the seminorm \(h\mapsto\max_{u\in\mathcal{U}}|(Th)_u|\), for a standard Gaussian \(g\in\mathbb{R}^d\), \[\gamma_2(B_2^d,\rho_{\mathcal{U}}) \lesssim \mathbb{E}\max_{u\in\mathcal{U}}|(Tg)_u| =\mathbb{E}\max_{u\in\mathcal{U}}\lvert \left\langle u,g \right\rangle \rvert .\] For \(Z=\max_{u\in\mathcal{U}}|\left\langle u,g \right\rangle|\) and any \(\lambda>0\), \[\mathbb{E}Z \leq \frac{1}{\lambda}\log \mathbb{E}e^{\lambda Z} \leq \frac{1}{\lambda}\log\left(2|\mathcal{U}|e^{\lambda^2/2}\right),\] because each \(\left\langle u,g \right\rangle\) is a standard normal random variable and the union bound does not require independence. Taking \(\lambda=\sqrt{2\log(2|\mathcal{U}|)}\) proves the claim. ◻
For our dictionary \(\mathcal{R}\), Lemma 4 gives \(\gamma_2(K,\rho)\leq\gamma_2(B_2^d,\rho)\lesssim\sqrt{\log n}\). This is the only entropy contribution paid by the proof; the size of an individual hyperedge never appears in this estimate.
The following proposition is the core probabilistic estimate. It is a Rudelson-type Rademacher bound [26], but the increments are controlled by the single global-dictionary metric 9 rather than by separate local metrics for individual hyperedges.
Proposition 4 (Global-dictionary chaining bound). In the connected setting of this subsection, with \(N_e\), \(K\), and \(\rho\) defined in 7 , 8 , and 9 , let \(e_1,\ldots,e_M\) be any multiset of hyperedges and define \[S^2=\sup_{y\in K}\sum_{i=1}^M N_{e_i}(y)^2 .\] If \(\sigma_1,\ldots,\sigma_M\) are independent Rademacher signs, then \[\mathbb{E}_{\sigma}\sup_{y\in K} \lvert \sum_{i=1}^M\sigma_iN_{e_i}(y)^2 \rvert \lesssim S\sqrt{\log n} .\]
Proof. Set \(X_y=\sum_{i=1}^M\sigma_iN_{e_i}(y)^2\) for \(y\in K\). Its canonical Rademacher increment metric is \[d_X(y,z)^2= \sum_{i=1}^M\bigl(N_{e_i}(y)^2-N_{e_i}(z)^2\bigr)^2 .\] The moment generating function bound for Rademacher sums shows that \((X_y)_{y\in K}\) is subgaussian with respect to \(d_X\). By 10 , \[\lvert N_e(y)^2-N_e(z)^2 \rvert \leq \rho(y-z)\bigl(N_e(y)+N_e(z)\bigr).\] Consequently, \[\begin{align} d_X(y,z)^2 &\leq \rho(y-z)^2 \sum_{i=1}^M\bigl(N_{e_i}(y)+N_{e_i}(z)\bigr)^2 \\ &\leq 2\rho(y-z)^2 \left(\sum_{i=1}^M N_{e_i}(y)^2+ \sum_{i=1}^M N_{e_i}(z)^2\right) \\ &\leq 4S^2\rho(y-z)^2 . \end{align}\] Thus \(d_X(y,z)\leq 2S\rho(y-z)\). Since \(0\in K\) and \(X_0=0\), Theorem 2 gives \[\mathbb{E}_\sigma\sup_{y\in K}\lvert X_y \rvert \lesssim \gamma_2(K,d_X) \lesssim S\gamma_2(K,\rho).\] Finally, \(K\subseteq B_2^d\) and Lemma 4 with \(\mathcal{U}=\mathcal{R}\) imply \[\gamma_2(K,\rho) \leq \gamma_2(B_2^d,\rho) \lesssim \sqrt{\log(2|\mathcal{R}|)} \lesssim \sqrt{\log n},\] because \(n\geq2\) and \(|\mathcal{R}|\leq\binom n2\). ◻
Remark 5 (Where the rank disappears). A local chaining analysis of a single hyperedge \(e\) views \(N_e\) as a maximum over \(O(|e|^2)\) pair directions and therefore pays a width of order \(\sqrt{\log |e|}\). Proposition 4 never introduces this local width. All hyperedge seminorms are chained through the common dictionary \(\mathcal{R}\), whose width is \(O(\sqrt{\log n})\) once and for all. Hence the sampling loss has the global \(\sqrt{\log n}\) scale but no additional \(\sqrt{\log r}\) factor.
We now complete the proof of Theorem 1. This empirical approximation step follows the same sampling, symmetrization, and self-bounding template as Lee [17] and Jambulapati–Liu–Sidford [18]. The sampling probabilities are the same leverage-overestimate probabilities, while Proposition 4 supplies the rank-independent Rademacher bound in place of the local chaining estimate.
Sample hyperedges independently with replacement from \[p_e=\frac{\tau_e}{\Lambda},\] where \(\Lambda=\sum_e\tau_e\). Given samples \(e_1,\ldots,e_M\), define \[\widehat F(y)=\frac{\Lambda}{M}\sum_{i=1}^M N_{e_i}(y)^2, \qquad \Delta=\sup_{y\in K}\lvert \widehat F(y)-F(y) \rvert .\] For every fixed \(y\), \(\mathbb{E}\widehat F(y)=F(y)\). Applying Lemma 1 to the function class \(f_y(e)=N_e(y)^2\) indexed by the energy body \(K\) in 8 yields \[\mathbb{E}\Delta \leq \frac{2\Lambda}{M} \mathbb{E}\mathbb{E}_\sigma\sup_{y\in K} \lvert \sum_{i=1}^M\sigma_iN_{e_i}(y)^2 \rvert .\] For a fixed sample, let \(S\) be the quantity in Proposition 4. The proposition gives \[\mathbb{E}\Delta\lesssim \frac{\Lambda}{M}\sqrt{\log n}\,\mathbb{E}S .\] The random variable \(S\) is self-bounded by the same deviation \(\Delta\): since \(F(y)\leq1\) for \(y\in K\), \[S^2=\frac{M}{\Lambda}\sup_{y\in K}\widehat F(y) \leq \frac{M}{\Lambda}(1+\Delta).\] Jensen’s inequality therefore implies \[\mathbb{E}S\leq \sqrt{\frac{M}{\Lambda}}\sqrt{1+\mathbb{E}\Delta},\] and hence \[\label{eq:self-bounding-delta} \mathbb{E}\Delta \lesssim \sqrt{\frac{\Lambda\log n}{M}}\sqrt{1+\mathbb{E}\Delta} .\tag{11}\] Choose \(M\gtrsim \Lambda\log n/\varepsilon^2\) with a sufficiently large universal constant. Let \(u=\mathbb{E}\Delta\), and absorb the universal constant in 11 into \(A\), so that \(u\leq A\sqrt{1+u}\) with \(A\lesssim\sqrt{\Lambda\log n/M}\). The implicit constant in the choice of \(M\) ensures \(A\leq\min\{1,\varepsilon/4\}\). If \(u\leq1\), then \(u\leq\sqrt2A\leq2A\); if \(u>1\), then \(u\leq A\sqrt{2u}\), so \(u\leq2A^2\leq2A\). Thus \(\mathbb{E}\Delta\leq\varepsilon/2\). Since \(\Delta\geq0\), there exists a realization of the samples with \(\Delta\leq\varepsilon\).
Fix such a realization, and let \(m_e\) be the multiplicity of hyperedge \(e\) in the sample. For each hyperedge with \(m_e>0\), set \[\widetilde{w}_e=\frac{m_e\Lambda w_e}{M\tau_e},\] and discard unsampled hyperedges. After consolidating repeated samples, the resulting weighted subhypergraph \(\widetilde{H}\) has at most \(M\) hyperedges. For every \(y\in\mathbf{1}^\perp\), \[\begin{align} Q_{\widetilde{H}}(L^{+/2}y) &=\sum_{e:m_e>0}\widetilde{w}_e \max_{p\subseteq e}R_p\left\langle u_p,y \right\rangle^2 \\ &=\sum_{e\in E}\frac{m_e\Lambda}{M}N_e(y)^2 =\widehat F(y). \end{align}\] The additive bound on \(K\) is homogeneous and therefore becomes a relative bound on all of \(\mathbf{1}^\perp\). Indeed, if \(F(y)=0\), then \(y=0\) by Lemma 3. Otherwise \(z=y/\sqrt{F(y)}\in K\), and the degree-two homogeneity of \(F\) and \(\widehat F\) gives \[\lvert \widehat F(y)-F(y) \rvert =F(y)\lvert \widehat F(z)-F(z) \rvert \leq \varepsilon F(y).\] Equivalently, \[\lvert Q_{\widetilde{H}}(L^{+/2}y)-Q_H(L^{+/2}y) \rvert \leq \varepsilon Q_H(L^{+/2}y) \qquad \forall y\in\mathbf{1}^\perp .\] Because \(L^{+/2}\) is invertible on \(\mathbf{1}^\perp\) and both hypergraph energies vanish on constant vectors, the same inequality holds for all \(x\in\mathbb{R}^V\). Since \(\Lambda\lesssim n\), the construction uses \(M=O(n\log n/\varepsilon^2)\) sampled hyperedges. This proves Theorem 1.
The fully dynamic directed consequence in 1.3 needs a one-step sampling estimate with the same ordered-pair coreset structure used by the data structure. In the ordered-pair primitive of Oko–Sakaue–Tanigawa [10], as used by Forster–Goranci–Momeni [12], each ordered pair \((u,v)\) keeps heavy hyperedges whose tail contains \(u\) and whose head contains \(v\), and the remaining hyperedges are half-sampled. The deletion routine maintains these same ordered-pair buckets. Thus the estimate below preserves the primitive and replaces only its sampling analysis.
The same global-dictionary chaining argument still applies. The directed coreset gives a lower bound that plays the role of the minorizing graph in the undirected proof: it controls a weighted Euclidean norm over the ordered pairs. After this normalization, every residual directed hyperedge is a maximum over a subset of a common set of at most \(n^2\) ordered-pair coordinates, and is therefore Lipschitz in a common metric. The sampling error can then be controlled by one chaining argument over this global ordered-pair dictionary. Its complexity is governed by the number of ordered pairs, giving the \(\log n\) term in the proposition, while the chosen failure probability contributes the separate \(\log(1/\delta)\) term.
Proposition 6 (Rank-independent directed coreset sampling). Let \(H=(V,E,w)\) be a directed hypergraph on \(n\) vertices, and assume every directed hyperedge has nonempty tail and head. For a directed hyperedge \(e\), write \(t(e)\) and \(h(e)\) for its tail and head, and set \(P_e=t(e)\times h(e)\). Define \[Q_H(x)=\sum_{e\in E}w_e\max_{u\in t(e),\,v\in h(e)}(x_u-x_v)_+^2 .\] Let \(\lambda\) be a positive integer. Let \(C\subseteq E\) be a directed \(\lambda\)-coreset in the ordered-pair sense of Oko–Sakaue–Tanigawa [10]: writing \(\mathcal{P}_E=\bigcup_{e\in E}P_e\), the set \(C\) can be partitioned into disjoint buckets \(C_p\), indexed by \(p\in\mathcal{P}_E\), such that
every \(f\in C_p\) satisfies \(p\in P_f\);
if some \(e\in E\setminus C\) satisfies \(p\in P_e\), then \(|C_p|=\lambda\);
for every \(f\in C_p\) and every \(e\in E\setminus C\) with \(p\in P_e\), one has \(w_f\geq w_e\).
Let \(S\subseteq E\setminus C\) be obtained by retaining each hyperedge independently with probability \(1/2\) and assigning each retained hyperedge weight \(2w_e\). Let \(\widehat H\) consist of the coreset hyperedges with their original weights and the retained hyperedges in \(S\) with these doubled weights. For every \(\eta,\delta\in(0,1)\), if \[\lambda\gtrsim \eta^{-2}\bigl(\log(2n)+\log(1/\delta)\bigr),\] then with probability at least \(1-\delta\), \(\widehat H\) is a \((1\pm\eta)\) spectral sparsifier of \(H\) with respect to the directed energy \(Q_H\).
Proof. Let \(R=E\setminus C\). If \(R=\emptyset\), then \(\widehat H=H\), so assume \(R\neq\emptyset\). Let \(\mathcal{P}=\mathcal{P}_E\). For a nonnegative vector \(z\in\mathbb{R}_+^{\mathcal{P}}\), define \[F(z)=\sum_{e\in E}w_e\max_{p\in P_e}z_p^2 .\] For every \(x\in\mathbb{R}^V\), the vector \(z(x)_{uv}=(x_u-x_v)_+\) satisfies \(F(z(x))=Q_H(x)\). It therefore suffices to prove the uniform sampling estimate for all nonnegative \(z\).
For each \(p\in\mathcal{P}\), set \[a_p=\max\{w_e:e\in R,\;p\in P_e\},\] with \(a_p=0\) if the set is empty, and let \(\mathcal{P}_+=\{p:a_p>0\}\). For \(p\in\mathcal{P}_+\), the coreset conditions give \(|C_p|=\lambda\); every \(f\in C_p\) contains \(p\) and has weight at least \(a_p\). Since the buckets are disjoint and each \(f\in C_p\) contributes at least \(w_fz_p^2\) to \(F(z)\), for every \(z\in\mathbb{R}_+^{\mathcal{P}}\), \[\label{eq:directed-coreset-lower} F(z) \geq \sum_{p\in\mathcal{P}}\sum_{f\in C_p}w_fz_p^2 \geq \lambda\sum_{p\in\mathcal{P}_+}a_pz_p^2 .\tag{12}\] For \(e\in R\), define \[N_e(z)=\sqrt{w_e}\max_{p\in P_e\cap\mathcal{P}_+}|z_p| .\] For every \(e\in R\) we have \(P_e\subseteq\mathcal{P}_+\); hence, for nonnegative vectors, \(N_e(z)^2=w_e\max_{p\in P_e}z_p^2\) is the residual energy contribution of \(e\). Moreover \(w_e\leq a_p\) for every \(p\in P_e\), and therefore each \(N_e\) is \(1\)-Lipschitz with respect to \[\rho(z-z')=\max_{p\in\mathcal{P}_+}\sqrt{a_p}\,|z_p-z_p'| .\] Projecting to the coordinates in \(\mathcal{P}_+\) does not change any \(N_e\). For \(z\in\mathbb{R}_+^{\mathcal{P}_+}\), write \(\bar z\) for its extension by zero to all of \(\mathcal{P}\), and define \(F_+(z)=F(\bar z)\). Thus, for \[K=\{z\in\mathbb{R}_+^{\mathcal{P}_+}:F_+(z)\leq1\},\] the lower bound 12 shows that the change of variables \(y_p=\sqrt{\lambda a_p}\,z_p\) maps \(K\) into the Euclidean unit ball. In these coordinates, the metric \(\rho\) becomes \(\lambda^{-1/2}\left\lVert \cdot \right\rVert_\infty\) on at most \(|\mathcal{P}_+|\leq n^2\) coordinates. Since \(F_+\) is continuous and 12 bounds \(\sum_{p\in\mathcal{P}_+}a_pz_p^2\) on \(K\), the set \(K\) is compact. Applying Lemma 4 to the standard coordinate dictionary gives \[\label{eq:directed-gamma-bound} \gamma_2(K,\rho) \lesssim \sqrt{\frac{\log(2n)}{\lambda}} .\tag{13}\]
Now consider the Rademacher process \(X_z=\sum_{e\in R}\sigma_eN_e(z)^2\) on \(K\). The increment calculation from Proposition 4 shows that its canonical metric is dominated by \(2S_R\rho\), where \[S_R^2=\sup_{z\in K}\sum_{e\in R}N_e(z)^2\leq \sup_{z\in K}F_+(z)\leq1 .\] Therefore, by Theorem 2 and 13 , \[\label{eq:directed-rademacher-bound} \mathbb{E}_\sigma\sup_{z\in K} \lvert \sum_{e\in R}\sigma_eN_e(z)^2 \rvert \lesssim \sqrt{\frac{\log(2n)}{\lambda}} .\tag{14}\]
Let \(\xi_e\) be the Bernoulli indicator that \(e\in R\) is sampled, and put \[\Delta= \sup_{z\in K} \lvert 2\sum_{e\in R}\xi_eN_e(z)^2- \sum_{e\in R}N_e(z)^2 \rvert .\] Since \(2\xi_e-1\) are independent Rademacher signs, 14 gives \(\mathbb{E}\Delta\lesssim\sqrt{\log(2n)/\lambda}\). In addition, for \(z\in K\) and \(e\in R\), \[0\leq N_e(z)^2\leq \frac{1}{\lambda}, \qquad \sum_{e\in R}N_e(z)^4\leq \frac{1}{\lambda} \sum_{e\in R}N_e(z)^2\leq\frac{1}{\lambda},\] where the pointwise bound follows from 12 applied to the zero extension \(\bar z\): if \(p\in P_e\) attains the maximum in \(N_e(z)\), then \(N_e(z)^2\leq a_pz_p^2\leq1/\lambda\). Bousquet’s concentration inequality for suprema of bounded empirical processes [27], applied to the centered class and its negatives, then gives, for all \(t\geq0\), with probability at least \(1-e^{-t}\), \[\Delta \lesssim \sqrt{\frac{\log(2n)+t}{\lambda}} +\frac{\log(2n)+t}{\lambda} .\] Taking \(t=\log(1/\delta)\) and the stated lower bound on \(\lambda\) gives \(\Delta\leq\eta\) after increasing the universal constant.
By homogeneity, the estimate on \(K\) extends to all vectors in \(\mathbb{R}_+^{\mathcal{P}_+}\), with \(F_+\) in place of \(F\). For arbitrary \(z\in\mathbb{R}_+^{\mathcal{P}}\), let \(z_+\) be its restriction to \(\mathcal{P}_+\). The residual sampled energy depends only on \(z_+\), while \(F_+(z_+)\leq F(z)\) because zeroing nonnegative coordinates cannot increase the maxima defining \(F\). Therefore, for every \(z\in\mathbb{R}_+^{\mathcal{P}}\), \[\lvert 2\sum_{e\in R}\xi_ew_e\max_{p\in P_e}z_p^2 -\sum_{e\in R}w_e\max_{p\in P_e}z_p^2 \rvert \leq \eta F(z).\] The hyperedges in \(C\) are kept deterministically, so this is the relative spectral error of \(\widehat H\) with respect to \(H\). Restricting to \(z=z(x)\) completes the proof. ◻
The one-step routine in Forster–Goranci–Momeni [12] is the Oko–Sakaue–Tanigawa coreset-and-half-sampling primitive [10]. For every ordered pair \((u,v)\), it keeps the \(\lambda\) heaviest still-unselected hyperedges whose tail contains \(u\) and whose head contains \(v\), and samples the residual hyperedges with probability \(1/2\). These ordered-pair buckets are used both in the proof and in the dynamic replacement rule: if a coreset edge chosen for \((u,v)\) is deleted, the data structure replaces it by the next heaviest available hyperedge whose tail contains \(u\) and whose head contains \(v\).
Their analysis uses the original one-step guarantee with \(\lambda=O(\eta^{-2}\log^3 m)\) for step error \(\eta\). The recursive construction has \(k=O(\log m)\) levels and sets \(\eta=\varepsilon/(2k)\), so the one-step parameter becomes \(O(\varepsilon^{-2}\log^5 m)\). Summing the \(O(n^2\lambda)\) coreset contribution over all levels gives their \(O(\varepsilon^{-2}n^2\log^6 m)\) static/decremental size, and the fully dynamic reduction adds one further factor of \(\log m\). Proposition 6 replaces the one-step parameter by \(\lambda=O(\eta^{-2}(\log n+\log(1/\delta)))\). Under the same \(m^{-O(1)}\) one-step failure probability used in their union bound, and when \(m\geq n\), this is \(O(\eta^{-2}\log m)\). With the same choice \(\eta=\varepsilon/(2k)\), the one-step parameter becomes \(O(\varepsilon^{-2}\log^3 m)\). Thus the static/decremental size becomes \(O(\varepsilon^{-2}n^2\log^4 m)\), and the fully dynamic size becomes \(O(\varepsilon^{-2}n^2\log^5 m)\).
The authors used ChatGPT and Codex as AI-assisted research and writing tools during the preparation of this paper. These tools were used to help survey related literature, explore proof strategies, and revise portions of the manuscript. All final mathematical claims, algorithms, proofs, citations, and wording were reviewed, edited, and verified by the authors, who take full responsibility for the integrity, accuracy, originality, and copyright of the submission.