This paper explores the question of minimizing the communication among workers while solving an optimization problem in a distributed fashion. In particular, the authors argue that most of the existing work in this direction focused on minimizing the amount of data during each message exchange between the works. In contrast, the authors focus on reducing the number of such exchanges (or communication rounds) during the optimization procedures. The authors argue that reducing the number of rounds is more beneficial as it does not degrade the rate of convergence for a wide class of objective functions. The authors propose a simple approach to reduce the communication: a worker sends the current values of the gradient (based on its data) only if this gradient is significantly far from the previous gradient supplied by this worker, leading to the name lazily aggregated gradient (LAG).

This paper presents a new optimization methods that combines Bayesian optimization applied locally with concepts from MADS to provide nonlocal exploration. The main idea of the paper is to find an algorithm that is suitable for the range of functions that are slightly expensive, but not enough to require the sample efficiency of standard Bayesian optimization. The authors applied this method for maximum likelihood computations within the range of a 1 second. A standard critique to Bayesian optimization methods is that they are very expensive due to the fact that they rely on a surrogate model, like a Gaussian process that has a O(n 3) cost. The method presented in this paper (BADS) also rely on a GP.

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.

The authors propose a reinforcement learning strategy to learn new heuristic (specifically, greedy) strategies for solving graph-based combinatorial problems. An RL framework is combined with a graph embedding approach. The RL approach effectively learns a greedy policy for selecting constructing an approximate solution. The approach is innovative and the empirical results appear promising. An important advantage of the work is that the learned policy is not restricted to a fixed problem size, in contrast to earlier work.

Update: I have considered the author response. Some of my previous questions have been answered. I have updated my review and "overall score". This paper focuses on graph matching problems with quadratic objective functions. These objectives are usually equivalent to a quadratic assignment problem (QAP) [1] on the permutation matrix space. The authors focused on the Frank-Wolfe algorithm (Algorithm 1) on the objectives with the relaxation from the permutation matrix space to the doubly stochastic matrix space DS.

This paper develops a novel alternating direction based method for linear programming problems. The paper presents global convergence results, and a linear rate, for their algorithm. As far as I could see, the mathematics appears to be sound, although I did not check thoroughly. Numerical experiments were also presented that support the practical benefits of this new approach; this new algorithm is compared with two other algorithms and the results seem favorable. Note that the authors call their algorithm FADMM - my suggestion is that the authors choose a different acronym because (i) there are several other ADMM variants already called FADMM, and (ii) this is an ADMM for LP so it might be more appropriate to call it something like e.g., LPADMM, which is a more descriptive acronym.

The paper provides an interpretation of a number of accelerated gradient algorithms (and other convex optimization algorithms) based on the theory of numerical integration and numerical solution of ODEs. In particular, the paper focuses on the well-studied class of multi-step methods to interpret Nesterov's method and Polyak's heavy ball method as discretizations of the natural gradient flow dynamics. The authors argue that this interpretation is more beneficial than existing interpretations based on different dynamics (e.g. Notice that the novelty here lies in the focus on multistep methods, as it was already well-known that accelerated algorithms can be obtained by appropriately applying Euler's discretization to certain dynamics (again, see Krichene et al). A large part of the paper is devoted to introducing important properties of numerical discretization schemes for ODEs, including consistency and zero-stability, and their instantiation in the case of multistep methods.

The authors study the problem of structure learning for Bayesian networks. The conventional methods for this task include the constraint-based methods or the score-based methods which involve optimizing a discrete score function over the set of DAGs with a combinatorial constraint. Unlike the existing approaches, the authors propose formulating the problem as a continuous optimization problem over real matrices, which performs a global search, and can be solved using standard numerical algorithms. The main idea in this work is using a smooth function for expressing an equality constraint to force acyclicity on the estimated structure. The paper is very well written and enjoyable to read.

This paper shows that "certain" adversarial prediction problems under multivariate losses can be solved "much faster than they used to be". The paper stands on two main ideas: (1) that the general saddle function optimization problem stated in eq. The paper is quite focused on the idea of obtaining a faster solution of the adversarial problem. However, the key simplification is applied to a specific loss, the F-score, so one may wonder if the benefits of the proposed method could be extended to other losses. The extension of the SVRG is a more general result, it seems that the paper could have been focused on proposing Breg-SVRG, showing the adversarial optimization with the F-score as a particular application.

The authors' response was in many respects quite comprehensive so I am inclined to slightly revise my score. As I said, I think the results presented in the paper seem interesting and novel, however I still feel that the motivation for signed DPP's is not sufficiently studied. The example of coffee, tea and mugs is nice, but there is just not enough concrete evidence in the current discussion suggesting that the signed DPP would even do the right thing in this simple case (I'm not saying that it wouldn't, just that it was not scientifically established in any way). The authors first define the generalized DPP and then discuss the challenges that the non-symmetric DPP poses for the task of learning of a kernel matrix from i.i.d samples when using the method of moments from prior work [23]. Then, under various assumptions on the nonsymmetric kernel matrix, a learning algorithm is proposed which runs in polynomial time (the analysis follows the ideas of [23], but addresses the challenges posed by the non-symmetric nature of the kernel).