Семинар HDI&TFAIM Lab «Scalable LinUCB: Low-Rank Design Matrix Updatesfor Recommenders with Large Action Spaces», «Теоретический анализ implicit score matching: адаптация к внутренней размерности и оценка матрицы Якоби score-функции»

E. Shustova, “Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces”

In this work, we introduce PSI-LinUCB, a scalable variant of LinUCB that enables efficient training, inference, and memory usage by representing the inverse regularized design matrix as a sum of a diagonal matrix and low-rank correction. We derive numerically stable rank-1 and batch updates that maintain the inverse without explicitly forming the matrix. To control memory growth, we employ a projector-splitting integrator for dynamical low-rank approximation, yielding an average per-step update cost and memory usage of O(dr) for approximation rank r. The inference complexity of the proposed algorithm is O(dr) per action evaluation. Experiments on recommender system datasets demonstrate the effectiveness of our algorithm.

A. Markovich, “Теоретический анализ implicit score matching: адаптация к внутренней размерности и оценка матрицы Якоби score-функции”

Задача оценки score-функции играет важную роль в современной статистике и машинном обучении. Она возникает, в частности, в генеративных диффузионных моделях, в задачах оценивания плотности распределения с точностью до нормировочной константы. Одним из классических подходов к оценке score-функции является implicit score matching. Несмотря на давнюю историю этого метода, его статистические свойства в реалистичных высокоразмерных моделях с низкоразмерной скрытой структурой изучены значительно слабее.

В докладе будет рассказано о недавних результатах, показывающих, что implicit score matching в модели с шумной низкоразмерной структурой способен избежать проклятия размерности и достигать тех же скоростей сходимости по объёму выборки, что и denoising score matching. Ключевой вывод состоит в том, что скорость определяется внутренней размерностью данных, а не размерностью окружающего пространства. Кроме того, те же методы позволяют оценивать якобиан score-функции, то есть гессиан логарифма плотности, без проклятия размерности, что важно для теоретического анализа ODE-based солверов в диффузионных моделях. Основной технический инструмент — взвешенные неравенства типа Гальярдо-Ниренберга, которые позволяют контролировать как функцию, так и её производные в естественных для задачи нормах.