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 ℝd, while the dual variable is confined to a constrained, low-dimensional space ℝJ, with J≪ d. Although existing theoretical frameworks establish that an accelerated rate of 𝒪(L/T2) 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 𝒪(L/T2) in primal objective suboptimality after T outer iterations, without strong dual concavity. The additional linear-algebra cost per outer iteration is 𝒪̃(dJ2+J3.5), alongside one evaluation of the component losses and their Jacobian.
Related
- The higher dimensional affine Bernstein and Plateau problems
- A Stochastic Optimization Approach to Control-Affine Optimal Control Problems
- A nonmonotone globalization framework for Anderson acceleration for contractive and nonexpansive fixed point problems
- Affine variational functionals, isoperimetric problems and stability
- A Regularized Newton-Type Method for Manifold--Affine Intersection Problems under Intrinsic Transversality
BibTeX
@misc{lezane2026acceleration,
title = {{Acceleration for Affine-coupling problems}},
author = {Clement Lezane and Sophie Langer and Wouter M. Koolen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36997},
eprint = {2609.36997},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36997},
}
RIS
TY - UNPB
TI - Acceleration for Affine-coupling problems
AU - Clement Lezane
AU - Sophie Langer
AU - Wouter M. Koolen
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.36997
UR - https://arxiv.org/abs/2609.36997
AB - 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 ℝ^d, while the dual variable is confined to a constrained, low-dimensional space ℝ^J, with J≪ d. Although existing theoretical frameworks establish that an accelerated rate of 𝒪(L/T^2) 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 𝒪(L/T^2) in primal objective suboptimality after T outer iterations, without strong dual concavity. The additional linear-algebra cost per outer iteration is 𝒪̃(dJ^2+J^3.5), alongside one evaluation of the component losses and their Jacobian.
ER -