mlsanityData to 14 Oct 2026

Nonsmooth Projection-Free Optimization with Functional Constraints

arXiv 2311.11180 ↗First posted 18 Nov 2023math.OC cs.LG cs.SYcited by 0

Not on the map. Why?

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.

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

41 of 111 references.

References · 41

  1. 2021Convex optimizationcited by 2,515
  2. 2017A Survey on Multi-Task Learningcited by 840
  3. 2014Convex Optimization: Algorithms and Complexitycited by 575
  4. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  5. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  6. 2017Online Convex Optimization with Stochastic Constraintscited by 95
  7. 2017Online Convex Optimization with Time-Varying Constraintscited by 56
  8. 2020Faster Projection-free Online Learningcited by 40
  9. 2019Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimizationcited by 38
  10. 2021Efficient Projection-Free Online Convex Optimization with Membership Oraclecited by 30
  11. 2013The Complexity of Large-scale Convex Programming under a Linear Optimization Oraclecited by 29
  12. 2022New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guaranteescited by 26
29 more
  1. 2017Efficient Convex Optimization with Membership Oraclescited by 23
  2. 2017Iteration complexity of inexact augmented Lagrangian methods for constrained convex programmingcited by 21
  3. 2021Complexity of Linear Minimization and Projection on Some Setscited by 20
  4. 2021Escaping from Zero Gradient: Revisiting Action-Constrained Reinforcement Learning via Frank-Wolfe Policy Optimizationcited by 18
  5. 2020Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Methodcited by 17
  6. 2018A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programmingcited by 14
  7. 2022Projection-free Adaptive Regret with Membership Oraclescited by 13
  8. 2019Revisiting the Approximate Carath'eodory Problem via the Frank-Wolfe Algorithmcited by 11
  9. 2023Projection-free Online Exp-concave Optimizationcited by 10
  10. 2016Faster Projection-free Convex Optimization over the Spectrahedroncited by 9
  11. 2020The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimizationcited by 9
  12. 2019On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problemscited by 8
  13. 2014Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methodscited by 7
  14. 2013Solving Variational Inequalities with Monotone Operators on Domains Given by Linear Minimization Oraclescited by 5
  15. 2015A Universal Primal-Dual Convex Optimization Frameworkcited by 5
  16. 2017A Deterministic Nonsmooth Frank Wolfe Algorithm with Coreset Guaranteescited by 5
  17. 2020Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraintscited by 4
  18. 2020Efficient Projection Algorithms onto the Weighted l1 Ballcited by 4
  19. 2021Radial Duality Part II: Applications and Algorithmscited by 4
  20. 2023Projection-Free Online Convex Optimization via Efficient Newton Iterationscited by 4
  21. 2014Hybrid Conditional Gradient - Smoothing Algorithms with Applications to Sparse and Low Rank Regularizationcited by 3
  22. 2017A Primal-Dual Parallel Method with O(1/ε) Convergence for Constrained Composite Convex Programscited by 3
  23. 2021Radial Duality Part I: Foundationscited by 3
  24. 2018Primal-Dual Frank-Wolfe for Constrained Stochastic Programs with Convex and Non-convex Objectivescited by 2
  25. 2018Solving Non-smooth Constrained Programs with Lower Complexity than O(1/varepsilon): A Primal-Dual Homotopy Smoothing Approachcited by 2
  26. 2022Projection-Free Functional Constrained Optimization for Risk Aversion and Sparsity Controlcited by 2
  27. 2023Projection-Free Online Convex Optimization with Stochastic Constraintscited by 2
  28. 2016A Primal-Dual Type Algorithm with the O(1/t) Convergence Rate for Large Scale Constrained Convex Programscited by 1
  29. 2023An Inexact Frank-Wolfe Algorithm for Composite Convex Optimization Involving a Self-Concordant Functioncited by 1

Built on by

Not cited yet.