Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond

Thank you for your valuable feedback and for the time spent reviewing our paper. We are pleased that you recognize the significance of our fully dynamic diameter algorithm and the improved update time for k-center. We're also glad that you found the robust centerpoint idea clean and broadly applicable.

Dear Reviewer SCZU,

Please note that only flagging "mandatory ack" is not sufficient, and please actively participate in the discussion with the authors. This could be short (for example, you think your comments are fully addressed), but you should anyway respond.

Regards,

AC

Thank you for your thorough feedback and for the time spent reviewing our paper. We appreciate your positive review and the helpful minor comments on the presentation. We answer your question below.

Is there a possibility of deamortizing the k-center algorithm? I assume that the recursive nature of the algorithm might make this hard, but maybe one can make these rounds of choosing the centers less dependent on each other.

Thanks for this very good question. It seems that the recursive nature of the algorithm mostly plays a role in the update time of the algorithm, causing an extra O(k) factor. The problem that we had with the deamortization was that we could not deamortize different guesses of OPT, as the ‘right’ guess might change multiple times during the course of the deamortization.

Dear Reviewer 8vVV,

Please note that only flagging "mandatory ack" is not sufficient, and please actively participate in the discussion with the authors. This could be short (for example, you think your comments are fully addressed), but you should anyway respond.

Regards,

AC

Thank you for your valuable feedback and for the time spent reviewing our paper. We are glad that the simplicity of our algorithms is valued and that you find the combination of computational geometry with basic robust statistics clever. We address the questions below.

To what extent do you think the approximation factor can be improved? Any comments?

We believe this to be an excellent direction for future work. While we thought about improving the factor using ideas from Chan and Pathak, we were unable to adopt their techniques to our setting. On a high level, the key problem is that the algorithm relies on obtaining a set of anchor points which are all far from each other, whereas our techniques intuitively try to do the opposite since we look at the centroid of the datapoints. Currently, it is not clear whether these ideas can be merged and we suspect that improving the approximation factor would require an approach that is distinct from the prior work in the non-adaptive setting.

to what extent do you think the update time can be improved?

Since a main bottleneck in the update time is the running time of the algorithm for finding centerpoints, we suspect that the poly(d) factor can be improved. Obtaining a time that does not depend on the complexity of finding a centerpoint is likely much more challenging and would require more complex techniques.

Why do you state O(k^6) as being "prohibitively large" even for small k for k-center while O(d^5) is good enough for the diameter?

The value of $d$ is generally assumed to be polylogarithmic in $n$ while no assumption is made on $k$. On a high level this is because at most log(n) dimensions are generally sufficient to capture the geometry of a dataset. Indeed, the Johnson–Lindenstrauss lemma shows any dataset of points in $R^d$ can be projected into a dataset in $R^{d’}$ where $d’ \in \Theta(\log(n))$ while approximately preserving distances.

for k-center, any ideas on reaching linear k dependence as in prior work while dealing with an adaptive adversary?

While we currently do not have any ideas for either obtaining a linear-time algorithm or establishing hardness, we suspect that obtaining such an algorithm would require substantially new techniques and may in fact be impossible. Indeed, the prior work of Bateni et al. for adaptive adversaries has an approximation ratio of $O(\min\{k, \log(n/k)/\log\log(n) \})$. This suggests that obtaining any constant factor approximation with linear update time is a challenging problem and would likely require substantially new techniques.

I'd like to see a more formal definition of the Definition 2.4 (Tukey Depth) …

We appreciate the suggestion to use a more formal definition for the Tukey Depth and to include a citation to Tukey’s original work. We provide a more formal definition below which we have included in the paper and have added the appropriate citation [1].

Given a point set $P = \{p_1, \dots, p_n\} \subset \mathbb{R}^d$, the Tukey depth of a point $x \in \mathbb{R}^d$ with respect to $P$ is defined as: $d_P(x) = \min_{\|v\|=1} \sum_{i=1}^n \mathbf{1} [v^\top (p_i - x) \ge 0 ]$

[1] Tukey, John W. "Mathematics and the picturing of data." In Proceedings of the international congress of mathematicians, vol. 2, pp. 523-531. 1975.

Finally, if you feel that our response has adequately addressed your major concerns, please, consider adjusting your score accordingly.

Dear Reviewer EhRa,

Would you please check if the authors address your major concerns, and if you have further comments? A minimal response would be to submit your “Mandatory Acknowledgement”.

Regards,

AC

Thank you for your valuable feedback and for the time spent reviewing our paper. We are encouraged by your positive comments, in particular that our techniques are highly non-trivial and that the model considered is significantly harder. We address the main concerns and questions below.

