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 $dgeq 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.
Download