Geometric Analysis of Nonlinear Manifold Clustering

We are grateful for your positive evaluation of our work, especially for acknowledging that “the paper … in this reviewers opinion fits very well into Neurips”. Thank you for the constructive comments, which we address below.

How to choose hyperparameters:

There are three hyperparameters of the method, $W$, $\eta$, and $\lambda$, which we discuss below.

• Choosing $W$: We define the weight matrix such that each entry $(i,j)$ is proportional to (a) the distance between data samples $x_i$ and $x_j$ (see model L-WMC), (b) the exponential of the distance between $x_i$ and $x_j$ (see model E-WMC).
• Choosing $\eta$: We perform a grid search over multiple lambda values, and the following grid values for eta: (a) 1 (b) empirical mean of $||x||2$, (c) empirical mean of $||x||_2^2$.
• Choosing $\lambda$: Please kindly refer to the response to Reviewer XZ5T.

We hope this alleviates your concern; if not, we are happy to engage with you during the discussion session. Thank you for the question!

Best Regards,

Authors of Submission 17809

Thank you for your strong support in the acceptance. Your comments are to the point, and we provide a reply below hoping to alleviate your concerns.

How to choose the hyperparameter $\lambda$ in practice:

Both reviewers XZ5T and Mh3Q pointed out this question. Our answer has two parts:

• Guided by Lemma 3, if one has an estimate of the norm of the data points, curvature of the manifold, and within-manifold data density (i.e. $\zeta$), then the lower bound, $\lambda_l$, of $\lambda$ can be estimated. One can search $\lambda$s that are near to or greater than $\lambda_l$.
• When the above quantities are difficult to know, one can alternatively rely on a heuristic grid search to find $\lambda$ on a training set, as we do in Appendix B.2.
  • The use of $\lambda_0$ in line 672 of the paper follows from the work of [A] (their $\S$ 4.2.2) and [18] (their $\S$ 4.2 and Appendix F). The idea is that, $\lambda_0$ rules out a family of hyperparameters that lead to the solution $c$ being all zeros; such $c$’s are useless since they suggest that every point forms its own cluster.
  • To figure out what $\alpha$ to use, we run experiments on CIFAR-100 data to grid search over $\alpha = \{2,5,10,20,50\}$. Since $\alpha = 20,50$ provided the best results, we used these values for the remaining experiments.

We will include this discussion under Lemma 3, and refer to it in the experiments (section 3.2.2). Thank you for helping us make the paper more self-contained!

Best Regards,

Authors of Submission 17809

[A] C. You, “Sparse Methods for Learning Multiple Subspaces from Large-scale, Corrupted and Imbalanced Data”, 2018.

Thank you for your time in reviewing our paper. We are happy to address your comments below.

(W1, W2, W3, W6) Comparison with SMCE

It was questioned how our method differs from SMCE, why such a difference is needed, and if the difference is significant.

• We agree that our formulation (1.1) differs from SMCE by penalizing the affine constraint.
• The modification is motivated by the goal of providing theoretical guarantees of non-linear manifold clustering methods.
  • With the affine constraint in the SMCE model, we are unable to provide an upper bound on $\lambda$. This prompted us, by necessity, to relax the constraint as a penalization leading to (1.1), which allows us to derive the bounds and theorems in section 2.
• The focus and contributions of this paper are therefore two-fold:
  • Providing geometric conditions that guarantee a manifold preserving solution of (1.1) in terms of curvature, sampling density, separation between the manifold;
  • Showing that (1.1) performs comparably to the state-of-the-art manifold clustering algorithms.

(W2) Geometric interpretation of the constraint $1^Tc = 1$ or its penalty version

• The affine constraint in SMCE is motivated by the fact that a manifold can be locally approximated by an affine subspace.
• Making it a soft penalty with multiplier $\eta$ is equivalent to homogenizing the data with homogenization constant $\sqrt{\eta}$, i.e., (WMC) is equivalent to (1.1).

We will include the clarification in the preamble of section 2, thanks for the comment!

(W3) Is the parameter $\eta$ set as very large?

In our experiments, the parameter $\eta$ is not chosen to be very large. We chose 3 different values of $\eta$ proportional to: (a) empirical mean of $||x||^2$, (b) empirical mean of $||x||$, and (c) the value 1.

(W4) In Eq. (WMC), a homogenization of the data is used, rather than using the raw data. (Part 1) So, are the input data properly normalized or not? Why or why not? (Part 2) Since that $\eta$ should be as large as possible, is that reasonable to appending a very large component on the data vector $x$? (Part 3)

• Part 1: Eq. (WMC) is equivalent to the objective (1.1), i.e., objective with affine constraint penalization, as we explained in the response above.
• Part 2: We did not normalize the input data. As a result, we see that the quantities in our geometric result (Lemma 1) depend on the norm of the data samples. We observe that the same analysis can be used for normalized data samples, which results in a special case.
• Part 3: Great question!
  • Making $\eta$ as large as possible has two effects: on the one hand, it helps enforce the affine constraint. On the other hand, it diminishes the importance of the reconstruction error term in (1.1); a different perspective is that the large $\eta$ dominates the computation of the Euclidean norm of the homogenized points.
  • So it is not reasonable to append a large $\eta$ to the data sample $x$. Thus, rather than choosing an arbitrarily large value for $\eta$ in our experiments, we choose $\eta$ as described in the response of W3.

(W5) Since that the data points are neighboring points and the data are not normalized (the reviewer did find out the normalization step), what can we expect the size of the inradius?

The size of the inradius does depend on the size of the data samples. If the norm of few (or all) data samples scales up, then the inradius will also scale up. However, note that this relationship is not linear. Furthermore, we believe that simply scaling up or down all the data samples by a constant will not have a significant impact on the theoretical results (Lemma 1) since other quantities (apart from inradius) involved in the result also change accordingly.

(W6) The experiments are insufficient and less convincing.

1. The performance comparison is neighther complete nor fair enough. Since that the so-called WMC is similar to SMCE (as discussed in L55-L66), SMCE is the most important baseline method. However, the experimental results listed in Table 1 don't include SMCE. Thus, the empirical evaluation is less convincing.

The goal of our experiments was to compare the performance of WMC with current state-of-the-art methods and show that WMC performs only slightly worse than these methods while also providing a theoretical understanding of the model.

2. For the results of EnSC and SSC listed in Table 1, is there some suitable postprocessing adopted as that in L-WMC or E-WMC? How much the performance improvement is coming from the spetial postprocessing step? What about the performance when the baseline methods also adopt a proper postprocessing?

EnSC and SSC did adopt/use post-processing; in particular, they use the symmetric normalization strategy (“S” in Appendix B.4). We also used the post-processing strategy described in Appendix B.4 when SSC method was used to cluser points in CIFAR-10 dataset. The clustering accuracy was observed to 86.4% (compared to 96.07% for our method).

(W7) In L42: the piled prior works are deep subspace clustering methods, none of them is for nonlinear manifold clustering method. Also, it is not a good practice to pile many citations in a single bracket.

We thank the reviewer for the suggestion, which we will certainly adopt for the final submission.

Best Regards,

Authors of Submission 17809