Краткое содержание

arXiv:2511.12659v1 Тип объявления: новый Аннотация: Фундаментальная теорема статистического обучения утверждает, что бинарное PAC-обучение определяется единственным параметром — размерностью Вапника-Червоненкиса (VC-размерностью), — который определяет как обучаемость, так и сложность выборки. Распространение этого результата на многоклассовую классификацию долгое время оставалось сложной задачей, начиная с работы Натараджана конца 80-х годов, предложившего размерность Натараджана (Nat) в качестве естественного аналога VC-размерности. Даниэли и Шалев-Шварц (2014) ввели DS-размерность, которая, как позже показали Брухим и др. (2022), характеризует обучаемость в многоклассовой задаче. Брухим и др. также показали, что Nat и DS могут сколь угодно сильно расходиться, что позволяет предположить, что многоклассовое обучение определяется DS-размерностью, а не Nat. Мы показываем, что сложность выборки для агностического многоклассового PAC-обучения на самом деле определяется двумя различными размерностями. В частности, мы доказываем почти точные границы сложности выборки для агностического случая, которые, с точностью до логарифмических множителей, имеют вид $\frac{DS^{1.5}}{\epsilon} + \frac{Nat}{\epsilon^2}$, где $\epsilon$ — точность.