Anastasia Koloskova — accepted AI-conference papers

2026

Adaptive Methods Are Preferable in High Privacy Settings: An SDE Perspective

Enea Monzio Compagnoni, Alessandro Stanghellini, Rustem Islamov, Aurelien Lucchi, Anastasia Koloskova

ICLR 2026poster

Differential Privacy (DP) is becoming central to large-scale training as privacy regulations tighten. We revisit how DP noise interacts with *adaptivity* in optimization through the lens of *stochastic differential equations*, providing the first SDE-based analysis of private optimizers. Focusing on…

Cited by 0 Source ↗code ↗Scholar ↗

2026

FedMuon: Federated Learning with Bias-corrected LMO-based Optimization

Yuki Takezawa, Anastasia Koloskova, Xiaowen Jiang, Sebastian U Stich

ICLR 2026poster

Recently, a new optimization method based on the linear minimization oracle (LMO), called Muon, has been attracting increasing attention since it can train neural networks faster than the existing adaptive optimization methods, such as Adam. In this paper, we study how Muon can be utilized in federa…

Cited by 0 Source ↗Scholar ↗

2025

Certified Unlearning for Neural Networks

Anastasia Koloskova, Youssef Allouah, Animesh Jha, Rachid Guerraoui, Sanmi Koyejo

ICML 2025poster

We address the problem of machine unlearning, where the goal is to remove the influence of specific training data from a model upon request, motivated by privacy concerns and regulatory requirements such as the “right to be forgotten.” Unfortunately, existing methods rely on restrictive assumptions…

Cited by 0 Source ↗PDF ↗code ↗Scholar ↗

2024

Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimization

Mathieu Even, Anastasia Koloskova, Laurent Massoulie

AISTATS 2024poster

Decentralized and asynchronous communications are two popular techniques to speedup communication complexity of distributed machine learning, by respectively removing the dependency over a central orchestrator and the need for synchronization. Yet, combining these two techniques together still remai…

Cited by 17 Source ↗PDF ↗Scholar ↗

2024

On Convergence of Incremental Gradient for Non-convex Smooth Functions

Anastasia Koloskova, Nikita Doikov, Sebastian U Stich, Martin Jaggi

ICML 2024poster

In machine learning and neural network optimization, algorithms like incremental gradient, single shuffle SGD, and random reshuffle SGD are popular due to their cache-mismatch efficiency and good practical convergence behavior. However, their optimization properties in theory, especially for non-con…

Cited by 1 Source ↗PDF ↗Scholar ↗

2024

The Privacy Power of Correlated Noise in Decentralized Learning

Youssef Allouah, Anastasia Koloskova, Aymane El Firdoussi, Martin Jaggi, Rachid Guerraoui

ICML 2024poster

Decentralized learning is appealing as it enables the scalable usage of large amounts of distributed data and resources without resorting to any central entity, while promoting privacy since every user minimizes the direct exposure of their data. Yet, without additional precautions, curious users ca…

Cited by 9 Source ↗PDF ↗code ↗Scholar ↗

2023

Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy

Anastasia Koloskova, Ryan McKenna, Zachary Charles, J Keith Rush, Hugh Brendan McMahan

NeurIPS 2023poster

