정규화된 분류를 위한 최적의 차원 독립적 샘플링 (Optimal Dimension-Free Sampling for Regularized

우리는 다양한 정규화 항 (regularization terms) 하에서 광범위한 Lipschitz 연속 분류 손실 함수 (Lipschitz continuous classification loss functions)에 대해 $(1 o ext{epsilon})$-상대 오차 (relative error)를 달성하는 최적의 샘플링 경계 (sampling bounds)를 증명합니다. 여기에는 대표적이고 대중적인 예시로서 로지스틱 및 시그모이드 손실 (logistic and sigmoid loss), 힌지 손실 (hinge loss), 그리고 ReLU 손실 (ReLU loss)과 같은 중요한 함수들이 포함됩니다. 특히, 우리는 $|\cdot|_2/k$ 정규화에 대해 $k^2/\varepsilon^2$ 상한 및 하한을 증명하였으며, $|\cdot|_1/k$ 정규화에 대해서는 $k/\varepsilon^2$ 상한 및 하한을 증명하였습니다. $|\cdot|_2^2/k$ 정규화의 경우, 샘플링 복잡도 (sampling complexity)는 주로 유계 미분 성질 (bounded derivative property)에 따라 달라집니다. 만약 $|g'(x)| \leq g(x)$이고, $g(0) > 0$이며, $g$가 단조(monotonic) 또는 볼록(convex) 함수라면, $k$에 선형적인 샘플링 복잡도를 가집니다. 그렇지 않은 경우 일반적인 경계는 $k^2/\varepsilon^2$입니다. 그러나 만약 $g(0)=0$이라면, 우리의 결과는 차원 독립적 경계 (dimension-free bounds)가 불가능하며, 심지어 하선형 경계 (sublinear bounds)조차 배제됨을 나타냅니다. 모든 상한은 다항 로그 항 (polylogarithmic terms)을 제외하고 일치하는 하한에 의해 보완됩니다. 또한, 우리의 연구는 개념적 및 알고리즘적으로 단순한 균등 샘플링 (uniform sampling) 또는 (제곱) 노름 샘플링 ((squared) norm sampling)에 의존하며, 이를 통해 최근 (Alishahi and Phillips, ICML'24)에서 제시된 $k^3/\varepsilon^2$의 삼차 민감도 샘플링 (sensitivity sampling) 경계를 개선합니다. 이는 사실상의 표준인 VC-차원 (VC-dimension) 및 민감도 프레임워크 (sensitivity framework)에서 나타나는 과잉 계산 (overcounting)을 피하기 위해, 고차 모멘트 경계 (higher moment bounds) 및 경험적 과정 분석 (empirical process analyses)을 포함하는 정교한 논증을 통해 달성되었습니다.