Understanding the Optimization Algorithms via Fixed-point Iterations and Their Applications

Abstract

고정점 반복법은 응용수학, 과학, 공학, 기계 학습 전반에 걸쳐 널리 사용되는 방법이다. 특히 최적화 분야에서는, 대규모 최적화 문제를 해결하는 일계 최적화 알고리즘을 널리 아울러서 이해하고 분석하는 방법의 틀을 제시한다.

응용수학 전반에서 고정점 반복법이 널리 활용됨에도 불구하고, 비확장 비선형 연산자로 정의되는 일반적인 고정점 문제를 푸는 고정점 반복법의 최적의 수렴 속도는 알려지지 않았다. 이는 수렴 속도 및 그와 일치하는 복잡도 하한에 대해 많은 연구가 이루어진 일계 최적화 알고리즘 연구와 대조된다. 더불어, 일계 최적화 알고리즘은 높은 활용도에도 불구하고, 데이터가 잘못 주어지거나 실현 불가능한 최적화 문제가 등장했을 때 알고리즘이 이를 어떻게 감지할 수 있는지가 불명확하다. 내부점 방법과 심플렉스 방법 등, 고전적인 수치적 방법에서는 실현 불가능한 최적화 문제를 감지하기 위한 여러 기전이 광범위한 이론 및 실험적 연구를 통하여 잘 이해되고 있으나, Douglas-Rachford 연산자 분해법 또는 ADMM 등의 일계 최적화 알고리즘에서는 이러한 기전이 최근 들어서야 주목을 받기 시작했다. 구체적으로, 주어진 문제의 실현 불가능성을 감지하는 방법의 계산 복잡도는 적극적으로 연구되지 않은 상황이다.

이 논문에서는 고정점 반복법의 최적 계산 복잡도를 분석한다. 첫째로, 비확장 및 수축 연산자에 활용할 수 있는 Halpern 메커니즘 기반 가속 고정점 반복법을 제시한다. 이에 더해, H¨older 유형의 증가 조건을 만족하는 고정점 연산자에 활용 가능한 가속 방법으로서, 재시작을 기반으로 한 고정점 반복법을 추가로 제시한다. 둘째로, 고정점이 없는 경우에 대하여, 고정점 반복법을 적용하였을 때의 최악 경우 (worst-case) 계산 복잡도를 분석한다. 이는 실현 불가능한 최적화 문제에 일계 최적화 알고리즘을 적용한 경우에 대한 계산 복잡도와 밀접한 관련이 있다. 셋째로, 논문에서 제시하는 가속 고정점 반복법의 수렴 속도가 최적임을 보이기 위하여, 수렴 속도와 정확하게 일치하는 계산 복잡도 하한 결과를 제시한다. 마지막으로, 광범위한 실험을 통하여 제시된 가속 고정점 반복법의 효율성을 입증한다.

The fixed-point iteration is ubiquitous throughout applied mathematics, science, engineering, and machine learning. Especially in the field of optimization, fixed-point iterations provide a framework to understand the first-order optimization algorithms, which are the method of choice for solving large-scale optimization problems.

Despite the broad use of fixed-point iterations throughout applied mathematics, the optimal convergence rate of general fixed-point problems with nonexpansive nonlinear operators has not been established. This stands in sharp contrast with the literature on first-order optimization algorithms, where convergence rates and matching lower bounds are carefully studied. Furthermore, first-order optimization algorithms are far less equipped to robustly detect infeasible or misspecified problem instances, which may often arise from user misspecification or from applications. Unlike the classical solvers based on interior point methods and simplex methods whose behavior under pathologies is well understood through extensive theoretical and empirical research, the analysis of first-order algorithms such as Douglas-Rachford splitting (DRS) and ADMM on pathological problems has just started to gain attention. Specifically, the computational complexity of determining the infeasibility of a given problem instance has yet to be formally studied.

In this thesis, we characterize the optimal accelerated complexity of fixed-point iterations. First, we provide an accelerated method based on Halpern mechanism [Halpern, 1967] for nonexpansive and contractive operators. Also, the acceleration mechanism based on restarting is provided to cover the fixed-point operator satisfying the Hölder-type growth condition. Second, we analyze the worst-case iteration complexity of the accelerated fixed-point method for fixed-point operators that does not have solutions, or fixed points. This fixed-point iterations without fixed points are highly related to the computational complexity of first-order methods with infeasible optimization problems. Third, we provide the complexity lower bound result which matches our upper bounds, establishing the exact optimality of the suggested methods. Finally, we demonstrate the effectiveness of the proposed acceleration mechanism through extensive experiments.