Ilya Levin — accepted AI-conference papers

2026

High-Order Error Bounds for Markovian LSA with Richardson–Romberg Extrapolation

Ilya Levin, Alexey Naumov, Sergey Samsonov

AAAI 2026technical

In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. We focus on the version of the algorithm with constant step size and propose a novel decomposition of the bias via a lineariza

Cited by 0 Source ↗PDF ↗Scholar ↗

2024

SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning

Paul Mangold, Sergey Samsonov, Safwan Labbi, Ilya Levin, Reda ALAMI, Alexey Naumov +1

NeurIPS 2024poster

In this paper, we analyze the sample and communication complexity of the federated linear stochastic approximation (FedLSA) algorithm. We explicitly quantify the effects of local training with agent heterogeneity. We show that the communication complexity of FedLSA scales polynomially with the inver…

Cited by 9 Source ↗PDF ↗Scholar ↗