Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization
Abstract
We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.
Related
- The Convergence Rate of Accelerated Proximal Gradient Methods with General Inertia Term for Convex Composite Multiobjective Optimization
- Relative-Error Composite Federated Optimization with One Server-Side Proximal Step per Round
- Composite and Stochastic Smoothed Decentralized Bregman Proximal-Gradient Methods
- A Parallel Adaptive Proximal ADMM for Linearly Constrained Separable Composite Optimization Problems
- Proximal-Linearized NEP Method for Composite Optimization with Set-Inclusion and Manifold Constraints
BibTeX
@misc{garber2026complexities,
title = {{Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization}},
author = {Dan Garber},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.24423},
eprint = {2609.24423},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24423},
}
RIS
TY - UNPB
TI - Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization
AU - Dan Garber
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.24423
UR - https://arxiv.org/abs/2609.24423
AB - We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.
ER -