- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes an accelerated method for convex–concave affine-coupling saddle-point problems, where the primal variable is high-dimensional and unconstrained, while the dual variable is low-dimensional and constrained on a convex compact set. These problems can be formulated as composite function minimization, and the proposed method achieves an convergence rate in primal objective suboptimality without strong dual concavity.
The method combines Nesterov's acceleration for the primal updates with a low-dimensional convex subproblem for the dual variable, which can be solved using quadratic programming or interior-point methods. Compared with Algorithm 9 of Drusvyatskiy and Paquette (2017), which reduces to the same dual subproblem in this setting, the proposed method uses a different parameter schedule and an inexactness criterion based on the cross-evaluation gap rather than dual near-stationarity. The paper analyzes conditions under which this criterion preserves the accelerated convergence rate and provides computational complexity bounds for the inner solvers.
Critical strengths
The paper provides a concrete implementation of accelerated composite optimization for affine-coupling problems, with second-order computations restricted to the low-dimensional dual space. It establishes explicit stopping criteria for inexact inner solves and derives computational complexity bounds for satisfying these criteria.
Critical weaknesses
The algorithmic novelty relative to prior work is limited. With exact inner solves, the proposed method has the same accelerated update structure as Algorithm 9 of Drusvyatskiy and Paquette (2017), apart from the parameter schedule. Moreover, the proposed cross-evaluation-gap criterion coincides with the duality-gap stopping criterion previously used by Cheung and Lou (2015) in accelerated composite optimization.
The paper claims a reduction in computational complexity compared with a generic dense solve. However, Algorithm 9 of Drusvyatskiy and Paquette (2017) also admits a low-dimensional dual formulation in this setting. Therefore, the comparison does not establish a computational advantage over an efficient implementation of the existing method. These observations make the algorithmic and computational contributions relative to prior work unclear.
[Cheung and Lou, 2015] Efficient Generalized Conditional Gradient with Gradient Sliding for Composite Optimization
Questions for authors
Under the affine-coupling setting, the two inner subproblems of Algorithm 9 in Drusvyatskiy and Paquette (2017) appear to reduce to a single dual subproblem identical in form to that of the proposed method. With exact inner solves, the outer updates also appear equivalent, apart from the parameter schedule. Could the authors clarify this relationship and the main differences between the methods?
The cross-evaluation gap appears to coincide with the duality-gap stopping criterion used by Cheung and Lou (2015) in accelerated composite optimization. Could the authors discuss how their use and analysis of this criterion differ from the prior work?
The paper compares its computational complexity against an joint dense solve. Since Algorithm 9 of Drusvyatskiy and Paquette (2017) also admits a low-dimensional dual formulation in the affine-coupling setting, could the authors compare the computational complexity of satisfying its near-stationarity criterion with that of the proposed stopping criterion, particularly in their dependence on ?
Points requiring clarification
- Assumption 1.1 / Theorem 2.1: Convexity and barrier compatibility of do not necessarily imply the continuity of required in Theorem 2.1.
- Theorems 4.2 / G.3: The assumption is , whereas the proof only requires .
- Theorem G.4: The initialization is stated as , whereas the proof assumes . Also, the extra factor of in the middle inequality on line 1262 should be removed.
- Equation (9): Since is a vector, the multiplied matrix should be .