Two-stage stochastic algorithm for solving large-scale (non)-convex separable optimization problems under affine constraints
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910014206115840 |
|---|---|
| author | Dubois-Taine, Benjamin Pfeiffer, Laurent Oudjane, Nadia Seguret, Adrien Bach, Francis |
| author_facet | Dubois-Taine, Benjamin Pfeiffer, Laurent Oudjane, Nadia Seguret, Adrien Bach, Francis |
| contents | 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 might be prohibitive in practical applications. To overcome this, we propose a two-stage algorithm, combining a stochastic subgradient algorithm on the dual problem, followed by a block-coordinate Frank-Wolfe algorithm to obtain primal solutions. The resulting algorithm requires only $O(\frac{1}{ε^2} + \frac{N}{ε^{2/3}})$ calls to Fenchel conjugates to obtain an $ε$-optimal primal solution in expectation in the convex case. We extend our results to nonconvex component functions and show that our method still applies and gets (almost) the same convergence rate, this time only to an approximate primal solution recovering the classical duality gap bounds usually obtained using the Shapley-Folkman theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_06637 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Two-stage stochastic algorithm for solving large-scale (non)-convex separable optimization problems under affine constraints Dubois-Taine, Benjamin Pfeiffer, Laurent Oudjane, Nadia Seguret, Adrien Bach, Francis Optimization and Control 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 might be prohibitive in practical applications. To overcome this, we propose a two-stage algorithm, combining a stochastic subgradient algorithm on the dual problem, followed by a block-coordinate Frank-Wolfe algorithm to obtain primal solutions. The resulting algorithm requires only $O(\frac{1}{ε^2} + \frac{N}{ε^{2/3}})$ calls to Fenchel conjugates to obtain an $ε$-optimal primal solution in expectation in the convex case. We extend our results to nonconvex component functions and show that our method still applies and gets (almost) the same convergence rate, this time only to an approximate primal solution recovering the classical duality gap bounds usually obtained using the Shapley-Folkman theorem. |
| title | Two-stage stochastic algorithm for solving large-scale (non)-convex separable optimization problems under affine constraints |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2602.06637 |