Publications associées à Coordinate descent

Data Downloaded via Parachute from a NASA Super-Pressure Balloon

David Richard Harvey, Mathilde Jauzac, Richard Massey, Lun Li

In April 2023, the superBIT telescope was lifted to the Earth's stratosphere by a helium-filled super-pressure balloon to acquire astronomical imaging from above (99.5% of) the Earth's atmosphere. It was launched from New Zealand and then, for 40 days, cir ...

MDPI2023

Impact of Redundancy on Resilience in Distributed Optimization and Learning

Nirupam Gupta, Shuo Liu

This paper considers the problem of resilient distributed optimization and stochastic learning in a server-based architecture. The system comprises a server and multiple agents, where each agent has its own local cost function. The agents collaborate with ...

Assoc Computing Machinery2023

Towards Stable and Efficient Adversarial Training against $l_1$ Bounded Adversarial Attacks

Sabine Süsstrunk, Mathieu Salzmann, Yulun Jiang, Chen Liu, Zhuoyi Huang

We address the problem of stably and efficiently training a deep neural network robust to adversarial perturbations bounded by an

l_1

norm. We demonstrate that achieving robustness against

l_1

-bounded perturbations is more challenging than in the

l_2

...

2023

Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity

Rachid Guerraoui, John Stephan, Sadegh Farhadkhani, Youssef Allouah, Nirupam Gupta, Rafaël Benjamin Pinot

Byzantine machine learning (ML) aims to ensure the resilience of distributed learning algorithms to misbehaving (or Byzantine) machines. Although this problem received significant attention, prior works often assume the data held by the machines to be homo ...

PMLR2023

Regularization Techniques for Low-Resource Machine Translation

Alejandro Ramírez Atrio

Neural machine translation (MT) and text generation have recently reached very high levels of quality. However, both areas share a problem: in order to reach these levels, they require massive amounts of data. When this is not present, they lack generaliza ...

EPFL2023

Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity

Rachid Guerraoui, Youssef Allouah, Geovani Rizk, Nirupam Gupta, Rafaël Benjamin Pinot

The theory underlying robust distributed learning algorithms, designed to resist adversarial machines, matches empirical observations when data is homogeneous. Under data heterogeneity however, which is the norm in practical scenarios, established lower bo ...

2023

Polynomial-time universality and limitations of deep learning

Emmanuel Abbé

The goal of this paper is to characterize function distributions that general neural networks trained by descent algorithms (GD/SGD), can or cannot learn in polytime. The results are: (1) The paradigm of general neural networks trained by SGD is poly-time ...

WILEY2023

Practical Byzantine-resilient Stochastic Gradient Descent

Sébastien Louis Alexandre Rouault

Algorithms are everywhere. The recipe for the frangipane cake is an algorithm. If all the listed ingredients are available and the cook is sufficiently deft, after a finite number of small, well-defined steps a delicious dessert will exit the oven. Now, wh ...

EPFL2022

AKSEL: Fast Byzantine SGD

Rachid Guerraoui, El Mahdi El Mhamdi, Alexandre David Olivier Maurer, Sébastien Louis Alexandre Rouault

Modern machine learning architectures distinguish servers and workers. Typically, a d-dimensional model is hosted by a server and trained by n workers, using a distributed stochastic gradient descent (SGD) optimization scheme. At each SGD step, the goal is ...

Schloss Dagstuhl--Leibniz-Zentrum für Informatik2021

Byzantine Fault-Tolerant Distributed Machine Learning with Norm-Based Comparative Gradient Elimination

Nirupam Gupta, Shuo Liu

This paper considers the Byzantine fault-tolerance problem in distributed stochastic gradient descent (D-SGD) method - a popular algorithm for distributed multi-agent machine learning. In this problem, each agent samples data points independently from a ce ...

IEEE COMPUTER SOC2021

Multi-armed Bandits in Action

Farnood Salehi

Making decisions is part and parcel of being human. Among a set of actions, we want to choose the one that has the highest reward. But the uncertainty of the outcome prevents us from always making the right decision. Making decisions under uncertainty can ...

EPFL2020

Global Convergence and Variance Reduction for a Class of Nonconvex-Nonconcave Minimax Problems

Negar Kiyavash

Nonconvex minimax problems appear frequently in emerging machine learning applications, such as generative adversarial networks and adversarial learning. Simple algorithms such as the gradient descent ascent (GDA) are the common practice for solving these ...

2020

Private and Secure Distributed Learning

Georgios Damaskinos

The ever-growing number of edge devices (e.g., smartphones) and the exploding volume of sensitive data they produce, call for distributed machine learning techniques that are privacy-preserving. Given the increasing computing capabilities of modern edge de ...

EPFL2020

Efficient Greedy Coordinate Descent for Composite Problems

Martin Jaggi, Sebastian Urban Stich, Sai Praneeth Reddy Karimireddy, Anastasiia Koloskova

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 ...

2019

Mean-Field methods for Structured Deep-Learning in Computer Vision

Pierre Bruno Baqué

In recent years, Machine Learning based Computer Vision techniques made impressive progress. These algorithms proved particularly efficient for image classification or detection of isolated objects. From a probabilistic perspective, these methods can predi ...

EPFL2018

Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization

Volkan Cevher, Quoc Tran Dinh, Ahmet Alacaoglu

We propose a new randomized coordinate descent method for a convex optimization template with broad applications. Our analysis relies on a novel combination of four ideas applied to the primal-dual gap function: smoothing, acceleration, homotopy, and coord ...

2017

Brief Announcement: Byzantine-Tolerant Machine Learning

Rachid Guerraoui, El Mahdi El Mhamdi, Peva François Blanchard, Julien Michel Stainer

We report on \emph{Krum}, the first \emph{provably} Byzantine-tolerant aggregation rule for distributed Stochastic Gradient Descent (SGD). Krum guarantees the convergence of SGD even in a distributed setting where (asymptotically) up to half of the workers ...

ACM2017

Principled Parallel Mean-Field Inference for Discrete Random Fields

Pascal Fua, François Fleuret, Pierre Bruno Baqué, Timur Bagautdinov

Mean-field variational inference is one of the most popular approaches to inference in discrete random fields. Standard mean-field optimization is based on coordinate descent and in many situations can be impractical. Thus, in practice, various parallel te ...

2016

Decomposition Strategies for Nonconvex Problems, a Parametric Approach

Jean-Hubert Hours

This thesis deals with the development of numerical methods for solving nonconvex optimisation problems by means of decomposition and continuation techniques. We first introduce a novel decomposition algorithm based on alternating gradient projections and ...

EPFL2016