6 papers
Improved Analysis of Adaptive Task Allocation and Non-Stationary Processing Times
Grigory Begunov, Ilgam Latypov, Yuriy Dorn +1
We study the task allocation problem, where our goal is to develop an online algorithm that efficiently distributes tasks among workers based on their computational performance. Th…
Same Flow, Different Paths: Variance Reduction in Flow Matching
Alexander Tyurin
In flow matching (FM), a velocity model is trained using a predefined path that connects data and noise samples (e.g., ). In this w…
Global Convergence of Gradient Descent for Score Matching in Gaussian Mixtures via Reverse Fisher Divergence
Alexander Tyurin
The score matching problem is a central training objective in modern generative modeling, diffusion models, fitting unnormalized statistical models, and inverse problems. A standar…
Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits
Grigory Begunov, Alexander Tyurin
In centralized, distributed, and federated learning with stochastic gradients and workers, it was recently shown that it is infeasible to find an -stationary point…
From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizes
Alexander Tyurin
We focus on the classification problem with a separable dataset, one of the most important and classical problems from machine learning. The standard approach to this task is logis…
Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics
Alexander Tyurin
In distributed stochastic optimization, where parallel and asynchronous methods are employed, we establish optimal time complexities under virtually any computation behavior of wor…