As the title suggests, this paper uses learning-theoretic tools to study a problem of estimating a (Lipschitz) spatial field using sensors which are location-unaware. The main contributions are the formulation of the sensing problem, a proposed algorithm, an analysis of its sample complexity, and some proof-of concept experiments. While in the future this may involve new "contributions to statistical learning theory," the present study does not really develop new techniques. Overall, the problem is interesting but the paper could be strengthened significantly in several directions as noted by the reviewers. In particular some more specific motivating examples would help ground the paper -- the authors mention "spatial sensing... in smart cities or IoT or climatology" but do not elaborate.

The present paper proposes an approximation, based on the first order Taylor expansion of convex regularizer. In the regularized regression setting and under some mild condition on the loss function and the underlying distribution that generates the data, the authors prove that one can replace the regularization term of the regression algorithm by its Taylor approximation and have a guarantee that the solution obtain with this approximation will be close to the original solution (according to the Mahalanobis distance). The authors give then examples of such proxy for square loss and logistic regression and also for Constrained Lasso, Penalized Lasso and Group Lasso. The paper also proposes a discussion where this approach can be useful. Although this paper is a bit technical, it is well written and the result are on my opinion non trivial and interesting.

Strengths: * The paper is concerned with the derivation of k-argmax function's continuous approximation as a generic projection of a score vector onto the (n, 1)-simplex or the (n, k)-simplex (for predicting top-k relevant labels) based on a strongly convex function g . The first interesting contribution shows how to obtain such approximation and derives the general solution of this problem provided some properties of g (it is separable, 1-strongly convex). Relevant g s are quadratic function, negative entropy. Specifically, Euclidean projection with adapted Lipschitz constant \alpha of the projection to the training instance is devised as the Rankmax operator. The key element is that \alpha can be computed such that the sample's labels occurs in the top-k.

Three knowledgeable referees support acceptance for the contributions. One reviewer (R1) was slightly on the reject side but I discounted that review because of low confidence. However, please consider revising your paper to include suggested references, as also promised in the rebuttal, and if possible also extend your empirical evaluation.

This paper derives complexity results for active learning queries to hierarchical clustering. The result is a partition or "cut", c, of the cluster tree, where the "flat" clustering is defined by the clusters at the leaves of a subtree of nodes AB(c) that have the same root as the original cluster tree. Learning occurs by making pairwise judgments on items (leaf nodes). All pairwise judgments form a "ground truth" matrix \Sigma. Given consistency conditions, this is an equivalent way to represent a clustering.

The reviewers appreciate the fact that the algorithm can achieve sharp query complexity guarantees under challenging noisy settings. The only weakness of the paper is motivation - what is a practical scenario where we have these two sources of data?

Strengths – The paper presents a novel and well-motivated approach that is crisply explained, with significant experimental results to back it up. Clean and well-documented code has been provided and the results should be easily reproducible. In particular, the data-independent optimization, ability to bake in priors, computational savings by trimming output dimensionality, improvements over (de-facto) softmax classification in the presence of class imbalance, and suitability for multitask learning without loss weighting are strong wins. The related section does well to clearly identify and present threads in prior work. Weaknesses / Questions – What is the performance of the multitask baseline (Table 5) with appropriate loss weighting?

Summary This paper concerns the asynchronous sparse online and stochastic optimization settings. In this setting several algorithms work in parallel to optimize the same objective. The difficulty herein lies that not all algorithms are aware of the current state of the objective, complicating the analysis. Existing convergence guarantees in this setting only hold for box shaped constraint sets. In this paper the authors develop several new algorithms that can deal with non-box shaped constrained sets: "AsynCADA" and "HedgeHog!".

Weaknesses: - The authors choose to select \beta based on predictive accuracy. This is sensible, but what other approaches could also be used? And does it make sense to consider predictive accuracy on a separate training dataset? In the SMC community, people usually care more about the efficiency with which you can calculate the likelihood function (in order to estimate the parameters with particle MCMC), the accuracy of the filtered distribution, or ESS. Predictive accuracy is usually not a primary accuracy criterion so does it make sense to select \beta with this metric? From the simulation study, it appears that using predictive accuracy works well, but also seems to be consistently sub-optimal.

Four knowledgeable reviewers recommend accept, on the basis that this paper provides a universal approach to hard shape-constrained supervised learning that is applicable to a wide range of problems of interest to the NeurIPS community.