arXiv preprint ·
Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Sample-Based Prophet Inequalities for Random Walks
Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
Optimal Investment and Consumption in Financial Markets with Integrated Variance Clocks
Reinforcement Learning in Operational Research: A Technical Review and Practical Roadmap
Reliability Theory for AI Control
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.