An Inexact Modified Quasi-Newton Method for Nonsmooth Regularized Optimization

기술 요약: 비매끄러운 정규화 최적화를 위한 부정확한 수정된 준 뉴턴 방법(An Inexact Modified Quasi-Newton Method for Nonsmooth Regularized Optimization)

문제 정의
본 논문은 다음과 같은 비매끄러운 정규화 최적화 문제를 다룬다:
$$\min_{x \in \mathbb{R}^n} f(x) + h(x)$$
여기서 $f: \mathbb{R}^n \to \mathbb{R}$는 연속 미분 가능하며(잠재적으로 비볼록할 수 있음), $h: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$는 적절하고(proper), 하반연속(lower semi-continuous)이며, 잠재적으로 비볼록할 수 있다. 함수 $h$는 희소성(sparsity)과 같은 특정 해의 특성을 촉진하기 위해 정규화 역할을 한다.

주요 과제는 $f$, 그 그래디언트 $\nabla f$, 그리고 $h$의 근사 연산자(proximal operator)를 정확하게 평가하는 데 드는 계산 비용이나 불가능성을 해결하는 것이다. 이러한 부정확성은 다음과 같은 시나리오에서 발생한다:

• 미분 또는 적분 연산자의 이산화.
• 머신 러닝에서의 확률적 샘플링(방대한 항들의 합).
• 폐형태(closed-form)의 해가 없는 근사 연산자를 평가하기 위한 반복 절차(예: $\ell_p$-노름 총 변동량, 비볼록 $\ell_p$-의사 노름 볼).
• 다중 정밀도 부동 소수점 산술.

방법론: iR2N 알고리즘
저자들은 부정확한 평가를 처리할 수 있도록 Diouane 등 [26]의 R2N 알고리즘을 확장한 수정된 근사 근접 뉴턴 방법인 iR2N(Inexact Regularized R2N)을 소개한다.

• 핵심 메커니즘: 각 반복 단계에서 iR2N은 $f$의 이차 근사, $h$의 모델, 그리고 적응형 이차 정규화 항으로 구성된 모델을 대략적으로 최소화하는 단계를 계산한다.
• 부정확성 처리:
  • 목적 함수 및 그래디언트: 알고리즘은 근사치 $\tilde{f}$와 $\tilde{\nabla}f$를 사용한다. 오차 범위는 단계 크기(step size)에 따라 스케일링된다고 가정한다(구체적으로, $|f(x) - \tilde{f}(x)| \leq \kappa_f \|s\|^2$ 및 $\|\nabla f(x) - \tilde{\nabla}f(x)\| \leq \kappa_\nabla \|s\|$).
  • 근사 연산자: 부문제(subproblem)는 부정확하게 평가되는 근사 연산자를 포함한다. 이 방법은 부문제를 해결하기 위해 근사 근접 경사법(proximal-gradient method)의 변형인 iR2를 사용한다. 결정적으로, 근사 연산자를 위한 반복 과정은 조기에 종료될 수 있다.
• 근사 단계의 정지 조건: 근사 근접 솔버를 위한 정지 조건은 핵심적인 혁신이다. 이는 전역 최소화 도달을 요구하는 대신, 현재 반복값 $\|\tilde{s}_{k,cp}\|$가 정확한 코시 단계(Cauchy step)의 상한 $M_k$의 일정 비율을 초과할 때 종료된다. 이는 문헌(예: Rockafellar의 가산 오차 기준)의 표준 요구 사항보다 약한 조건이지만, 수렴하기에는 충분하다.
• 수용 기준: 알고리즘은 (부정확한 평가에 기반한) 달성된 감소량과 예측된 감소량의 비율를 사용하여 단계를 수용하거나 거부하며, 이에 따라 정규화 파라미터 $\sigma_k$를 동적으로 업데이트한다.

주요 기여

