Совместный семинар HDI Lab & TFAIM Lab «Поиск кратчайших путей в больших графах с помощью генеративных потоковых сетей; On approximation and estimation of Schrödinger potentials without the curse of dimensionality»

Н. Морозов, “Поиск кратчайших путей в больших графах с помощью генеративных потоковых сетей”

В данной работе мы представляем новый вероятностный фреймворк обучения для решения задач поиска кратчайших путей, основанный на генеративных потоковых сетях (GFlowNets). Сначала мы рассмотриваем теоретические свойства GFlowNets в неациклических средах в отношении кратчайших путей. Мы доказываем, что при минимизации потока, GFlowNets выставляют ненулевую вероятностную массу исключительно на кратчайшие пути между начальным и терминальными состояниями. Основываясь на этом результате, мы показываем, что задача поиска кратчайших путей в произвольном графе может быть сведена к обучению неациклических GFlowNets с потоковой регуляризацией. Мы экспериментально демонстрируем эффективность нашего метода в задачах поиска кратчайших путей в графе Кэли группы перестановок, а также в задаче сборки кубика Рубика. В последней задаче наш метод показывает результаты, сравнимые со state-of-the-art подходами в терминах длины пути, а также требует меньший бюджет для поиска путей на этапе инференса.


A. Patarusau, “On approximation and estimation of Schrödinger potentials without the curse of dimensionality”

We examine generative modelling approaches based on the construction of Schrödinger bridges between Gaussian noise and a target distribution. It is known that the solution of the dynamic Schrödinger problem is a diffusion process with a drift associated with Doob's h-transform of a Schrödinger potential. Although its accurate restoration from finite samples is crucial for reliable, high-quality data generation, the existing literature lacks theoretical guarantees regarding this question. In our work, we establish theoretical upper bounds on the complexity of Schrödinger potential approximation and estimation via neural networks. These bounds are determined by the effective dimension of the target distribution. To our knowledge, this is the first result demonstrating that generative modelling methods based on Schrödinger bridges and stochastic optimal control can escape the curse of dimensionality.