On Approximate Computation of Critical Points

기술 요약: 근사 임계점 계산에 관하여

문제 정의
본 논문은 비볼록 함수(nonconvex functions)의 임계점(기울기가 0이 되는 정지점)을 찾는 계산 복잡도, 특히 근사적(approximate) 계산의 추적 가능성(tractability)에 초점을 맞추어 다룹니다. 3차 다항식의 정확한 임계점을 찾는 것이 NP-hard라는 사실은 이미 잘 알려져 있지만, 최적화 커뮤니티에는 임계점의 근사치(즉, 기울기 노름이 작거나($\|\nabla f(x)\| \le \epsilon$), 실제 임계점과 가까운 점 $\|x - x^*\| \le \epsilon$)를 찾는 것은 계산적으로 추적 가능하다는 믿음이 널리 퍼져 있습니다. 저자들은 이러한 직관에 도전하며, 저차 다항식과 같은 단순한 형태의 비볼록 함수 클래스에 대해서조차 거친(coarse) 근사 임계점을 다항 시간 내에 계산할 수 있는지 조사합니다.

방법론
저자들은 입력이 매개변수 함수 클래스(주로 고정된 차수의 다항식)의 계수로 구성되는 표준 튜링 모델(Turing model)의 계산 방식을 채용합니다. 핵심 방법론은 클리크(Clique) 문제(알려진 NP-완전 문제)로부터 근사 임계점 찾기 문제로의 다항 시간 환원(polynomial-time reduction)을 이용하는 것입니다.

주요 기술적 도구는 다음과 같습니다:

1. 다항식 구성: 저자들은 주어진 그래프의 클리크와 임계점이 정확히 일치하도록 설계된 특정 3차 및 4차 다항식(그리고 다항식과 지수 함수의 곱)을 구성합니다. 중심이 되는 구성은 그래프 $G$의 $k$-클리크의 지표 벡터(indicator vectors)와 정확히 대응하는 4차 다항식 $g_{G,C,k}(x)$입니다.
2. 근사의 어려움(Hardness of Approximation): 근사 계산의 어려움을 증명하기 위해, 저자들은 만약 알고리즘이 "가까운" 임계점을 반환한다면 그것이 근본적인 NP-hard 결정 문제를 해결하는 것과 같음을 입증해야 합니다. 이는 기울기 노름이나 유클리드 거리 측면에서 임계점에 가까운 점을 찾는 경우를 모두 포함합니다.
3. 해석적 경계(Analytical Bounds): 증명은 구성된 다항식의 거동을 경계 짓는 데 크게 의존합니다. 여기에는 다음이 포함됩니다:
   • 다항식이 강제성(coercive)을 가지며 최솟값을 갖는다는 것을 확립함.
   • 1차 및 2차 필요 조건(FONC/SONC)을 사용하여 최솟값 위치를 제한함.
   • 임계점 근처의 점에서의 다항식 값과 실제 임계점에서의 값을 연관시키기 위해 립시츠 연속성(Lipschitz continuity) 논리를 적용함.
   • 변수의 크기를 제한하기 위해 단항 다항식의 근에 대한 경계(Fujiwara의 경계)를 활용함.

주요 기여 및 결과

본 논문은 다양한 "근사"의 정의와 구조적 가정 하에서 근사 임계점을 계산하는 것이 (P=NP가 아니라면) 불가능함을 입증합니다.

1. $\epsilon$-근사 임계점 (기울기 노름):

   • 정리 3: P=NP가 아니라면, $n$개의 변수를 가진 3차 다항식에 대해 $2^n$-근사 임계점($\|\nabla p(x)\| \le 2^n$)을 계산할 수 있는 다항 시간 알고리즘은 존재하지 않습니다. 이는 알고리즘이 임계점이 존재하지 않을 때 임의의 점을 반환하도록 허용되는 경우에도 성립합니다.
   • 따름정리 8: 이 결과는 $n^d$-근사 임계점을 찾는 의사 다항 시간(pseudo-polynomial time) 알고리즘으로 확장됩니다.
   • 유일한 임계점에 대한 함의: 이 어려움은 다항식이 유일한 임계점을 갖도록 보장되는 경우에도 지속됩니다. 이 설정에서 $2^n$-근사 임계점을 찾는 것은 Planted Clique 추측을 반박하며 NP=RP를 의미하게 됩니다.

