acceptodds
Under review as a conference paper at ICLR 2027

Acceleration for Affine-coupling problems

Abstract

Saddle-point problems play an important role in modern machine learning, including robust optimization and algorithmic fairness. We investigate structured convex-concave minimax problems where the primal variable lies in a high-dimensional, unconstrained space , while the dual variable is confined to a constrained, low-dimensional space , with . Although existing theoretical frameworks establish that an accelerated rate of is possible, solving the associated subproblems efficiently can become a computational bottleneck in high dimensions. To address this, we introduce a decoupling technique. By restricting second-order updates to the low-dimensional dual space and employing first-order methods in the high-dimensional primal space, our framework combines Newton methods with Nesterov acceleration. For simplex-constrained dual variables and regularizers compatible with a self-concordant barrier, the resulting algorithm achieves a convergence rate of in primal objective suboptimality after outer iterations, without strong dual concavity. The additional linear-algebra cost per outer iteration is , alongside one evaluation of the component losses and their Jacobian.

Primary area:
optimization
Keywords:
Saddle-point, optimization, acceleration, interior point method

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_jaeFOpenReview ↗
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 O(1/T2)O(1/T^2) 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 O((d+J)3)O((d+J)^3) 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 O((d+J)3)O((d+J)^3) 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 JJ?

Points requiring clarification

  1. Assumption 1.1 / Theorem 2.1: Convexity and barrier compatibility of RR do not necessarily imply the continuity of Φ\Phi required in Theorem 2.1.
  2. Theorems 4.2 / G.3: The assumption is δ≤β2\delta\le\beta^2, whereas the proof only requires δ≤β\delta\le\beta.
  3. Theorem G.4: The initialization is stated as μ0=1J1\mu_0=\frac1J \mathbf{1}, whereas the proof assumes μ0∈arg⁡min⁡R+B\mu_0\in\arg\min R+B. Also, the extra factor of 22 in the middle inequality on line 1262 should be removed.
  4. Equation (9): Since AA is a vector, the multiplied matrix should be [∇2Fτ(μ)AA⊤0]\begin{bmatrix}\nabla^2F_\tau(\mu) & A \\ A^\top & 0 \end{bmatrix}.
Reviewer_A6FxOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers convex–concave minimax problems with affine coupling and proposes an accelerated method that achieves an O(1/T2)O(1/T^2) rate without requiring strong concavity in the dual variable. The method uses first-order updates for the primal variable and Newton-type methods to solve low-dimensional dual subproblems. The paper also analyzes the complexity of the inner solves and presents experiments on synthetic logistic regression problems.

Critical strengths

Exploiting the low-dimensional dual structure. The proposed method avoids high-dimensional second-order computations by solving subproblems in the dual space. This can be computationally useful when the dual dimension is much smaller than the primal dimension.

Critical weaknesses

Limited novelty. The main contribution appears to be incremental. The affine-coupling problem can be reformulated as a standard convex-composite optimization problem, for which accelerated prox-linear methods, such as Drusvyatskiy and Paquette (2017), already achieve an O(1/T2)O(1/T^2) convergence rate. Moreover, the quadratic dual subproblem in Eq. (5) is precisely the Fenchel dual of a standard prox-linear subproblem, so the proposed dimensional decoupling largely follows from standard convex duality. The main additional contribution therefore seems to lie in the inner-solver analysis and implementation. However, the paper does not clearly establish what computational advantage these developments provide over existing accelerated prox-linear methods implemented using the same dual formulation.

Questions for authors

Constrained Setting: Could the authors clarify whether the proposed framework can be extended to problems with a constrained primal variable w∈Ww\in\mathcal W, assuming projections onto W\mathcal W are tractable? In particular, can the O(1/T2)O(1/T^2) convergence rate and the computational advantages of the low-dimensional dual formulation still be preserved, or does the primal constraint introduce additional difficulties?

