경험적 위험 최소화를 이용한 확률적 볼록 최적화: $O(1/n)$ 및 $O(1/n^2)$ 형태의 위험 경계

감독 학습을 위한 경험적 위험 최소화(ERM) 이론은 풍부하지만, 관련 문제인 확률적 볼록 최적화(SCO)를 위한 현재의 이론적 이해는 제한적입니다. 본 연구에서는 부드러움과 강한 볼록성 조건을 활용하여 SCO에 대한 ERM의 위험 경계를 개선함으로써 ERM의 영역을 강화합니다. 첫째, 무작위 함수가 음이 아닌, 볼록하고 부드럽고, 기대 함수가 리프시츠 연속일 때 $\widetilde{O}(d/n + \sqrt{F_/n})$ 위험 경계를 설정합니다. 여기서 $d$는 문제의 차원, $n$은 샘플 수, $F_$는 최소 위험입니다. 따라서 $F_$가 작을 때 $\widetilde{O}(d/n)$ 위험 경계를 얻게 되며, 이는 감독 학습에서 ERM의 $\widetilde{O}(1/n)$ 낙관적인 비율과 유사합니다. 둘째, 목적 함수가 또한 $λ$-강한 볼록성을 가질 경우 $\widetilde{O}(d/n + κF_/n)$ 위험 경계를 증명하며, $n=\widetildeΩ(κd)$일 때 이를 $O(1/[λn^2] + κF_/n)$로 개선합니다. 결과적으로, $n$이 충분히 크고 $F_$가 작을 때 $O(κ/n^2)$ 위험 경계를 얻게 되는데, 이는 우리 지식 범위 내에서 처음으로 제시되는 $O(1/n^2)$ 형태의 ERM 위험 경계입니다. 셋째, 위의 결과들은 통합된 프레임워크에서 설정되었음을 강조하며, 이는 무작위 함수의 볼록성이나 기대 함수의 리프시츠 연속성과 같은 더 약한 조건 하에서도 새로운 위험 경계를 도출할 수 있게 합니다. 마지막으로, 감독 학습에서 $\widetilde{O}(1/[λn^2] + κF_*/n)$ 위험 경계를 달성하기 위해 필요한 $n$에 대한 $\widetildeΩ(κd)$ 요구사항을 차원에 독립적인 $Ω(κ^2)$로 대체할 수 있음을 보여줍니다.