기술 요약: 이중 수준 최적화(Bilevel Optimization)에서의 조건수 의존성에 관하여

문제 정의

본 논문은 1차 방법론(first-order methods)을 사용하여 이중 수준 최적화 문제의 $\epsilon$-정지점(stationary point)을 찾는 오라클 복잡도(oracle complexity)를 조사한다. 고려된 구체적인 설정은 비볼록-강볼록(nonconvex-strongly-convex, NC-SC) 이중 수준 최적화로, 다음과 같이 정의된다:
$$\min_{x \in \mathbb{R}^{d_x}} F(x) = f(x, y^*(x)), \quad \text{단, } y^*(x) = \arg\min_{y \in \mathbb{R}^{d_y}} g(x, y).$$
여기서 상위 수준 목적 함수 $f$는 비볼록(nonconvex)이며, 하위 수준 목적 함수 $g$는 $y$에 대해 강볼록(strongly convex)이다. 주요 과제는 수렴 속도가 하위 수준 문제의 **조건수(condition number)**인 $\kappa_y = L_1/\mu_y$ (여기서 $L_1$은 매끄러움 상수, $\mu_y$는 강볼록성 상수) 및 전역 조건수 $\bar{\kappa}_y$에 어떻게 의존하는가에 있다.

최근 연구들이 결정론적 매끄러운 문제(deterministic smooth problems)에 대해 $\tilde{O}(\bar{\kappa}_y^4 \epsilon^{-2})$ 또는 개선된 $\tilde{O}(\bar{\kappa}_y^{7/2} \epsilon^{-2})$의 상한(upper bounds)을 확립했으나, 조건수에 대한 최적의 의존성은 여전히 알려지지 않았다. 특히, 미니맥스(minimax) 문제(여기서 $f = -g$)가 $\Omega(\sqrt{\kappa_y}\epsilon^{-2})$의 하한을 갖는 것과 비교하여, 이중 수준 문제가 조건수 의존성 측면에서 증명 가능하게 더 어려운지는 불분명하다.

방법론

저자들은 제로 체인(zero-chain) 구조를 기반으로 한 "어려운 인스턴스(hard instances)"를 구축함으로써 새로운 하한(lower bounds)을 확립한다. 이는 최적화 하한 문헌에서 널리 사용되는 기법이다.

1. 어려운 인스턴스 구축:
   핵심 혁신은 NC-SC 미니맥스 문제를 위해 사용된 체인 형태의 어려운 인스턴스를 변형한 것이다. 저자들은 상위 수준 함수 $f$와 하위 수준 함수 $g$ 사이의 비대칭성을 활용하는 구성을 도입했다.

   • 이원적 소스 특성(Two-Source Characterization): 이 구성은 조건수 의존성을 증폭시키기 위해 두 가지 특정 변수를 활용한다:
     • 결합 변수(coupling variable) $y$ (하위 수준에 존재): $y^*(x)$를 계산하는 복잡성을 포착한다.
     • 재스케일링 변수(rescaling variable) $z$ (상위에서 하위 수준으로 이동됨): 하이퍼 목적 함수(hyper-objective) $F(x)$의 매끄러움에 대한 의존성을 포착한다.
   • 메커니즘: 변수 $x, z, y$ 사이의 연결을 정교하게 설계하고, $x$ 대신 $z$에 비볼록 정규화(nonconvex regularization)를 추가함으로써, 저자들은 상위 수준에서의 유효 체인 길이가 $\kappa_y$와 관련된 인자에 의해 스케일링되는 시나리오를 만든다. 구체적으로, 하이퍼 목적 함수는 $K = \Omega(\sqrt{\kappa_y})$에서 평가된 비볼록 제로 체인과 동등하게 된다.

2. 알고리즘 클래스:
   하한은 다음 클래스들에 적용됨을 증명한다:

   • 결정론적 1차 알고리즘(Deterministic First-Order Algorithms): 그래디언트 $\nabla f$와 $\nabla g$에 접근하는 알고리즘.
   • HVP 기반 알고리즘: 헤시안-벡터 곱(Hessian-Vector Product, HVP)에 접근하는 알고리즘. 저자들은 이차(quadratic) 하위 수준 함수에 대해 HVP 오라클이 정보 접근 측면에서 1차 오라클과 동일함을 증명하며, 따라서 하한이 두 클래스 모두에 적용됨을 보인다.
   • 확률적 알고리즘(Stochastic Algorithms): 노이즈와 분산을 처리하기 위해 무작위 제로 체인을 사용하는 별도의 구성을 사용한다.

