Constrained convex minimization via model-based excessive gap
We introduce a model-based excessive gap technique to analyze first-order primaldual methods for constrained convex minimization. As a result, we construct firstorder primal-dual methods with optimal convergence rates on the primal objective residual and the primal feasibility gap of their iterates separately. Through a dual smoothing and prox-center selection strategy, our framework subsumes the augmented Lagrangian, alternating direction, and dual fast-gradient methods as special cases, where our rates apply.
The paper proposes a primal dual optimization scheme for decomposable problems with linear coupling constraints, which can recover augmented Lagrangian, ADMM and fast dual descent methods.The paper is novel and highly non-trivial, but incremental in the sense that it provides convergence rates for the iterates themselves, avoiding the need to average as in existing methods. Unfortunately, the paper is hard to read due to the many technical details in the main part. Meaningful experiments are provided in the supplementary material only. The presented theory only applies with known accuracy for the subproblem solutions in each iteration, however the experiments (e.g. 1P2D) only use a few inexact steps.* The supplementary material contains a large collection of examples of applications, and these experiments seem encouraging for the presented method. Still, for all applications I do miss a comparison to the naive approach of just penalizing ||Ax-b||^2 in the objective and running standard accelerated gradient methods. Also, the experiments do not compare to other amenable methods, only standard ADMM in some cases.Instead of including just one experiment of the 1P2D method in the main paper, compared to the theoretical bound, it would be much more valuable to have some practical experiments comparing to competing methods, such as e.g. the SVM or Robust PCA case as presented in the appendix currently.* Another critique point I have is that the iteration complexity of the proposed methods are not discussed in the paper. While the theory only holds for known accuracy for the sub-problems / prox-operators, the experiments are performed with arbitrary inexact subproblems (12) or (15) or prox operators, e.g. a few FISTA iterations, which is not covered by the presented theory.(Update after author feedback: Unfortunately the feedback has not precisely addressed the computational complexity or the accuracy level of the subproblems. Hope this will be made more precise in the paper in case of acceptance.)* Structural assumption of decomposability:It is important to motivate the considered class of optimization problems. The assumption (3) alone is strong as it requires both sum structure as well as dependence of each summands on only one corresponding coordinate block. Using auxiliary variables, many ML problems can be transformed to form (1), which is however only explained in the lengthy supplementary material. Please add in the text that this is indeed possible for applications of interest. Similarly: When mentioning "we employ (3) to do away with the X -feasibility of the algorithmic iterates and focus on linear constraints": add a comment which important applications then still fall into the setting. The relation to Nesterov [1] could be made more clear also. Furthermore, it should be stated early that standard gradient methods do not apply to problems of the form (1) (even assuming prox tractability) due to the linear coupling constraints. However, they do apply for the penalized versions when just adding ||Ax-b|| to the objective.The abstract is not written precisely as to reveal the problem setting. You should clarify that your method can deal with linear coupling constraints, but assumes separable objective.* Introduction paragraph on comparison to [3]: This seems the wrong reference, I see no connection of the concepts used there to optimization setting here.* Adaptive proximal-centers are not explained, and it's not clear if the presented theory applies to this case as well.* Add references when mentioning "immediately supports parallel and distributed implementations in synchronous hardware architectures", as this is non-trivial.### Minor details:-l43: you might want to add that x_i \in X_i, or that the parts of coordinates x_i of x form a partition. And maybe use cartesian product notation instead of pi product for X.-l106: slightly tune down "radically different"-l118: +more structured-l201: phi is not defined here when introducing Nesterov's setting-ref [17]: venue missing