Summary: [19] has proposed recently an efficient iterative spectral (eigendecomposition) method (ISM) for the non-convex interpretable kernel dimensionality reduction (IKDR) objective in the context of alternative clustering. It established theoretical guarantees of ISM for the Gaussian kernel. The paper extends the theoretical guarantees of ISM to a family of kernels [Definition 1]. Each kernel in the ISM family has an associated surrogate matrix \Phi and the optimal projection is formed by the most dominant eigenvectors of \Phi [Theorem 1 and 2]. They showed that any conic combination of the ISM kernels is still an ISM kernel [Proposition 1] and therefore ISM can be extend to conic combination of kernels.

This paper proposes an efficient computation of kernel dimension reduction, extending the previous work [19] to much more general class of kernels. We think this extension has an impact both in theory and practice from the general applicability of the framework.

The authors consider the problem of clustering a set of lines in R d. The goal is to minimize the k-means objective: given n lines L in R d find the best set of k points c1,...,ck in R d so as to minimize sum_{l in L} min_{ci} dist(ci, l) 2. This a clean, nicely motivated problem. The authors provide a coreset construction (namely a small size summary of the input so that any alpha-approximation for the summary yields an alpha(1 epsilon)-approximation for the entire input). This implies the first (1 epsilon)-approximation for the problem with running time nd exp(poly(k)) together with a streaming algorithm with similar running time and memory size 2 {poly(k)} log n. En route to the result the authors provide a bicriteria approximation algorithms: namely a solution that contains O(k (log n dk log k)) centers and whose cost is at most 4 times the cost of the optimal solution with k centers.

This paper proposes an PTAS for k-means clustering of lines. The key contribution is the construction of a small coreset, on which brute force algorithms are run. The authors also extend this to the streaming setting. An important computer vision application is used as motivation. The authors should revise the final version to address the issues raised by the reviewers, and make it more readable to researchers in related but not in the exact area.

This has clarified some of my comments, and thus I have increased my score by one level. However, a negative aspect from the author response was the excuse given for the absence of a comparison against SVN; "the results we obtained were much worse than our methods and baselines, and hence did not investigate it further". To me this seems like a very obvious thing to include and discuss in the paper, lending strong support to the new method, so I am a bit suspicious about why it wasn't included. I hope the authors will include it in the revised manuscript, if accepted. Another reviewer commented on the lack of wall-time comparison, and again I feel that the authors did not give a valid excuse for omitting this information from the manuscript (the reader can, I think, be trusted to adjust for different computational setups and hardware when interpreting the wall-time data).

The reviewers felt that this submission represents an important contribution to the field. Please be sure to carefully review and address the concerns of all reviewers (e.g., introducing a comparison with SVNM and providing complete implementation details) in the revision.

Originality: the paper is mostly original in considering the problem of robustness to multiple perturbation types. The trade-off between adversarial robustness to different norms and the definition of "affine attacks" has been also investigated for linear classifiers in: - A. Demontis, P. Russu, B. Biggio, G. Fumera, and F. Roli. In that paper, it is shown that while one can design an optimal classifier against one lp-norm attack, the same classifier will be vulnerable to the corresponding dual-norm attack (e.g., if one designs a robust classifier against l-inf attacks, it will be vulnerable to l1 attacks). In other words, it is shown that a proper regularizer can be the optimal response to a specific lp-norm attack. In the submitted paper, this phenomenon is stated in terms of mutually exclusive perturbations (MEPs) and shown for a toy Gaussian dataset.

Update: I read authors' responce RE:sampling rate does not tell the whole story - i was suggesting to add information about on average how many instances were used for each of the splits (because it is not equal to sampling rate * total dataset size). I am keeping my accept rating, hoping that authors do make the changes to improve the derivations/clarity in the final submission Summary: this paper is concerned with a common trick that a lot of GBDT implementation apply - subsampling instances in order to speed up calculations for finding the best split. The authors formulate the problem of choosing the instances to sample as an optimization problem and derive a modified sampling scheme that is aimed at mimicking the gain that would be assigned to a split on all the of the data by using a gain calculated only on a subsampled instances. The experiments demonstrate good results. The paper is well written and easy to follow, apart from a couple of places in derivations(see my questions).

The authors propose a non-uniform sampling strategy for stochastic gradient boosted decision trees. In particular, sampling probability of the training data is optimized towards maximizing the estimation accuracy of the splitting score of decision trees. The optimization problem allows an approximate closed-form solution. Experiment results demonstrate superior performance of the proposed strategy. The reviewers agree that the paper can not only help understand sampling within GBDT from a more rigorous perspective but also improve GBDT implementations in practice.

Weaknesses: The error of the rank r subspace given by recursively merging local updates is not stated concretely. I would expect the analyis of error between the subspace given by this algorithm after observing n data points and the subspace spanned by leading r singular vectors of the full dataset. Can the authors explain whether that is not feasible in this setting? When performing input perturbation for privacy, since the paper discusses PCA with adaptive rank'r', I would expect an analysis of the error in subspace spanned by leading r eigenvectors given by the algorithm as opposed to the error in first eigenvector. In line 190, it claims the memory requirement is O(cdn) as opposed to O(d 2) in mod-sulq.