Overall Comments This paper is reasonably well motivated and provide justifications for the key use of integrated gradients as part of the computing the confidence score. The paper also presents several empirical demonstrations of the algorithm. The key motivation is that one might want to compute calibration scores without retraining like is typical for isotonic regression and platt scaling. Originality I am not aware of work using integrated gradients for computing calibration scores. However, the literature on interpretability and uncertainty representation is vast.

Relation to Prior Work: 1) Intuitively, the proposed model seems hugely over-parametrized (O(n 2) parameters!) for the described purpose of modeling non-negative functions. Indeed, in the proof of Theorem 3, to obtain a cc-universal approximator, it suffices to take an operator A of the form A ww T. From a statistical perspective, a preferable model would simply be f_w(x) (w T \phi(x)) 2. The benefit of allowing A to be full-rank is convexity, which makes the model easier to fit. The prior knowledge that the optimization problem has an exact rank-1 solution is presumably the motivation for imposing a nuclear norm constraint. I think clarifying this logic would help motivate the model, as well as the elastic net regularization proposed in (6). I am confused about why one would fix the bandwidth.

The focus of the work is modeling non-negative functions (or more generally functions with output in convex cones). The authors propose a non-parametric approach to tackle this task. They show that the proposed approach have various favorable properties including convexity, universal approximation, representer theorem (hence it is computationally tractable) and it gives rise to complexity bounds alike to standard kernel approaches. The efficiency of the approach is illustrated in density estimation, heteroscedastic Gaussian process estimation and multiple quantile regression. This a nice submission: the paper is clearly written, it delivers both interesting theoretical insights and have practical relevance.

This work achieves an improved bound on the sample complexity of random tensor projection and it is argued that this bound is tight and nearly optimal. A key observation is to view the random sketch as a bilinear form of a random matrix. It makes the analysis suitable to apply general matrix concentration inequalities. The authors can obtain better bounds by analyzing both operator and Frobenius norm of the random matrix, which is the key challenges of this work. Their proof techniques are different from previous approaches but very impressive.

This paper presents tight bounds on the dimension of random projection for tensor product of vectors, achieving exponential improvement on sketch dimension compared to the prior work. The reviewers found the work solid and of high significance.

Originality: For the aforementioned contributions, I believe this work provides a creative, unique approach to this problem. Quality: I believe this paper to be technically sound, a complete work that presents interesting approaches for hierarchical clustering. Clarity: The paper is written well and clearly explains the approach. But there were a some details that I thought could have been made clearer in both the presentation and in the experiments. Unless I've missed something, I think that it would be good to more clearly state the process (and its complexity) of going from the ultrametric fit to data to a dendrogram.

The authors develop a nice method for fitting a hierarchical clustering by solving an optimization problem that leads to an ultrametric (and thus a hierarchical clustering). The reviewers are in agreement that this work should be accepted.

I agree with R3 that you did a poor job on relating your work to existing methods, in particular SARAH. Please also make sure that you carefully address the question of optimality. I also realized that your method in fact has nothing to do with momentum. Consider for instance deterministic objective, f(x, \xi) f(x). If one has a tight estimate, i.e. d_{t-1} abla f(x_{t-1}), then from your update rules it follows that d_t abla f(x_t), i.e. the method become gradient descent with no momentum! Your title, thus, is very confusing and I highly encourage you to change it.

Summary and Contributions: Update: Thanks for addressing the concerns raised by the reviewers, based on re-reading the paper and going over the comments, I am able to understand the experiments better - and based on the authors comments that they will revise the draft to make things more clear, I will change my score to accept. Having said that, I would still keep my confidence low since I am unable to accurately access the significance of the result and I believe that would be a key factor to consider in a novel theoretical paper. The result is based on two key properties of the transformed space that they identify. The first is'safety', which is a measure of how well can we recover the posterior in the original space from the feature space. The second is smoothness, which is a measure of how hard it is to recover the posterior in the original space from the feature space.

This paper provides some interesting theoretical insights into the convergence of kNN over feature transformations. This is backed up by some empirical results. All three reviewers argue for acceptance, but have also provided some directions for improvement, which was acknowledged by the authors in their feedback, promising to include these changes in the final version. Personally I have one issue with the paper, which is introducing some datasets in the experimental section, without providing any results. These are supplied in the additional material, to me that feels like cheating.