1. 알고리즘 설계: 부정확한 평가의 목적 함수, 그래디언트 및 근사 연산자를 수정된 준 뉴턴 프레임워크 내에 통합한 iR2N의 공식화.
2. 수렴 분석:
   • 전역 수렴: (그래디언트 $\nabla f$의 리프시츠 연속성, 헤시안 근사의 유계성, 특정 부정확성 조건 하에서) 저자들은 일차 정지 측정치(first-order stationarity measure)가 0으로 수렴함을 증명한다.
   • 복잡도: 논문은 정지 측정치를 $\epsilon > 0$ 아래로 줄이기 위한 최악의 경우 평가 복잡도가 $O(\epsilon^{-2})$임을 확립한다. 이는 정확한 R2N 방법의 복잡도와 일치하며, 부정확한 평가가 점근적 최악의 성능 차수를 저하시키지 않음을 보여준다.
3. 부정확성의 실질적 구현: 저자들은 세 가지 까다로운 정규화 도구에 대해 정확한 코시 단계의 노름에 대한 구체적인 이론적 경계치를 제공한다:
   • $\ell_p$-노름 ($1 \leq p < \infty$).
   • $\ell_p$-총 변동량 ($1 \leq p < \infty$).
   • 비볼록 $\ell_p$-의사 노름 볼의 지시 함수 ($0 < p < 1$).
     이러한 경계치는 내부 반복 솔버를 위한 효과적인 조기 종료 조건을 구축할 수 있게 한다.
4. 소프트웨어: Julia 언어로 구현된 효율적인 구현체를 제공하며, 오픈 소스 패키지인 RegularizedOptimization.jl에 통합되어 있다.

결과
수치 실험은 다음 세 가지 문제 클래스에 대해 수행되었다:

1. 기저 추적 노이즈 제거(BPDN): $\ell_p$-노름 정규화 사용.
2. 행렬 완성(Matrix Completion): $\ell_p$-총 변동량 정규화 사용.
3. FitzHugh-Nagumo 역문제: 비볼록 $\ell_p$-의사 노로 볼 지시 함수 사용.

실험은 부정확성 파라미터 $\kappa_s$(근사 단계의 품질을 제어)와, 한 사례에서는 목적 함수/그래디언트 평가의 정확도(ODE 솔버 허용 오차를 통해 제어)를 변화시켰다.

• 성능: 작은 $\kappa_s$ 값(더 거친 근사 단계를 허용)에 대해, 이 방법은 반복당 계산 시간을 크게 단축했다. 이로 인해 외곽 반복 횟수가 약간 증가할 수 있었으나, 결과적으로 "정확 모드"(근사 연산자가 높은 정밀도로 해결되는 모드)에 비해 전체 CPU 시간을 상당히 단축하는 순이익을 얻었다.
• 강건성: 부정확 모드에서 얻은 해는 정확 모드에서 얻은 해와 본질적으로 동일하였으며, 희소한 서포트(support)를 성공적으로 회복하고 신호를 재구성하였다.
• 부정확한 그래디언트: 적응형 허용 오차 체계(adaptive tolerance scheme)를 통해 부정확한 그래디엔트가 적용된 FitzHugh-Nagumo 문제에 적용했을 때, 성공적인 반복에서 정확도를 충분히 높여준다면 수렴을 유지하면서 상당한 시간 절감을 달 Achieved 했다.

의의 및 주장
본 논문은 iR2N이 정확한 평가가 너무 비용이 많이 들거나 불가능한 시나리오에서 매우 큰 유연성을 제공한다고 주장한다. 주요 의의는 제어된 부정확성을 활용함으로써, 이론적 수렴 보장이나 최악의 경우 복잡도 차수를 훼손하지 않고도 계산 노력을 크게 줄일 수 있음을 입증한 데 있다.

저자들은 근사 연산자를 위한 반복 절차를 조기에 중단할 수 있는 접근 방식이 특히 비볼록 정규화 도구(예: $\ell_p$-의사 노름 볼)에서 매우 유용하다는 점을 강조한다. 이 연구는 이론적 복잡도 분석과 실제적인 계산 효율성 사이의 간극을 메운다.