This thesis develops the average-case analysis of first-order methods on quadratic forms and derive optimal algorithms under the average-case analysis. In order to obtain the average-case optimal method, we adapt the three-term relation of orthogonal polynomial with respect to the expected spectrum of Hessian of objective. The original result considers only the distance from optimal point under the initial distance condition and we expand the choices of optimality measures and initial conditions for a unified analysis. In addition, we analyze the convergence rates for the exponential distribution. Numerical experiments are detailed on diverse optimality measures.
이 논문에서는 2차식에 대한 1차 방법의 평균 사례 분석을 다루고 평균 사례 분석에서 최적의 알고리즘을 도출한다. 최적 방법을 얻기 위해 우리는 2차식의 헤세 행렬의 예상 스펙트럼에 대해 직교 다항식의 3항 관계를 적용한다. 기존의 결과는 초기 거리 조건에서 최적점과의 거리만을 고려하지만 우리는 통합적인 분석을 위해 최적 측정 및 초기 조건의 선택을 확장한다. 또한, 지수 분포에 대한 수렴률을 분석한다. 다양한 최적 측정에 대한 수치 실험이 설명되어 있다.
