개별 평활성 조건 하에서의 거의 최적 2차 볼록 유한 합 최적화

요약

본 논문은 $n$개 구성 요소의 볼록 유한 합 최적화에 대한 확률적 2차 오라클 복잡도를 연구합니다. 개별 평활성 및 볼록성을 가정하여, 기존보다 강력한 조건 하에서 하한 복잡도 $\Omega(n+ n^{5/7} \epsilon^{-2/7})$를 증명했습니다. 또한 새로운 Taylor-수정형 게으른 뉴턴 방법을 설계하여 최적의 $O(n + n^{5/7} \epsilon^{-2/7})$ 복잡도를 달성했음을 보여줍니다.

핵심 포인트

• 개별 평활성과 볼록성을 가정하여 최적화 복잡도 개선을 입증함.
• 하한 복잡도는 $\Omega(n+ n^{5/7} \epsilon^{-2/7})$임을 증명함.
• 새로운 2차 자체 경계 부등식을 확립하는 데 기여함.
• Taylor-수정형 게으른 뉴턴 방법을 설계하여 최적 복잡도를 달성함.