# Nonsmooth Projection-Free Optimization with Functional Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 41 of its 111 references that are in the map.
- First posted on arXiv 18 Nov 2023.

## Builds on (most cited first, 30 of 41)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Efficient Convex Optimization with Membership Oracles](https://mlsanity.com/paper/1706.07357/) (2017)
- [Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming](https://mlsanity.com/paper/1711.05812/) (2017)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Escaping from Zero Gradient: Revisiting Action-Constrained Reinforcement Learning via Frank-Wolfe Policy Optimization](https://mlsanity.com/paper/2102.11055/) (2021)
- [Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method](https://mlsanity.com/paper/2010.01848/) (2020)
- [A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming](https://mlsanity.com/paper/1804.08544/) (2018)
- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [Revisiting the Approximate Carath'eodory Problem via the Frank-Wolfe Algorithm](https://mlsanity.com/paper/1911.04415/) (2019)
- [Projection-free Online Exp-concave Optimization](https://mlsanity.com/paper/2302.04859/) (2023)
- [Faster Projection-free Convex Optimization over the Spectrahedron](https://mlsanity.com/paper/1605.06203/) (2016)
- [The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization](https://mlsanity.com/paper/2006.04340/) (2020)
- [On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems](https://mlsanity.com/paper/1902.01644/) (2019)
- [Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods](https://mlsanity.com/paper/1403.7588/) (2014)
- [Solving Variational Inequalities with Monotone Operators on Domains Given by Linear Minimization Oracles](https://mlsanity.com/paper/1312.1073/) (2013)
- [A Universal Primal-Dual Convex Optimization Framework](https://mlsanity.com/paper/1502.03123/) (2015)
- [A Deterministic Nonsmooth Frank Wolfe Algorithm with Coreset Guarantees](https://mlsanity.com/paper/1708.06714/) (2017)
- [Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints](https://mlsanity.com/paper/2007.00153/) (2020)
- [Efficient Projection Algorithms onto the Weighted l1 Ball](https://mlsanity.com/paper/2009.02980/) (2020)

## Abstract (arXiv)

This paper presents a subgradient-based algorithm for constrained nonsmooth convex optimization that does not require projections onto the feasible set. While the well-established Frank-Wolfe algorithm and its variants already avoid projections, they are primarily designed for smooth objective functions. In contrast, our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints. It achieves an ε-suboptimal solution in O(ε-2) iterations, with each iteration requiring only a single (potentially inexact) Linear Minimization Oracle (LMO) call and a (possibly inexact) subgradient computation. This performance is consistent with existing lower bounds. Similar performance is observed when deterministic subgradients are replaced with stochastic subgradients. In the special case where there are no functional inequality constraints, our algorithm competes favorably with a recent nonsmooth projection-free method designed for constraint-free problems. Our approach utilizes a simple separation scheme in conjunction with a new Lagrange multiplier update rule.