Online Adaptive Methods, Universality and Acceleration Volkan Cevher EPFL
We present a novel method for convex unconstrained optimization that, without any modifications, ensures: (i) accelerated convergence rate for smooth objectives, (ii) standard convergence rate in the general (non-smooth) setting, and (iii) standard convergence rate in the stochastic optimization setting. To the best of our knowledge, this is the first method that simultaneously applies to all of the above settings. At the heart of our method is an adaptive learning rate rule that employs importance weights, in the spirit of adaptive online learning algorithms [12,20], combined with an update that linearly couples two sequences, in the spirit of [2]. An empirical examination of our method demonstrates its applicability to the above mentioned scenarios and corroborates our theoretical findings.
This paper considers the problem of designing universal gradient methods, that is designing iterative methods which given gradient or subgradient oracles automatically achieve the best rate for a given problem even without knowing all problem parameters beforehand. In particular, this paper provides a method they call AcceleGrad (which in turn is inspired from AdaGrad) which provided the initial distance of a point to the minimizer is appropriately estimated and an un upper bound on the norm of gradient is given, achieves the best rates possible for smooth minimization, non-smooth minimization, and the stochastic versions of each of these problems. Crucially, the algorithm does not need to be given the smoothness bound beforehand. The algorithm provides experiments to analyze the efficacy of the method.  This paper is well-written and the proposed algorithm is very clean and some of the analysis is quite nice. This paper does a good job of unifying the analysis of multiple convex optimization problems and has key properties that as they point out, no universal method had previously. The main weaknesses of the paper are that it claims universality and optimality fairly strongly in the beginning, but requires upper bounds on the gradient and the domain size up front. While this is not necessarily a major detriment the writing should make this abundantly clear in the beginning. Also, the experiments of the paper could be strengthened. Why the particular experimental settings are chosen and what they really say about the practicality of AcceleGrad could be improved. Furthermore, it isn’t clear there is something particular novel in the analysis or how well known the open problem being addressed is.   Nevertheless, this paper provides a very interesting algorithm that advances the state of the art for convex optimization and unifies the analysis of a number of techniques in a clever way. Consequently, it could make for a nice addition to the program.  Specific comments: - 65: “are explore” --> “are explored” - 78: “we assume to be given” --> “we assume we are given” - 83: “Note that we allow to choose point outside K” – I would clarify this further. - 83: “We also assume that the objective function I G” – throughout the paper or just here, I would be clear. - Figure 1 – what is rho and epsilon in the charts, would make this clearer.  EDIT: Thank you for your thoughtful response. Thank you for clarifying and for agreeing to make certain changes. However, I believe novelty in analysis requires more than being the first to analyze a particular algorithm, it requires an argument of why previous analysis techniques might be stuck, a simple approach might fail, etc. I still think this paper could be a nice addition to the program, but a more concrete case would be need to raise my score much more.