# Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2020.

## Built on by (most cited first, 17 of 17)

- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Optimizing generalized Gini indices for fairness in rankings](https://mlsanity.com/paper/2204.06521/) (2022)
- [Being Properly Improper](https://mlsanity.com/paper/2106.09920/) (2021)
- [Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach](https://mlsanity.com/paper/2109.11135/) (2021)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator](https://mlsanity.com/paper/2206.09370/) (2022)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Primal Methods for Variational Inequality Problems with Functional Constraints](https://mlsanity.com/paper/2403.12859/) (2024)
- [Contextual bandits with concave rewards, and an application to fair ranking](https://mlsanity.com/paper/2210.09957/) (2022)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)
- [Provable Reduction in Communication Rounds for Non-Smooth Convex Federated Learning](https://mlsanity.com/paper/2503.21627/) (2025)
- [Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization](https://mlsanity.com/paper/2609.24423/) (2026)
- [Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization](https://mlsanity.com/paper/2610.00254/) (2026)

## Abstract (arXiv)

We consider the classical setting of optimizing a nonsmooth Lipschitz continuous convex function over a convex constraint set, when having access to a (stochastic) first-order oracle (FO) for the function and a projection oracle (PO) for the constraint set. It is well known that to achieve ε-suboptimality in high-dimensions, Theta(ε-2) FO calls are necessary. This is achieved by the projected subgradient method (PGD). However, PGD also entails O(ε-2) PO calls, which may be computationally costlier than FO calls (e.g. nuclear norm constraints). Improving this PO calls complexity of PGD is largely unexplored, despite the fundamental nature of this problem and extensive literature. We present first such improvement. This only requires a mild assumption that the objective function, when extended to a slightly larger neighborhood of the constraint set, still remains Lipschitz and accessible via FO. In particular, we introduce MOPES method, which carefully combines Moreau-Yosida smoothing and accelerated first-order schemes. This is guaranteed to find a feasible ε-suboptimal solution using only O(ε-1) PO calls and optimal O(ε-2) FO calls. Further, instead of a PO if we only have a linear minimization oracle (LMO, a la Frank-Wolfe) to access the constraint set, an extension of our method, MOLES, finds a feasible ε-suboptimal solution using O(ε-2) LMO calls and FO calls---both match known lower bounds, resolving a question left open since White (1993). Our experiments confirm that these methods achieve significant speedups over the state-of-the-art, for a problem with costly PO and LMO calls.