Algorithm duality from resolvent Moreau identities
Abstract
Duality is classically defined as a relationship between objective functions, one that breaks down beyond convexity. We show that a more fundamental duality persists between the resolvent operators used to solve associated problems. We establish a framework from which we obtain complete characterizations of the duality-like correspondences between proximal fixed-point iterations and their alternating minimization scheme counterparts. Namely, we show the known primal-dual relationships between forward--backward splitting and Tseng's alternating minimization algorithm, and between the Douglas-Rachford method and alternating direction method of multipliers, to hold generically and irrespective of problem assumptions. The approach considered herein avoids the machinery of convex analysis entirely, providing a definitive formulation of algorithmic dualities in maximal generality while greatly simplifying their proofs. In particular, assumptions such as monotonicity, weak monotonicity, Lipschitz continuity, and injectivity of linear operators are all shown to be unnecessary. In addition, we utilize our framework to reveal and analyze a novel primal-dual relationship between backward-backward splitting and a special instance of the alternating minimization algorithm. This illustrates how our duality framework provides a principled basis for primal-dual algorithm design and analysis in nonmonotone settings. Finally, our experiments show that our backward--backward splitting--based approach reliably outperforms the FISTA and SR3 algorithms for the LASSO problem.
Related
- Resolvent intertwining and spectral duality in Markov chains with geometric resetting
- Bethe Cycles, Frobenius Identities, and Quantum/Classical Duality
- Moreau de Jonnès, du choléra à la SGF : une énigme de l'histoire de la statistique
- Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift
- Completing the Arakawa--Moreau Conjecture on Maximal Ideals of Affine Vertex Algebras
BibTeX
@misc{calcan2026algorithm,
title = {{Algorithm duality from resolvent Moreau identities}},
author = {Andrew Calcan and Alberto De Marchi and Scott B. Lindstrom},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29548},
eprint = {2610.29548},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29548},
}
RIS
TY - UNPB
TI - Algorithm duality from resolvent Moreau identities
AU - Andrew Calcan
AU - Alberto De Marchi
AU - Scott B. Lindstrom
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29548
UR - https://arxiv.org/abs/2610.29548
AB - Duality is classically defined as a relationship between objective functions, one that breaks down beyond convexity. We show that a more fundamental duality persists between the resolvent operators used to solve associated problems. We establish a framework from which we obtain complete characterizations of the duality-like correspondences between proximal fixed-point iterations and their alternating minimization scheme counterparts. Namely, we show the known primal-dual relationships between forward--backward splitting and Tseng's alternating minimization algorithm, and between the Douglas-Rachford method and alternating direction method of multipliers, to hold generically and irrespective of problem assumptions. The approach considered herein avoids the machinery of convex analysis entirely, providing a definitive formulation of algorithmic dualities in maximal generality while greatly simplifying their proofs. In particular, assumptions such as monotonicity, weak monotonicity, Lipschitz continuity, and injectivity of linear operators are all shown to be unnecessary. In addition, we utilize our framework to reveal and analyze a novel primal-dual relationship between backward-backward splitting and a special instance of the alternating minimization algorithm. This illustrates how our duality framework provides a principled basis for primal-dual algorithm design and analysis in nonmonotone settings. Finally, our experiments show that our backward--backward splitting--based approach reliably outperforms the FISTA and SR3 algorithms for the LASSO problem.
ER -