Quantum (Inspired) $D^2$-sampling with Applications

We thank you for your positive comments on our work and appreciate your valuable and constructive feedback

We address the issues pointed out by the reviewer. >Page 1: I find the abstract to have too much low-level information :) Thank you for the suggestion. We will try to make the abstract more concise in the revised version. >Page 4: Can you please expand on related work? How about the connections of your work to computational complexity? We discuss previous work done in relation to this problem in the introduction section of the submission. This discussion includes previous work done on quantum algorithms for k means as well as recent implementations of kmeans++ with improved runtime .We would also be including a table of comparisons (please see below) among various algorithms to serve as a summary of related work done on this problem. It would also make it simpler to see where our contributions lie in the algorithmic landscape. We would be happy to discuss about any specific work the reviewer would like to discuss about. >Page 5: Please give some extra background knowledge in quantum computing and Dirac bra-ket notation :) Thanks for pointing this out. We will make sure to include a brief section in the appendix which would contains pointers to literature covering the required background knowledge. We believe that this is a good suggestion as additional background will make our work more accessible to a broader audience at ICLR. >Page 6: Can you please elaborate on the concept of dequantization and provide some examples? Dequantization refers to a technique recently developed to compare quantum and classical machine learning algorithms on a more level ground starting from the breakthrough work of Tang on recommendation systems [1]. The main idea is to efficiently simulate a quantum algorithm assuming that one has both sampling and query access to the data being provided as input (which can be setup in linear time) , analogous to how data is assumed to be provided in a QRAM data structure to QML algorithms [2] . The PhD thesis [3] nicely classifies QML algorithms into those which have a speedup only due their input assumptions and those for which such results are known (or not expected to exist). We show that $D^2$ sampling belongs to the former class and hence illustrate efficient classical versions of our quantum algorithms. >Page 7: I do not see why the states are the right ones involved in the quantum -sampling algorithm :) The states $(1),\dots,(4)$ represent a high level overview of our quantum algorithm for $D^2$ sampling. In particular , state (4) is as follows : $$ | \Phi_{sample}\rangle = \frac{1}{\sqrt{N}} \sum_{i \in [N]} |i\rangle (\beta_i | 0 \rangle + \sqrt{1 - |\beta_i|^2} |0\rangle ) $$ Here $\beta_i = \frac{1}{Z}\min_{j \in [m]} D(v_i, c_j)$. Note that if we were to measure this state, the probability of getting the outcome as $(i,0)$ would be proportional to $\min_{j \in [m]} D^2(v_i, c_j)$, which is what we want - the $D^2$ distribution itself. This means that if we can prepare this state efficiently, then we can also perform $D^2$ sampling efficiently. >Page 8: I do not understand the Lines 412 -- 417. What does pseudo approximate mean here? In the context of the k means problem , an $(\alpha, \beta)$ pseudo approximate solution means that instead of outputing a set of $k$ centers, we are allowed to output a set of $\beta k$ centers for some $\beta > 1$ such that the clustering cost using these $\beta k$ centers is atmost $\alpha$ times the optimal $k$ means cost. >Page 9: I am not an expert with experiments :) We would be more than happy to clarify any specific comments the reviewer might have on any of the experiments . >Page 10: Where is the Conclusion? :) Can you please add a Conclusion and Future Work section? Thanks again for the suggestion. We have discussed the pros and cons of QIkmeans++ in the experiments section. We will also try to add a separate conclusion and future work section in the revised edition which would also include the discussions done during this period. The major open problem from our work is to see whether we can improve the dependence on the aspect ratio while still maintaining logarithmic dependence on the size of the dataset. We would be happy to address any other concerns , clarifications or comments the reviewer may have.

Request for Rebuttal Feedback - Discussion Period closing soon

Dear Reviewer ZoT4, Thank you for your valuable feedback on our submission. As the discussion phase closes soon, we would greatly appreciate your thoughts on our revision. Early feedback would allow us time to address any remaining concerns you may have. Thank you for your time and consideration. Best regards, Authors

We thank you for your positive comments on our work and appreciate your valuable and constructive feedback