We study gradient descent under linearly correlated noise. Our work is motivated by recent practical methods for optimization with differential privacy (DP), such as DP-FTRL, which achieve strong performance in settings where privacy amplification techniques are infeasible (such as in federated lear…

Cited by 19 Source ↗PDF ↗Scholar ↗

2023

Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees

Anastasia Koloskova, Hadrien Hendrikx, Sebastian U Stich

ICML 2023poster

Gradient clipping is a popular modification to standard (stochastic) gradient descent, at every iteration limiting the gradient norm to a certain value $c >0$. It is widely used for example for stabilizing the training of deep learning models (Goodfellow et al., 2016), or for enforcing differential…

Cited by 56 Source ↗PDF ↗Scholar ↗

2022

Decentralized Local Stochastic Extra-Gradient for Variational Inequalities

Aleksandr Beznosikov, Pavel Dvurechensky, Anastasia Koloskova, Valentin Samokhin, Sebastian U Stich, Alexander Gasnikov

NeurIPS 2022accept

We consider distributed stochastic variational inequalities (VIs) on unbounded domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the computational network that, in particular, covers the settings of fully decentral…

Cited by 52 Source ↗PDF ↗Scholar ↗

2022

Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning

Anastasia Koloskova, Sebastian U Stich, Martin Jaggi

NeurIPS 2022accept

We study the asynchronous stochastic gradient descent algorithm, for distributed training over $n$ workers that might be heterogeneous. In this algorithm, workers compute stochastic gradients in parallel at their own pace and return them to the server without any synchronization. Existing convergen…

Cited by 106 Source ↗PDF ↗Scholar ↗

2021

A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!

Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi, Peter Richtarik, Sebastian Stich

AISTATS 2021poster

Decentralized optimization methods enable on-device training of machine learning models without a central coordinator. In many scenarios communication between devices is energy demanding and time consuming and forms the bottleneck of the entire system. We propose a new randomized first-order method…

Cited by 93 Source ↗PDF ↗Scholar ↗

2021

An Improved Analysis of Gradient Tracking for Decentralized Machine Learning

Anastasia Koloskova, Tao Lin, Sebastian U Stich

NeurIPS 2021poster

We consider decentralized machine learning over a network where the training data is distributed across $n$ agents, each of which can compute stochastic model updates on their local data. The agent's common goal is to find a model that minimizes the average of all local loss functions. While gradien…

Cited by 112 Source ↗PDF ↗Scholar ↗

2021

Consensus Control for Decentralized Deep Learning

Lingjing Kong, Tao Lin, Anastasia Koloskova, Martin Jaggi, Sebastian Stich

ICML 2021spotlight

Decentralized training of deep learning models enables on-device learning over networks, as well as efficient scaling to large compute clusters. Experiments in earlier works reveal that, even in a data-center setup, decentralized training often suffers from the degradation in the quality of the mode…

Cited by 100 Source ↗PDF ↗Scholar ↗

2021

RelaySum for Decentralized Deep Learning on Heterogeneous Data

Thijs Vogels, Lie He, Anastasia Koloskova, Sai Praneeth Karimireddy, Tao Lin, Sebastian U Stich +1

NeurIPS 2021poster

In decentralized machine learning, workers compute model updates on their local data. Because the workers only communicate with few neighbors without central coordination, these updates propagate progressively over the network. This paradigm enables distributed training on networks without all-to-al…

Cited by 70 Source ↗PDF ↗code ↗Scholar ↗

2020

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, Sebastian Stich

ICML 2020poster

Decentralized stochastic optimization methods have gained a lot of attention recently, mainly because of their cheap per iteration cost, data locality, and their communication-efficiency. In this paper we introduce a unified convergence analysis that covers a large variety of decentralized SGD metho…

Cited by 610 Source ↗PDF ↗Scholar ↗

2019

Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication

Anastasia Koloskova, Sebastian Stich, Martin Jaggi

ICML 2019oral

We consider decentralized stochastic optimization with the objective function (e.g. data samples for machine learning tasks) being distributed over n machines that can only communicate to their neighbors on a fixed communication graph. To address the communication bottleneck, the nodes compress (e.g…

Cited by 609 Source ↗PDF ↗Scholar ↗

2019

Efficient Greedy Coordinate Descent for Composite Problems

Sai Praneeth Karimireddy, Anastasia Koloskova, Sebastian U. Stich, Martin Jaggi

AISTATS 2019poster

Coordinate descent with random coordinate selection is the current state of the art for many large scale optimization problems. However, greedy selection of the steepest coordinate on smooth problems can yield convergence rates independent of the dimension $n$, requiring $n$ times fewer iterations.…

Cited by 33 Source ↗PDF ↗code ↗Scholar ↗