First-Order Methods for Convex Constrained Optimization under Error Bound Conditions with Unknown Growth Parameters
Preprint
Abstract
We propose first-order methods based on a level-set technique for convex constrained optimization that satisfies an error bound condition with unknown growth parameters. The proposed approach solves the original problem by solving a sequence of unconstrained subproblems defined with different level parameters. Different from the existing level-set methods where the subproblems are solved sequentially, our method applies a first-order method to solve each subproblem independently and simultaneously, which can be implemented with either a single or multiple processors. Once the objective value of one subproblem is reduced by a constant factor, a sequential restart is performed to update the level parameters and restart the first-order methods. When the problem is non-smooth, our method finds an $\epsilon$-optimal and $\epsilon$-feasible solution by computing at most $O(\frac{G^{2/d}}{\epsilon^{2-2/d}}\ln^3(\frac{1}{\epsilon}))$ subgradients where $G>0$ and $d\geq 1$ are the growth rate and the exponent, respectively, in the error bound condition. When the problem is smooth, the complexity is improved to $O(\frac{G^{1/d}}{\epsilon^{1-1/d}}\ln^3(\frac{1}{\epsilon}))$. Our methods do not require knowing $G$, $d$ and any problem dependent parameters.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Restarting the accelerated coordinate descent method with a rough strong convexity estimateComputational Optimization and Applications, 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
- 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
- From error bounds to the complexity of first-order descent methods for convex functionsMathematical Programming, 2016
- Gradient methods for minimizing composite functionsMathematical Programming, 2012
- Smooth minimization of non-smooth functionsMathematical Programming, 2004
- Error bounds for analytic systems and their applicationsMathematical Programming, 1994
- Error bounds and convergence analysis of feasible descent methods: a general approachAnnals of Operations Research, 1993