论文标题
O（1）功能约束问题的一阶方法几乎具有与无约束问题的收敛率相同
First-order methods for problems with O(1) functional constraints can have almost the same convergence rate as for unconstrained problems
论文作者
论文摘要
最近已经应用和分析了一阶方法（FOM），以解决具有复杂功能约束的问题。现有的作品表明，功能性约束问题的FOM比无约束问题的FOM具有低阶收敛率。特别是，对于平滑的强键问题的FOM可以具有线性收敛，而如果禁止投影到约束集合集合，则只能对约束问题收敛。在本文中，我们指出，较慢的收敛是由大量功能约束引起的，但不是约束本身。当只有$ m = o（1）$功能约束时，我们表明，即使没有对可行集合的投影，FOM的收敛率几乎可以与解决不受约束的问题相同。此外，如果只有$ m = o（\ varepsilon^{ - \ frac {1} {1} {2} {2}}}}）$功能约束，则给定$ \ varepsilon> 0 $，我们表明可以获得比下界更好的复杂性结果。我们的结果令人惊讶，但与现有的较低复杂性约束并不矛盾，因为我们专注于特定的问题子类。对四二次二次计划的实验结果证明了我们的理论。
First-order methods (FOMs) have recently been applied and analyzed for solving problems with complicated functional constraints. Existing works show that FOMs for functional constrained problems have lower-order convergence rates than those for unconstrained problems. In particular, an FOM for a smooth strongly-convex problem can have linear convergence, while it can only converge sublinearly for a constrained problem if the projection onto the constraint set is prohibited. In this paper, we point out that the slower convergence is caused by the large number of functional constraints but not the constraints themselves. When there are only $m=O(1)$ functional constraints, we show that an FOM can have almost the same convergence rate as that for solving an unconstrained problem, even without the projection onto the feasible set. In addition, given an $\varepsilon>0$, we show that a complexity result that is better than a lower bound can be obtained, if there are only $m=o(\varepsilon^{-\frac{1}{2}})$ functional constraints. Our result is surprising but does not contradict to the existing lower complexity bound, because we focus on a specific subclass of problems. Experimental results on quadratically-constrained quadratic programs demonstrate our theory.
