Исследователи представили алгоритм для восстановления параметров многомерного гауссовского распределения, подвергшегося усечению неизвестным полупространством. Работа решает проблему оптимизации сложности выборки и времени вычислений, достигая теоретически оптимальных границ. Предложенный метод значительно превосходит предыдущие полиномиальные решения, обеспечивая высокую точность аппроксимации при заданном уровне погрешности в условиях высокой размерности данных.

Задача обучения усеченных распределений является фундаментальной для статистики и машинного обучения, особенно в сценариях, где данные подвергаются фильтрации или отбору. Предыдущие подходы, представленные на конференции FOCS 2024, заложили основу для полиномиальной разрешимости задачи, однако их показатели сложности оставались далеки от оптимальных. Авторы новой работы смогли сократить разрыв, предложив более эффективную вычислительную схему.

Технический прогресс в этой области позволяет точнее моделировать процессы, в которых наблюдаемые данные представляют собой лишь часть генеральной совокупности, ограниченную определенными условиями. Это критически важно для задач оценки плотности вероятности, обучения генеративных моделей и анализа данных с селективным смещением, где стандартные методы оценки параметров распределений дают значительные искажения.

Ключевые факты

  • Предложен алгоритм с оптимальной сложностью выборки для обучения усеченного гауссовского распределения.
  • Метод улучшает показатели сложности, достигнутые в работе Lee, Mehrotra и Zampetakis (FOCS'24).
  • Алгоритм работает в условиях высокой размерности (d) и произвольной точности (ε).
  • Исследование направлено на решение фундаментальной проблемы статистического вывода при наличии неизвестных ограничений на область определения данных.