# Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

arXiv: https://arxiv.org/abs/2609.24423 · HTML: https://mlsanity.com/paper/2609.24423/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 18 references that are in the map.
- First posted on arXiv 21 Sep 2026.

## Builds on (most cited first, 11 of 11)

- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method](https://mlsanity.com/paper/2010.01848/) (2020)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [Frank-Wolfe with a Nearest Extreme Point Oracle](https://mlsanity.com/paper/2102.02029/) (2021)
- [Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems](https://mlsanity.com/paper/1802.05581/) (2018)
- [Fast Stochastic Algorithms for Low-rank and Nonsmooth Matrix Problems](https://mlsanity.com/paper/1809.10477/) (2018)
- [Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle](https://mlsanity.com/paper/2210.13968/) (2022)
- [Projection-Free Non-Smooth Convex Programming](https://mlsanity.com/paper/2208.05127/) (2022)
- [Weak Proximal Newton Oracles for Composite Convex Optimization](https://mlsanity.com/paper/2503.01432/) (2025)
- [First-Order Sparse Convex Optimization: Better Rates with Sparse Updates](https://mlsanity.com/paper/2506.19075/) (2025)

## Abstract (arXiv)

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 textitweak 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.