Summary: the paper proposes a clustering method for linear dynamical systems, based on minimizing the kernalized norm between extended observability spaces. Since the objective function contains terms involving discrete Lypanunov equations (DLEs), the paper derives how to pass the derivatives through, yielding a gradient descent algorithm. Experiments are presented on 2 datasets, for LDS clustering and sparse codebook learning. Originality: 1) novelty: the paper is moderately novel, but fairly straightforward. The difference with other related works [3,9,10,11,12] in terms of objective functions, assumptions/constraints, canonical forms should be discussed more.

The authors introduce embedding propagation (EP), a new message-passing method for learning representations of attributed vertices in graphs. EP computes vector representations of nodes from the'labels' (sparse features) associated with nodes and their neighborhood. The learning of these representations is facilitated by two different types of messages sent along edges: a'forward' message that sends the current representation of the node, and a'backward' message that passes back the gradients of some differentiable reconstruction loss. The authors report results that are competitive with or outperform baseline representation learning methods such as deepwalk and node2vec. Quality: The quality of the paper is high.

The analysis assumes the input samples are iid Gaussian and the output is realizable, i.e. the target value y_k for input x_k is constructed via y_k ReLU(w *.x_k). The paper studies a regression setting and uses least squares as the loss function.

The SDE is first transformed into a random ordinary differential equation. Several solution paths are then simulated to generate a large number of ordinary differential equations, and each of these is then solved using an EM algorithm type approach that was introduced in an earlier paper. The method is tested on two systems, the Lorenz96 and Lorenz63 models, and compared to a competitor method showing that the new approach can be faster and more accurate. There are some interesting ideas in the paper but I can't accept it for publication in its current form. The general approach seems reasonable, but there are some details of it that the authors don't really mention that I think need to be explored.

This paper analyses concentration rates (speed of posterior concentration) for Bayesian regression histograms and demonstrates that under certain conditions and priors, the posterior distribution concentrates around the true step regression function at the minimax rate. Different approximating functions are considered, starting from the set of step functions supported on equally sized intervals, up to more flexible functions supported on balanced partitions. The most important part of the paper is building the prior on the space of approximating functions. The paper is relatively clear and brings up an interesting first theoretical result regarding speed of posterior concentration for Bayesian regression histograms. The authors assume very simple conditions (one predictor, piecewise-constant functions), but this is necessary in order to get a first analysis.

Summary: This paper derives statistical guarantees for the gradient EM algorithm applied to clustering in Gaussian mixture models, generalizing the results of [1] to multiple clusters and non-uniform cluster weights. The first result (Theorem 1) concerns the "population EM algorithm", i.e., when the expectation step can be computed exactly rather than being estimated from data. For this case, if the cluster centers are sufficiently separated and all the estimated cluster centers are initialized sufficiently close to the true cluster centers (i.e., roughly if there is already a sufficiently clear 1-1 correspondence between the estimated and true cluster centers), then the estimated cluster centers converge linearly to the true centers. This result relies on first showing (Theorem 4) that, under these conditions, due to properties of the Gaussian distribution, the curvature of the Q function is bounded (i.e., specifically, the gradient is Lipschitz). By a standard proof, the Lipschitz gradient then implies convergence of gradient descent.

This submission is concerned with unconstrained nonconvex stochastic optimization problems, in a setting in which the function to optimize is only available through stochastic estimates. Obtaining points satisfying second-order necessary optimality conditions has been a recent topic of interest at NIPS, as such points can be as good as global minima on several problems arising from machine learning. The authors present new complexity results that improve over the existing complexity bounds for finding an approximate local minimum, identified as a point for which the gradient norm is less than a threshold \epsilon and the minimum Hessian eigenvalue is at least -\sqrt{\epsilon} . By assuming that the objective function possesses a Lipschitz continous third-order derivative, the authors are able to guarantee a larger decrease for steps of negative curvature type: this argument is the key for obtaining lower terms in the final complexity bounds and, as a result, lower dependency on the tolerance \epsilon compared to other techniques ( \epsilon {-10/3} versus \epsilon {-7/2} in previous works). The authors conduct a thorough review of the related literature, and discuss the main differences between existing algorithms and theirs in Section 2. This literature review appears exhaustive, and identifies key differences between this work and the cited ones.

This is a very interesting paper at the intersection of bandit problems and stochastic optimization. The authors consider the setup where at each time step a decision maker takes an action and gets as a feedback a gradient estimate at the chosen point. The gradient estimate is noisy but the assumption is that we have control over how noisy the gradient estimate is. The challenge for the decision maker is to make a sequence of moves such that the average of all iterates has low error compared to the optima. So the goal is similar to the goal in stochastic optimization, but unlike stochastic optimization (but like bandit problems) one gets to see limited information about the loss function.

The fundamental claim [line 101 & 239] is that asymptotically, for streaming PCA, the delay tau is allowed to scale as (1 - mu) 2 / sqrt(eta), where mu is the step size and mu the momentum parameter. Major Comments Before we discuss the proof, I think the introduction is somewhat misleading. In line 76, the authors point out previous work all focus on analyzing convergence to a first order optimal solution. The readers can be confused that this paper improved the results of previous work. However, the problems studies in those paper and streaming PCA are different.

The paper addresses the problem of performing the distributed k-mean/median clustering in the presence of outliers, and at the same time identifying the outliers. Data are partitioned across multiple sites either adversarially or randomly, and the sites and a central coordinator work jointly by communications to get the data clustering and the outliers. The authors proposed a practical algorithm with bounded running time O(max{k,\log n} n), and bounded communication cost O(s(k\log n t)) and O(sk\log n t) for adversarial and random data partitioning respectively, for a dataset with n data points, k centers, t outliers, and partitioned across s sites. They used a traditional two-level clustering framework (Guha et al. 2017). If using a \gamma -approximation algorithm for (k,t)-mean/median as the second-level clustering algorithm, their distributed algorithm has a bounded O(\gamma) approximation factor. Extensive experimental studies were conducted to compare the performance of their algorithm with three baseline algorithms.