Weak proximal oracles trade speed for complexity in convex optimization
Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization
Machine Learning
Summary
The paper studies a special way to solve certain math problems that involve finding the best solution with some smooth or rough features. It focuses on methods that use a 'weak proximal oracle,' which is easier to run but less precise than the usual method. The authors found that while these easier oracles can speed up each step, they cannot fully match the fastest possible overall solving methods. They also provide a new approach that nearly matches traditional methods for nonsmooth problems using these weaker oracles.
What this means in practice
- •For optimization algorithm developers: Design efficient algorithms balancing step cost and iteration count for sparse structured convex problems.
- •For machine learning engineers: Understand limitations of accelerating weak proximal oracle methods when optimizing large-scale composite models.
A theory result. No direct application yet.
Authors
Dan Garber
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.