Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods

기술 요약: 약한 볼록 함수(Weakly Convex Functions)에 대한 오차 경계, PL 조건, 이차 성장 및 근접 점 방법(Proximal Point Methods)의 선형 수렴

문제 정의
많은 실용적인 최적화 문제, 특히 머신러닝 및 신호 처리 분야의 문제들은 강한 볼록성(strong convexity)이 결여되어 있다. 1차 알고리즘이 강한 볼록성 하에서 선형 수렴을 달eric 수 있다는 것은 잘 알려져 있으나, 최근 연구들은 매끄러운(smooth) 볼록 함수에 대해 더 약한 정규성 조건(예: Polyak-Lojasiewicz 부등식, 오차 경계, 이차 성장) 하에서도 선형 수렴이 보장될 수 있음을 보여주었다. 그러나 이러한 조건들 사이의 관계는 비매끄러운(nonsmooth) 비볼록(nonconvex) 함수의 설정에서는 명확히 이해되지 않았다. 특히, 약한 볼록 함수(함수 $f + \frac{\rho}{2}\|\cdot\|^2$가 어떤 $\rho \geq 0$에 대해 볼록한 함수)는 현대적 모델(예: 비매끄러운 딥 네트워크, 볼록 함수와 매끄러운 함수의 합성)을 포괄하지만, 이러한 정규성 조건들을 연결하는 통합된 프레임워크가 부족했다. 또한, 근접 점 방법(Proximal Point Method, PPM)의 선형 수렴에 대한 기존의 증명들은 종종 제한적인 가정(예: 유일한 최소화점, 역 부도함수의 국소 리프시츠 연속성)이나 복잡한 논증에 의존해 왔다.

