On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback--Leibler regression

기술 요약: 쿨백-라이블러(Kullback–Leibler) 회귀에 대한 응용을 포함한 브레그만 근접 경사법의 선형 수렴성에 관하여

문제 정의
본 논문은 $J(x) = F(x) + R(x)$ 형태의 볼록 합성 범함수(convex composite functionals)의 최소화 문제를 다룬다. 여기서 $F$는 미분 가능한 볼록 함수이고 $R$은 미분 불가능한 볼록 정규화 항이다. 근접 경사법(Proximal Gradient Methods, PGM)은 이러한 문제에 표준적으로 사용되지만, $F$가 강볼록성(strong convexity)을 만족하지 않는 한 일반적으로 아선형(sublinear) 수렴 속도($O(1/k)$)를 보인다. 그러나 포아송 회귀(Poisson regression)나 쿨백-라이블러(KL) 회귀와 같은 역문제(inverse problems)를 포함한 많은 실제 응용 사례에서는 $F$가 강볼록하지 않은 매끄러운 항(smooth terms)을 포함한다 (예: 측정 행렬 $A$가 랭크 결핍인 경우).

브레그만 근접 경사법(Bregman Proximal Gradient Methods, BPGM)은 미러 맵(mirror map) $\phi$를 통해 $J$의 기하학적 구조에 적응하도록 도입되었으나, 기존의 BPGM 선형 수렴 보장은 일반적으로 $F$가 $\phi$에 대해 전역적으로 상대적 강볼록성(globally relatively strongly convex)을 가져야 한다는 조건을 요구한다. 이 조건은 실제 KL 회귀 문제에 적용하기에는 너무 제한적이며, 왜 이러한 설정에서 선형 수렴이 발생하는지에 대한 이론적 이해에 공백을 남긴다.

방법론 및 이론적 프레임워크
저자들은 전역적 상대적 강볼록성보다 더 완화된 조건 하에서 BPGM의 선형 수렴을 확립하기 위한 새로운 이론적 프레임워크를 제안한다.

1. 제한적 상대적 강볼록성 (Restricted Relative Strong Convexity, RRSC): 본 논문은 '제한적 상대적 강볼록성'이라 명명된 새로운 성질을 도입한다. 이는 유클리드 공간에서의 제한적 강볼록성(Restricted Strong Convexity, RSC) 개념을 브레그만 설정으로 확장한 것이다. 구체적으로, $F$가 $\phi$에 대해 RRSC를 만족한다는 것은 다음을 만족하는 $\mu > 0$가 존재함을 의미한다:
   $$\langle \nabla F(x) - \nabla F(\bar{x}_{\ell_2}), x - \bar{x}_{\ell_2} \rangle \geq \mu \langle \nabla \phi(x) - \nabla \phi(\bar{x}_{\ell_2}), x - \bar{x}_{\ell_2} \rangle$$
   여기서 $\bar{x}_{\ell_2}$는 $x$의 해 집합 $S$에 대한 유클리드 투영이다. 결정적으로, 이 조건은 KL 다이バージ언스(divergence)의 기하학적 구조를 처리하기 위해 기술적으로 필요한 유클리드 투영에 의존한다.

2. 제한적 대칭 계수 (Restricted Symmetry Coefficient): $\phi$가 이차 형식(quadratic)이 아닌 경우 브레그만 다이バージ언스가 갖는 비대칭성을 처리하기 위해, 저자들은 해 집합 $S$에 국한된 다이バージ언스의 대칭성을 측정하는 제한적 대칭 계수 $\alpha_S(\phi)$를 정의한다. 저자들은 수렴을 보장하기 위해 $\alpha_S(\phi) > 0$을 요구한다.