Reviewer_c7HROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces an algorithm that provably accelerates convergence on a class of structured convex-concave objectives of the form min⁡w∈Rdmax⁡λ∈ΛΦ(λ,w)\min_{w \in \mathbb{R}^d} \max_{\lambda \in \Lambda} \Phi(\lambda,w), with Φ(λ,w):=⟨λ,f(w)⟩−R(λ)\Phi(\lambda,w) := \langle \lambda, f(w) \rangle - R(\lambda), under the following asusmptions

  • The set Λ⊂RJ\Lambda \subset \mathbb{R}^J is non-empty, compact, and convex. The primal and dual dimensions satisfy d,J∈N+d,J \in\mathbb{N}_+, and are such that d≫Jd \gg J.
  • Λ\Lambda admits a ν\nu-self-concordant barrier BΛ:relint⁡(Λ)→R.B_\Lambda : \operatorname{relint}(\Lambda) \to \mathbb{R}.
  • The function R:Λ→RR:\Lambda \to \mathbb{R} is convex and RR is compatible with BΛB_\Lambda (for every c≥0c \geq 0, cR+BΛcR+B_\Lambda is convex and 1-self-concordant).
  • For every λ∈Λ\lambda \in \Lambda, the function w↦f(w)λw \mapsto f(w)\lambda is convex and LL-smooth, and its gradient is bounded by G>0G > 0.

The authors ensure the method's computational efficiency in the regime J<<dJ<<d by decoupling Nesterov-type acceleration in the primal variable from second-order optimization of the low-dimensional dual variable, with the latter subproblems being solved inexactly. To obtain convergence guarantees, the authors relate the local Newton decrement of interior-point methods to the global approximation error required by the accelerated outer method. The authros provide theoretical guarantees for the accelerated O(1/T2)O(1/T^2) convergence of the algorithm in the general case, and give end-to-end implementation and complexity statements for simplex-constrained dual variables and the negative Burg entropy barrier. The theory is backed by numerical experiments.

Critical strengths
  • The problem is relevant to the optimization community
  • The proposed solution is conceptually neat and contributes to filling the gap in acceleration without strong convexity (concavity) for the considered class of structured convex-concave saddle point problems
  • The paper is well structured
  • The technical claims are rigorous (while I did not check the proofs in full detail, the approach to proving the results and the main steps seem correct)
  • The experiments support the theoretical claims
Critical weaknesses

(Please see details in the next section)

  • The technical presentation of the approach lacks precision and some necessary discussions
  • The results currently require a too-strong structural assumption on ff
  • While the paper's theoretical developments cover generic versions of problem (1) under Assumption 1.1, the fully-specified and theoretically analyzed implementation is restricted to simplex-constrained dual variables and negative Burg entropy barrier.
  • Related literature comparisons need more details
Questions for authors

