Effective Dual Subgradient Methods Through Sequential Subgradient-Aligned Rays
Abstract
In this paper, we propose an efficient subgradient-based framework, referred to as the sequential subgradient-aligned rays (SSAR) method, for improving the convergence performance of the dual subgradient method. In particular, the proposed method identifies and exploits a finite sequence of rays, when available, as the dual subgradient method evolves, along each of which a subgradient of the negative dual function remains constant and aligns with the ray. While the dual variable iterates remain on each identified ray, a constant stepsize associated with the ray is employed, with the associated constant stepsizes decreasing from one ray to the next. This approach yields constant decrements in the negative dual function values while the dual variable iterates remain on the associated rays, enabling the dual variable iterates to progress more quickly toward a dual optimal solution. We then show that the proposed SSAR method can be leveraged to improve the performance of the dual decomposition method for minimizing the average of local loss functions associated with multiple agents that share a common decision variable, a widely used problem formulation in many large-scale real-world applications. In particular, the SSAR method improves the convergence performance of the corresponding dual decomposition method while also reducing its communication cost. Numerical experiments on a least squares regression problem and a logistic regression problem using real datasets are conducted to evaluate the performance of the SSAR method.
Related
- Nonminimizing Attractors of Stochastic Subgradient Methods on Semialgebraic Functions
- Primal-Dual Adaptive Subgradient Methods
- Projected Subgradient Methods for a Class of Nonsmooth and Nonconvex Optimization Problems
- Subgradient Methods for Nonsmooth Sample Average Approximation
- Retraction-Free Nonsmooth Optimization on the Stiefel Manifold: Subgradient and Proximal Landing Methods
BibTeX
@misc{abeynanda2026effective,
title = {{Effective Dual Subgradient Methods Through Sequential Subgradient-Aligned Rays}},
author = {Hansi Abeynanda and Chathuranga Weeraddana and Carlo Fischione},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31486},
eprint = {2610.31486},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31486},
}
RIS
TY - UNPB
TI - Effective Dual Subgradient Methods Through Sequential Subgradient-Aligned Rays
AU - Hansi Abeynanda
AU - Chathuranga Weeraddana
AU - Carlo Fischione
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.31486
UR - https://arxiv.org/abs/2610.31486
AB - In this paper, we propose an efficient subgradient-based framework, referred to as the sequential subgradient-aligned rays (SSAR) method, for improving the convergence performance of the dual subgradient method. In particular, the proposed method identifies and exploits a finite sequence of rays, when available, as the dual subgradient method evolves, along each of which a subgradient of the negative dual function remains constant and aligns with the ray. While the dual variable iterates remain on each identified ray, a constant stepsize associated with the ray is employed, with the associated constant stepsizes decreasing from one ray to the next. This approach yields constant decrements in the negative dual function values while the dual variable iterates remain on the associated rays, enabling the dual variable iterates to progress more quickly toward a dual optimal solution. We then show that the proposed SSAR method can be leveraged to improve the performance of the dual decomposition method for minimizing the average of local loss functions associated with multiple agents that share a common decision variable, a widely used problem formulation in many large-scale real-world applications. In particular, the SSAR method improves the convergence performance of the corresponding dual decomposition method while also reducing its communication cost. Numerical experiments on a least squares regression problem and a logistic regression problem using real datasets are conducted to evaluate the performance of the SSAR method.
ER -