Id: arxiv/2602.06637 Url: https://arxiv.org/abs/2602.06637 Tags: math.OC Score: 0 Title: Two-stage stochastic algorithm for solving large-scale (non)-convex separable optimization problems under affine constraints Domain: math.OC Source: arxiv Authors: Benjamin Dubois-Taine, Laurent Pfeiffer, Nadia Oudjane, Adrien Seguret, Francis Bach Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-06 Page: https://delphi.science/r/arxiv/2602.06637 We consider nonsmooth optimization problems under affine constraints, where the objective consists of the average of the component functions of a large number $N$ of agents, and we only assume access to the Fenchel conjugate of the component functions. The algorithm of choice for solving such problems is the dual subgradient method, also known as dual decomposition, which requires $O(\frac{1}{ε^2})$ iterations to reach $ε$-optimality in the convex case. However, each iteration requires computing the Fenchel conjugate of each of the $N$ agents, leading to a complexity $O(\frac{N}{ε^2})$ which…