We discuss and address the issues pointed out in the review : > One of the downsides of the algorithm's runtime dependencies is the dependence of the preprocessing cost O(Nd), which is ignored when comparing against existing results. If we add in O(Nd) to the equation, then both the new algorithm and classical algorithms has a linear dependence on . Perhaps it would be meaningful to have experiments that showcase runtime after preprocessing so the plots in Figures 2-3 can be more reflective of the runtime dependencies after preprocessing. Our algorithm indeed has an $O(Nd)$ pre processing cost which is used to setup the SQ access data structures required by the algorithm. We point out that other fast implementations of k means++ like [3],[2]} also have an $O(Nd)$ pre-processing cost for setting up the Multi-Tree Embeddings and the initial distribution for Monte Carlo Markov Chain sampling respectively. The SQ data structures setup in the pre-processing step also allows us to update / add data points in just $O(\log N)$ time so that we do not need to repeat the complete algorithm all over again.This is because we just need to traverse the height of the complete binary tree which represents the SQ data structure. We also mention that there exist implementations of the SQ data structure which can be set up in $O(\mathtt{nnz}(V))$ time, where $\mathtt{nnz}(V)$ is the number of non zero entries in the dataset $V$, which can be much lower than $O(Nd)$ for sparse datasets [4]. Regarding the experiments, we do consider the pre-processing time for comparing the runtimes both with kmeans++ and AFK-MC2. The . We also compare the setup cost needed for both the algorithms in appendix F. Indeed, we observe that for datasets lying in the advatageous regime of QIkmeans++, the runtime after pre-processing is quite fast due to its logarithmic dependence on $N$ for performing multiple clusterings, and is almost constant (and this constant is precisely the pre-processing cost). To be more clear, the plots show the cumulative runtime for performing multiple clusterings i.e, $O(Nd) + \sum_{i \in [q]} \tilde{O}(\zeta^2 k_i^2 d)$ > In page 4, there is discussion about dependencies in the assumption-free case but seems like there are no results for the cases with assumptions. What comparisons and improvements can be made in scenarios with assumptions? The results of [2] with and without assumptions are as follows ($\phi_{OPT}$ is the optimal k means cost and $\phi$ is the solution returned by their algorithm. For a dataset $V$, $\mathbb{V}[V]$ is the variance of the dataset):} 1. Without any assumptions, the runtime is $O(Nd) + O(\frac{1}{\varepsilon}k^2d \log k)$ and the approximation guarantee is $\mathbb{E}[\phi] \leq 8(\log k + 2)\phi_{OPT} + \varepsilon \mathbb{V}[V]$. 2. Under certain assumptions, the runtime is $O(Nd) + O(k^3d \log k)$ and the approximation guarantee is $\mathbb{E}[\phi] \leq 8(\log k + 3)\phi_{OPT}$ For the assumption free case, the approximation guarantee as an additive term which can be arbitrarily larger than the k means cost. For the same approximation guaarantee as k means++, $\varepsilon$ would have to scale as $\mathbb{V}[V] / \phi_{OPT}$. We see that the $\varepsilon^{-1}$ factor can be seen to be analogous to the factor of $\zeta^2$ in QI-kmeans++. For the case with certain assumptions, their algorithm's runtime is independent of any additional factors, but has a worse dependence on $k$ ($k^3$ vs $k^2$) Let us also clarify on the assumptions made by [2]. Their runtime ($O(Nd) + O(\beta(V)k^2d\log k)$) depends on a parameter which they denote as $\beta(V)$ defined as follows : $$\beta(V) = \frac{\mathbb{V}[V]}{\phi_{OPT}}$$ Note that estimating this factor involves solving the k means problem itself and hence it is not computationally efficient to compute. They then show that if the data comes from a distribution which "has exponentially decreasing tail bounds and is approximately uniform on a hypersphere" then $\beta(V) = O(k)$

Request for Rebuttal Feedback - Discussion Period closing soon

Dear Reviewer 66Ux, Thank you for your valuable feedback on our submission. As the discussion phase closes soon, we would greatly appreciate your thoughts on our revision. Early feedback would allow us time to address any remaining concerns you may have. Thank you for your time and consideration. Best regards, Authors

We thank you for your positive comments on our work and appreciate your valuable and constructive feedback

