main.tex

%%%%%%%% mlsys 2022 EXAMPLE LATEX SUBMISSION FILE %%%%%%%%%%%%%%%%%

\documentclass{article}

% Recommended, but optional, packages for figures and better typesetting:
%\usepackage{microtype}
\usepackage{graphicx}
\usepackage{booktabs} % for professional tables
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{amssymb}
\usepackage{xcolor}
\usepackage{soul}
\usepackage[noend]{algorithmic}
%\usepackage[noend]{algpseudocode}
\usepackage{dsfont}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{todonotes}

% hyperref makes hyperlinks in the resulting PDF.
% If your build breaks (sometimes temporarily if a hyperlink spans a page)
% please comment out the following usepackage line and replace
% \usepackage{mlsys2022} with \usepackage[nohyperref]{mlsys2022} above.
\usepackage{hyperref}

% Attempt to make hyperref and algorithmic work together better:
\newcommand{\theHalgorithm}{\arabic{algorithm}}

% Use the following line for the initial blind version submitted for review:
%\usepackage{mlsys2022}

% If accepted, instead use the following line for the camera-ready submission:
 \usepackage{mlsys2022}

% The \mlsystitle you define below is probably too long as a header.
% Therefore, a short form for the running title is supplied here:
%\mlsystitlerunning{D-Cliques}

\begin{document}

\twocolumn[
\mlsystitle{D-Cliques: Compensating for Data Heterogeneity with Topology in
Decentralized Federated Learning}

% It is OKAY to include author information, even for blind
% submissions: the style file will automatically remove it for you
% unless you've provided the [accepted] option to the mlsys2022
% package.

% List of affiliations: The first argument should be a (short)
% identifier you will use later to specify author affiliations
% Academic affiliations should list Department, University, City, Region, Country
% Industry affiliations should list Company, City, Region, Country

% You can specify symbols, otherwise they are numbered in order.
% Ideally, you should not use this facility. Affiliations will be numbered
% in order of appearance and this is the preferred way.
%\mlsyssetsymbol{equal}{*}

\begin{mlsysauthorlist}
\mlsysauthor{Aur\'elien Bellet}{inria-lille}
\mlsysauthor{Anne-Marie Kermarrec}{epfl}
\mlsysauthor{Erick Lavoie}{epfl}
\end{mlsysauthorlist}

\mlsysaffiliation{epfl}{EPFL, Lausanne, Switzerland}
\mlsysaffiliation{inria-lille}{Inria, Lille, France}

\mlsyscorrespondingauthor{Erick Lavoie}{erick.lavoie@epfl.ch}

% You may provide any keywords that you
% find helpful for describing your paper; these are used to populate
% the "keywords" metadata in the PDF but will not be shown in the document
\mlsyskeywords{Decentralized Learning, Federated Learning, Topology,
Non-IID Data, Stochastic Gradient Descent}

\vskip 0.3in

\begin{abstract}
%This document provides a basic paper template and submission guidelines.
%Abstracts must be a single paragraph, ideally between 4--6 sentences long.
%Gross violations will trigger corrections at the camera-ready phase.
The convergence speed of machine learning models trained with Federated
Learning is significantly affected by heterogeneous data partitions, even more
so in a fully decentralized setting without a central server. In this paper, we show that the impact of
label distribution skew, an important type of data heterogeneity, can be
significantly reduced by carefully designing
the underlying communication topology. We present D-Cliques, a novel topology
that reduces gradient bias by grouping nodes in sparsely interconnected
cliques such that the label distribution in a clique is representative
of the global label distribution. We also show how to adapt the updates of
decentralized SGD
to obtain unbiased gradients and implement an effective momentum with
D-Cliques. Our empirical evaluation on MNIST and CIFAR10 demonstrates that our approach
provides similar convergence speed as a fully-connected topology with a
significant reduction in the number of edges and messages. In a 1000-node
topology, D-Cliques requires 98\% less edges and 96\% less total messages,
with further possible gains using a small-world topology across cliques.
\end{abstract}
]

% this must go after the closing bracket ] following \twocolumn[ ...

% This command actually creates the footnote in the first column
% listing the affiliations and the copyright notice.
% The command takes one argument, which is text to display at the start of the footnote.
% The \mlsysEqualContribution command is standard text for equal contribution.
% Remove it (just {}) if you do not need this facility.

%\printAffiliationsAndNotice{}  % leave blank if no need to mention equal contribution
\printAffiliationsAndNotice{\mlsysEqualContribution} % otherwise use the standard text.

\input{intro}
\input{setting}
\input{d-cliques}
\input{exp}
\input{related_work}
\input{conclu}

\bibliography{main.bib}
\bibliographystyle{mlsys2022}

\input{appendix}

\end{document}