Title:Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization

Abstract:Consider applying first-order methods to solve the smooth convex constrained optimization problem of the form $\min_{x \in X} F(x).$ For a simple closed convex set $X$ which is easy to project onto, Nesterov proposed the Accelerated Gradient Descent (AGD) method to solve the constrained problem as efficiently as an unconstrained problem in terms of the number of gradient computations of $F$ (i.e., oracle complexity). For a more complicated $\mathcal{X}$ described by function constraints, i.e., $\mathcal{X} = \{x \in X: g(x) \leq 0\}$, where the projection onto $\mathcal{X}$ is not possible, it is an open question whether the function constrained problem can be solved as efficiently as an unconstrained problem in terms of the number of gradient computations for $F$ and $g$. In this paper, we provide an affirmative answer to the question by proposing a single-loop Accelerated Constrained Gradient Descent (ACGD) method. The ACGD method modifies the AGD method by changing the descent step to a constrained descent step, which adds only a few linear constraints to the prox mapping. It enjoys almost the same oracle complexity as the optimal one for minimizing the optimal Lagrangian function, i.e., the Lagrangian multiplier $\lambda$ being fixed to the optimal multiplier $\lambda^*$. These upper oracle complexity bounds are shown to be unimprovable under a certain optimality regime with new lower oracle complexity bounds. To enhance its efficiency for large-scale problems with many function constraints, we introduce an ACGD with Sliding (ACGD-S) method which replaces the possibly computationally demanding constrained descent step with a sequence of basic matrix-vector multiplications. The ACGD-S method shares the same oracle complexity as the ACGD method, and its computation complexity, measured by the number of matrix-vector multiplications, is also unimprovable.