The paper extends the work of Dasgupta towards defining a theoretical framework for evaluating hierarchical clustering. The paper defines an objective function that is equivalent to that of Dasgupta in the sense that an optimal solution for the cost function defined by Dasgupta will also be optimal for the one defined in this paper and vice versa. The behaviour of approximate solution will differ though because the cost function is of the form D(G) - C(T), where D is a constant (depending on the input G) and C(T) is the cost (defined by Dasgupta) and T is the hierarchical solution. The authors show a constant approximation guarantee w.r.t. They complement this approximation guarantee by showing that this approximation guarantee is almost tight.

This paper introduces an alternative to CNN based architectures being inspired by the recently proposed capsule networks. The authors proposed to replace the last layer of ResNet variants by a capsule projection network, thereby getting promising results on the CIFAR and SVHN datasets. However, the motivation for using a capsule projection layer is unclear even though the technique is straightforward and easy to implement with minor computational overhead. The main idea of the capsule projection layer is to project the input feature vector to some learnt capsule subspaces (one for each class in classification setting), which are then used to distinguish between the different classes in classification. The authors also show that this projection technique leads to computation of gradients which are orthogonal to the learnt subspace, enabling discovery of novel characteristics leading to improvement of the learnt subspace.

The authors propose a notion of additive perturbation stability (APS) for Euclidean distances that maintain the optimal k-means clustering solution when each point in the data is moved by a sufficiently small Euclidean distance. I think the paper is rather interesting; however, the results of the paper are not very surprising. Here are my comments regarding the paper: (1) To my understanding, the results of Theorem 1.2 are only under the condition of APS. They only hold for the case of k 2 components and may lead to exponential dependence on k components for large k . However, under the additional margin condition between any two pairs of cluster, we will able to guarantee the existence of polynomial algorithm on k .

The paper proposes an algorithm that can learn good decision-making policies over a continuous set of decisions using only access to observational data. The problem is well-motivated, but the paper can be substantially strengthened. Quality: Ok The paper clearly motivates a weakness of direct regression (e.g. from context and decision, to predict expected cost). The regression models may have different uncertainty for different decisions, and so it is useful to include an empirical estimate of variance and bias of the regression when selecting decisions. The paper will be more informative by highlighting several choices of regression models, each with different V (variance) and B (bias), and observing how lambda_1 lambda_2 are tuned to pick low-cost decisions with high probability.

The idea is to represent each class as its mean/prototype within a learned embedding space, and then recognising new classes via softmax over distances to the prototypes. The model is trained by randomly randomly sampling classes and instances per episode. This is appealing due to its simplicity and speed compared to other influential few-shot methodologies [21,28]. Some insights are given about the connection to mixture density estimation in the case of Bregman divergence-based distances, linear models, and matching networks. The same framework extends relatively straightforwardly to zero-shot learning by making the class prototype be the result of a learned mapping from meta-data like attributes to the prototype vector.

The article analyses convergence in hard-thresholding algorithms and proposes an accelerated stochastic hybrid hard thresholding method that displays better convergence with respect to the compared methods. The article is dense but relatively fine to follow. Theoretical development seems to be complete and accurate, though I admit I have not throughly followed the full derivation. Experimental section is in accordance with the theoretical claims and is more than sufficient. Just for the sake of reproducibility of the results an exhaustive pseudocode or repository should be made available as a companion to the article to further strength the autor's points.

The paper investigates a minimax framework for statistical learning where the goal is to minimize the worst-case population risk over a family of distributions that are within a prescribed Wasserstein distance from the unknown data-generating distribution. The authors develop data-dependent generalization bound and data-independent excess risk bounds (using smoothness assumptions) in the setting where the classical empirical risk minimization (ERM) algorithm is replaced by a robust procedure that minimizes the worst-case empirical risk with respect to distributions contained in a Wasserstein ball centered around the data-generating empirical distribution. The statistical minimax framework investigated by the authors resembles in spirit the one introduced in [9], where the ambiguity set is defined via moment constraints instead of the Wasserstein distance. The paper is well-written, with accurate references to previous literature and an extensive use of remarks to guide the development of the theory. The contributions are clearly emphasized, and the math is solid.

The article "Linear regression without correspondence" considers the problem of estimation in linear regression model in specific situation where the correspondence between the covariates and the responses is unknown. The authors propose the fully polynomial algorithms for the solution of least squares problem and also study the statistical lower bounds. The main emphasis of the article is on the construction of fully polynomial algorithms for least squares problem in noisy and noiseless case, while previously only the algorithms with exponential complexity were known for the cases with dimension d 1. For the noisy case the authors propose the algorithm which gives a solution of least squares problem with any prespecified accuracy. For noiseless case another algorithm is proposed, which gives the exact solution of the least squares problem.

This paper focuses on the optimization problem min f(x) h(x), where f is of a finite sum structure (with n functions in the sum), with nonconvex but smooth components, and h is a convex but possibly nonsmooth function. So, this is a nonconvex finite sum problem with a convex regularizer. Function h is treated using a prox step. The authors propose a small modification to ProxSVRG (called ProxSVRG), and prove that this small modification has surprisingly interesting consequences. The modification consists in replacing the full gradient computation in the outer loop of ProxSVRG by an approximation thereof through subsampling/minibatch (batch size B).

This paper focuses on quadratic minimization and proposes a novel stochastic gradient descent algorithm by interpolating randomized coordinate descent (RCD) and stochastic spectral descent (SSD). Those two algorithms were studied in prior but they have drawbacks to apply for practical usage. Hence, authors combine them by random coin-tossing (i.e., with probability \alpha run RCD and with probability 1-\alpha run SSD) and provide the optimal parameters to achieve the best convergence rate. In addition, they study the rate of their algorithm for some special cases, e.g., a matrix in objective has clustered or exponentially decaying eigenvalues. In experiments, they report practical behavior of their algorithm under synthetic settings. The proposed algorithm takes advantages of two prior works, i.e., efficient gradient update from RCD and fast convergence from SSD.