Optimal Black-Box Reductions Between Optimization Objectives *
The diverse world of machine learning applications has given rise to a plethora of algorithms and optimization methods, finely tuned to the specific regression or classification task at hand. We reduce the complexity of algorithm design for machine learning by reductions: we develop reductions that take a method developed for one setting and apply it to the entire spectrum of smoothness and strong-convexity in applications. Furthermore, unlike existing results, our new reductions are optimal and more practical. We show how these new reductions give rise to new and faster running times on training linear classifiers for various families of loss functions, and conclude with experiments showing their successes also in practice.
The authors consider the composite convex optimization problem of minizing the sum of a smooth and a simple convex function, which prox operator is efficiently computatble. The analysis of the authors is based on an abstract decrease property of descent methods for smooth strongly convex optimization: the HOOD property. The main mechanisms behind the proposed method is to approximate convex problems by smooth strongly convex models and tune the level of approximation as a function of the iteration counter. The authors propose and analyse nested algorithms, the inner loop is a call to an abstract descent method which satisfies the HOOD property and the outer loop consists in adjusting the smoothness and / or strong convexity levels of approximate objective function. Careful tuning of approximate model parameters and inner loop calls to HOOD algorithms allows the authors to derive convergence rates for the proposed reductions. Combining these results with known methods for strongly convex optimization, the authors derive algorithms with optimal convergence rates in important optimization model classes. The results are illustrated on Lasso and SVM problems with benchmark datasets.
Overall, the paper is convincing and well written. The problem is very relevant for machine learning applications and the proof arguments are quite convincing. I could not find major flaw in the paper.  I have several concerns to raise regarding this work. - Presentation and comparison with existing methods of similar flavor is not really fair. Smoothing has a long history in optimization and recent work on accelerated methods through strong convexity are not properly presented. Some elements of discussion are missing and no concurrent algorithm is implemented in the numerical section. - The authors put a lot of emphasis on what they call the "old" or "classic" reduction methods. There is no reference about these methods and related complexity results mentioned in the paper. Furthermore, most of the discussion about comparison with state of the art focuses on these "old" reductions. I am not really convinced that this is a fair baseline. - Some aspects of the discussion regarding lasso are very inaccurate.  %% Details about the main comment  Comparison with existing literature:  Smoothing nonsmooth objectives is a relevant topic in optimization literature. For example reference [20] in the main text or the following reference Beck, Amir, and Marc Teboulle. "Smoothing and first order methods: A unified framework." SIAM Journal on Optimization 22.2 (2012): 557-580. I guess the superiority of the proposed framework is the "anytime" property, but this deserved to be presented more clearly.  The authors present the work in [8] and [15] as being identical to the "traditional regularization reduction". I do not understand this point. These works are based on extensions of the proximal point algorithm which indeed adds a strongly convex term with a fixed modulus of strong convexity at each step. But the term itself depends on the iterate counter which is very different from what is described as the classical reduction method. These methods may suffer from log factors, but I disagree with the fact that they suffer from bias. There is no discussion about parameters that are required for the proposed algorithm compared to these methods. For example, in Theorem 3.1, AdaptReg requires an estimate of the distance to the optimum point. How to estimate this? Is the method robust to under estimation of this parameter? Do concurrent methods require this parameter. To my understanding, Catalyst only requires a bound on suboptimality which is easier to estimate. Similar comments hold for Theorem C.2. Finally, no concurrent or even baseline method is implemented apart from the "old" reduction which I think weakens considerably the numerical illustration. Indeed, they mostly illustrate the fact that the "old" reduction is not an anytime method.  The complexity results regarding the old reduction method in section 1.1 should be justified by proper references.   %% Additional questions and suggestions  The bibliography should be in alphabetical order. Ref [27] is not cited in the main text.  On line 24 it is argued that "for a non-SC objective such as Lasso, its dual is not even be well-defined". First, there is a typo and, second, this does not make sense to me. The dual is well defined, feasible and its optimal value is attained.  On page 3, the authors mention optimality of the convergence rates they obtain and justify them by citing reference [1]. From my understanding, the mentioned paper does not focus on lower bounds and there should be a better reference.  In remark 3.2, the authors mention that it is much easier to tune \sigma_0 than \sigma because this is "seen from the plots". This remark is repeated in the numerical section and I do not find that this discussion is convincing.   The presentation of Section 6.1 is very fuzzy. Contrary to what is said, the lasso problem is not smooth. There must be a confusion somewhere. What is meant by indirect solver on line 246?  The whole analysis is based on the HOOD property and the numerical illustration is done with methods which do not satisfy this property. This is a bit disappointing.  Since the duality gap is only an upper bound on suboptimality, the remark on line 255 is only an heuristic and is not sufficient to ensure that the results of the paper apply. This could be precised. A similar comment holds for line 283.  The numerical section does not describe what happens for a bad choice of \sigma_0.  At the end of appendix A, it is mentioned that it is not possible to compute duality gaps for the Lasso. I know at least one possibility from the Appendix of Julien Mairal's Thesis. Moreover, the norm of the gradient is not really the best indicator of suboptimality since it is not 0 in general at the optimum for the lasso. May be the authors refer to the gradient mapping (which includes the prox step). Or may be this is related to the confusion that I pointed out earlier.