It would have been great, if the authors highlighted the intuition behind their novel sampling to improve update time.

Thank you for suggesting to add the intuition behind our novel sampling technique. Our sampling mechanism runs in time $\tilde{O}(\min(k^2, \sqrt{k}n))$ (see Lemma B.3). This enables a total running time of $\tilde{O}(dk^{1.5}n)$ for the offline clustering algorithm (see Lemma B.6), and an amortized update time of $\tilde{O}(dk^{2.5})$ for our dynamic algorithm under adversarial updates (see Lemma B.7). We explain the intuition behind this novel sampling method in the updated version of the paper. For completeness, we provide a summary here.

Recall that the robustness (see Definition 4.1) of a point $x$ is defined as the fraction of points in the dataset $P$ that lie within a ball centered at $x$ of a given radius. A higher robustness implies that $x$ is a stronger candidate for a center, as it can serve effectively over a longer sequence of dynamic updates.

To estimate the robustness of sampled points efficiently, we take into account that there are $k$ clusters. We sample $\tilde{O}(k)$ points and estimate the robustness of each by measuring the fraction of other sampled points lying within a ball of radius $2\cdot OPT$ around it (where $OPT$ denotes the optimal clustering cost). This allows us to identify a robust point—i.e., one that covers the most sampled points—in time $\tilde{\Theta}(k^2)$. Note that since $OPT$ is not known in advance, we use a logarithmic number of guesses, one of which is guaranteed to be within a constant factor of the true $OPT$.

This robustness estimation mechanism is efficient for our dynamic algorithm when the number of clusters $k$ is relatively small, specifically when $k \leq n^{2/3}$, yielding a total running time of $\tilde{O}(k^2)$.

When $k$ exceeds this threshold, we employ a different mechanism. In this case, we reduce the sample size to $\tilde{O}(\sqrt{k})$ and modify our robustness estimation strategy. Instead of testing the fraction of sampled points within radius $2\cdot OPT$ around each sample point, we test the fraction of original points in $P$ that lie within such a ball.

There are two cases:

Case 1: The largest $\sqrt{k}$ clusters each have size at least $n/k$. In this case, with high probability, each of these large clusters will be represented in the sample. Estimating robustness based on coverage of original points will allow us to identify robust centers from these clusters.

Case 2: The remaining $k - \sqrt{k}$ clusters collectively contain at most $n/t$ points, for some constant $t$ (e.g., $t = 4$). Since the large clusters contain at least $(1 - 1/t)n$ points, by the pigeonhole principle, there exists a cluster with at least $\frac{n}{4\sqrt{k}}$ points. Sampling $\tilde{O}(\sqrt{k})$ points uniformly at random ensures, with high probability, that at least one point from this large cluster is included. We can then test its robustness against the full dataset in time $\tilde{O}(\sqrt{k}n)$.

The authors heavily rely on a prior work to find the center point. Essentially these center points serve as the anchor points (from folklore).

There are two novelties in our dynamic algorithm for the diameter problem. The first is the connection we made between dynamic algorithms against adaptive adversaries and the concept of a center point. The concept of a center point is known in computational geometry and machine learning; however, its role in making dynamic algorithms resilient to adaptive adversaries is new and has not been explored before. We think that bridging a connection between two different lines of research would be as interesting as developing new techniques for one line of research. It in fact shows that tools classical in one area may help improve achievements in other areas. The second novelty is the set of lemmas that prove that center points can be maintained in a dynamic setting. This includes Lemma 2.10 and 20.9, which show an α-center point of a point set lies inside the convex hull of that set, and Lemma 2.7, which shows a point inside the convex hull of a set P can encode useful information, such as a 2-approximation of the diameter of P.

The authors explain the role of adaptive adversaries, motivating it. Such an adversary model is common in the literature, and the writing could be improved to focus more on the overview of technical challenges.

There are different variations of adaptive adversaries in the literature. The model we consider in this paper is the strongest. We thought it would be good if we explained the differences between randomness-adaptive adversaries and the weaker version, the output-adaptive adversaries. In this way, it will be clear to the readers precisely what adversarial model we consider. However, you are right; the discussion is a bit long. In the updated version of our paper, we make this section more compact and expand the overview of our algorithm and the analysis.

Finally, if you feel that our response has adequately addressed your major concerns, please, consider adjusting your score accordingly.

Dear Reviewer LwQb,

Would you please check if the authors address your major concerns, and if you have further comments? A minimal response would be to submit your “Mandatory Acknowledgement”.

Regards,

AC