(References in this section are at the end)

  • Qestions:

    • Is the Lipschitz continuity of w↦f(w)λw \mapsto f(w)\lambda a technical convenience or is it absolutely necessary for deriving Section 4.2's results? This assumption is quite restrictive. Please provide a short discussion on the limitations of your framework in terms of assumptions, compared to the related works mentioned in the paper.
    • The introduction of Assumption 4.1 requires at least a small discussion, since its dependence on the minimizer makes it unverifiable in practice. Why is it necessary? How reasonable is it to expect it to hold in practice?
    • The scope of Lemma 4.1 seems unnecessarily restricted. In particular, the proof does not use that RR is quadratic, and the proof's reliance on simplex geometry seems extendable. A more general formulation could strengthen the contribution. Can the authors please clarify this? Minor: there is a typo in line 1087 y→μy \rightarrow \mu.
    • Can the authors explain why SciPy's trust-constr returning a barrier_parameter of value 1/τk1/\tau_k would imply μk,jzk,j=1/τk\mu_{k,j}z_{k,j} = 1/\tau_k for all j∈{1,…,J}j \in \{1,\ldots,J\}? This appears to assume exact computation. It would be useful to include an appendix section giving the exact correspondence between the named outputs of trust-constr and the quantities in Lemma~4.1.
    • Can the authors elaborate of the comparison between their dual subproblems and the subproblems solved in Section 7 of [1]? It seems to me that under the identification of objectives given in line 088 of the paper, the expression of min⁡zFt,α(z;y,v)\min_z F_{t,\alpha}(z; y, v) in section 7 of [1] ( with g=0g = 0, c=fc = f, h=h = expression in line 088) turns into a min-max objective for which strong duality holds and the arg⁡min⁡z\arg \min_z for fixed λ\lambda has a clean expression. This in turns yields an optimization over λ\lambda highly reminiscent of that in the present paper.
  • Concerns / observations / notes for improvement:

    • Notation and consistency.

      • I suggest replacing (w,wmd,wag)(w,w^{md},w^{ag}) with the classical acceleration triplet (x,y,z)(x,y,z), which would both simplify the notation and improve readability for those familiar with accelerated methods.
      • The iterates' dependence on λ\lambda should either be indicated consistently (as a functional argument or sub/super script) or explicitly suppressed through a sentence identifying all quantities whose dependence on λ\lambda is omitted.
      • Optimal solutions should be defined before use, and the ⋆\star notation should be standardized, as it currently appears both as a subscript and a superscript (for λ\lambda, ww).
      • usage of w⋆w_\star in the body of Thm 3.2 is confusing. Based on the proof, w⋆w_\star is used as an arbitrary point, however, the notation suggests an optimum (especially as later noted by Assumption 4.1).
      • Please rename the quantity S_\star in Assump[tion 4.1] since the letter S clashes with the name of function S_t(lambda)
      • Equation 4 would have been easier to parse if written in terms of \Phi.
      • The surrogate g~\widetilde g is introduced with a single argument (the evaluation point). However in line 225 f~\widetilde f has two arguments: the evaluation point and the expansion point. Please correct g~\widetilde g's definition to include the expansion point. Furthermore, based on how it is subsequently used, I believe that the first argument of f~\widetilde f should be wt+1agw_{t+1}^{ag}.
    • Presentation of technical arguments.

      • The reasoning behind the specific form of StS_t's and ϵt\epsilon_t's definitions is currently vague. More importantly, the fact that this linearization leads to a tractable constrained convex optimization problem, whose solution recovers an approximation of the optimal dual variable, is missing (it is instead introduced abruptly at the beginning of Section 4 as hth_t). As a side note, the authors currently choose to present the construction of the surrogate problem using g~\widetilde g. However, one may arrive at the same point by simply linearizing ff in the optimal expression from (4), and this route would also give the reader more clarity around the purpose of StS_t and ϵt\epsilon_t.
      • The authors refer to equation (4) as an update rule in the body of Thm 2.2. However, its current form somewhat obscures that, in the sense that writing it as an arg⁡max⁡\arg\max yielding the dual variable would have been more in line wiht an "update rule form".
      • The Lipschitz continuity of w↦f(w)λw \mapsto f(w)\lambda is a very strong assumption, not satisfied e.g., by quadratic functions. Given the authors' target applications in ML where quadratics abound, this is a nontrivial shortcoming. However, based on the proofs, this assumption is only needed for the results of Section 4.2. I suggest splitting this requirement from Assumption 1.1 into a separate assumption to emphasize that it is not needed for the accelerated outer-convergence argument.
      • The authors frame the precision of \epsilon_t \in O(1/t^4) as necessary, but less accurate subproblems (i.e., less computation in the subsolver) can still preserving the rate. For example, choosing ϵt∈O(1/(t3(log⁡t)2))\epsilon_t \in O(1/(t^3 (\log t)^2)), or more generally O(1/t3+ξ)O(1/t^{3 + \xi}) for ξ>0\xi > 0.
      • The Bregman divergence definition is not needed to introduce smoothness and strong convexity, especially since it is not further used in the main text
  • Related literature.

    • Line 277: "When RR is self-concordant, the problem of minimising hth_t is well-studied" --- please provide citations here.
    • Paper [2] below also partially relates to the present work in terms of goal/problem formulation, as it addresses objectives of the form min⁡x∈Xmax⁡1≤i≤nfi(x)\min_{x \in X} \max_{1 \leq i \leq n} f_i(x)
  • Contributions statement concern.

    • The per-iteration linear-algebra complexity stated in contribution 1, assuming the authors mean "per-outer-iteration", is incongruent with the complexities stated in the abstract and Table 2 (3 vs 3.5). Please address this. Furthermore, contribution 1 needs an additional qualifier indicating that only a subclass of problems of type (1) are addressed, since Assumption 1.1 contains substantive further restrictions (e.g., bounded gradient).
    • While contribution 3 highlights the extension of interior point guarantees to general geometries from Theorem 4.2, the latter assumes a sufficiently small Newton decrement. The analysis of how the proposed algorithm achieves this sufficiently small decrement is restricted to the simplex with the negative Burg entropy barrier. I believe the contribution should be further qualified in accordance to this.

[1] Drusvyatskiy, and Paquette. "Efficiency of minimizing compositions of convex functions and smooth maps: D. Drusvyatskiy, C. Paquette." Mathematical Programming 178.1 (2019): 503-558.

[2] Vladarean, et al. "Linearization algorithms for fully composite optimization." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.