Efficiency of Stochastic Coordinate Proximal Gradient Methods on Nonseparable Composite Optimization

Ion Necoara () and Flavia Chorobura ()
Additional contact information
Ion Necoara: Automatic Control and Systems Engineering Department, University Politehnica Bucharest, 060042 Bucharest, Romania; and Gheorghe Mihoc-Caius Iacob Institute of Mathematical Statistics and Applied Mathematics of the Romanian Academy, 050711 Bucharest, Romania
Flavia Chorobura: Automatic Control and Systems Engineering Department, University Politehnica Bucharest, 060042 Bucharest, Romania

Mathematics of Operations Research, 2025, vol. 50, issue 2, 993-1018

Abstract: This paper deals with composite optimization problems having the objective function formed as the sum of two terms; one has a Lipschitz continuous gradient along random subspaces and may be nonconvex, and the second term is simple and differentiable but possibly nonconvex and nonseparable. Under these settings, we design a stochastic coordinate proximal gradient method that takes into account the nonseparable composite form of the objective function. This algorithm achieves scalability by constructing at each iteration a local approximation model of the whole nonseparable objective function along a random subspace with user-determined dimension. We outline efficient techniques for selecting the random subspace, yielding an implementation that has low cost per iteration, also achieving fast convergence rates. We present a probabilistic worst case complexity analysis for our stochastic coordinate proximal gradient method in convex and nonconvex settings; in particular, we prove high-probability bounds on the number of iterations before a given optimality is achieved. Extensive numerical results also confirm the efficiency of our algorithm.

Keywords: Primary: 90C25; 90C06; 65K05; composite minimization; nonseparable objective; coordinate descent; convergence rates (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2023.0044 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:2:p:993-1018

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().