3. 수렴 분석: RRSC, 상대적 매끄러움(relative smoothness, Lipschitz 유사 조건), 그리고 양의 제한적 대칭 계수 가설 하에서, 저자들은 반복값(iterates)과 해 집합 사이의 브레그만 다이バージ언스 및 목적 함수 값이 선형적으로 수렴함을 증명한다. 또한 백트래킹(backtracking)을 통한 자동 단계 크기 선택 규칙을 포함하도록 이 결과를 확장한다.

쿨백-라이블러 회귀에 대한 응용
이 이론적 프레임워크는 $F(x) = KL(y, Ax+b)$인 (정규화된) KL 회귀 문제에 적용된다. 저자들은 거리 생성 함수(distance-generating function) $\phi$의 세 가지 특정 선택지에 대해 수렴 거동을 분석한다:

• 제곱 $\ell_2$-노름: 표준적인 유클리드 케이스.
• 버그 엔트로피 (Burg's Entropy): KL 문제에 널리 쓰이는 선택지 ($\phi_B(x) = -\sum \log x_n$).
• 스무딩된 버그 엔트로피 (Smoothed Burg's Entropy): 새로운 제안 ($\phi_{sB}(x) = -\sum \log(x_n + \xi)$).

주요 발견 및 결과

• 버그 엔트로피의 한계: 분석 결과, 표준 버그 엔트로피($\phi_B$)를 사용하는 것은 모든 KL 회귀 시나리오에서 선형 수렴을 보장하지 못한다. 구체적으로, 해 집합이 비음수 직교 영역의 경계($\partial C$)에 위치하거나 반복값이 특정 방식으로 $A$의 커널(kernel)에 접근하는 경우, RRSC 조건이 실패하며 아선형 수렴만이 관찰된다.
• 스무딩된 버그 엔트로의 장점: 저자들은 스무딩된 버전($\phi_{sB}$)을 사용하는 것이 경계에 위치한 해를 포함한 더 넓은 범위의 시나리오에서 RRSC 조건을 만족시키고 양의 대칭 계수를 보장하는 데 필요한 기하학적 구조를 유도함을 입증한다.
• 수치적 검증: 합성 포아송 역문제에 대한 실험은 이론적 예측을 확인해 준다.
  • $\phi_{sB}$의 경우, 해가 유일한지 혹은 유일하지 않은지, 또는 제약 집합의 내부 혹은 경계에 있는지에 관계없이 일관되게 선형 수렴이 관찰된다.
  • $\phi_B$의 경우, 해가 제약 집합의 내부(interior)에 엄격히 존재할 때만 선형 수렴이 관찰되며, 그렇지 않으면 수렴 속도가 아선형으로 저하된다.
  • $\phi_{sB}$의 성능은 스무딩 파라미터 $\xi$에 민감하며, 강볼록성 상수와 상대적 매끄러움 상수 사이의 최적의 트레이드오프(trade-off)가 존재한다.

의의 및 주장
본 논문은 제한적 강볼록성을 브레그만 설정으로 일반화한 최초의 사례라고 주장하며, 이를 통해 전역적 상대적 강볼록성을 요구하지 않고도 BPGM의 선형 수렴 속도를 확립한다. 주요 기여는 선형 수렴을 위해 필요한 특정 기하학적 조건(RRSC 및 제한적 대칭성)을 식별한 것이다.

저자들은 왜 대중적인 버그 엔트로피가 특정 실무적 환경(예: 경계 해)에서 선형 수렴을 달성하는 데 실패할 수 있는지를 설명하고, 선형 수렴을 보장하는 견고한 대안으로서 스무딩된 버그 엔트로피를 제안한다. 결과는 이론적 및 수치적으로 검증되었으며, 도출된 조건과 관찰된 경험적 행동 사이의 강력한 일치를 보여준다. 이 연구는 비볼록(non-convex) 문제를 해결하거나 비볼록 KL 회귀로 확장하는 것을 목표로 하지 않으며, KL 다이バージ언스 맥락에서의 볼록 합성 최적화에 대한 이해를 정교화하는 데 중점을 둔다.