A Parameter-free and Projection-free Restarting Level Set Method for Adaptive Constrained Convex Optimization Under the Error Bound Condition
Preprint
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 decent 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.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Stochastic algorithms with geometric step decay converge linearly on sharp functionsMathematical Programming, 2023
- A Simple Nearly Optimal Restart Scheme For Speeding Up First-Order MethodsFoundations of Computational Mathematics, 2021
- Iteration complexity of inexact augmented Lagrangian methods for constrained convex programmingMathematical Programming, 2019
- New analysis of linear convergence of gradient-type methods via unifying error bound conditionsMathematical Programming, 2019
- Level-set methods for convex optimizationMathematical Programming, 2018
- Mirror Descent and Convex Optimization Problems with Non-smooth Inequality Constraints2018
- Linear convergence of first order methods for non-strongly convex optimizationMathematical Programming, 2018
- New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measureMathematical Programming, 2017
- Gradient methods for minimizing composite functionsMathematical Programming, 2012
- Smooth minimization of non-smooth functionsMathematical Programming, 2004