Статистика пока была в основном о средних и асимптотике. Неравенства концентрации задают более острый, конечновыборочный вопрос: насколько вероятно случайной величине упасть далеко от своего среднего? Их ответы — математический хребет того, почему ML вообще может давать гарантии.
Самое базовое, требующее лишь неотрицательной переменной и её среднего, — неравенство Маркова:
Оно говорит, что неотрицательная переменная не может часто быть многократно больше своего среднего. Если среднее мало, большие значения должны быть редки. Грубо, но требует почти ничего.
Где это встречается в MLГраница Хёффдинга — сердце теории генерализации: почему измеренная ошибка модели на конечном тестовом множестве доказуемо близка к истинной, с высокой вероятностью — формальное обоснование доверия к тестовому баллу. Это двигатель PAC-обучения («вероятно приблизительно корректно»): при достаточном числе сэмплов разрыв между тренировочной и истинной производительностью мал с высокой вероятностью.…