The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
提出一种通用技术，通过构造目标函数的近似对偶间隙来分析一阶方法，统一了连续时间方法和离散化误差分析，适用于凸最小化、光滑凸最小化、复合最小化、强凸最小化、变分不等式和凸凹鞍点优化等问题。
We present a general technique for the analysis of first-order methods. The technique relies on the construction of a duality gap for an appropriate approximation of the objective function, where the function approximation improves as the algorithm converges. We show that in continuous time the enforcement of an invariant, which corresponds to the approximate duality gap decreasing at a certain rate, exactly recovers a wide range of first-order continuous-time methods. We characterize the discretization errors incurred by different discretization methods, and show how iteration-complexity-optimal methods for various classes of problems cancel out the discretization error. The techniques are illustrated on various classes of problems---including convex minimization for Lipschitz-continuous objectives, smooth convex minimization, composite minimization, smooth and strongly convex minimization, solving variational inequalities with monotone operators, and convex-concave saddle-point optimization---and naturally extend to other settings.