Low-Rank Thinning

We thank the reviewer for the positive and constructive feedback and are delighted that the reviewer found our theoretical guarantees strong, our methods practical, and our applications diverse and of benefit to the community.

A new application: We presented three vignettes with three diverse applications (SGD training, two-sample testing, and attention approximation) to demonstrate the broad applicability and generalizability of the techniques, but we are happy to include an additional experiment with a different architecture and application as further evidence of generalizability. We have recreated the BigGAN image generation benchmarking experiment of Zandieh et al. where leading attention approximation methods are scored on computational expense and image generation quality. We used the experimental setup and released implementations of Zandieh et al. for all other methods. Our results table (https://imgur.com/a/F5Y7pfh) shows that Thinformer (g=2) yields better Frechet Inception Distance (FID) and Inception Scores (IS) than all of the alternatives while running significantly faster than exact, KDEformer, and Reformer. Performer runs faster still but at the expense of substantially worse FID and IS.

Low-rankness: For attention approximation, even if the matrices Q and K are full rank, we still obtain the theoretical and practical benefits advertised (since their rank is d < n). The KMS guarantees (4) and (5) of Thm. 1 also ensure that we obtain a high-quality KMS approximation even if the kernel matrix is full-rank.

For the other two applications, we have run two new analyses to test to what extent the relevant matrices are approximately low-rank in practice. In the CTT setting of Sec. 6.2, we find that the empirical inflation factor $R_k = O(\log^5(n))$ owing to approximate low-rankness: see https://imgur.com/a/hmAVQIU. In the LKH experiment setting of Sec. 5.2, we find that the stochastic gradient matrices $X_k$ have rapidly decaying singular values and a median $\epsilon_k^*$-rank of 10: see https://imgur.com/a/MyA7gR1.

Thank you for the suggestion regarding hyperparameters! We initially omitted hyperparameters when recreating experiments fully specified in prior work, but we will include those hyperparameters in the revision. These include Sec. 6.2 (learning rate = 5e-5; batch size = full sample), Sec. 5.2 (learning rate = 1e-2; batch size = 16), and Sec. 4.2 (learning rate = N/A (inference only); batch size = 64).

We thank the reviewer for the positive and constructive feedback and are glad that the reviewer found our framework “comprehensive” and our speed improvements “significant.”

We apologize for any inaccessibility in our presentation. We aimed to showcase the broad applicability of theory developed in this paper by explicitly deriving sub-Gaussian thinning solutions with state-of-the-art guarantees for three practical problems. We will improve the coherence of the presentation and the accessibility for non-expert readers by providing a more detailed overarching roadmap in the introduction (with guidelines on what will be included in each section), improving transitions between the different application sections, summarizing our main proof arguments, and providing more high-level discussion of theoretical and practical takeaways.

In addition, we will make the definition and broad scope of thinning clearer from the outset by highlighting that thinning flexibly allows one to summarize any of collection of points, be they datapoints (as in our testing application), stochastic gradients (as in our SGD application), or key-value pairs (as in our attention application).

We will also clarify in the introduction that related work for the main results and applications are discussed separately in each section.

We thank the reviewer for the positive and constructive feedback and are delighted that the reviewer found our methods broadly applicable, our experiments extensive and convincing, and our contributions novel and clearly positioned within the literature.

Summaries: Following the reviewer’s advice, we will add a summary of core ideas underpinning the main results. For example, for (3), we decompose the sub-Gaussian error vector $K^{1/2}w$ for $w = p_{in}-p_{out}$ into a rank-r projection $V_r^\top K^{1/2}w\in R^r$ and a residual. We bound the residual error in terms of $\lambda_{r+1}$ and $\vert\vert w\vert\vert_2=1/n_{out}-1/n_{in}$ and bound $\vert\vert V_r^\top K^{1/2}w\vert\vert_2=\sup_{\vert\vert u\vert\vert_2\le1} u^\top V_r^\top K^{1/2}w$ with high probability using the sub-Gaussianity of $w$ and the union bound over a finite cover of the unit ball in $R^r$. Similarly, (4) follows from the sub-Gaussianity of $w$ and the union bound over $\pm e_i$ for each $i\in\mathcal{I}$. Finally, (5) follows from a more elaborate chaining argument that frames $(e_i^\top Kw)_{i\in\mathcal{I}}$ as a sub-Gaussian process and uses the Lipschitzness of $K$ to control its entropy integral.

We will also add summaries and high-level discussions of theoretical takeaways. For example, in Sec. 6.1, we will highlight that a standard way to summarize the discriminating power of a test is through its detectable separation rate, the smallest MMD separation between P and Q detectable with power at least $1-\beta$. Standard quadratic-time MMD tests have a minimax-optimal separation rate of order $1/\sqrt{\min(m,n)}$ (Kim & Schrab, 2023, Thm. 8), and our Thm. 4 shows that CTT matches this rate up to an inflation factor $R_k/2^g$ depending on the eigenvalue decay of the kernel. In other words, CTT provides minimax-optimal detectable separation in near-linear time whenever $\textup{rank}_{\epsilon}(K)$ is polylog(n) for $\epsilon=$polylog(n). As a practical concrete example, we derive the first power guarantees for deep kernel CTT in Cors. 3 and 4; these ensure that CTT can match the power of quadratic-time deep kernel testing in near-linear time. The original CTT analysis used the RKHS covering number bounds of Dwivedi & Mackey (DM) instead of kernel matrix eigenvalues to bound compression error, yielding less sharp results. For example, substituting DM bounds into our deep kernel analysis would yield a larger, order $\log^{3d/4+2}(n/\widetilde \beta)$ inflation factor that does not adapt to the intrinsic manifold dimension.

We will also add a brief summarization of the methods analyzed in the revision and follow the reviewer’s other suggestions to improve clarity.

Tightness: In the revision we will highlight that our Thm. 1 guarantee (5) with GS-Thin matches the minimax lower bound of Phillips & Tai (Thm. 3.1) for KMS coresets on $R^d$; that our Thm. 3 matches the minimax lower bound of Cha et al. (Thm. 4.5) for reordered SGD algorithms up to the epsilon rank parameter r; and that, by Kim & Schrab, 2023 (Thm. 8), the separation rate of our Thm. 4 is minimax optimal up to the inflation factor $R_k/2^g$ and that of Cors. 3 and 4 is minimax optimal up to log factors.

We will also clarify that the observed accelerated convergence rate of LKH-SGD over the standard slow SGD rate of RR provides a direct verification of the Thm. 3 guarantee, while the improved power-runtime trade-off of CTT over the standard Monte Carlo tradeoff of subsampling provides a direct verification of the Thm. 4 guarantee.

Following the reviewer’s advice, we have also conducted two new analyses to explicitly measure the approximate low-rankness of our matrices and thereby gauge the relevance of our guarantees. In the CTT setting of Sec. 6.2, we find that the empirical inflation factor $R_k = O(log^5(n))$ owing to approximate low-rankness: see https://imgur.com/a/hmAVQIU. In the LKH experiment setting of Sec. 5.2, we find that the stochastic gradient matrices $X_k$ have rapidly decaying singular values and a median $\epsilon_k^*$-rank of 10: see https://imgur.com/a/MyA7gR1. We will investigate whether another simple experiment could provide further insight into bound tightness.

We thank the reviewer for championing this submission and are delighted that the reviewer found the paper “clear and easy to follow,” the theoretical results “solid and comprehensive,” and the “wealth and diversity of application quite impressive.”

Thank you also for the interesting question concerning variance proxies. If we understand correctly, the question is whether for each thinning algorithm we have identified the smallest possible sub-Gaussian constant $\nu$. We have not yet had a chance to verify this, but one tractable lower-bounding strategy would be to compute (or lower-bound) each algorithm’s variance parameter $\sigma^2 = \sup_{u} E[u^\top K(p_{in} - p_{out})(p_{in} - p_{out})^\top K^\top u] / u^\top K u$ as a function of the sample size, $\delta$, and the kernel matrix. It seems at least plausible that the derived sub-Gaussian and variance parameters would match in the worst-case setting.

While we do not yet have a precise answer to this question, we can currently comment on the rate optimality of our sub-Gaussian constants. Specifically, Thm. 3.1 of Phillips & Tai implies that any thinning algorithm must incur at least $\Omega(\sqrt{d}/n_{out})$ KMS error for some dataset in $R^d$ and many common kernels. Meanwhile, our Prop. B.6 and Thm. 1 imply that GS-Thin has $\nu = O(1/n_{out})$ and hence KMS $O(\sqrt{d}/n_{out})$. Thus, GS-Thin has a minimax rate-optimal sub-Gaussian constant, and no thinning algorithm can have sub-Gaussian constant $\nu = o(1/n_{out})$.

Finally, thank you for flagging our typo. In the revision, we will replace "Since" with "Moreover" and "surely" with "with probability 1."