Publication

On the Strategyproofness of the Geometric Median

Résumé

The geometric median, an instrumental component of the secure machine learning toolbox, is known to be effective when robustly aggregating models (or gradients), gathered from potentially malicious (or strategic) users. What is less known is the extent to which the geometric median incentivizes dishonest behaviors. This paper addresses this fundamental question by quantifying its strategyproofness. While we observe that the geometric median is not even approximately strategyproof, we prove that it is asymptotically α-strategyproof: when the number of users is large enough, a user that misbehaves can gain at most a multiplicative factor α, which we compute as a function of the distribution followed by the users. We then generalize our results to the case where users actually care more about specific dimensions, determining how this impacts α. We also show how the skewed geometric medians can be used to improve strategyproofness.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Concepts associés (16)
Médiane (statistiques)
En théorie des probabilités et en statistiques, la médiane est une valeur qui sépare la moitié inférieure et la moitié supérieure des termes d’une série statistique quantitative ou d’une variable aléatoire réelle. On peut la définir aussi pour une variable ordinale. La médiane est un indicateur de tendance centrale. Par comparaison avec la moyenne, elle est insensible aux valeurs extrêmes mais son calcul est un petit peu plus complexe. En particulier, elle ne peut s’obtenir à partir des médianes de sous-groupes.
Loi géométrique
En théorie des probabilités et en statistique, la loi géométrique désigne, selon la convention choisie, l'une des deux lois de probabilité suivantes : la loi du nombre X d'épreuves de Bernoulli indépendantes de probabilité de succès p ∈ ]0,1[ (ou q = 1 – p d'échec) nécessaire pour obtenir le premier succès. X est la variable aléatoire donnant le rang du premier succès. Le support de la loi est alors {1, 2, 3, ...}. La loi du nombre Y = X – 1 d'échecs avant le premier succès. Le support de la loi est alors {0, 1, 2, 3, .
Geometric median
In geometry, the geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances for one-dimensional data, and provides a central tendency in higher dimensions. It is also known as the 1-median, spatial median, Euclidean minisum point, or Torricelli point. The geometric median is an important estimator of location in statistics, where it is also known as the L1 estimator (after the L1 norm).
Afficher plus
Publications associées (7)

Predictive performance of multi-model ensemble forecasts of COVID-19 across European nations

Ekaterina Krymova, Nicola Parolini, Andrea Kraus, David Kraus, Daniel Lopez, Markus Scholz, Tao Sun

Background:Short-term forecasts of infectious disease burden can contribute to situational awareness and aid capacity planning. Based on best practice in other fields and recent insights in infectious disease epidemiology, one can maximise the predictive p ...
eLIFE SCIENCES PUBL LTD2023

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

Function Computation over Networks

Chien-Yi Wang

This thesis looks at efficient information processing for two network applications: content delivery with caching and collecting summary statistics in wireless sensor networks. Both applications are studied under the same paradigm: function computation ove ...
EPFL2015
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.