2. 구조적 가정 (하한 유계성 및 유일성):

   • 명제 9: 3차 다항식의 지수 함수(항상 하한이 유계됨)가 임계점을 갖는지 결정하는 것은 NP-hard입니다.
   • 명제 10: 임계점이 반드시 존재하고 가짜 임계점(spurious critical points)이 없는 (즉, 모든 임계점이 전역 최솟값인) 하한 유계 함수에 대해서도 임계점을 찾는 것은 어렵습니다. 이는 가짜 지역 최솟값이 없다는 사실이 계산 가능성을 보장하지 않음을 시사합니다.
   • 정리 11: 하한 유계인 4차 다항식의 경우, 반지름 $2^n$의 구(ball) 내에서 $2^n$-근사 임계점을 찾는 것은 NP-hard입니다. 이는 알고리즘이 단위 초입방체(unit hypercube) 내에 임계점이 없을 때 임의로 동작하는 것이 허용되더라도 마찬가지입니다.

3. $\epsilon$-근접 임계점 (해와의 거리):

   • 정의: $\epsilon$-근접 임계점은 실제 임계점으로부터 거리 $\epsilon$ 이내에 있는 점을 의미합니다.
   • 정리 13: P=NP가 아니라면, 3차 다항식에 대해 $\frac{1}{12000 n^{3.5}}$-근접 임계점을 계산할 수 있는 다항 시간 알고리즘은 존재하지 않습니다.
   • 정리 15: 이 어려움의 결과는 하한 유계 함수(4차 다항식과 지수 함수의 곱)로 확장되어, $\frac{1}{1000 n^7}$-근접 임계점을 찾는 것 또한 불가능함을 보여줍니다.

의의 및 주장

본 논문의 주요 의의는 근사 임계점 계산이 비볼록 최적화에서 추적 가능한 작업이라는 일반적인 믿음을 뒤집었다는 데 있습니다. 저자들은 비볼록 최적화의 어려움이 단순히 가짜 지역 최솟값이나 안장점(saddle points)의 존재에서 기인하는 것이 아니라, 어떠한 정지점이라도 근사적으로 찾아내는 작업 자체에 내재된 본질적인 문제라고 주장합니다.

• 오라클 모델과의 대비: 저자들은 자신들의 결과가 쿼리 복잡도(query complexity)에 하한을 제공하는 기존의 오라클 기반 모델(예: Carmon et al., Hollender and Zampetakis) 연구와 구별됨을 명시합니다. 본 논문은 튜링 모델에서 작동하며, 비볼록 릴랙세이션(convex relaxation)이나 다른 비오라클 접근 방식을 포함한 모든 다항 시간 알고리즘을 배제합니다.
• 알고리즘에 대한 함의: 이 결과는 경사 하강법(Gradient Descent)이나 뉴턴 방법(Newton's method)(및 그 고차 확장형)과 같은 표준 알고리즘들이 일반적인 3차 다항식에 대해 심지어 거친 근사 임계점조차 다항 시간 내에 찾는 것을 보장할 수 없음을 시사합니다. 특히, 뉴턴 방법의 가장 자연스러운 고차 확장(3차 테일러 전개의 임계점을 구하는 방식)은 P=NP가 아니라면 매 반복(iteration)당 계산 복잡도가 추적 가능하지 않음을 지적합니다.
• 향atic 방향: 저자들은 자신의 결과가 어떤 구조적 특성이 효율적인 근사를 가능하게 하는지에 대한 이해의 간극을 남겨두고 있음을 언급하며, 근사 임계점 계산이 추적 가능해질 수 있는 특정 매개변수 함수 클래스와 구조적 가정(다항 시간에 확인 가능한)을 탐색하는 동기를 부여한다고 겸허히 결론짓습니다. 이들은 볼록성(convexity)이 추적 가능성을 허용하지만, 4차 이상의 다항식에 대해 볼록성을 확인하는 것 자체가 어렵다는 점을 들어, 어떤 구조적 속성이 효율적인 근사를 가능케 하는지에 대한 연구가 필요함을 시사합니다.