The paper introduces an algorithm for splitting neurons when training neural networks using gradient descent, in order to progressively grow a neural network architecture for a better fit to the data. Some theoretical connections to wasserstein-infinity gradient steps are presented, as well as multiple experiments for learning interpretable or lightweight neural networks. The proposed method is original and interesting, and the experiments suggest that it is promising for various applications. However, the current proposed method seems far from practical in large scale settings, and the presented theoretical results are quite limited: * computationally, the algorithm as presented in Algorithm 1 requires (i) to check if a local optima is reached on the full training loss (and it seems that gradient updates are performed on the full training loss, which is costly), (ii) eigenvector computation on splitting matrices, (iii) dealing with dynamically growing weight matrices. These aspects seem to make the algorithm impractical compared to simply running SGD on an over-parameterized network.

Additional Feedback: This paper suggests a reduced-rank regression (RRR) estimator suitable for the high-dimensional n p setting. The estimator is very simple and consists of two steps: (1) reduce X with PCA to Z; (2) do SVD on cross-covariance between Z and Y. The paper claims that this procedure has good statistical guarantees and outpeforms all existing competitors. It develops a detailed mathematical treatment (mostly in the Appendix) to provide some statistical guarantees on the performance. That said, I am not convinced that this paper provides a contribution of NeurIPS level.

I have read the authors authors rebuttal; I still believe that the experiments are not convincing enough and that a paper claiming to beat the state-of-the-art in scalable tensor decompositions should contain more thorough and clearer experiment setup (larger-scale experiments, fewer ambiguities about experiment setup decisions). The authors demonstrate how the memory blow-up occurring during the Tucker decomposition can be avoided, by formulating the derivations in a way that sub-tensor partitions of the original input tensor can be processed in a sequential manner. The authors provide convergence guarantees of their algorithm to a point where the gradient is equal to zero. Although the approach is sensible and it is backed by theoretical analysis, I find that the experiments are not convincing enough for a work in which improved scalability is regarded as the main advancement. I first list my comments regarding the experiments and provide with additional comments below: - The authors choose to "arbitrarily set the size of the Movielens and Enron tensors to M M 200 and M M 610".

The paper proposes efficient methods for computing the Tucker decomposition of higher-order tensors. The problem is a hard, basic problem in numerical linear algebra with reasonably wide applicability. Tensor decompositions have played an important role in a variety of machine learning applications, see for example: Anandkumar et al "Tensor Decompositions for Learning Latent Variable Models" JMLR 2014; Novikov et al "Tensorizing Neural Networks" NeurIPS 2015, which used tensor decompositions to massively compress the dense layers of VGG; Moitra and Wein "Spectral Methods from Tensor Networks"; and Becker and Osman "Low rank Tucker decompositions of large tensors using tensorsketch" NeurIPS 2018. Singleshot is a coordinate descent based algorithm which applies gradient updates to variables in the Tucker decomposition, which it cycles over. The paper carefully considers the memory usage of Singleshot (and its variants) since tensor computations are often extremely memory intensive.

Additional Feedback: I think this is a very well written manuscript. Some low-level/stylistic comments: -I think a more detailed statement of the last known bound from NS18 (approximation ratio, additive error, and running time) might have been useful for the reader. I found this a bit misleading for someone who does not know what k-means/median is (ell_2 is not just the square of ell_1 beyond the real line). So I would remove "without privacy constraints" from this sentence. I consider learning with a margin to be on separable data, that is, realizable, by default.

Summary and Contributions: The authors have proposed two new algorithms to solve the timely and important distributionally robust SVM problem. These new algorithms are instances of incremental projected subgradient descent and incremental proximal point algorithm. The main novelty of ISG and IPPA proposed in this work is that they developed efficient algorithms (in linear time) for the subproblems in these solving strategies, which are interesting and potentially beneficial for other problems with similar structures. Besides, the authors carefully analyze the iteration complexity of their new algorithms under the so-called BLR condition. They show if the BLR condition is satisfied, the exponent in the Holderian growth condition could be explicitly determined.

This paper addresses important problems, presents novel techinical analysis, and neumerical results are encouraging. All of the reviewers and I have agreed to accept this paper. However, several reviewers (especially R1 and R4) have pointed out some important concerns. Please consider revising your paper to address them before submitting a camera-ready.

They suggest a new algorithm and prove that it achieves logarithmic regret. Quality: Overall the results in the paper seem technically correct, but I had some concerns about the model/assumptions/results: - it is unclear to me how restrictive the parametric assumption that the expected log of the valuation is linear in the covariates. Although authors claim that predictor variables can be arbitrarily transformed, the task of designing the appropriate transformation, ie. "feature engineering", is a non-trivial task itself. Additionally it is unclear how realistic/flexible the logarithm/exponential relationship is, as it imposes that the valuations are exponentially far in relationship to the weighted covariate distances.

The paper studies a variant of "contextual dynamic pricing", with a parametric model of buyer valuations and non-parametric "residual noise". The model is "rigged" in a specific way which allows for a strong positive result (and reviewers agree this is a feature, not a bug). Reviews are largely positive, but not without some caveats. As per one of the comments, relation to "bandits with side information" should be clarified.

Additional Feedback: Post rebuttal: The authors addressed my comments. Therefore, I keep my score as'accept' but not higher as I think the clarity of the writing should be improved. When G is nonsmooth and proximable, using proximal maps lead to much faster convergence compared to using subgradients in the optimization case. It is therefore an important problem to investigate the sampling analogue of this scheme which is the topic of this paper. As mentioned, some previous work has been done on this problem, but this paper presents an approach that is most general (in terms of G being supported on a more general set) to date.