We discuss and address the issues pointed out by the reviewer : > Provide a more detailed justification for why the algorithm presented has quadratic dependence on the aspect ratio. Our algorithms (both quantum and classical) have a quadratic dependence on the aspect ratio $\zeta$ of the dataset. Below, we give a simplified description of our techniques for performing $D^2$ sampling and point out exactly where the dependence on $\zeta$ arises. #### The Quantum Case Essentially, the quantum algorithm performs $D^2$-sampling efficiently by preparing a quantum state such that measuring that state would lead to generating samples from (close to) the $D^2$ distribution. Let the dataset be $V$ and the points in $V$ be $v_1,\dots,v_n$ and let $C$ be the set of cluster centers with points $c_1,\dots,c_t$ For brevity, let us assume that we can efficiently perform the operation $|i\rangle|j\rangle|0\rangle \rightarrow |i\rangle |j \rangle |D(v_i, c_j)\rangle $. A more thorough discussion regarding this can be found in the introduction of section B. By using these operations, we can efficiently prepare the following state by iteratively applying controlled SWAP gates on the second register: $$ |\Phi_C\rangle = \frac{1}{\sqrt{N}} \sum_{i \in [N]} |i\rangle | \min_{j \in [t]} D(v_i,c_j) \rangle $$ Now we transform this state into the following state $|\Phi_{sample} \rangle$ where the term in the second register of $|\Phi_C\rangle $ acts as the amplitude (denoted by $ \beta_i = \frac{\min_{j \in [t]} D(v_i,c_j)}{\sqrt{2\Phi(V,C)}}$) by performing controlled rotations. We can see that we can now sample from the $D^2$ distribution by measuring $|\Phi_{sample}\rangle$. $$ | \Phi_{sample}\rangle = \frac{1}{\sqrt{N}} \sum_{i \in [N]} |i\rangle (\beta_i | 0 \rangle + \sqrt{1 - |\beta_i|^2} |0\rangle ) $$ But to perform the transformation $|\Phi_C\rangle \rightarrow |\Phi_{sample}\rangle$ we need to know the clustering cost $\Phi(V,C)$ to be able to apply the necessary controlled rotations. To be more specific, a rotation gate $R_y(\theta)$ can perform the transformation $|0\rangle \rightarrow \cos \frac{\theta}{2} |0 \rangle - \sin \frac{\theta}{2} |1\rangle $. We can use a controlled rotation gate (with the control on the second register of $|\Phi_C\rangle $) to calculate the required rotation angle to be applied, which needs $\Phi(V,C)$ to compute. It is in computing an approximation to $\Phi(V,C)$ that we get the factor of $\zeta^2$. To estimate $\Phi(V,C)$ , we measure $m$ copies of the state $|\Phi_C \rangle $ and compute the average of the squares of the values measured in the second register (note that these are bounded above by $\zeta^2$). We then use hoeffding's concentration inequality to get an upper bound on the number of samples required, which scales as $\zeta^2$. #### The Classical Case The classical dequantized algorithm works similarly. We want to get sample and query access to a vector which represents the $D^2$ distribution . We do this in the following two compositional steps : 1. Given SQ access to the dataset $SQ(V)$ and the cluster centers $SQ(c_1),\dots , SQ(c_t)$, we setup SQ access to vectors $u_1,\cdots , u_t$ defined as $u_j(i) = D(v_i, c_j)$. 2. Given SQ access to the vectors $SQ(u_1), \dots , SQ(u_t)$, we setup SQ access to a vector $w$ defined as $w(i) = \min_{j \in [t]} u_j(i)$ Note that "setting up" SQ access for a desired vector means providing an algorithm that given SQ access to the inputs allows us to generate samples from the distribution represented by that vector . Note that it is not directly clear how to setup $SQ(w)$ given $SQ(u_1),\dots , SQ(u_t)$. The idea for overcoming this barrier is to setup SQ access to another vector $\tilde{w}$ whose SQ access is simple to construct and which acts as an appropriate upper bound on the original vector $w$. Then samples from $SQ(\tilde{w})$ can be converted to samples from $SQ(w)$ by using rejection sampling. The key step then is to design such a vector $\tilde{w}$. We prove in Lemma 10 that the following choice satisfies all the requirements : $$ \tilde{w}(i) = \sqrt{\frac{1}{t} \sum_{j \in [t]} |u_j(i)|^2} $$ It is in converting $SQ$ access to $\tilde{w}$ to SQ access to $w$ that we get a factor of $\zeta^2$. The rejection sampling step incurrs an overhead of $\phi = \| \tilde{w}\|^2 / \| w\|^2$ in the runtime. We are able to show an upper bound of $\phi \leq 8\zeta^2$ in the proof of Theorem 2.

Request for Rebuttal Feedback - Discussion Period closing soon

Dear Reviewer D44y, Thank you for your valuable feedback on our submission. As the discussion phase closes soon, we would greatly appreciate your thoughts on our revision. Early feedback would allow us time to address any remaining concerns you may have. Thank you for your time and consideration. Best regards, Authors

We thank you for your positive comments on our work and appreciate your valuable and constructive feedback

