This paper extends Kleinberg's work on the impossibility of clustering. That is, Kleinberg introduced 3 axioms that any clustering procedure should satisfy and then showed that it is impossible to satisfy all three simultaneously. This work suggests a refinement of Kleinberg's 3rd axiom having to do with consistency. In the original axiom, if the clustering distance function is perturbed such that all within-cluster distances do not increase and all across cluster distances do not decrease, then the optimal clustering should be the same with respect to both the perturbed and unperturbed distance functions. The refined consistency axiom proposed in this work says that under the perturbed distance function, the optimal clustering may be different so long as the number of clusters in the optimal partition is different as well.

Summary This paper describes a framework for detecting proxy variables in a linear regression framework. It poses the problem as two optimization problems and presents (with proofs only in supplemental material) theorems that relate the solutions to the two optimization problems to cases of proxy existence in a problem. The paper also describes incorporation of an exempt variable, a proxy that is deemed acceptable for use for one reason or another. The paper leverages a prior work that defines a proxy in a classification framework as a variable that is associated with a sensitive attriute and causally infulential on the decision of the system. The paper describes how to reformulate this definition for the case of linear regression.

The paper proposes Non-parametric Neural Networks (N3) a method that combines advantages of deep models for learning strong relations between input and output variables with the capabilities of probabilistic graphical models at modeling relationships between the output variables. Towards this goal, the proposed method is designed based on three components: a) a deep neural network (DNN) which learns the parameters of local non-parametric distributions conditioned on the input variables, b) a non-parametric graphical model (NGM) which defines a graph structure on the local distributions considered by the DNN. The proposed method is sound, well motivated and each of its components are properly presented. The method is evaluated covering a good set of baselines and an ablation study showing variants of the proposed method. The evaluation shows that state of the art results are achieved by the proposed method.

Note: in view of other related papers pointed out during the discussion process, I have adjusted the rating to reflect concerns over the contribution of this work. This submission presents two new methods, namely sparseflex and sparsehourglass, for mapping input vectors to the probability simplex set (unit sum vectors in the positive orthant). The main motivation is to improve the popular softmax function to induce sparse output vectors, as advocated by the sparsemax function. To this end, a general optimization framework (sparsegen) to the design of such probably mapping functions is proposed, by minimizing the mismatch to a transformation of the input penalized by negative Euclidean norm. Interestingly, it turns out that the sparsegen is equivalent to sparsemax, and it is possible to recover various existing mapping functions by choosing different transformation g(.) and penalization coefficient lambda.

This paper lies in the well-developed field of variance-reduced stochastic gradient algorithms. It proposes a theoretical study of the well-known HSGD for sampling without replacement scheme, which is known to perform better than sampling with replacement in practice. The considered setting makes the analysis of the algorithm more difficult, since in this case the mini-batch gradients are not unbiased anymore. Rates for strongly-convex, non-strongly convex and non-convex objectives are provided, with a special care for linearly structured problems (such as generalized linear models). Numerical experiments are convincing enough, although the datasets used in experiments are not very large (largest one is covtype) (while authors argue that this methods is interesting in the large n medium precision setting).

A) My main concern with this paper is with respect to the main results (Theorems 2 and 3). It seems the authors have not put sufficient care to the fact that \partial \hat{Q} in Algorithm 2 is a biased estimator of the true gradient \partial Q. Also, \hat{Q} defined in Line 189 depends on \hat{\pi} which is an estimate of \pi. Thus, a probabilistic proof would require to look at a conditional probability of the estimation of Q depending on the estimation of \pi. B) Regardless of the above, the final high probability statement in Theorems 2 and 3, seem to be missing the union bound of the error probability in Assumption 1.

This is a very well-written paper and excellently presented with some interesting supporting theoretical results. The paper introduces a method (mirror map) from the optimization literature, mirrored descent, to perform scalable Monte Carlo sampling in a constrained state space. The mirror map works by transforming the sampling problem onto an unconstrained space, where stochastic gradient Markov chain Monte Carlo (MCMC) algorithms, in particular, stochastic gradient Langevin dynamics, can be readily applied. The Fenchal dual of the transformation function is used to transform the samples from the unconstrained space back onto the constrained space. In the paper, the authors state that a "good" mirror map is required.

The authors explore the relation between the trajectory of Gradient Descent (GD) initiated in the origin and the regularization path for l2-regularized minimization of the same objective. They first study the continuous-time setting where GD is replaced Gradient Flow, assuming that the objective is smooth and strongly convex. The main result (Theorem 1 whose proof I have verified) is as follows: under the appropriate scaling between the time t in GD and the inverse regularization parameter \eta, the two trajectories do not diverge much. This result is obtained by quantifying the shrinkage of the gradients as t and eta tend to infinity. In the continuous-time setting, the authors manage to reduce this task to formulating and solving certain ODEs.

The goal of this paper is to speed up logistic regression using a coreset based approach. The key idea is to "compress" the data set into a small fake set of points (called coreset) and to then train on that small set. The authors first show that, in general, no sublinear size coreset can exist. Then, they provide an algorithm that provides small summaries for certain data sets that satisfy a complexity assumption. Finally, they empirically compare that algorithm to two competing methods.

The work proposed a nonparametric Bayesian model for event tensor decomposition. Existing tensor works lack of a way to integrate the complete temporal information in the factorization. This work formulates the so called "event-tensor" to preserver all the time stamps, where each entry consists of a sequence of events rather than a value. To decompose the event-tensor, the work hybridizes Gaussian processes and Hawkes processes to model the entries as mutually excited Hawkes processes, and base rates Gaussian processes on the latent factors. The authors exploit the Poisson process super-position theorem and variational sparse GP framework to derive a decomposable variational lower bound and develop a doubly stochastic algorithm for scalable inference.