Publications related to Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

Optimization Algorithms for Decentralized, Distributed and Collaborative Machine Learning

Distributed learning is the key for enabling training of modern large-scale machine learning models, through parallelising the learning process. Collaborative learning is essential for learning from privacy-sensitive data that is distributed across various ...

EPFL2024

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Mehmet Fatih Sahin

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...

EPFL2023

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika Tapani Göös

We prove an N2-o(1) lower bound on the randomized communication complexity of finding an epsilon-approximate Nash equilibrium (for constant epsilon > 0) in a two-player N x N game. ...

Philadelphia2023

Estimation of Self-Exciting Point Processes from Time-Censored Data

Thomas Alois Weber, Philipp Schneider

Self-exciting point processes, widely used to model arrival phenomena in nature and society, are often difficult to identify. The estimation becomes even more challenging when arrivals are recorded only as bin counts on a finite partition of the observatio ...

2023

Communication Complexity of Collision

Mika Tapani Göös, Siddhartha Jain

The Collision problem is to decide whether a given list of numbers (x_1,…,x_n) ∈ [n]ⁿ is 1-to-1 or 2-to-1 when promised one of them is the case. We show an n^Ω(1) randomised communication lower bound for the natural two-party version of Collision where Ali ...

Leibniz-Zentrum für Informatik2022

Flash Freezing Flash Boys: Countering Blockchain Front-Running

Bryan Alexander Ford, Verónica del Carmen Estrada Galiñanes, Louis-Henri Manuel Jakob Merino, Haoqian Zhang

Front-running, the practice of benefiting from advanced knowledge of pending transactions, has proliferated in the cryptocurrency space with the emergence of decentralized finance. Front-running causes devastating losses to honest participants-estimated at ...

IEEE COMPUTER SOC2022

Coordinating Active Distribution Networks with Multi-Microgrids: An ADMM-based Decentralized Adjustable Robust Operation Model

Yuning Jiang

This paper proposes a decentralized adjustable robust operation model achieving the coordinated operation between an active distribution network (ADN) and microgrids (MGs). Thanks to the autonomous characteristic and heterogeneity of the individual agents ...

IEEE2022

A first-order primal-dual method with adaptivity to local smoothness

Volkan Cevher, Maria-Luiza Vladarean

We consider the problem of finding a saddle point for the convex-concave objective

\min_x \max_y f(x) + \langle Ax, y\rangle - g^*(y)

, where

f

is a convex function with locally Lipschitz gradient and

g

is convex and possibly non-smooth. We propose an ...

2021

Last iterate convergence of SGD for Least-Squares in the Interpolation regime

Nicolas Henri Bernard Flammarion, Aditya Vardhan Varre, Loucas Pillaud-Vivien

Motivated by the recent successes of neural networks that have the ability to fit the data perfectly \emph{and} generalize well, we study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs ...

2021

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Ahmet Alacaoglu

Stochastic gradient descent (SGD) and randomized coordinate descent (RCD) are two of the workhorses for training modern automated decision systems. Intriguingly, convergence properties of these methods are not well-established as we move away from the spec ...

EPFL2021

Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

Graph Chatbot

Chat with Graph Search

Optimization Algorithms for Decentralized, Distributed and Collaborative Machine Learning

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Estimation of Self-Exciting Point Processes from Time-Censored Data

Communication Complexity of Collision

Flash Freezing Flash Boys: Countering Blockchain Front-Running

Coordinating Active Distribution Networks with Multi-Microgrids: An ADMM-based Decentralized Adjustable Robust Operation Model

A first-order primal-dual method with adaptivity to local smoothness

Last iterate convergence of SGD for Least-Squares in the Interpolation regime

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Flash Freezing Flash Boys: Countering Blockchain Front-Running

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

A first-order primal-dual method with adaptivity to local smoothness

Last iterate convergence of SGD for Least-Squares in the Interpolation regime

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Estimation of Self-Exciting Point Processes from Time-Censored Data

Optimization Algorithms for Decentralized, Distributed and Collaborative Machine Learning

Communication Complexity of Collision

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Coordinating Active Distribution Networks with Multi-Microgrids: An ADMM-based Decentralized Adjustable Robust Operation Model