We discuss and address the issues pointed out in the review : >The performance of the algorithm is only better in certain parameter regimes compared to prior work. That is indeed true. The runtime of QI-$k$-means++ is $O(Nd)$ (pre-processing) + $O(\zeta^2 k^2 d \log Nd)$ and we expect it to perform better when the dataset has large $N$ , small $k$ and a bounded aspect ratio (for example, the binary MNIST dataset). We would also like to point out that due to the setup of the sample and query access (SQ) data structures in the pre-processing step, our algorithm can also handle fast data addition / updation in $O(\log Nd)$ time as compared with previous work. We also see from the previous work that there is no one single algorithm which performs best in all scenarios and would be adding a table of comparision for runtimes, approximation guarantees and the quantities on which the runtimes depend. | Algorithm | Runtime | Approximation Guarantee | Key Parameters| Reference | |----------|----------|----------|------------------------------|--| | $\text{QI-K\small{MEANS}++}$ | $O(Nd) + O(\zeta^2k^2 d \log k \log Nd)$ | $\mathbb{E}[\Phi] \leq O(\log k) \Phi^k_{OPT}$ | $\zeta$ is the aspect ratio i.e, the ratio of the maximum to minimum interpoint distance| This Work | $\text{K-\small{MC}}^2$ | $ O(\gamma k^2 d \log (k \beta) )$ , $ O(k^3 d \log^2 N \log k)$ | $\mathbb{E}[\Phi] \leq O(\log k) \Phi^k_{OPT}$ | $\gamma = 4 N\frac{\max_{x \in V} D^2(x,\mu)}{\sum_{x\in V}D^2(x,\mu)} \frac{\Phi^1_{OPT}}{\Phi^k_{OPT}}$ , $\beta = \frac{\Phi^1_{OPT}}{\Phi^k_{OPT}}$ , Under certain assumptions, $\gamma = O(k\log^2 N)$ and $\beta = O(k)$| [1] | $\text{AFK-\small{MC}}^2$ | $O(Nd) + O\left(\frac{1}{\varepsilon}k^2 d \log \frac{k}{\varepsilon}\right)$ , $O(Nd) + O(k^3 d \log k)$ | $\mathbb{E}[\Phi] \leq O(\log k) \Phi^k_{OPT} + 2\varepsilon \Phi^1_{OPT}$| $\varepsilon \in (0,1)$ is an error parameter, Under certain assumptions $\varepsilon = \Omega(1/k)$ gives $O(\log k)$ approximation | [2] | $\text{R\small{EJECTION}S\small{AMPLING}}$ | $O(Nd \log (\zeta d) + N \log N\log (\zeta d)) + O\left(kc^2 d^3 \log \zeta (N \log \zeta)^{O(1/c^2)} \right)$ | $\mathbb{E}[\Phi] \leq O(c^6\log k) \Phi^k_{OPT}$ |$\zeta$ is the aspect ratio i.e, the ratio of the maximum to minimum interpoint distance $c \geq 1$ is a parameter which controls the runtime - approximation quality tradeoff. | [3] In the above table , $\Phi$ represents the cost of the centers returned by the algoritm, $\Phi^k_{OPT}$ represents the optimal $k$ means cost. $\mu$ is the mean of the dataset. Since we are discussing $k$ means++ like seeding, all the cluster centers are from the dataset itself. > Minor comments: -Line 94: I would call it “result” instead of “observation” In many places throughout the paper, I believe the tilde notation is a bit abused. It should only be used to hide factors logarithmic in the function displayed, not arbitrary ones as in Theorem 1 for example. Thanks for pointing that out. We will make the necessary adjustments in the revised version and also be more explicit about the factors hidden in the $\tilde{O}(\cdot)$ notation while stating our results. > How can someone choose which algorithm to use between the ones in Theorem 2 and Theorem 3? For example, is there an efficient way to compute $\zeta$ in advance? The aspect ratio parameter $\zeta$ can be efficiently computed in advance, since it is the ratio of the maximum to minimum interpoint distance. $\zeta$ can be computed exactly in $O(N\log N)$ deterministic time [4] and in $O(N)$ time using randomization [5]. We can also get an upper bound on the maximum interpoint distance by choosing any point of the dataset and computing twice the maximum distance from all other points in $O(N)$ time. We can then compare $d$ and $\zeta$ to appropriately decide on the algorithm to be used. We would be happy to address any other concerns , clarifications or comments the reviewer may have.

Request for Rebuttal Feedback - Discussion Period closing soon

Dear Reviewer 9Gxa, Thank you for your valuable feedback on our submission. As the discussion phase closes soon, we would greatly appreciate your thoughts on our revision. Early feedback would allow us time to address any remaining concerns you may have. Thank you for your time and consideration. Best regards, Authors