%%%%%%%% 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[accepted]{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 NonIIDness 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 non-independent and identically
distributed (non-IID) data partitions, even more so in a fully decentralized
setting without a central server. In this paper, we show that the impact of
\textit{local class bias}, an important type of data non-IIDness, 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 interconnected cliques such
that the local joint distribution in a clique is representative of the global
class 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}