First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. Summary of paper and review: In this paper, the authors consider stochastic-gradient algorithms, and using an importance/weighted sampling scheme, they show how it is possible to attain faster convergence rates in certain regimes. In particular, for strongly convex problems, the authors show how--if one knows Lipschitz constants of every term in a finite sum objective--it is possible to attain convergence rates that depend not on a squared norm of Lipschitz constants but on a 1-norm-like quantity, which is always smaller. The downside of this approach is that one must know these Lipschitz constants, and it is difficult (perhaps impossible) to apply the results to objectives that are not of the from f(x) = \sum_{i=1}^n f_i(x). I am also not convinced that I should care to use these algorithms; the lack of empirical insights leaves me wondering if this analysis matters. Detailed comments: The idea here is a simple enough idea, and makes sense.

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. This paper addresses the problem of robustly estimating the low-dimensional subspace of contaminated observations when the observations are inherently coherent. Performance goes worse with increasing data coherence is a standard theoretical bottleneck of previous RPCA methods. This paper, however, circumvents this problem in a clever manner. Considering that such cluster structure is rather common in realistic data, solving this issue is certainly significantly meaningful.

This paper addresses the problem of learning causal networks with interventions, when each intervention is limited to size k. The paper is generally well-written and addresses a relevant question, as it is generally not feasible to learn the causal structure from observational data alone. Moreover, in some cases, it may also not be possible to perform arbitrarily large interventions, but it is possible to perform interventions over smaller subsets of the variables. The authors prove a number of results around the number of interventions required to learn complete and chordal graphs, and, while I was not able to check all the proofs in detail, the results are as expected (and appear to be correct). The results on chordal graphs are applicable to general causal structures in the sense that application of conditional independence learning and Meek rules results in a chain graph with chordal chain components.

Summary and Contributions: post-rebuttal update I am satisfied with the author's responses in their rebuttal and my score remains the same. In particular, regarding motivation for their own setting, I think the author's response about malicious users affecting the feedback of a learning algorithm is great. Regarding the simulations, the author's explained why some of the plots were weird. Rather than taking out these plots, I think it's great to leave them in and just explain the effect (as the author's did in their rebuttal). This paper studies decision-theoretic online learning (the Hedge setting), a full-information online learning game, under the assumption that the data is stochastic (with a gap in the mean between the best and second best experts) but only observed under adversarial corruption (with a parameter measuring the amount of corruption).

Summary and Contributions: This paper aims to improve the reviewer-paper matching algorithms that many computer science conferences use to assign reviewers to submitted papers. Most conferences currently employ a deterministic algorithm with a linear program at its core that maximizes the total match quality (sum of similarity scores) subject to load balancing constraints ensuring that no reviewer is assigned too many papers and every paper is assigned enough reviewers. A problem with a deterministic algorithm is that unethical reviewers can manipulate their similarity scores (either through bids or submitted features) in order to try to get assigned one particular paper in order to boost it or nuke it. Another problem with a deterministic algorithm is that it cannot be shared to the public without the public being able to reverse engineer the match and reveal the reviewers assigned to a paper. The authors show that both problems can be alleviated by going with a randomized algorithm.

Summary and Contributions: The paper considers the possibility of running algorithms directly on the compressed data to obtain significant time savings. In particular, the paper considers the compression with restricted form of grammar compressed strings that capture modern compression tools like Lempel-Ziv. Let N be the input size and T(N) n be the compressed size. The goal would be to create algorithms with running time that depend on n in the same way standard algorithms depend on N. In this paper the authors consider dot product, matrix vector product and matrix matrix product and show conditional lower bounds by reduction from problems assumed to be hard (3SUM, K-SUM) For matrix-matrix product, the authors show that even when the input matrices can be greatly compressed the output (in compresses form) still requires essentially N 2 bits, which means that any algorithm working on compressed data would need at least this time. For dot product of two vectors, the authors show several results for different assumptions.

Summary and Contributions: This paper studies the selection problem, which (in the most general case) can be stated as follows: there is a data-independent set of n candidate solutions R that we would like to select from. For each candidate r in R, there is a quality score function q_r that maps any input dataset D to a real number q_r(D). The goal is to, given dataset D, select r in R that maximizes q_r(D), while respecting the notion of differential privacy (DP). Here, we say that the algorithm incurs an error of q * - Expectation[q_{output}(D)] where q * min_r q_r(D); in other words, the error is the expected quality loss of the return solution compared to the optimum. Many well-studied problems in machine learning can be stated in the selection formulation; for example, each r could be a hypothesis and q_r(D) is the empirical error.

Summary: A large number of machine learning models are trained on potentially sensitive data, and it is often import to guarantee privacy of the training data. Chaudhuri and Monteleoni formulated the differentially private ERM problem and started a line of work on designing differentially private optimization algorithms for variants of ERM problems. Recent works have gotten nearly optimal tradeoffs between the additional error introduced by the DP algorithm (the privacy risk) and the privacy parameter, for a large class of settings. In this work, these results are improved in the additional axis of computational efficiency. For smooth and strongly convex losses, this work gets privacy risk bounds that are essentially the best known, but do so at a computational cost that is essentially (n \kappa) gradient computaitons, instead of n\kappa, where \kappa is the condition number.

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).

The results provide useful insights to the understanding of Boltzmann exploration and multi-armed bandits - The paper is clearly written Cons: - The technique is incremental, and the technical contribution to multi-armed bandit research is small. The paper studiee Boltzmann exploration heuristic for reinforcement learning, namely use empirical means and exponential weight to probabilistically select actions (arms) in the context of multi-armed bandit. The purpose of the paper is to achieve property theoretical understanding of the Boltzmann exploration heuristic. I view that the paper achieves this goal by several useful results. First, the authors show that the standard Boltzmann heuristic may not achieve good learning result, in fact, the regret could be linear, when using monotone learning rates.