Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

This paper investigates the oracle complexity of first-order optimization methods that rely on a Weak Proximal Oracle (WPO) rather than an exact proximal operator. While WPOs are computationally cheaper to implement—especially in high-dimensional problems with sparse or low-rank structures—it was previously unclear whether these methods could achieve accelerated convergence rates (like those of Nesterov’s accelerated gradient method) or if they are fundamentally limited by their relaxed optimality conditions.

The author analyzes the oracle complexity of WPO-based methods under the quadratic growth condition. The study develops new deterministic and randomized lower bounds by constructing hard instances where the feasible set is accessed through a k-fold sparse projection oracle. These lower bounds demonstrate that the convergence rates for WPO-based methods cannot be improved beyond certain limits. Additionally, the paper provides a new upper-bound analysis for the nonsmooth composite convex optimization case, showing that WPO-based methods can achieve performance nearly matching the standard proximal subgradient method.

In many large-scale machine learning and optimization tasks, computing an exact proximal operator (such as a full singular value decomposition for matrix problems) is prohibitively expensive. WPOs offer a practical alternative that significantly reduces the runtime of individual iterations. This paper clarifies the trade-off: while WPOs provide substantial computational savings per iteration, they come with an inherent loss in oracle complexity, meaning they cannot match the accelerated convergence rates of exact proximal methods. This result helps researchers understand the theoretical limits of projection-free or proximal-relaxed algorithms.