6 papers
Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
Sasha Voitovych, Adam Block, Alexander Rakhlin +1
Online learning is an attractive framework in many domains because it permits well-defined learning even when data are dependent or chosen adversarially. This generality, however,…
Learning with Simulators: No Regret in a Computationally Bounded World
Sasha Voitovych, Abhishek Shetty, Noah Golowich +1
Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some…
On Traceability in Stochastic Convex Optimization
Sasha Voitovych, Mahdi Haghifam, Idan Attias +3
In this paper, we investigate the necessity of traceability for accurate learning in stochastic convex optimization (SCO) under geometries. Informally, we say a learning a…
Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updates
Youssef Allouah, Sadegh Farhadkhani, Rachid GuerraouI +4
The possibility of adversarial (a.k.a., {\em Byzantine}) clients makes federated learning (FL) prone to arbitrary manipulation. The natural approach to robustify FL against adversa…
On the Inherent Anonymity of Gossiping
Rachid Guerraoui, Anne-Marie Kermarrec, Anastasiia Kucherenko +2
Detecting the source of a gossip is a critical issue, related to identifying patient zero in an epidemic, or the origin of a rumor in a social network. Although it is widely acknow…
Near-Optimal Leader Election in Population Protocols on Graphs
Dan Alistarh, Joel Rybicki, Sasha Voitovych
In the stochastic population protocol model, we are given a connected graph with nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and…