비교 오라클을 통한 정지점 찾기

우리는 두 지점이 주어졌을 때 어느 쪽의 함수 값이 더 큰지를 출력하는 비교 오라클 (comparison oracle)을 통해서만 목적 함수에 접근할 수 있는 경우, 비볼록 함수 (non-convex functions)의 정지점 (stationary points)을 찾는 문제를 연구합니다. Lipschitz 연속인 기울기 (gradient)와 헤시안 (Hessian)을 갖는 두 번 미분 가능한 $f\colon\mathbb R^n\to\mathbb R$에 대하여, 우리는 $\widetilde O(n^2/ε^{1.5})$번의 쿼리를 사용하여 $ε$-정지점 ($ε$-stationary point)을 방문하는 알고리즘을 개발합니다. 우리의 접근 방식은 $\widetilde O(n^2\log(1/δ))$번의 쿼리를 사용하여 정규화된 헤시안 (normalized Hessian)을 정확도 $δ$로 추정하는 서브루틴 (subroutine)을 사용합니다. 나아가 우리는 쿼리를 중첩 (superpositions) 상태로 수행할 수 있는 양자 비교 오라클 (quantum comparison oracle) 모델에서 이 문제를 추가로 연구하며, $\widetilde O(n/ε^{1.5})$번의 쿼리가 소요되는 $ε$-정지점을 찾는 최초의 양자 알고리즘 (quantum algorithm)을 개발합니다.