A Universal Primal-Dual Convex Optimization Framework
We propose a new primal-dual algorithmic framework for a prototypical constrained convex optimization template. The algorithmic instances of our framework are universal since they can automatically adapt to the unknown Hölder continuity degree and constant within the dual formulation. They are also guaranteed to have optimal convergence rates in the objective residual and the feasibility gap for each Hölder smoothness degree. In contrast to existing primal-dual algorithms, our framework avoids the proximity operator of the objective function. We instead leverage computationally cheaper, Fenchel-type operators, which are the main workhorses of the generalized conditional gradient (GCG)-type methods. In contrast to the GCG-type methods, our framework does not require the objective function to be differentiable, and can also process additional general linear inclusion constraints, while guarantees the convergence rate on the primal problem.
The authors presents a framework for the analysis of constrained convex optimization based on Fenchel duality. Rather than the traditionnal proximal operator, this analysis relies on the the sharp operator, a linear minimization oracle, whose computation is generally simpler. The authors formulate a dual problem for which they derive the proximal gradient step as well as a condition on its Hoelder constant. They then introduces two algorithms to solve the dual problem, the second adding a Nesterov-like acceleration scheme. Their methods are said universal as they rely on a line search to automatically adapt to the Holder constant of the dual objective's gradient. The authors present an analysis of the average number of steps involved in this line search. Finally they present several numerical experiments in which they illustrate the advantages of their methods over the Frank-Wolfe algorithm.The paper seems very sound and rely on different state-of-the-art methods. They provide satisfying results on the computation burden of their line-search step.The paper is rather clear despite the complexity of its content. The paper might be difficult to read for those unfamiliar with both universal gradients and generalized conditional gradient methods as the authors cover those notions rather briefly, but the authors do cite the appropriate references. Some graphs are hard to read and the captioning could be improved however.The paper does not propose an entirely novel method as the algorithms combine several existing methods (universal gradients, GCG methods, FISTA acceleration). Those methods however combine rather gracefully into a simple enough algorithmic scheme, and the use of both universal Hoelder inequality and the sharp operaor is far from ubiquitous in the communityThe results are not as encouraging as they could be. The unaccelerated method does not seem to perform better than Frank-Wolfe, even with constant step, despite its significant increase in both theoretical and implementation complexity. The accelerated method seems to have a slight edge on Frank-Wolfe with line-search however. Even if in the second setting their algorithm seems more promising, its bad graph formatting makes it hard for the reader to determine the extent to which the accelerated method outperforms Frank-Wolfe. A plot of log((error_min-error)/error_min) where error_min is the RMSE/NMAE for a large number of iterations would really help to assess the performance.The authors finally presents two settings in which FW-like methods do not apply. As the authors do not compare their results with any baseline it is hard to reach any conclusion, beyond the great acceleration provided by their second scheme. Even naive baselines (like projected sub-gradient) would be useful to assess the quality of the results.It is however rather satisfying to see an empirical confirmation of the authors' prediction regarding the number of call involved in the line search.In the end I think the ideas proposed by the authors are quite good, but the paper fail to deliver a convincing case for their use against conditionnal gradient methods yet. A better vizualization of the performance of their algorithms in the experimental part could however convince me otherwise.l53 dou you mean "may not" rather than cannot? Figure 2: bad formating, hard to read Figure 2 & 3: captioning is lacking, it is not clear to me which is what