The proximal point method (PPM) is a fundamental method in optimization that is often used as a building block for designing optimization algorithms. In this work, we use the PPM method to provide conceptually simple derivations along with convergence analyses of different versions of Nesterov's accelerated gradient method (AGM). The key observation is that AGM is a simple approximation of PPM, which results in an elementary derivation of the update equations and stepsizes of AGM. This view also leads to a transparent and conceptually simple analysis of AGM's convergence by using the analysis of PPM. The derivations also naturally extend to the strongly convex case. Ultimately, the results presented in this paper are of both didactic and conceptual value; they unify and explain existing variants of AGM while motivating other accelerated methods for practically relevant settings.
翻译:准点法(PPM)是优化的基本方法,通常用作设计优化算法的构件。在这项工作中,我们使用PPM法提供概念上简单的推算,同时对Nesterov加速梯度法的不同版本进行趋同分析。关键的意见是,AGM是PPM的简单近似值,它导致对AGM的更新方程和阶梯进行初步推导。这个观点还导致利用PPM分析对AGM的趋同进行透明和概念上简单的分析。其推算自然也延伸至强烈的Convex案。最后,本文提出的结果既具有理论价值,又具有概念价值;它们统一和解释AGM的现有变量,同时为实际相关的环境鼓励其他加速方法。