주요 기여 및 결과

1. 결정론적 NC-SC 하한

본 논문은 조건수 의존성 측면에서 이중 수준 문제와 미니맥스 문제 사이의 첫 번째 증명 가능한 격차를 확립한다.

• 1차 매끄러운 경우 ($p=1$): $\Omega(\kappa_y^{5/2} \epsilon^{-2})$. 이는 미니맥스 하한인 $\Omega(\sqrt{\kappa_y}\epsilon^{-2})$를 개선한 것이다.
• 2차 매끄러운 경우 ($p=2$): $\Omega(\kappa_y^{3/14} \epsilon^{-12/7})$.
• 임의의 매끄러운 경우 ($p \ge 3$): $\Omega(\kappa_y^{21/10} \epsilon^{-8/5})$.

2. 볼록 및 강볼록 설정

저자들은 하이퍼 목적 함수가 볼록하거나 강볼록인 설정으로 결과를 확장한다:

• 볼록-강볼록 (C-SC): 기존 하한 $\tilde{\Omega}(\min\{\kappa_y, \epsilon^{-3/2}\}/\sqrt{\epsilon})$을 $\Omega(\kappa_y^{3/2}/\sqrt{\epsilon})$으로 개선한다.
• 강볼록-강볼록 (SC-SC): 기존 $\tilde{\Omega}(\kappa_y \sqrt{\kappa_x})$를 $\tilde{\Omega}(\kappa_y^{3/2} \sqrt{\kappa_x})$로 개선한다.

3. 확률적 NC-SC 하한

노이즈가 있는 그래디언트를 가진 확률적 문제의 경우:

• 하한: $\Omega(\kappa_y^4 \epsilon^{-4})$ (분산 항에 의해 지배됨).
• 통찰: 저자들은 확률적 설정에서 분산(variance)(재스케일링 변수에 의해 증폭됨)이 편향(bias)보다 근본적인 병목 현상이라고 주장한다. 이는 편향에 집중했던 병행 연구들과 비교하여 훨씬 더 타이트한 하한을 이끌어낸다.

4. 정교화된 상한

하한을 맥락화하기 위해, 저자들은 내부 루프(하위 수준 솔버)에 네스테로프 가속(Nesterov acceleration)을 적용하여 기존 상한을 정교화한다:

• 1차 매끄러운 결정론적 문제의 경우, 상한은 $\tilde{O}(\bar{\kappa}_y^{7/2} \epsilon^{-2})$로 정교화되며, 하위 수준 함수가 이차 함수인 경우 $\tilde{O}(\kappa_y^{5/2} \epsilon^{-2})$가 된다.
• 이를 통해 이차 하위 수준 문제를 가진 설정에서 상한과 하한 사이의 간극을 작은 폴리로그(polylogarithmic) 인자 또는 작은 다항식(polynomial) 인자 수준으로 좁혔으며, 이는 해당 설정에서 거의 최적(near-optimal)임을 시사한다.

의의 및 주장

본 논문은 조건수 의존성 측면에서 이중 수준 최적화와 미니맥스 최적화의 복잡도 사이의 **첫 번째 증명 가능한 분리(provable separation)**를 제공한다고 주장한다.

• 근본적 난이도: 결과는 이중 수준 문제가 미니맥스 문제보다 증명 가능하게 더 어렵다는 것을 보여준다. 증가된 $\kappa_y$ 의존성(예: $\sqrt{\kappa_y}$ 대비 $\kappa_y^{5/2}$)은 이중 수준 구조 자체, 즉 하위 수준 솔루션 계산과 상위 수준 매끄러움 사이의 상호작용에서 비롯되는 근본적인 어려움을 반영한다.
• 분산 vs 편향: 확률적 설정에서, 본 연구는 분산을 수렴 속도를 제한하는 주요 요인으로 식별하며, 왜 확률적 이중 수준 최적화가 어려운지에 대한 새로운 관점을 제공한다.
• 타이트함(Tightness): 이차 하위 수준 문제에 대해, 확립된 하한은 작은 인자 차이 내에서 상한과 일치하므로 거의 최적임이 입증되었다.

저자들은 자신들의 하한이 이차 하위 수준 함수에 대해서는 타이트하지만, 일반적인 비이차 함수에 대해 더 타이트한 하한을 확립하는 것은 여전히 열린 문제라고 언급한다. 또한 고차 매끄러움(higher-order smoothness) 및 평균 제곱 매끄러움(mean-squared smoothness)과 같은 다른 문제 설정에 대한 확률적 하한의 확장을 향후 과제로 남겨두었다.