SOURCE-LINKED INTELLIGENCE

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

arXiv · AI, language, vision and robotics · article · Sep 21, 2026 · UTC

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 m

Read original source ↗ Open in workspace

recordType

paper

region

Global