Nonsmooth Projection-Free Optimization with Functional Constraints
Kamiar Asgari Michael J. Neely
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 $\epsilon$-suboptimal
solution in $\mathcal{O}(\epsilon^{-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.