Journal article
An Adaptive Parameter-free and Projection-free Restarting Level Set Method for Constrained Convex Optimization Under the Error Bound Condition
Journal of machine learning research, Vol.26, 200
01/01/2025
Abstract
Recent efforts to accelerate first-order methods have focused on convex optimization problems that satisfy a geometric property known as error-bound condition, which covers a broad class of problems, including piece-wise linear programs and strongly convex programs. Parameter-free first-order methods that employ projection-free updates have the potential to broaden the benefit of acceleration. Such a method has been developed for unconstrained convex optimization but is lacking for general constrained convex optimization. We propose a parameter-free level-set method for the latter constrained case based on projection-free subgradient method that exhibits accelerated convergence for problems that satisfy an error-bound condition. Our method maintains a separate copy of the level-set sub-problem for each level parameter value and restarts the computation of these copies based on objective function progress. Applying such a restarting scheme in a level-set context is novel and results in an algorithm that dynamically adapts the precision of each copy. This property is key to extending prior restarting methods based on static precision that have been proposed for unconstrained convex optimization to handle constraints. We report promising numerical performance relative to benchmark methods.
Details
- Title: Subtitle
- An Adaptive Parameter-free and Projection-free Restarting Level Set Method for Constrained Convex Optimization Under the Error Bound Condition
- Creators
- Qihang Lin - Univ Iowa, Tippie Coll Business, Iowa City, IA 52242 USANegar Soheili - University of Illinois Urbana-ChampaignRunchao Ma - University of IowaSelvaprabu Nadarajah - University of Illinois Urbana-Champaign
- Resource Type
- Journal article
- Publication Details
- Journal of machine learning research, Vol.26, 200
- ISSN
- 1532-4435
- Publisher
- Microtome Publ
- Number of pages
- 45
- Language
- English
- Date published
- 01/01/2025
- Academic Unit
- Business Analytics
- Record Identifier
- 9985129576602771
Metrics
1 Record Views