방법론
본 논문은 비매끄러운 해석학(nonsunsmooth analysis)의 도구들, 구체적으로 기울기(slope) 개념, 에켈란드의 변분 원리(Ekeland's variational principle), 그리고 **거리 추정 보조정리(distance estimation lemmas)**를 사용하여 정규성 조건들 사이의 관계를 분석한다. 저자들은 다음과 같은 다섯 가지 핵심 조건을 하위 레벨 집합 $[f \leq f^\star + \nu]$에 대해 정의한다:

1. 강한 볼록성 (Strong Convexity, SC)
2. 제한된 섹트 부등식 (Restricted Secant Inequality, RSI)
3. 부도함수 오차 경계 (Subdifferential Error Bound, EB)
4. Polyak-Lojasiewicz (PL) 부등식
5. 이차 성장 (Quadratic Growth, QG)

저자들은 매끄러운 설정과 비매끄러운 설정 사이의 간극을 메우기 위해 기울기 $|\nabla f|(x) = \text{dist}(0, \hat{\partial}f(x))$ (여기서 $\hat{\partial}f$는 프레셰 부도함수)를 활용한다. 이들은 이러한 조건들 사이의 논리적 함의와 동치를 확립하며, 특히 이차 성장 상수 $\mu_q$가 약한 볼록성 파라미터 $\rho$보다 큰 경우에 집중한다.

이러한 동치 관계를 바탕으로, 본 논문은 다음의 **근접 점 방법(PPM)**을 분석한다:
$$x_{k+1} = \text{prox}_{c_k f}(x_k) = \arg\min_x \left( f(x) + \frac{1}{2c_k}\|x - x_k\|^2 \right)$$
저자들은 볼록 및 약한 볼록 설정 모두에서 선형 수렴을 위한 모듈형 증명을 제공한다. 또한, 하위 문제를 근사적으로 해결하는 **불완전 근접 점 방법(Inexact PPM, iPPM)**으로 분석을 확장하며, 이때 정지 기준(stopping criteria)과 가용성(feasibility, 반복값이 $f$의 도메인 내에 머무름을 보장함)에 관한 미묘한 차이를 다룬다.

주요 기여

1. 약한 볼록 함수를 위한 정규성 조건의 통합:
   본 논문은 $\rho$-약한 볼록 함수에 대한 정규성 조건의 계층 구조와 동치를 확립한다.

   • 일반적 함의 체인: $(SC) \implies (RSI) \implies (EB) \iff (PL) \implies (QG)$.
   • $\mu_q > \rho$ 하에서의 동치성: 만약 $\rho$-약한 볼록 함수가 상수 $\mu_q > \rho$를 갖는 이차 성장을 만족한다면, 네 가지 조건 $(RSI), (EB), (PL), (QG)$는 모두 동치이다.
   • 저자들은 이러한 조건들 사이의 명시적인 계수 변환을 도출하여(논문의 표 1에 요약됨), 실무자들이 한 조건의 상수를 다른 조건으로 변환할 수 있도록 한다.

2. PPM의 단순화된 선형 수렴 증명:
   본 논문은 볼록 및 약한 볼록 함수에 대한 PPM의 선형 수렴을 위한 단순하고 모듈화된 증명을 제시한다.

   • 볼록 케이스: 동치인 정규성 조건(PL, EB, RSI, QG) 중 어느 하나를 만족할 때, PPM은 함수 값과 해 집합까지의 거리에 대해 선형 수렴을 달성한다. 이 증명은 유일한 최소화점이나 역 부도함수의 국소 리프시츠 연속성 요구 사항을 제거함으로써 기존의 가정을 완화한다.
   • 약한 볼록 케이스: 초기화가 QG를 만족하는 $\mu_q > \rho$인 하위 레벨 집합 내에 있고 단계 크기가 $1/c_k > \rho$를 만족하는 경우, 결과가 $\rho$-약한 볼록 함수로 확장된다.

3. 불완전 근접 점 방법(iPPM) 분석:
   저자들은 iPPM에서 불완전성과 가용성의 미묘한 차이를 명확히 한다. 이들은 함수가 해 집합의 근방에서 QG를 만족하는 경우, 표준 정지 기준(Rockafellar의 기준 A 및 B) 하에서 iPPM의 선형 수렴을 확립한다. 이 증명은 기존 문헌의 핵심 부등식과 모듈형 정규성 조건 프레임워크를 결합한다.

결과

• 이론적 결과: 정리 3.1은 $\mu_q > \rho$일 때 약한 볼록 함수에 대한 정규성 조건의 동치가 성립함을 확인한다. 이는 매끄럽거나 볼록한 함수로 제한되었던 이전의 결과들을 일반화한다.
• 알고리즘적 결과: 정리 4.2와 4.3은 PPM이 정규성 상수(예: $\omega_k = \frac{1}{1+c_k\mu_p}$)에 의존하는 비율로 선형 수렴함을 보여준다. 정리 5.3은 이를 iPPM으로 확장하여, 불완전성이 통제되는 한(오차의 합이 유한함) 점근적으로 선형 수렴 속도가 유지됨을 보여준다.
• 수치적 결과: Linear SVM, Lasso, Elastic-Net 문제에 대한 실험은 PPM의 이론적 선형 수렴을 확인한다. 실험에는 YALMIP 모델링 패키지와 MOSEK 솔버가 사용되었으며, 비용 값 격차와 해 집합까지의 거리 모두에서 빠른 수렴을 보여주었다.

의의 및 주장
본 논문은 매끄러운/볼록한 설정으로부터 정규성 조건에 대한 이해를 더 넓은 범위인 비매끄러운 약한 볼록 함수로 일반화한다고 주장한다. 이러한 조건들 사이의 연결을 명확히 함으로써, 저자들은 반복 알고리즘의 분석을 단순화하는 통합된 프레임워크를 제공한다.

구체적으로, 본 논문은 다음과 같이 단언한다:

• $\mu_q > \rho$ 하에서의 조건들의 동치성(RSI, EB, PL, QG)은 유연한 분석을 가능하게 한다. 즉, 하나의 조건을 확립함으로써 다른 조건들을 통해 수렴 결과를 도출할 수 있다.
• PPM 선형 수렴에 대한 증명은 유일한 최소화점과 같은 제한적인 가정을 피함으로써 기존 문헌보다 더 단순하고 투명하다.
• 본 결과는 약한 볼록성이 널리 퍼져 있는 대규모 코닉 최적화(conic optimization) 및 머신러닝 응용 분야를 포함하여, 비매끄러운 최적화를 위한 알고리즘 개발을 용이하게 한다.

저자들은 이러한 조건들의 동치가 매끄럽거나 볼록한 함수에 대해서는 알려져 있었으나, 이를 약한 볼록 설정으로 확장하고 (불완전 버전까지 포함하여) PPM에 대한 깔끔한 증명을 제공하는 것이 주요한 독창성이라고 언급한다. 본 연구는 상세한 증명, 계수 변환, 그리고 확장된 iPPM 분석이 추가된 컨퍼런스 논문의 확장판으로 제시된다.