\section{Introduction}

Please follow the steps outlined below when submitting your manuscript to
the IEEE Computer Society Press.  This style guide now has several
important modifications (for example, you are no longer warned against the
use of sticky tape to attach your artwork to the paper), so all authors
should read this new version.

\subsection{Language}

All manuscripts must be in English.

\subsection{Dual submission}

Please refer to the author guidelines on the ICCV 2021 web page for a
discussion of the policy on dual submissions.

\subsection{Paper length}
Papers, excluding the references section,
must be no longer than eight pages in length. The references section
will not be included in the page count, and there is no limit on the
length of the references section. For example, a paper of eight pages
with two pages of references would have a total length of 10 pages.
{\bf There will be no extra page charges for ICCV 2021.}

Overlength papers will simply not be reviewed.  This includes papers
where the margins and formatting are deemed to have been significantly
altered from those laid down by this style guide.  Note that this
\LaTeX\ guide already sets figure captions and references in a smaller font.
The reason such papers will not be reviewed is that there is no provision for
supervised revisions of manuscripts.  The reviewing process cannot determine
the suitability of the paper for presentation in eight pages if it is
reviewed in eleven.  

\subsection{The ruler}
The \LaTeX\ style defines a printed ruler which should be present in the
version submitted for review.  The ruler is provided in order that
reviewers may comment on particular lines in the paper without
circumlocution.  If you are preparing a document using a non-\LaTeX\
document preparation system, please arrange for an equivalent ruler to
appear on the final output pages.  The presence or absence of the ruler
should not change the appearance of any other content on the page.  The
camera ready copy should not contain a ruler. (\LaTeX\ users may uncomment
the \verb'\iccvfinalcopy' command in the document preamble.)  Reviewers:
note that the ruler measurements do not align well with lines in the paper
--- this turns out to be very difficult to do well when the paper contains
many figures and equations, and, when done, looks ugly.  Just use fractional
references (e.g.\ this line is $095.5$), although in most cases one would
expect that the approximate location will be adequate.

\subsection{Mathematics}

Please number all of your sections and displayed equations.  It is
important for readers to be able to refer to any particular equation.  Just
because you didn't refer to it in the text doesn't mean some future reader
might not need to refer to it.  It is cumbersome to have to use
circumlocutions like ``the equation second from the top of page 3 column
1''.  (Note that the ruler will not be present in the final copy, so is not
an alternative to equation numbers).  All authors will benefit from reading
Mermin's description of how to write mathematics:
\url{http://www.pamitc.org/documents/mermin.pdf}.

\subsection{Blind review}

Many authors misunderstand the concept of anonymizing for blind
review.  Blind review does not mean that one must remove
citations to one's own work---in fact it is often impossible to
review a paper unless the previous citations are known and
available.

Blind review means that you do not use the words ``my'' or ``our''
when citing previous work.  That is all.  (But see below for
tech reports.)

Saying ``this builds on the work of Lucy Smith [1]'' does not say
that you are Lucy Smith; it says that you are building on her
work.  If you are Smith and Jones, do not say ``as we show in
[7]'', say ``as Smith and Jones show in [7]'' and at the end of the
paper, include reference 7 as you would any other cited work.

An example of a bad paper just asking to be rejected:
\begin{quote}
\begin{center}
    An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of our
   previous paper [1], and show it to be inferior to all
   previously known methods.  Why the previous paper was
   accepted without this analysis is beyond me.

   [1] Removed for blind review
\end{quote}

An example of an acceptable paper:

\begin{quote}
\begin{center}
     An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of the
   paper of Smith \etal [1], and show it to be inferior to
   all previously known methods.  Why the previous paper
   was accepted without this analysis is beyond me.

   [1] Smith, L and Jones, C. ``The frobnicatable foo
   filter, a fundamental contribution to human knowledge''.
   Nature 381(12), 1-213.
\end{quote}

If you are making a submission to another conference at the same time,
which covers similar or overlapping material, you may need to refer to that
submission in order to explain the differences, just as you would if you
had previously published related work.  In such cases, include the
anonymized parallel submission~\cite{Authors14} as additional material and
cite it as
\begin{quote}
[1] Authors. ``The frobnicatable foo filter'', F\&G 2014 Submission ID 324,
Supplied as additional material {\tt fg324.pdf}.
\end{quote}

Finally, you may feel you need to tell the reader that more details can be
found elsewhere, and refer them to a technical report.  For conference
submissions, the paper must stand on its own, and not {\em require} the
reviewer to go to a tech report for further details.  Thus, you may say in
the body of the paper ``further details may be found
in~\cite{Authors14b}''.  Then submit the tech report as additional material.
Again, you may not assume the reviewers will read this material.

Sometimes your paper is about a problem which you tested using a tool which
is widely known to be restricted to a single institution.  For example,
let's say it's 1969, you have solved a key problem on the Apollo lander,
and you believe that the ICCV70 audience would like to hear about your
solution.  The work is a development of your celebrated 1968 paper entitled
``Zero-g frobnication: How being the only people in the world with access to
the Apollo lander source code makes us a wow at parties'', by Zeus \etal.

You can handle this paper like any other.  Don't write ``We show how to
improve our previous work [Anonymous, 1968].  This time we tested the
algorithm on a lunar lander [name of lander removed for blind review]''.
That would be silly, and would immediately identify the authors. Instead
write the following:
\begin{quotation}
\noindent
   We describe a system for zero-g frobnication.  This
   system is new because it handles the following cases:
   A, B.  Previous systems [Zeus et al. 1968] didn't
   handle case B properly.  Ours handles it by including
   a foo term in the bar integral.

   ...

   The proposed system was integrated with the Apollo
   lunar lander, and went all the way to the moon, don't
   you know.  It displayed the following behaviours
   which show how well we solved cases A and B: ...
\end{quotation}
As you can see, the above text follows standard scientific convention,
reads better than the first version, and does not explicitly name you as
the authors.  A reviewer might think it likely that the new paper was
written by Zeus \etal, but cannot make any decision based on that guess.
He or she would have to be sure that no other authors could have been
contracted to solve problem B.
\medskip

\noindent
FAQ\medskip\\
{\bf Q:} Are acknowledgements OK?\\
{\bf A:} No.  Leave them for the final copy.\medskip\\
{\bf Q:} How do I cite my results reported in open challenges?
{\bf A:} To conform with the double blind review policy, you can report results of other challenge participants together with your results in your paper. For your results, however, you should not identify yourself and should not mention your participation in the challenge. Instead present your results referring to the method proposed in your paper and draw conclusions based on the experimental comparison to other results.\medskip\\

\begin{figure}[t]
\begin{center}
\fbox{\rule{0pt}{2in} \rule{0.9\linewidth}{0pt}}
  
\end{center}
   \caption{Example of caption.  It is set in Roman so that mathematics
   (always set in Roman: $B \sin A = A \sin B$) may be included without an
   ugly clash.}
\label{fig:long}
\label{fig:onecol}
\end{figure}

\subsection{Miscellaneous}

\noindent
Compare the following:\\
\begin{tabular}{ll}
 \verb'$conf_a$' &  $conf_a$ \\
 \verb'$\mathit{conf}_a$' & $\mathit{conf}_a$
\end{tabular}\\
See The \TeX book, p165.

The space after \eg, meaning ``for example'', should not be a
sentence-ending space. So \eg is correct, {\em e.g.} is not.  The provided
\verb'\eg' macro takes care of this.

When citing a multi-author paper, you may save space by using ``et alia'',
shortened to ``\etal'' (not ``{\em et.\ al.}'' as ``{\em et}'' is a complete word.)
However, use it only when there are three or more authors.  Thus, the
following is correct: ``
   Frobnication has been trendy lately.
   It was introduced by Alpher~\cite{Alpher02}, and subsequently developed by
   Alpher and Fotheringham-Smythe~\cite{Alpher03}, and Alpher \etal~\cite{Alpher04}.''

This is incorrect: ``... subsequently developed by Alpher \etal~\cite{Alpher03} ...''
because reference~\cite{Alpher03} has just two authors.  If you use the
\verb'\etal' macro provided, then you need not worry about double periods
when used at the end of a sentence as in Alpher \etal.

For this citation style, keep multiple citations in numerical (not
chronological) order, so prefer \cite{Alpher03,Alpher02,Authors14} to
\cite{Alpher02,Alpher03,Authors14}.

\begin{figure*}
\begin{center}
\fbox{\rule{0pt}{2in} \rule{.9\linewidth}{0pt}}
\end{center}
   \caption{Example of a short caption, which should be centered.}
\label{fig:short}
\end{figure*}

\section{Formatting your paper}

All text must be in a two-column format. The total allowable width of the
text area is $6\frac78$ inches (17.5 cm) wide by $8\frac78$ inches (22.54
cm) high. Columns are to be $3\frac14$ inches (8.25 cm) wide, with a
$\frac{5}{16}$ inch (0.8 cm) space between them. The main title (on the
first page) should begin 1.0 inch (2.54 cm) from the top edge of the
page. The second and following pages should begin 1.0 inch (2.54 cm) from
the top edge. On all pages, the bottom margin should be 1-1/8 inches (2.86
cm) from the bottom edge of the page for $8.5 \times 11$-inch paper; for A4
paper, approximately 1-5/8 inches (4.13 cm) from the bottom edge of the
page.

\subsection{Margins and page numbering}

All printed material, including text, illustrations, and charts, must be kept
within a print area 6-7/8 inches (17.5 cm) wide by 8-7/8 inches (22.54 cm)
high.

Page numbers should be included for review submissions but not for the 
final paper. Review submissions papers should have page numbers in the 
footer with numbers centered and .75 inches (1.905 cm) from the bottom 
of the page and start on the first page with the number 1.

Page numbers will be added by the publisher to all camera-ready papers 
prior to including them in the proceedings and before submitting the 
papers to IEEE Xplore. As such, your camera-ready submission should 
not include any page numbers. Page numbers should automatically be 
removed by uncommenting (if it's not already) the line
\begin{verbatim}
\end{verbatim}
near the beginning of the .tex file.

\subsection{Type-style and fonts}

Wherever Times is specified, Times Roman may also be used. If neither is
available on your word processor, please use the font closest in
appearance to Times to which you have access.

MAIN TITLE. Center the title 1-3/8 inches (3.49 cm) from the top edge of
the first page. The title should be in Times 14-point, boldface type.
Capitalize the first letter of nouns, pronouns, verbs, adjectives, and
adverbs; do not capitalize articles, coordinate conjunctions, or
prepositions (unless the title begins with such a word). Leave two blank
lines after the title.

AUTHOR NAME(s) and AFFILIATION(s) are to be centered beneath the title
and printed in Times 12-point, non-boldface type. This information is to
be followed by two blank lines.

The ABSTRACT and MAIN TEXT are to be in a two-column format.

MAIN TEXT. Type main text in 10-point Times, single-spaced. Do NOT use
double-spacing. All paragraphs should be indented 1 pica (approx. 1/6
inch or 0.422 cm). Make sure your text is fully justified---that is,
flush left and flush right. Please do not place any additional blank
lines between paragraphs.

Figure and table captions should be 9-point Roman type as in
Figures~\ref{fig:onecol} and~\ref{fig:short}.  Short captions should be centered.

\noindent Callouts should be 9-point Helvetica, non-boldface type.
Initially capitalize only the first word of section titles and first-,
second-, and third-order headings.

FIRST-ORDER HEADINGS. (For example, {\large \bf 1. Introduction})
should be Times 12-point boldface, initially capitalized, flush left,
with one blank line before, and one blank line after.

SECOND-ORDER HEADINGS. (For example, { \bf 1.1. Database elements})
should be Times 11-point boldface, initially capitalized, flush left,
with one blank line before, and one after. If you require a third-order
heading (we discourage it), use 10-point Times, boldface, initially
capitalized, flush left, preceded by one blank line, followed by a period
and your text on the same line.

\subsection{Footnotes}

Please use footnotes\footnote {This is what a footnote looks like.  It
often distracts the reader from the main flow of the argument.} sparingly.
Indeed, try to avoid footnotes altogether and include necessary peripheral
observations in
the text (within parentheses, if you prefer, as in this sentence).  If you
wish to use a footnote, place it at the bottom of the column on the page on
which it is referenced. Use Times 8-point type, single-spaced.

\subsection{References}

List and number all bibliographical references in 9-point Times,
single-spaced, at the end of your paper. When referenced in the text,
enclose the citation number in square brackets, for
example~\cite{Authors14}.  Where appropriate, include the name(s) of
editors of referenced books.

\begin{table}
\begin{center}
\begin{tabular}{|l|c|}
\hline
Method & Frobnability \\
\hline\hline
Theirs & Frumpy \\
Yours & Frobbly \\
Ours & Makes one's heart Frob\\
\hline
\end{tabular}
\end{center}
\caption{Results.   Ours is better.}
\end{table}

\subsection{Illustrations, graphs, and photographs}

All graphics should be centered.  Please ensure that any point you wish to
make is resolvable in a printed copy of the paper.  Resize fonts in figures
to match the font in the body text, and choose line widths which render
effectively in print.  Many readers (and reviewers), even of an electronic
copy, will choose to print your paper in order to read it.  You cannot
insist that they do otherwise, and therefore must not assume that they can
zoom in to see tiny details on a graphic.

When placing figures in \LaTeX, it's almost always best to use
\verb+\includegraphics+, and to specify the  figure width as a multiple of
the line width as in the example below
{\small\begin{verbatim}
   \usepackage[dvips]{graphicx} ...
   \includegraphics[width=0.8\linewidth]
                   {myfile.eps}
\end{verbatim}
}

\subsection{Color}

Please refer to the author guidelines on the ICCV 2021 web page for a discussion
of the use of color in your document.

\section{Final copy}

You must include your signed IEEE copyright release form when you submit
your finished paper. We MUST have this form before your paper can be
published in the proceedings.

{\small
\bibliographystyle{ieee_fullname}

\section{Introduction}

Please follow the steps outlined below when submitting your manuscript to
the IEEE Computer Society Press.  This style guide now has several
important modifications (for example, you are no longer warned against the
use of sticky tape to attach your artwork to the paper), so all authors
should read this new version.

\subsection{Language}

All manuscripts must be in English.

\subsection{Dual submission}

Please refer to the author guidelines on the ICCV 2021 web page for a
discussion of the policy on dual submissions.

\subsection{Paper length}
Papers, excluding the references section,
must be no longer than eight pages in length. The references section
will not be included in the page count, and there is no limit on the
length of the references section. For example, a paper of eight pages
with two pages of references would have a total length of 10 pages.
{\bf There will be no extra page charges for ICCV 2021.}

Overlength papers will simply not be reviewed.  This includes papers
where the margins and formatting are deemed to have been significantly
altered from those laid down by this style guide.  Note that this
\LaTeX\ guide already sets figure captions and references in a smaller font.
The reason such papers will not be reviewed is that there is no provision for
supervised revisions of manuscripts.  The reviewing process cannot determine
the suitability of the paper for presentation in eight pages if it is
reviewed in eleven.  

\subsection{The ruler}
The \LaTeX\ style defines a printed ruler which should be present in the
version submitted for review.  The ruler is provided in order that
reviewers may comment on particular lines in the paper without
circumlocution.  If you are preparing a document using a non-\LaTeX\
document preparation system, please arrange for an equivalent ruler to
appear on the final output pages.  The presence or absence of the ruler
should not change the appearance of any other content on the page.  The
camera ready copy should not contain a ruler. (\LaTeX\ users may uncomment
the \verb'\iccvfinalcopy' command in the document preamble.)  Reviewers:
note that the ruler measurements do not align well with lines in the paper
--- this turns out to be very difficult to do well when the paper contains
many figures and equations, and, when done, looks ugly.  Just use fractional
references (e.g.\ this line is $095.5$), although in most cases one would
expect that the approximate location will be adequate.

\subsection{Mathematics}

Please number all of your sections and displayed equations.  It is
important for readers to be able to refer to any particular equation.  Just
because you didn't refer to it in the text doesn't mean some future reader
might not need to refer to it.  It is cumbersome to have to use
circumlocutions like ``the equation second from the top of page 3 column
1''.  (Note that the ruler will not be present in the final copy, so is not
an alternative to equation numbers).  All authors will benefit from reading
Mermin's description of how to write mathematics:
\url{http://www.pamitc.org/documents/mermin.pdf}.

\subsection{Blind review}

Many authors misunderstand the concept of anonymizing for blind
review.  Blind review does not mean that one must remove
citations to one's own work---in fact it is often impossible to
review a paper unless the previous citations are known and
available.

Blind review means that you do not use the words ``my'' or ``our''
when citing previous work.  That is all.  (But see below for
tech reports.)

Saying ``this builds on the work of Lucy Smith [1]'' does not say
that you are Lucy Smith; it says that you are building on her
work.  If you are Smith and Jones, do not say ``as we show in
[7]'', say ``as Smith and Jones show in [7]'' and at the end of the
paper, include reference 7 as you would any other cited work.

An example of a bad paper just asking to be rejected:
\begin{quote}
\begin{center}
    An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of our
   previous paper [1], and show it to be inferior to all
   previously known methods.  Why the previous paper was
   accepted without this analysis is beyond me.

   [1] Removed for blind review
\end{quote}

An example of an acceptable paper:

\begin{quote}
\begin{center}
     An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of the
   paper of Smith \etal [1], and show it to be inferior to
   all previously known methods.  Why the previous paper
   was accepted without this analysis is beyond me.

   [1] Smith, L and Jones, C. ``The frobnicatable foo
   filter, a fundamental contribution to human knowledge''.
   Nature 381(12), 1-213.
\end{quote}

If you are making a submission to another conference at the same time,
which covers similar or overlapping material, you may need to refer to that
submission in order to explain the differences, just as you would if you
had previously published related work.  In such cases, include the
anonymized parallel submission~\cite{Authors14} as additional material and
cite it as
\begin{quote}
[1] Authors. ``The frobnicatable foo filter'', F\&G 2014 Submission ID 324,
Supplied as additional material {\tt fg324.pdf}.
\end{quote}

Finally, you may feel you need to tell the reader that more details can be
found elsewhere, and refer them to a technical report.  For conference
submissions, the paper must stand on its own, and not {\em require} the
reviewer to go to a tech report for further details.  Thus, you may say in
the body of the paper ``further details may be found
in~\cite{Authors14b}''.  Then submit the tech report as additional material.
Again, you may not assume the reviewers will read this material.

Sometimes your paper is about a problem which you tested using a tool which
is widely known to be restricted to a single institution.  For example,
let's say it's 1969, you have solved a key problem on the Apollo lander,
and you believe that the ICCV70 audience would like to hear about your
solution.  The work is a development of your celebrated 1968 paper entitled
``Zero-g frobnication: How being the only people in the world with access to
the Apollo lander source code makes us a wow at parties'', by Zeus \etal.

You can handle this paper like any other.  Don't write ``We show how to
improve our previous work [Anonymous, 1968].  This time we tested the
algorithm on a lunar lander [name of lander removed for blind review]''.
That would be silly, and would immediately identify the authors. Instead
write the following:
\begin{quotation}
\noindent
   We describe a system for zero-g frobnication.  This
   system is new because it handles the following cases:
   A, B.  Previous systems [Zeus et al. 1968] didn't
   handle case B properly.  Ours handles it by including
   a foo term in the bar integral.

   ...

   The proposed system was integrated with the Apollo
   lunar lander, and went all the way to the moon, don't
   you know.  It displayed the following behaviours
   which show how well we solved cases A and B: ...
\end{quotation}
As you can see, the above text follows standard scientific convention,
reads better than the first version, and does not explicitly name you as
the authors.  A reviewer might think it likely that the new paper was
written by Zeus \etal, but cannot make any decision based on that guess.
He or she would have to be sure that no other authors could have been
contracted to solve problem B.
\medskip

\noindent
FAQ\medskip\\
{\bf Q:} Are acknowledgements OK?\\
{\bf A:} No.  Leave them for the final copy.\medskip\\
{\bf Q:} How do I cite my results reported in open challenges?
{\bf A:} To conform with the double blind review policy, you can report results of other challenge participants together with your results in your paper. For your results, however, you should not identify yourself and should not mention your participation in the challenge. Instead present your results referring to the method proposed in your paper and draw conclusions based on the experimental comparison to other results.\medskip\\

\begin{figure}[t]
\begin{center}
\fbox{\rule{0pt}{2in} \rule{0.9\linewidth}{0pt}}
  
\end{center}
   \caption{Example of caption.  It is set in Roman so that mathematics
   (always set in Roman: $B \sin A = A \sin B$) may be included without an
   ugly clash.}
\label{fig:long}
\label{fig:onecol}
\end{figure}

\subsection{Miscellaneous}

\noindent
Compare the following:\\
\begin{tabular}{ll}
 \verb'$conf_a$' &  $conf_a$ \\
 \verb'$\mathit{conf}_a$' & $\mathit{conf}_a$
\end{tabular}\\
See The \TeX book, p165.

The space after \eg, meaning ``for example'', should not be a
sentence-ending space. So \eg is correct, {\em e.g.} is not.  The provided
\verb'\eg' macro takes care of this.

When citing a multi-author paper, you may save space by using ``et alia'',
shortened to ``\etal'' (not ``{\em et.\ al.}'' as ``{\em et}'' is a complete word.)
However, use it only when there are three or more authors.  Thus, the
following is correct: ``
   Frobnication has been trendy lately.
   It was introduced by Alpher~\cite{Alpher02}, and subsequently developed by
   Alpher and Fotheringham-Smythe~\cite{Alpher03}, and Alpher \etal~\cite{Alpher04}.''

This is incorrect: ``... subsequently developed by Alpher \etal~\cite{Alpher03} ...''
because reference~\cite{Alpher03} has just two authors.  If you use the
\verb'\etal' macro provided, then you need not worry about double periods
when used at the end of a sentence as in Alpher \etal.

For this citation style, keep multiple citations in numerical (not
chronological) order, so prefer \cite{Alpher03,Alpher02,Authors14} to
\cite{Alpher02,Alpher03,Authors14}.

\begin{figure*}
\begin{center}
\fbox{\rule{0pt}{2in} \rule{.9\linewidth}{0pt}}
\end{center}
   \caption{Example of a short caption, which should be centered.}
\label{fig:short}
\end{figure*}

\section{Formatting your paper}

All text must be in a two-column format. The total allowable width of the
text area is $6\frac78$ inches (17.5 cm) wide by $8\frac78$ inches (22.54
cm) high. Columns are to be $3\frac14$ inches (8.25 cm) wide, with a
$\frac{5}{16}$ inch (0.8 cm) space between them. The main title (on the
first page) should begin 1.0 inch (2.54 cm) from the top edge of the
page. The second and following pages should begin 1.0 inch (2.54 cm) from
the top edge. On all pages, the bottom margin should be 1-1/8 inches (2.86
cm) from the bottom edge of the page for $8.5 \times 11$-inch paper; for A4
paper, approximately 1-5/8 inches (4.13 cm) from the bottom edge of the
page.

\subsection{Margins and page numbering}

All printed material, including text, illustrations, and charts, must be kept
within a print area 6-7/8 inches (17.5 cm) wide by 8-7/8 inches (22.54 cm)
high.

Page numbers should be included for review submissions but not for the 
final paper. Review submissions papers should have page numbers in the 
footer with numbers centered and .75 inches (1.905 cm) from the bottom 
of the page and start on the first page with the number 1.

Page numbers will be added by the publisher to all camera-ready papers 
prior to including them in the proceedings and before submitting the 
papers to IEEE Xplore. As such, your camera-ready submission should 
not include any page numbers. Page numbers should automatically be 
removed by uncommenting (if it's not already) the line
\begin{verbatim}
\end{verbatim}
near the beginning of the .tex file.

\subsection{Type-style and fonts}

Wherever Times is specified, Times Roman may also be used. If neither is
available on your word processor, please use the font closest in
appearance to Times to which you have access.

MAIN TITLE. Center the title 1-3/8 inches (3.49 cm) from the top edge of
the first page. The title should be in Times 14-point, boldface type.
Capitalize the first letter of nouns, pronouns, verbs, adjectives, and
adverbs; do not capitalize articles, coordinate conjunctions, or
prepositions (unless the title begins with such a word). Leave two blank
lines after the title.

AUTHOR NAME(s) and AFFILIATION(s) are to be centered beneath the title
and printed in Times 12-point, non-boldface type. This information is to
be followed by two blank lines.

The ABSTRACT and MAIN TEXT are to be in a two-column format.

MAIN TEXT. Type main text in 10-point Times, single-spaced. Do NOT use
double-spacing. All paragraphs should be indented 1 pica (approx. 1/6
inch or 0.422 cm). Make sure your text is fully justified---that is,
flush left and flush right. Please do not place any additional blank
lines between paragraphs.

Figure and table captions should be 9-point Roman type as in
Figures~\ref{fig:onecol} and~\ref{fig:short}.  Short captions should be centered.

\noindent Callouts should be 9-point Helvetica, non-boldface type.
Initially capitalize only the first word of section titles and first-,
second-, and third-order headings.

FIRST-ORDER HEADINGS. (For example, {\large \bf 1. Introduction})
should be Times 12-point boldface, initially capitalized, flush left,
with one blank line before, and one blank line after.

SECOND-ORDER HEADINGS. (For example, { \bf 1.1. Database elements})
should be Times 11-point boldface, initially capitalized, flush left,
with one blank line before, and one after. If you require a third-order
heading (we discourage it), use 10-point Times, boldface, initially
capitalized, flush left, preceded by one blank line, followed by a period
and your text on the same line.

\subsection{Footnotes}

Please use footnotes\footnote {This is what a footnote looks like.  It
often distracts the reader from the main flow of the argument.} sparingly.
Indeed, try to avoid footnotes altogether and include necessary peripheral
observations in
the text (within parentheses, if you prefer, as in this sentence).  If you
wish to use a footnote, place it at the bottom of the column on the page on
which it is referenced. Use Times 8-point type, single-spaced.

\subsection{References}

List and number all bibliographical references in 9-point Times,
single-spaced, at the end of your paper. When referenced in the text,
enclose the citation number in square brackets, for
example~\cite{Authors14}.  Where appropriate, include the name(s) of
editors of referenced books.

\begin{table}
\begin{center}
\begin{tabular}{|l|c|}
\hline
Method & Frobnability \\
\hline\hline
Theirs & Frumpy \\
Yours & Frobbly \\
Ours & Makes one's heart Frob\\
\hline
\end{tabular}
\end{center}
\caption{Results.   Ours is better.}
\end{table}

\subsection{Illustrations, graphs, and photographs}

All graphics should be centered.  Please ensure that any point you wish to
make is resolvable in a printed copy of the paper.  Resize fonts in figures
to match the font in the body text, and choose line widths which render
effectively in print.  Many readers (and reviewers), even of an electronic
copy, will choose to print your paper in order to read it.  You cannot
insist that they do otherwise, and therefore must not assume that they can
zoom in to see tiny details on a graphic.

When placing figures in \LaTeX, it's almost always best to use
\verb+\includegraphics+, and to specify the  figure width as a multiple of
the line width as in the example below
{\small\begin{verbatim}
   \usepackage[dvips]{graphicx} ...
   \includegraphics[width=0.8\linewidth]
                   {myfile.eps}
\end{verbatim}
}

\subsection{Color}

Please refer to the author guidelines on the ICCV 2021 web page for a discussion
of the use of color in your document.

\section{Final copy}

You must include your signed IEEE copyright release form when you submit
your finished paper. We MUST have this form before your paper can be
published in the proceedings.

{\small
\bibliographystyle{ieee_fullname}

\section{Introduction}

Efficient distributed training across multiple computing nodes is critical for large-scale deep learning tasks nowadays. As a principal training algorithm, Parallel SGD computes a globally averaged gradient either using the {\em Parameter Server (PS)} \cite{li2014scaling} or the {\em All-Reduce} communication primitive \cite{patarasuk2009bandwidth}. 
Such global synchronization across all nodes either incurs significant bandwidth cost or high latency that can severely hamper the training scalability. 

Decentralized SGD \cite{nedic2009distributed, chen2012diffusion, lian2017can, lian2018asynchronous, assran2019stochastic} based on {\em partial averaging} has become one of the major approaches in the past decade to reduce communication overhead in distributed optimization. Partial averaging, as opposed to {\em global averaging} used in Parallel SGD, requires every node to compute the average of the nodes in its neighborhood, see Fig.~\ref{fig:decen_comm}. If a sparse topology such as one-peer exponential graph \cite{assran2019stochastic} is utilized to connect all nodes, each node only communicates with {\em one} neighbor {\em each} iteration and hence saves remarkable communications. Decentralized SGD can typically achieve $1.3\sim2\times$ training time speedup without performance degradation \cite{lian2017can,assran2019stochastic,kong2021consensus}. 

Existing Decentralized SGD methods \cite{lian2017can,lian2018asynchronous,tang2018d,lin2021quasi,assran2019stochastic} and their momentum accelerated variants \cite{yu2019linear,singh2020squarm, gao2020periodic,balu2020decentralized} primarily utilize  small-batch in their algorithm design. However, recent hardware advances make it feasible to store large batches in memory and compute their gradients timely. Furthermore, the total batch size naturally grows when more computing nodes participate into training. These two primary reasons lead to the recent  exploration of large-batch deep training algorithms. 


\begin{figure}[t!]
    \centering
    \includegraphics[width=0.48\textwidth]{./images/topology.pdf}
    \vspace{-1mm}
    \caption{\small Illustration of decentralized methods. Nodes receive information from neighbors; they do not relay information. For example, nodes $4$ and $6$ collect information from their neighbors $\{1,5\}$ and $\{3,5\}$, respectively.
   
    Other nodes do the same but not depicted. Topology connectivity can be represented in a matrix, as shown in the right figure, see more details in Sec.~\ref{sec:DmSGD}. }
    \label{fig:decen_comm} \vspace{-2mm}
    \vspace{-2mm}
\end{figure}

In fact, large-batch training has been extensively studied in Parallel SGD. Pioneering works \cite{goyal2017accurate,you2017large,you2019largeb} find large-batch can significantly speed up Parallel SGD. First, the computation of a large-batch  gradient can fully utilize the computational resources (e.g., the computing nodes, the CUDA cores and GPU memories within each node). Second, large-batch gradient will result in a reduced variance and hence enables a much larger learning rate. 
With newly-proposed layer-wise adaptive rate scaling (LARS) \cite{you2017large} and its variant \cite{you2019largeb}, large-batch Parallel momentum SGD (PmSGD) can cut down the training time of BERT and Resnet-50 from days to hours \cite{you2018imagenet}.

\begin{table}[t]
\centering
\vskip 0.15in
\begin{tabular}{ccccc}
\toprule
\textbf{Dataset}           & \multicolumn{2}{c}{\textbf{Cifar-10}} & \multicolumn{2}{c}{\textbf{ImageNet}} \\
\textbf{Batch-size} & 2K    & 8K    & 2K    & 32K     \\ \midrule
\textbf{PmSGD}     & 91.6\%    & 89.2\%     & 76.5\% & 75.3\%   \\
\textbf{DmSGD}      & 91.5\%  & 88.3\%    & 76.5\%     & 74.9\%  \\ 
\bottomrule \\
\end{tabular}
\vskip -0.1in
\caption{Top-1 validation accuracy comparison between PmSGD and DmSGD under the small-batch and large-batch settings. No layer-wise adaptive rate scaling is used in any of these algorithms. All hypter-parameters are exactly the same. More experimental details can be referred to Appendix \ref{app-table-introduction}}
\vskip -0.2in
\label{talbe:motivation}
\end{table}

This naturally motivates us to study {\em how Decentralized momentum SGD (DmSGD) performs with large batch-size}. To this end, we compared PmSGD and DmSGD over Cifar-10 (Resnet-20) and ImageNet (Resnet-50) with both small and large batches.
Their performances are listed in Table \ref{talbe:motivation}. While DmSGD achieves the same accuracy as PmSGD with small batch-size, it has far more performance degradation in the large-batch scenario. This surprising observation, which reveals that the extension of DmSGD to large-batch is non-trivial, raises two fundamental questions: 
\begin{itemize}
    \item Why does DmSGD suffer from severe  performance degradation in the large-batch scenario?
    \vspace{-2mm}
    \item Is there a way to enhance the accuracy performance of large-batch DmSGD so that it can match with or even beat large-batch PmSGD?
    \vspace{-2mm}
   
\end{itemize}
This paper focuses on these questions and provides affirmative answers. In particular, our main contributions are:
\begin{itemize}
    \item We find large-batch DmSGD has severe performance degradation compared to large-batch PmSGD and have clarified the reason behind this phenomenon.  
   
    It is discovered that the momentum term can significantly amplify the inconsistency bias in DmSGD.  When batch-size is large and the gradient noise is hence dramatically reduced, such inconsistency bias gets dominant and thus degrades DmSGD's performance notably. 
    \vspace{-2mm}
    \item We propose DecentLaM, a novel \underline{decent}ralized \underline{la}rge-batch \underline{m}omentum SGD to remove the momentum-incurred bias in DmSGD. We establish its convergence rate for both non-convex and strongly-convex scenarios. Our theoretical results show that DecentLaM has superior performance to  existing decentralized momentum methods, and such superiority gets more evident as batch size gets larger.
    \vspace{-2mm}
    \item Experimental results on a variety of computer vision tasks and models show that DecentLaM outperforms various existing baselines such as DmSGD, DA/AWC/D$^2$-DmSGD, SlowMo, PmSGD, and PmSGD$+$LARS in terms of the training accuracy.
    \vspace{-2mm}
\end{itemize}

The rest of this paper is organized as follows: We briefly summarize related works in Sec.~\ref{sec:related_works} and review DmSGD in Sec.~\ref{sec:DmSGD}. We identify the issue that causes performance degradation in DmSGD (Sec.~\ref{sec:DmSG-bias}) and propose DecentLaM to resolve it (Sec.~\ref{sec:decentLaM}). The convergence analysis and experiments are established in Sec.~\ref{sec:DecentLaM_convergence} and  Sec.~\ref{sec:experiment}, respectively. 

\section{Related Works}
\label{sec:related_works}
\vspace{1mm}
\noindent \textbf{Decentralized deep training.}
Decentralized optimization can be tracked back to \cite{tsitsiklis1986distributed}. Decentralized gradient descent \cite{nedic2009distributed,yuan2016convergence}, diffusion \cite{chen2012diffusion,sayed2014adaptation} and dual averaging \cite{duchi2011dual} are among the first decentralized algorithms that target on general optimization problems arise from  signal processing and control communities. In the context of deep  learning, Decentralized SGD (DSGD) has gained a lot of attentions recently. DSGD will incur model inconsistency among computing nodes. However, it is established in \cite{lian2017can} that DSGD can reach the same linear speedup as vanilla Parallel SGD in terms of convergence rate. After that, \cite{assran2019stochastic} comes out to extend DSGD to directed topologies. A recent work \cite{koloskova2020unified} proposes a unified framework to analyze DSGD  with changing topologies and local updates. \cite{lian2018asynchronous,luo2020prague} extend DSGD to the asynchronous setting. Various communication-efficient techniques can be further integrated into DSGD such as periodic  updates \cite{stich2019local,koloskova2020unified,yu2019linear}, communication compression \cite{alistarh2017qsgd,bernstein2018signsgd,koloskova2019decentralized,koloskova2019decentralized2,tang2019doublesqueeze}, and lazy communication \cite{chen2018lag,liu2019communication}. 

\vspace{1mm}
\noindent \textbf{Momentum SGD training.} Momentum SGD  have been extensively studied due to their empirical success in deep learning. The works \cite{loizou2020momentum,yuan2016influence,gitman2019understanding,liu2020improved,yu2019linear} establish that momentum SGD converges at least as fast as SGD. Momentum SGD for overparameterized models are shown to converge faster than SGD asymptotically \cite{sebbouh2020convergence}.  The exploration in decentralized momentum SGD (DmSGD) is relatively limited.  \cite{assran2019stochastic} proposes a widely-used DmSGD approach in which a local momentum SGD step is updated first before the partial averaging is conducted (see Algorithm \ref{Algorithm: DmSGD}). This approach is extended by  \cite{singh2020squarm,gao2020periodic} to involve communication quantization and periodic local updates. Another work (Doubly-averaging DmSGD, or DA-DmSGD) \cite{yu2019linear} imposes an additional partial averaging over momentum to increase stability. \cite{wang2019slowmo} proposes a slow
momentum (SlowMo) framework, where each node periodically synchronize and
perform a momentum update. \cite{balu2020decentralized} proposes a new variant in which the partial-averaging step is mixed up with the local momentum SGD update. All these decentralize momentum methods were studied and tested with {\em small} batch sizes. 

\vspace{1mm}
\noindent \textbf{Large-batch training.} The main challenge to use large-batch lies in the generalization performance degradation. Recent works in large-batch training centered on adaptive learning rate strategies to enhance accuracy performance. For example, Adam and its variants \cite{kingma2014adam, reddi2019convergence} adjust the learning rate based on the gradient variance, 
and \cite{goyal2017accurate} utilizes learning rate warm-up and linear scaling to boost the performance in large-batch scenario. The layer-wise adaptive rate scaling \cite{you2017large,you2019large}  can reduce the training time of Resnet-50 and BERT from days to hours. However, the study of large-batch training in decentralized algorithms is quite limited. This paper does not focus on the adaptive rate strategy for decentralized algorithms. Instead, we target on clarifying why existing momentum methods result in an intrinsic convergence bias, and how to update momentum properly to remove such bias and hence improve the performance in the large-batch scenario.

\vspace{1mm}
\noindent \textbf{Decentralized methods on heterogeneous data.} Decentralized large-batch training within data-centers shares the same essence with decentralized training on heterogeneous data for EdgeAI applications. In large-batch training, the stochastic bias caused by gradient noise gets significantly reduced and the inconsistency bias caused by data heterogeneity will become dominant. \cite{tang2018d,lu2019gnsd,yuan2020influence,xin2020improved} proposed decentralized stochastic primal-dual algorithms to remedy the influence of data heterogeneity. However, none of these algorithms, due to their difficulty to be integrated with momentum acceleration, show strong effective empirical performances in commenly-used deep learning models such as ResNet-50 or EfficientNet. A concurrent work \cite{lin2021quasi} proposes Quasi-Global momentum (QG-DmSGD), which locally approximates the global optimization direction, to mitigate the affects of heterogeneous data.
It is worth noting that while DecentLaM is proposed for the large-batch setting within data-centers, it is also suitable for  EdgeAI applications where inconsistency bias resulted from heterogeneous data dominates.


\section{Decentralized Momentum SGD}
\label{sec:DmSGD}
\noindent \textbf{Problem.} Suppose $n$ computing nodes collaborate to solve the distributed optimization problem:
\begin{align}\label{dist-opt}
\min_{x \in \mathbb{R}^d}\ f(x)=\frac{1}{n}\sum_{i=1}^n [f_i(x): = \mathbb{E}_{\xi_i \sim D_i} F(x;\xi_i)]
\end{align}
where $f_i(x)$ is local to node $i$, and random variable $\xi_i$ denotes the local data that follows distribution $D_i$. Each node $i$ can locally evaluate stochastic gradient $\nabla F(x;\xi_i)$; it must communicate to access information from other nodes.

\vspace{1mm}
\noindent \textbf{Notation.} We let $[n] := \{1,\cdots,n\}$, and $\mathds{1} \in \mathbb{R}^d$ be a vector with each element being $1$. We let $\lambda_i(A)$ denote the $i$-th largest eigenvalue of matrix $A$.

\vspace{1mm}
\noindent \textbf{Network topology and weights.} Decentralized methods are based on partial averaging within neighborhood that is defined by the network topology. We assume all computing nodes are connected by an undirected network topology. Such connected  topology can be of any shape, but its degree and connectivity will affect the communication efficiency and convergence rate of the decentralized algorithm. For a given topology, we define $w_{ij}$, the weight to scale information flowing from node $j$ to node $i$, as follows:
\begin{align}\label{wij}
w_{ij}
\begin{cases}
> 0 & \mbox{if node $j$ is connected to $i$, or $i=j$;} \\
= 0 & \mbox{otherwise.}\vspace{-2mm}
\end{cases}
\end{align}
We further define $\mathcal{N}_i:=\{j|w_{ij} > 0\}$ as the set of neighbors of node $i$ which also includes node $i$ itself. We define {\em weight matrix} $W := [w_{ij}]_{i,j=1}^{n} \in \mathbb{R}^{n\times n}$ to stack all weights into a matrix. Such matrix $W$ will characterize the sparsity and connectivity of the underlying network topology. An example of the topology and its associated weight matrix $W$ is illustrated in Fig.~\ref{fig:decen_comm}.

\vspace{1mm}
\noindent \textbf{Partial averaging.}
With weights $\{w_{ij}\}$ and the set of neighbors $\mathcal{N}_i$, the neighborhood partial averaging operation of node $i$ can be expressed as 
\begin{align}\label{partial-ave}
\hspace{-10mm}
\mbox{Partial averaging:}\quad x_i^{+} \leftarrow \sum_{j\in \mathcal{N}_i}w_{ij} x_j.
\end{align}
Partial averaging has much lower communication overheads. When the network topology is sparse, partial averaging typically incurs $O(1)$ latency plus $O(1)$ bandwidth cost, which are independent of the number of computing nodes $n$. Consequently, decentralized methods are more communication efficient than those based on global averaging.

\vspace{1mm}
\noindent \textbf{Decentralized SGD (DSGD).} Given a connected network topology and weights $\{w_{ij}\}$, each node $i$ in DSGD will iterate in parallel as follows: 
\begin{align}
x_i^{(k+\frac{1}{2})} &= x_i^{(k)} - \gamma \nabla F(x_i^{(k)}; \xi_i^{(k)})\quad \mbox{(local update)} \label{dsgd-1}\\
x_i^{(k+1)} &= \sum_{j\in \mathcal{N}_i} w_{ij}\, x_j^{(k+\frac{1}{2})} \hspace{0.8cm} \mbox{(partial averaging)} \label{dsgd-2}
\end{align}
where $x_i^{(k)}$ is the local model of node $i$ at iteration $k$, $\xi_i^{(k)}$ is the realization of $\xi_i$ at iteration $k$, and $\gamma$ is the learning rate. When the network topology is fully connected and $w_{ij} = 1/n$, DSGD will reduce to the  Parallel SGD algorithm. 

\begin{algorithm}[t]
 	\DontPrintSemicolon
 	\KwRequire{Initialize $\gamma$, $x^{(0)}_{i}$; let  $m^{(0)}_{i}\hspace{-0.3mm}=\hspace{-0.3mm}0, \beta\hspace{-0.3mm}\in\hspace{-0.3mm}(0,1)$}

    \vspace{1mm}
 	\For{$k=0, 1,2,...,T-1$, every node $i$}{
 		Sample $\xi^{(k)}_{i}$ and update $\tilde{g}_i^{(k)} \hspace{-0.8mm}=\hspace{-0.8mm} {\nabla}F(x^{(k)}_{i}\hspace{-0.4mm};\xi^{(k)}_{i})$ \;
 		
 		$m^{(k+1)}_i = \beta m^{(k)}_{i} + \tilde{g}_i^{(k)} \hspace{0.7cm} \triangleright \mbox{\footnotesize{momentum update}}$ \;
 		
 		$x^{(k+\frac{1}{2})}_i = x^{(k)}_{i} - \gamma m^{(k+1)}_i \hspace{0.38 cm} \triangleright \mbox{\footnotesize{local model update}}$ \;
 		
 		$x^{(k+1)}_i  = \sum_{j\in \mathcal{N}_i} w_{ij} x^{(k+\frac{1}{2})}_j \hspace{1.1mm} \triangleright \mbox{\footnotesize{partial average}}$\;
 	}
 	\caption{DmSGD}
 	\label{Algorithm: DmSGD}
 \end{algorithm}

\vspace{1mm}
\noindent \textbf{Decentralized momentum SGD (DmSGD).} Being the momentum accelerated extension of DSGD, DmSGD has been widely-used in existing literatures \cite{lian2018asynchronous,assran2019stochastic,singh2020squarm, gao2020periodic,yu2019linear,balu2020decentralized}. The primary version of DmSGD is listed in Algorithm \ref{Algorithm: DmSGD}. 
When small-batch is used, DmSGD will achieve $1.3\sim2\times$ speedup in training time compared to PmSGD without visibly loss of generalization performance. 

\vspace{1mm}
\noindent \textbf{Assumptions.} We introduce several standard assumptions to facilitate future analysis:

\vspace{0.5mm}
\noindent \textbf{A.1} Each $f_i(x)$ is $L$-smooth, i.e., $\|\nabla f_i(x) - \nabla f_i(y)\| \le L \|x - y\|$ for any $x,y\in \mathbb{R}^d$.

\vspace{0.5mm}
\noindent \textbf{A.2} The random sample  $\xi_i^{(k)}$ is independent of each other for any $k$ and $i$. We also assume each stochastic gradient is unbiased and has bounded variance, i.e., $\mathbb{E}[{\nabla}F(x;\xi_{i})] = \nabla f_i(x)$ and $\mathbb{E}\|{\nabla}F(x;\xi_{i}) - \nabla f_i(x) \|^2 \le  \sigma^2$.

\vspace{0.5mm}
\noindent \textbf{A.3} The network topology is strongly connected, and the weight matrix is symmetric and satisfies $W\mathds{1} = \mathds{1}$.

\vspace{1mm} 
\noindent Assumption A.3 indicates  $\sum_{j\in\mathcal{N}_i}w_{ij} = 1$ for $i\in[n]$, which is critical to guarantee the partial averaging \eqref{partial-ave} to  converge to the global averaging asymptotically. The weight matrix satisfying Assumption A.3 can be easily constructed, see \cite[Table~14.1]{sayed2014adaptation}.

\section{DmSGD Incurs Severe Inconsistency Bias}

Table \ref{talbe:motivation} shows that large-batch DmSGD has severe performance degradation compared to PmSGD in the large-batch scenario.  This section targets to explore the reason behind this phenomenon. To highlight the insight, we assume each $f_i(x)$ to be strongly convex in this section, and $x^\star$ to be the global solution to problem \eqref{dist-opt}. We let matrix ${\mathbf{x}} = [x_1, \cdots, x_n]^T \in \mathbb{R}^{n\times d}$ to stack all local models across the network, and matrix $\nabla f({\mathbf{x}}) = [\nabla f(x_1), \cdots, \nabla f(x_n)]^T \in \mathbb{R}^{n\times d}$ to stack all local (accurate) gradients.

\vspace{1mm}
\noindent \textbf{Limiting bias of decentralized methods.} The convergence of decentralized methods such as DSGD and DmSGD will suffer from two sources of bias:
\begin{itemize}
    \item \textbf{Stochastic bias} is caused by the utilization of stochastic gradient in algorithms.
    
    \item \textbf{Inconsistency bias} is caused by the data  inconsistency between nodes. 
\end{itemize}

\noindent In addition, these two bias are orthogonal to each other, i.e., 
\begin{align}
\boxed{\lim_{k\to \infty} \sum_{i=1}^n \mathbb{E}\|x_i^{(k)} - x^\star\|^2 = \mbox{sto. bias} + \mbox{inconsist. bias}} \nonumber 
\end{align}
An example illustrating the stochastic and inconsistency bias of DSGD is established in Appendix \ref{app-limit-bias-dsgd}.

\vspace{1mm}
\noindent \textbf{Inconsistency bias dominates large-batch scenario.} In the large-batch scenario, the gradient nosie will be notably reduced. In an extreme case where a full-batch gradient is utilized, the stochastic bias becomes zero. This leads to
\begin{proposition}\label{prop-limit-bias}
The inconsistency bias dominates the convergence of {\em large-batch} decentralized algorithms.
\end{proposition}

\vspace{1mm}
\noindent \textbf{DmSGD's inconsistency bias: intuition.}
\label{sec:DmSG-bias}
The inconsistency bias can be achieved by letting gradient noise be zero. To this end, we let $g_i^{(k)} = \mathbb{E}[{\nabla}F(x^{(k)}_{i}\hspace{-0.4mm};\xi^{(k)}_{i})] = \nabla f_i(x_i^{(k)})$ be the full-batch gradient.
Note that both model $x_i$ and gradient $g_i$ are deterministic due to the removal of gradient noise. By substituting the momentum update and local model update into the partial averaging step in Algorithm \ref{Algorithm: DmSGD}, we can write DmSGD (see Appendix \ref{app-reform-dsgd}) into: 
\begin{align}\label{xsdhs7}
{\mathbf{x}}^{(k+1)} &= \underbrace{W \Big( {\mathbf{x}}^{(k)} - \gamma \nabla f({\mathbf{x}}^{(k)}) \Big)}_{\rm DSGD} + \underbrace{\beta \Big( {\mathbf{x}}^{(k)} - W {\mathbf{x}}^{(k-1)}\Big)}_{\rm momentum}.
\end{align}
Since the momentum term in DmSGD \eqref{xsdhs7} {\em cannot vanish} as $k$ increases, it will impose an extra inconsistency bias to DSGD. A simple numerical simulation on a full-batch linear regression problem confirms such conclusion. It is observed in Fig.~\ref{fig:ls-dsgd-dmsgd} that DmSGD converges faster but suffers from a larger bias than DSGD. 
\begin{figure}[t!]
    \centering
    \includegraphics[width=0.35\textwidth]{./images/ls_dsgd_dmsgd.pdf}
    \caption{Convergence comparison between DSGD and DmSGD for a full-batch linear regression problem. Detailed experimental setting is in Appendix \ref{app-exp-linear-regression}.}
    \label{fig:ls-dsgd-dmsgd} \vspace{-2mm}
    \vspace{-2mm}
\end{figure}

\vspace{1mm}
\noindent \textbf{DmSGD's inconsistency bias: magnitude.}
The following proposition quantitatively evaluates the magnitude of DmSGD's inconsistency bias. We let $\rho = \max\{|\lambda_2(W)|,|\lambda_n(W)|\}$, which characterize how well the network is connected. Since $W$ is doubly stochastic (Assumption A.3), it holds that $\rho \in (0,1)$ (see Appendix \ref{app-pre}). A well connected network will have $\rho \to 0$. 


\begin{proposition}\label{prop-dmsdg-bias}
Under Assumptions A.1 and A.3, if each $f_i(x)$ is further assumed to be strongly-convex, and the full-batch gradient $\nabla f_i(x)$ is accessed per iteration,  then DmSGD \eqref{xsdhs7} has the following inconsistency bias:
\begin{align}\label{DmSGD-hb}
\lim_{k\to \infty} \sum_{i=1}^n \|x_i^{(k)} - x^\star\|^2 = O\Big( \frac{\gamma^2 b^2}{(1-\beta)^2(1-\rho)^2} \Big),
\end{align}
where $b^2 = (1/n)\sum_{i=1}^n \|\nabla f_i(x^\star)\|^2$ denotes the data inconsistency between nodes, and $\beta$ is the momentum coefficient. (Proof is in Appendix \ref{app-inconsist-bias-dsgd})
\end{proposition}

\noindent 
Note that we do not take expectation over $\sum_{i=1}^n \|x_i^{(k)} - x^\star\|^2$ in \eqref{DmSGD-hb} because no gradient noise exists in recursion \eqref{xsdhs7}. Recall from Appendix \ref{app-limit-bias-dsgd} that DSGD has an inconsistency bias on the order of $O(\gamma^2 b^2/(1-\rho)^2)$. Comparing it with \eqref{DmSGD-hb}, it is observed that the momentum term in DmSGD is essentially amplifying the inconsistency bias by a margin of $1/(1-\beta)^2$. This can explain why DmSGD converges less accurate than DSGD as illustrated in Fig.~\ref{fig:ls-dsgd-dmsgd}. Noting that $\beta$ is typically set close to $1$ in practice, DmSGD can suffer from a significantly large inconsistency bias. Since inconsistency bias dominates the large-batch scenario (see Proposition \ref{prop-limit-bias}),  DmSGD is thus observed to have  severely deteriorated performance as illustrated in Table \ref{talbe:motivation}. 




\section{Improving Inconsistency Bias: DecentLaM}\label{sec:decentLaM}
To improve large-batch DmSGD's accuracy, we have to reduce the influence of momentum on inconsistency bias.

\vspace{1mm}
\noindent \textbf{DSGD interprets as standard SGD.} Without loss of generality, we assume each node $i$ can access the accurate gradient $\nabla f_i(x)$ in DSGD recursions \eqref{dsgd-1}--\eqref{dsgd-2}. In this scenario, DSGD can be rewritten into a compact form:
\begin{align}\label{dsgd-compact}
{\mathbf{x}}^{(k+1)} = W\big({\mathbf{x}}^{(k)} - \gamma \nabla f({\mathbf{x}}^{(k)})\big).
\end{align}
To simplify the derivation, we assume the weight matrix $W$, in addition to satisfying Assumption A.3, is positive-definite. With this assumption, $W$ can be eigen-decomposed into $W = U\Lambda U^T$ where $U$ is an orthogonal matrix and $\Lambda$ is a positive definite matrix. We define $W^{\frac{1}{2}} = U \Lambda^{\frac{1}{2}}U^T$ so that $W^{\frac{1}{2}}$ is also positive-definite and $W = W^{\frac{1}{2}}\times W^{\frac{1}{2}}$. We next introduce ${\mathbf{x}} = W^{\frac{1}{2}} {\mathbf{s}}$ and hence ${\mathbf{s}} = W^{-\frac{1}{2}} {\mathbf{x}}$. Left-multiplying $W^{-\frac{1}{2}}$ to both sides of \eqref{dsgd-compact}, 
\begin{align}
{\mathbf{s}}^{(k+1)} 
&= W{\mathbf{s}}^{(k)} - \gamma W^{\frac{1}{2}} \nabla f(W^{\frac{1}{2}} {\mathbf{s}}^{(k)}) \nonumber \\
&= W{\mathbf{s}}^{(k)} - \gamma \nabla_{{\mathbf{s}}} f(W^{\frac{1}{2}} {\mathbf{s}}^{(k)}) \nonumber \\
&= {\mathbf{s}}^{(k)} - \gamma \big( \nabla_{{\mathbf{s}}} f(W^{\frac{1}{2}} {\mathbf{s}}^{(k)}) + \frac{1}{\gamma}(I-W){\mathbf{s}}^{(k)} \big) \label{dsgd-s-recursion}
\end{align}
In other words, DSGD \eqref{dsgd-compact} (with constant $\gamma$) can be interpreted as a standard SGD \eqref{dsgd-s-recursion} (in terms of ${\mathbf{s}}$) to solve:
\begin{align}\label{s-prob}
\min_{{\mathbf{s}}} \quad f(W^{\frac{1}{2}}{\mathbf{s}}) + \frac{1}{2\gamma} \|{\mathbf{s}}\|^2_{I-W},
\end{align}
and ${\mathbf{x}}^{(k)}$ can be achieved by ${\mathbf{x}}^{(k)} = W^{\frac{1}{2}}{\mathbf{s}}^{(k)}$ per iteration. When recursion \eqref{dsgd-s-recursion} approaches the solution ${\mathbf{s}}^o$ to problem \eqref{s-prob}, DSGD \eqref{dsgd-compact} will achieve the fixed point ${\mathbf{x}}^o = W^{\frac{1}{2}}{\mathbf{s}}^{o}$. The inconsistency bias of DSGD is essentially the distance between ${\mathbf{x}}^o$ and ${\mathbf{x}}^\star = [x^\star,\cdots, x^\star]\in {\mathbb{R}}^{n\times d}$ where $x^\star$ is the global solution to problem \eqref{dist-opt}. Since  ${\mathbf{x}}^o\neq {\mathbf{x}}^\star$, such inconsistency bias generally exists in DSGD. 

\begin{figure}[t!]
    \centering
    \includegraphics[width=0.35\textwidth]{./images/ls_dsgd_dmsgd_decentLaM.pdf}
    \caption{Convergence comparison between DSGD, DmSGD and decentLaM for a full-batch linear regression problem.}
    \label{fig:ls-dsgd-dmsgd-decentLaM} \vspace{-2mm}
\end{figure}


\begin{remark}
The interpretation of DSGD \eqref{dsgd-compact}, which is  usually named as the adaptation-then-combination (ATC) version of DSGD, as standard SGD \eqref{dsgd-s-recursion} is novel. Existing literatures \cite{yuan2016convergence,balu2020decentralized} can bridge the adaptation-with-combination (AWC) version of DSGD, i.e., ${\mathbf{x}}^{(k+1)} = W{\mathbf{x}}^{(k)} - \gamma \nabla f({\mathbf{x}}^{(k)})$, with standard SGD, but not for ATC-DSGD. ATC-DSGD can enable larger learning rates and has a better convergence performance than AWC-DSGD \cite[Secs.~10.6 and 11.5]{sayed2014adaptation}, \cite{yuan2018exact2,li2017decentralized}, and is hence more widely used in deep training  \cite{lian2018asynchronous,assran2019stochastic,tang2018d,yu2019linear,gao2020periodic,singh2020squarm,lin2021quasi,koloskova2019decentralized}.
\end{remark}

\vspace{1mm}
\noindent \textbf{DecentLaM development.} 
It is established in Proposition \ref{prop-dmsdg-bias} that the momentum term in DmSGD can significantly amplify the inconsistency bias especially when $\beta \to 1$. 
This section proposes DecentLaM to remove the negative influence of momentum in DmSGD.  

Since DSGD can be interpreted as a standard SGD, we can easily integrate it to the existing momentum acceleration techniques  \cite{loizou2020momentum,yuan2016influence,gitman2019understanding,liu2020improved,yu2019linear}. By letting ${\mathbf{g}}_s^{(k)}$ be the standard gradient of problem \eqref{s-prob} at iteration $k$, the standard momentum SGD approach to solving problem \eqref{s-prob} is 
\begin{align}
{\mathbf{g}}_s^{(k)} &=  \nabla_{{\mathbf{s}}} f(W^{\frac{1}{2}} {\mathbf{s}}^{(k)}) + \frac{1}{\gamma}(I-W){\mathbf{s}}^{(k)} \label{decentLaM-s-1}\\
{\mathbf{m}}^{(k+1)}_{s} &= \beta {\mathbf{m}}^{(k)}_{s} + {\mathbf{g}}_s^{(k)} \label{decentLaM-s-2}\\
{\mathbf{s}}^{(k+1)} &= {\mathbf{s}}^{(k)} - \gamma {\mathbf{m}}^{(k+1)}_{s} \label{decentLaM-s-3}
\end{align}
After achieving ${\mathbf{s}}^{(k+1)}$, we get ${\mathbf{x}}^{(k+1)} = W^{\frac{1}{2}} {\mathbf{s}}^{(k+1)}$. Recursions \eqref{decentLaM-s-1}--\eqref{decentLaM-s-3} are  named as DecentLaM, and we simulate their convergence behaviour under the same setting as in Fig.~\ref{fig:ls-dsgd-dmsgd}. It is observed in  Fig.~\ref{fig:ls-dsgd-dmsgd-decentLaM} that the proposed algorithm converges as fast as DmSGD but to a more accurate solution. Since DecentLaM is with an improved inconsistency bias, it better fits into  the large-batch scenario.




\vspace{1mm}
\noindent \textbf{Efficient implementation.} To apply DecentLaM \eqref{decentLaM-s-1}-\eqref{decentLaM-s-3} to train deep neural networks,  we need two additional modifications: (i) the full-batch gradient $\nabla f_i(x)$ needs to be replaced with the stochastic gradient $\nabla F(x;\xi_i)$; (ii) the matrix $W^{\frac{1}{2}}$ should be removed from the algorithm update. To this end, by letting  ${\mathbf{g}}=W^{\frac{1}{2}}{\mathbf{g}}_{s}$, ${\mathbf{m}} = W^{\frac{1}{2}}{\mathbf{m}}_{s}$, and $\tilde{{\mathbf{g}}}$ be the stochastic version of ${\mathbf{g}}$, \eqref{decentLaM-s-1}-\eqref{decentLaM-s-3} can be rewritten as 
\begin{align}
\tilde{{\mathbf{g}}}^{(k)} &= W \nabla F({\mathbf{x}}^{(k)};{\boldsymbol{\xi}}^{(k)}) + \frac{1}{\gamma}(I-W){\mathbf{x}}^{(k)} \label{decentLaM-x-1}\\
{\mathbf{m}}^{(k+1)} &= \beta {\mathbf{m}}^{(k)} + \tilde{{\mathbf{g}}}^{(k)} \label{decentLaM-x-2}\\
{\mathbf{x}}^{(k+1)} &= {\mathbf{x}}^{(k)} - \gamma {\mathbf{m}}^{(k+1)} \label{decentLaM-x-3}
\end{align}
where we have replaced $\nabla f({\mathbf{x}}^{(k)})$ with $\nabla F({\mathbf{x}}^{(k)};{\boldsymbol{\xi}}^{(k)})$ in \eqref{decentLaM-x-1} to enable the usage of stochastic gradient. The above  algorithm is almost the same as the vanilla momentum SGD within a single computing node, with the exception to construct ${\mathbf{g}}^{(k)}$ as in \eqref{decentLaM-x-1}. The decentralized implementation of \eqref{decentLaM-x-1}-\eqref{decentLaM-x-3} is listed in Algorithm \ref{Algorithm: DecentLaM}, where 
\begin{align}\label{DecentLaM-gi}
\tilde{g}_i^{(k)} \hspace{-0.8mm}=\hspace{-0.8mm} \frac{1}{\gamma} x_i^{(k)} \hspace{-0.8mm}-\hspace{-0.8mm} \frac{1}{\gamma} \sum_{j\in\mathcal{N}_i}w_{ij}\big( x_j^{(k)} \hspace{-0.8mm}-\hspace{-0.8mm} \gamma \nabla F(x_j^{(k)}; \xi_j^{(k)})\big).
\end{align}
The momentum update and local model update in Algorithm \ref{Algorithm: DecentLaM} can be conducted via the mSGD optimizer provided by PyTorch or TensorFlow. As shown in Fig.~\ref{fig:workflow-decentLaM}, the dashed part, which is different from the DmSGD workflow, enables an efficient wait-free backpropagation (WFBP) implementation that can overlap communication and computation.


\begin{algorithm}[t!]
 	\DontPrintSemicolon
 	\KwRequire{Initialize $\gamma$, $x^{(0)}_{i}$; let  $m^{(0)}_{i}\hspace{-0.3mm}=\hspace{-0.3mm}0, \beta\hspace{-0.3mm}\in\hspace{-0.3mm}(0,1)$}

    \vspace{1mm}
 	\For{$k=0, 1,2,...,T-1$, every node $i$}{
 		Sample $\xi^{(k)}_{i}$ and update $\tilde{g}_i^{(k)}$ according to \eqref{DecentLaM-gi} \;
 		
 		$m^{(k+1)}_i = \beta m^{(k)}_{i} + \tilde{g}_i^{(k)} \hspace{0.6cm} \triangleright \mbox{\footnotesize{momentum update}}$ \;
 		
 		$x^{(k+1)}_i = x^{(k)}_{i} - \gamma m^{(k+1)}_i \hspace{0.35 cm} \triangleright \mbox{\footnotesize{local model update}}$ \;
 	}
 	\caption{DecentLaM}
 	\label{Algorithm: DecentLaM}
 \end{algorithm}




\begin{figure}[b!]
    \centering
    \includegraphics[width=0.5\textwidth]{./images/workflow_1.png}
    \caption{The workflow of DecentLaM in a training iteration.}
    \label{fig:workflow-decentLaM} \vspace{-2mm}
\end{figure}
 
\vspace{1mm}
\noindent \textbf{DecentLaM's inconsistency bias.} The following proposition quantitatively evaluates the magnitude of DecentLaM's inconsistency bias (Proof is in Appendix \ref{app-inconsist-bias-decentLaM}):
\begin{proposition}\label{prop-decentlam-bias}
Under the same assumptions as Proposition \ref{prop-dmsdg-bias}, DecentLaM has an inconsistency bias as follows:
\begin{align}\label{DecentLaM-hb}
\lim_{k\to \infty} \sum_{i=1}^n \|x_i^{(k)} - x^\star\|^2 = O\Big(\frac{\gamma^2 b^2}{(1-\rho)^2}\Big),
\end{align}
\end{proposition}
\begin{remark}\label{remark-decentLam-1}
Comparing with DmSGD's inconsistency bias \eqref{DmSGD-hb}, it is observed that DecentLaM completely removes the negative effects of momentum; it improves DmSGD's inconsistency bias by a margin of $1/(1-\beta)^2$. When $b^2$ is large or $\beta$ is close to $1$, such improvement is remarkable. 
\end{remark}
\begin{remark}\label{remark-decentLam-2}
Comparing with DSGD's inconsistency bias $O(\gamma^2 b^2/(1-\rho)^2)$, it is observed that DecentLaM has exactly the same inconsistency bias as DSGD. However, the momentum term in DecentLaM will significantly speed up its convergence rate. The simulation results in Fig.~\ref{fig:ls-dsgd-dmsgd-decentLaM} are consistent with the conclusions discussed in Remarks \ref{remark-decentLam-1}-\ref{remark-decentLam-2}.
\end{remark}






 
\section{Convergence analysis of DecentLaM}
\label{sec:DecentLaM_convergence}
Sec.~\ref{sec:decentLaM} proposes a novel algorithm DecentLaM and explains why it better fits into the large-batch scenario. This section establishes the formal convergence analysis in the non-convex and strongly-convex scenarios, respectively. 

\subsection{Non-convex scenario}
We introduce a standard data inconsistency assumption for the non-convex scenario:

\vspace{1mm}
\noindent \textbf{Assumption A.4} There exits a constant $\hat{b} > 0$ such that $\frac{1}{n}\sum_{i=1}^n\|\nabla f_i(x) - \nabla f(x)\|^2 \le \hat{b}^2$ for any $x$, where $f(x)$ is the global cost function defined in \eqref{dist-opt}.

\vspace{1mm}
\noindent Assumption A.4 is much more relaxed than the commonly used assumption that each $\nabla f_i(x)$ is upper bounded (i.e., $\|\nabla f_i(x)\| \le M$) \cite{gao2020periodic,singh2020squarm,balu2020decentralized}. When  data distribution $D_i$ in each computing node $i$ is identical to each other, it holds that $f_i(x) = f_j(x)$ for any $i$ and $j$, which implies $\hat{b}=0$. 

\begin{theorem}\label{thm-decentLaM--nc}
Under Assumptions A.1--A.4, if learning rate $\gamma =  \min\{\frac{(1-\beta)^2}{5\sqrt{\beta+\beta^2}L}, \frac{(1-\beta)^2}{(5-\beta+2\beta^2)L}, \frac{(1-\beta)^2}{12L\beta^2}, \frac{1-\rho}{20\sqrt{\rho}L}\}$, $W$ is positive-definite, and $\beta + \frac{16\beta^2}{(1-\beta)(1-\rho)^2}  \le \frac{3+\rho}{4}$,  the DecentLaM algorithm in Algorithm \ref{Algorithm: DecentLaM} will converge as follows  (Proof is in Appendix \ref{app-section-non-convex}, and $\bar{x}^{(k)} = \frac{1}{n}\sum_{i=1}^n x_i^{(k)}$):
\begin{align}\label{decentLaM-conv-nc}
& \frac{1}{T}\sum_{k=0}^{T-1}\hspace{-0.5mm}\mathbb{E}\|\frac{1}{n}\sum_{i=1}^n \nabla f_i(\bar{x}^{(k)})\|^2  \\
=& O\Big( \underbrace{\frac{1-\beta}{\gamma T}}_{\rm convg.\ rate} + \underbrace{\frac{\gamma \sigma^2}{n(1-\beta)} + \frac{ \gamma^2\sigma^2}{1-\rho}}_{\rm sto.\ bias} + \underbrace{\frac{ \gamma^2 \hat{b}^2}{(1-\rho)^2}}_{\rm inconsist. bias}\Big) \nonumber
\end{align}
\end{theorem}
Expression \eqref{decentLaM-conv-nc} indicates that DecentLaM will converge sublinearly to a limiting bias. The limiting bias (which can be achieved by letting $T\to \infty$) can be separated into the stochastic bias and the inconsistency bias, which is consistent with our discussion in Sec.~\ref{sec:DmSG-bias}. It is also observed that the inconsistency bias term in \eqref{decentLaM-conv-nc} is unrelated to the momentum coefficient $\beta$, which implies, as discussed in Sec.~\ref{sec:decentLaM}, that DecentLaM has removed the negative affects of momentum. 
Theorem~\ref{thm-decentLaM--nc} has restrictions on the positive-definiteness of $W$ and the momentum parameter $\beta$ so that the analysis can be simplified. However, they are not needed in the real practice and not used in any of our experiments in Sec.~\ref{sec:experiment}. We find the concurrent work \cite{lin2021quasi} also imposes a restriction on momentum parameter to simply the analysis. 

\begin{corollary}\label{coro-decentLaM-nc}
Under the same assumptions as in  Theorem~\ref{thm-decentLaM--nc}, if learning rate $\gamma = O((1-\beta)/\sqrt{T/n})$, DecentLaM will converge at rate $O(1/\sqrt{n T})$ (Proof is in Appendix \ref{app-section-non-convex}), which achieves the same linear speedup as PmSGD.
\end{corollary}

\subsection{Strongly-convex scenario}

\noindent \textbf{Assumption A.5} Each $f_i(x)$ is $\mu$-strongly convex, i.e., $\langle \nabla f_i(x) - \nabla f_i(y), x- y \rangle \ge \mu \|x-y\|^2$ for any $x,y\in \mathbb{R}^d$.

\vspace{1mm}
Under Assumption A.5, the global solution to problem \eqref{dist-opt} is unique. Furthermore, we do need to make the data heterogeneity assumption A.4 in the strongly-convex scenario. Instead, we will use $b^2 = \frac{1}{n}\sum_{i=1}^n \| \nabla f_i(x^\star)\|^2$ to gauge the data heterogeneity 



\begin{theorem}\label{thm-decentLaM--sc}
Under Assumption A.1--A.3 and A.5, if $\gamma =  \min\{\frac{(1-\beta)^2}{27L},\frac{(1-\rho)(1-\beta)(\kappa+1)}{5L},\frac{1-\rho}{\sqrt{1728(\kappa+1)}}\}$, $W$ is  positive definite, and $\beta + \frac{16\beta^2}{(1-\beta)(1-\rho)^2}  \le \frac{3+\rho}{4}$,  DecentLaM in Algorithm \ref{Algorithm: DecentLaM} will converge as (Proof is in Appendix \ref{app-thm-decentLaM--sc}):
\begin{align}\label{decentLaM-conv-sc}
&\ \frac{1}{n H_T}\sum_{k=0}^{T} \sum_{i=1}^n h_k(\mathbb{E} f_i(\bar{x}^{(k)}) - f^*)\nonumber \\
=& O\Big(\underbrace{\frac{(1-\beta)}{\gamma}(1-\frac{\gamma}{(1-\beta)})^{T}}_{\rm convg.\ rate} \nonumber \\
&\quad +\underbrace{\frac{\gamma \sigma^2}{n(1-\beta)} + \frac{\gamma^2 \sigma^2}{1-\rho}}_{\rm sto.\ bias} +\underbrace{\frac{\gamma^2 {b}^2}{(1-\rho)^2}}_{\rm inconsist.bias}\Big)
\end{align}
where $h_k$ is some positive weight (see Appendix \ref{app-thm-decentLaM--sc}) and $H_T = \sum_{k=0}^T h_k$. Quantity $f^\star = \min_{x} f(x)$.
\end{theorem}
\noindent 
The inconsistency bias in \eqref{decentLaM-conv-sc} is independent of the momentum $\beta$, which is consistent with Proposition \ref{prop-decentlam-bias} . It implies that DecentLaM achieves the same  $O(\gamma^2b^2/(1-\rho)^2)$ inconsistency bias as DSGD (see \eqref{dsgd-convergence}).





Theorem~\ref{thm-decentLaM--sc} establishes the convergence of DecentLaM with a constant learning rate. When learning rate is decaying, DecentLaM converges  exactly to the global solution:
\begin{corollary}\label{coro-sc}
Under the same assumptions as Theorem~\ref{thm-decentLaM--sc}, if learning rate $\gamma = {O}(\frac{(1-\beta)\ln(nT^2)}{T})$, DecentLaM will converge as follows (Proof is in Appendix \ref{app-thm-decentLaM--sc}):
\begin{align}\label{decentLaM-conv-sc-2}
\frac{1}{n H_T}\sum_{k=0}^{T} \sum_{i=1}^n h_k(\mathbb{E} f_i(\bar{x}^{(k)}) - f^*) = \tilde{O}\Big( \frac{1}{nT} \Big)
\end{align}
where $\tilde{O}(\cdot)$ hides all logarithm factors. 
\end{corollary}

\noindent Corollary~\ref{coro-sc} implies that DecentLaM achieves the same linear speedup as PmSGD in the strongly-convex scenario \cite{liu2020improved}. However, it saves more communication per iteration due to the partial averaging (see Sec.~\ref{sec:DmSGD}). 



    




\subsection{Comparison with existing methods}
As we discussed in Sec.~\ref{sec:DmSG-bias}, the  inconsistency bias will dominate the convergence performance as batch-size gets large. For this reason, we list the inconsistency bias comparison between DecentLaM and existing DmSGD variants in Table \ref{table:algoriothm-comparison}. By removing the influence of momentum, DecentLaM has the smallest inconsistency bias. This implies DecentLaM can perform better in the large-batch scenario.   

\begin{table}[h]
\centering
\begin{tabular}{rcc}
\toprule
\multicolumn{1}{l}{} & \textbf{Strongly-convex} & \textbf{Non-convex}                           \\ \midrule
DmSGD \cite{gao2020periodic}                & N.A.                                                               & $O\big(\frac{\gamma^2 M^2}{(1-\beta)^2}\big)$ \vspace{0.5mm}\\
DmSGD \cite{singh2020squarm}                & $O\big(\frac{\gamma^{5/2} M^2}{(1-\beta)^6}\big)$                                                               & $O\big(\frac{\gamma^2 M^2}{(1-\beta)^4}\big)$ \vspace{0.5mm}\\
DmSGD  (eq.\eqref{DmSGD-hb})              & $O\big(\frac{\gamma^2 b^2}{(1-\beta)^2}\big)$  & N.A                                           \\
DA-DmSGD \cite{yu2019linear}             & N.A.                                                               & $O\big(\frac{\gamma^2 \hat{b}^2}{(1-\beta)^2}\big)$ \vspace{0.5mm}\\
AWC-DmSGD \cite{balu2020decentralized}           & $O\big(\frac{\gamma^2 M^2}{(1-\beta)^2}\big)$                      & $O\big(\frac{\gamma^2 M^2}{(1-\beta)^4}\big)$ \vspace{0.5mm}\\
SlowMo \cite{wang2019slowmo}           & N.A                     & N.A   \vspace{1.5mm}\\
\textbf{DecentLaM (Ours)}            & $\boldsymbol{O(\gamma^2 b^2)}$                                                  & $\boldsymbol{O(\gamma^2 \hat{b}^2)}$                             \\ \bottomrule
\end{tabular}
\vspace{2mm}
\caption{Inconsistency bias comparison between various decentralized momentum algorithms. Constant $M$ is the gradient's upper bound, which is typically much larger than the data inconsistency $b$ or $\hat{b}$. SlowMo \cite{wang2019slowmo} only examined the data-homogeneous scenario. It did not clarify what the inconsistency bias is. }
\label{table:algoriothm-comparison}
\end{table}

After completing this work, we become aware of the concurrent work QG-DmSGD \cite{lin2021quasi} that can also achieve $O(\gamma^2 \hat{b}^2)$ for non-convex scenario. However, QG-DmSGD is based on a strategy to mimic the global momentum, which is different from the core idea to develop DecentLaM. Furthermore, QG-DmSGD is designed for highly data-heterogeneous scenario in EdgeAI applications while DecentLaM is for large-batch training within data-centers. As a result, our experimental tasks and algorithm settings are very different. In addition, our analysis is also different from QG-DmSGD. With a delicately designed Lyapunov function, we can cover the convergence analysis for both non-convex and strongly-convex scenarios. In contrast, the analysis in QG-DmSGD is for the non-convex scenario. Finally, we theoretically uncovered the reason why traditional DmSGD \cite{yu2019linear,gao2020periodic,singh2020squarm} has degraded performance in Sec.~\ref{sec:DmSG-bias} while QG-DmSGD only justifies it empirically. 

\begin{figure*}[t!]
\centering
\includegraphics[width=0.245\textwidth]{./images/Imagenet-resnet50-loss-epoch-bs2k-0317.pdf} 
\includegraphics[width=0.245\textwidth]{./images/Imagenet-resnet50-acc-epoch-bs2k-0317.pdf} 
\includegraphics[width=0.245\textwidth]{./images/Imagenet-resnet50-loss-epoch-bs16k-cos-0317.pdf} 
\includegraphics[width=0.245\textwidth]{./images/Imagenet-resnet50-acc-epoch-bs16k-cos-0317.pdf}

\caption{\small Convergence results on the ImageNet with respect to training loss and validation top-1 accuracy. The batch size is 2k for left-side two figures and 16k for right-side two figures. For clarity, we do not depict the curves of other baselines.}
\label{Fig:Imagenet-16k}
\end{figure*}


\section{Experiments}
\label{sec:experiment}

In this section, we systematically compare the proposed method, DecentLaM, with well-known state-of-the-art methods on typical large-scale computer vision tasks: image classification and object detection. In particular, we compare DecentLaM with the following algorithms. \textbf{PmSGD} is the standard Parallel momentum SGD algorithm in which a global synchronization across all nodes are required per iteration. \textbf{PmSGD + LARS} exploits a layer-wise adaptive rate scaling strategy \cite{you2017large} to boost  performance with large batch-size. \textbf{DmSGD} \cite{assran2019stochastic,gao2020periodic,singh2020squarm} exploits partial averaging to save communications. Its recursions are listed in Algorithm \ref{Algorithm: DmSGD}. \textbf{DA-DmSGD} \cite{yu2019linear} incurs additional partial averaging over the momentum to increase stability; it has double partial averages per iteration. \textbf{AWC-DmSGD} \cite{balu2020decentralized} accelerates AWC-DSGD with momentum. \textbf{SlowMo} \cite{wang2019slowmo} periodically synchronize each node and adds an additional slow momentum update. \textbf{QG-DmSGD} \cite{lin2021quasi} is a concurrent work to DecentLaM that adds a quasi-global momentum to DSGD. We utilize the QG-DmSGD Heavy-ball variant. \textbf{D$^2$} \cite{tang2018d} is a primal-dual approach that can completely remove the inconsistency bias theoretically. The vanilla D$^2$ algorithm does not perform well in our experiments. We refer to another form of D$^2$ in \cite{yuan2020influence} and add momentum acceleration to the local update step. We name this algorithm as \textbf{D$^2$-DmSGD}. All baseline algorithms are tested with the recommended hyper-parameters in their papers. Note that DecentLaM requires {\em symmetric} (but not necessarily positive definite) weight matrix to guarantee empirical convergence. 




We implement all the aforementioned algorithms with PyTorch \cite{paszke2019pytorch} 1.6.0 using NCCL 2.8.3 (CUDA 10.2) as the communication backend. For PmSGD, we used PyTorch's native Distributed Data Parallel (DDP) module. For the implementation of decentralized methods, we utilize \textbf{BlueFog} \cite{bluefog}, which is a high-performance decentralized deep training framework, to facilitate the topology organization, weight matrix generation, and efficient partial averaging. We also follow DDP's design to enable computation and communication overlap. Each server contains 8 V100 GPUs in our cluster and is treated as one node. The inter-node network fabrics are 25 Gbps TCP as default, which is a common distributed training platform setting. To eliminate the effect of topology with different size in decentralized algorithms, we used 8 nodes (i.e. $8\times 8=64$ GPUs) in all decentralized training and changed the batch size of every single GPU respectively. 




\subsection{Image Classification} 

\begin{table}[t!]
\vskip 0.15in
\begin{center}
\begin{small}
\begin{sc}
\begin{tabular}{ccccc}
\toprule
    \multirow{2}{*}{method} & \multicolumn{4}{c}{Batch Size}  \\
     & 2k    & 8k        & 16k & 32k    \\ 
\midrule
PmSGD & 76.32 & 76.08 & 76.27 & 75.27   \\ 
PmSGD+LARS\cite{you2017large}  & 76.16 & 75.95 & 76.65 & 75.63 \\
DmSGD\cite{assran2019stochastic,gao2020periodic,singh2020squarm} & 76.27 & 76.01 & 76.23 & 74.97 \\
DA-DmSGD\cite{yu2019linear} & 76.35 & $\mathbf{76.19}$ & 76.62 & 75.51 \\
AWC-DmSGD\cite{balu2020decentralized} & 76.29 & 75.96 & 76.31 & 75.37 \\
SlowMo\cite{wang2019slowmo} & 76.30 & 75.47 & 75.53 & 75.33 \\
QG-DmSGD\cite{lin2021quasi} & 76.23 & 75.96 & 76.60 & 75.86 \\
D$^2$-DmSGD\cite{tang2018d} & 75.44 & 75.30 & 76.16 & 75.44 \\
DecentLaM (Ours) & $\mathbf{76.43}$ & $\mathbf{76.19}$ & $\mathbf{76.73}$ & $\mathbf{76.22}$ \\
\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vskip -0.1in
\caption{Top-1 validation accuracy of aforementioned methods when training ResNet-50 model with different batch sizes.}
\vskip -0.2in
\label{table-imagenet-resnet50-acc}
\end{table}

\noindent \textbf{Implementation.} We conduct a series of image classification experiments with the ImageNet-1K \cite{deng2009imagenet} dataset, which consists of 1,281,167 training images and 50,000 validation images in 1000 classes. We train classification models 
with different batch sizes to verify our theoretical findings. As suggested in \cite{goyal2017accurate}, we treat batch size equal or less than 8k as small-batch setting and the training protocol in \cite{goyal2017accurate} is used. In details, we train total 90 epochs. The learning rate is warmed up in the first 5 epochs and is decayed by a factor of 10 at 30, 60 and 80 epochs. For large-batch setting (batch size larger than 8K), we train total 120 epochs. The learning rate is warmed up in the first 20 epochs and is decayed in a cosine annealing scheduler as suggested in \cite{you2019large}. The choice of hyper-parameter setting is not cherry-picked and we try to keep our PmSGD's baseline around 76\% while \cite{goyal2017accurate}'s setting has severe performance drop even for large-batch PmSGD. The momentum SGD optimizer is  with linear scaling by default. 
Experiments are trained in the mixed precision using Pytorch native amp module.

\begin{table*}[t]
\begin{center}
\begin{small}
\begin{sc}
\setlength{\tabcolsep}{1.8mm}{
\begin{tabular}{cccccccccccccccc}
\toprule
    model & \multicolumn{3}{c}{ResNet-18} & \multicolumn{3}{c}{ResNet-34} & \multicolumn{3}{c}{ResNet-50} & \multicolumn{3}{c}{MobileNet-v2} & \multicolumn{3}{c}{EfficientNet} \\
    Batch Size & 2k & 8k & 16k & 2k & 8k & 16k & 2k & 8k & 16k & 2k & 8k & 16k & 2k & 8k & 16k \\
    \midrule
    PmSGD & 70.0 & 69.5 & 68.3 & $\mathbf{73.8}$ & 72.8 & 72.9  & 76.3 & 76.1 & 76.3 & 70.6 & 71.1 & 69.5 & 77.6 & 77.0 & 78.1 \\ 
    PmSGD+LARS & 70.2 & 69.9 & $\mathbf{70.6}$ & 73.6 & $\mathbf{73.2}$ & 73.3 & 76.2 & 76.0 & $\mathbf{76.7}$ & 70.7 & 71.3 & $\mathbf{72.3}$ & 77.7 & 77.2 & 78.2 \\
    DmSGD & 69.9 & 69.3 & 68.7 & 73.1 & 72.7 & 72.4 & 76.3 & 76.0 & 76.2 & 70.5 & 71.0 & 72.1 & 77.5 & 76.9 & 77.5 \\
    DA-DmSGD & 70.2 & 70.0 & 70.2 & 73.3 & 73.1 & 73.1 & $\mathbf{76.4}$ & $\mathbf{76.2}$ & 76.6 & 70.4 & $\mathbf{71.4}$ & 72.1 & 77.6 & $\mathbf{77.4}$ & 77.8 \\
    AWC-DmSGD & 69.5 & 69.4 & 70.4 & 73.2 & 72.7 & 73.2 & 76.3 & 76.0 & 76.3 & 70.6 & 70.8 & 71.9 & 77.4 & 76.9 & 77.7 \\
    SlowMo & 70.5 & 70.0 & 69.9 & 73.5 & 73.0 & 73.0 & 76.3 & 75.5 & 75.5 & 68.7 & 69.1 & 67.8 & 77.4 & 77.2 & 77.1 \\
    QG-DmSGD & 70.2 & $\mathbf{70.5}$ & ${70.3}$ & $\mathbf{73.8}$ & 73.1 & 73.3 & 76.2 & 76.0 & 76.6 & $\mathbf{70.8}$ & 70.6 & 72.0 & 76.8 & 76.5 & 76.7 \\
    D$^2$-DmSGD & 69.1 & 68.9 & 70.1 & 72.7 & 72.3 & 73.1 & 75.4 & 75.3 & 76.2 & 70.2 & 70.6 & 71.8 & 76.6 & 76.4 & 76.5 \\
    DecentLaM & $\mathbf{70.3}$ & 69.9 & 70.5 & 73.4 & 73.1 & $\mathbf{73.4}$ & $\mathbf{76.4}$ & $\mathbf{76.2}$ & $\mathbf{76.7}$ & 70.3 & $\mathbf{71.4}$ & 72.2 & $\mathbf{77.8}$ & 77.2 & $\mathbf{78.3}$ \\

\bottomrule
\end{tabular}}
\end{sc}
\end{small}
\end{center}
\vskip -0.1in
\caption{Top-1 validation accuracy comparison with different models and batch sizes on ImageNet dataset.}
\label{table-imagenet-backbone-acc}
\end{table*}

\vspace{1mm}
\noindent \textbf{Performance with different batch-sizes}.
We first compare the top-1 accuracy of the aforementioned methods when training ResNet-50 \cite{he2016deep} model ($\sim$25.5M parameters)  with different batch-sizes on ImageNet. The network topology is set as the symmetric exponential topology (see  \ref{app-topo}). The results are listed in Table  \ref{table-imagenet-resnet50-acc}. It is observed that:
\begin{itemize}
    \item DecentLaM always has better accuracy than other decentralized algorithms, and its superiority gets evident as batch size grows. DecentLaM outperforms  other baselines by a large margin in the 32K batch size scenario due to its improved inconsistency bias derived in Proposition \ref{prop-decentlam-bias}, Theorems~\ref{thm-decentLaM--sc} and \ref{thm-decentLaM--nc}. 

    \item DecentLaM even outperforms PmSGD and PmSGD + LARS for each batch-size. One conjecture is that its model inconsistency between nodes caused by the partial averaging helps the algorithm escape from shallow local minimums. As a result, DecentLaM can be better as well as faster than DmSGD (with LARS). 


    \item DmSGD, DA/AWC-DmSGD, and SlowMo have a severe degraded performance in the 32K batch size scenario. It is because the momentum have amplified their inconsistency bias, see Proposition \ref{prop-dmsdg-bias} and the results listed in Table \ref{table:algoriothm-comparison}. D$^2$-DmSGD's performance also drops significantly while it can  theoretical remove all inconsistency bias. QG-DmSGD has relatively small performance degradation, but it still performs worse than DecentLaM. 
     
\end{itemize}


We also depict the training loss and top-1 validation accuracy curves on ResNet-50 with 2K and 16K batch sizes in Fig.~\ref{Fig:Imagenet-16k}. When batch size is 2K, it is observed that DecentLaM achieves roughly the same training loss as DmSGD. However, as batch size grows to 16K, DecentLaM achieves visibly smaller training loss than DmSGD. This observation illustrates that DecentLaM improves  inconsistency bias which can 
boost its convergence when batch-size is large. 





\begin{table}[t!]
\vskip 0.15in
\begin{center}
\begin{small}
\begin{sc}
\begin{tabular}{ccc}
\toprule
    \multirow{2}{*}{topology} & \multicolumn{2}{c}{Batch Size}  \\
     & 16k & 32k \\
    \midrule
    Ring & 76.65 & 76.34 \\
    Mesh & 76.54 & 76.47 \\
    Symmetric Exponential & 76.73 & 76.22 \\
    bipartite random match & 76.53 & 76.11 \\
   
   
   
\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vskip -0.05in
\caption{DecentLaM has consistent performance with different network topologies on ImageNet (ResNet-50).}
\label{table-imagenet-resnet50-topo}
\vskip -0.2in
\end{table}

\vspace{1mm}
\noindent \textbf{Performance with different models.} We now validate whether DecentLaM is effective to different neural network architectures. Table  \ref{table-imagenet-backbone-acc} compares the top-1 accuracy with  backbones widely-used in image classification tasks including ResNet \cite{he2016deep}, MobileNetv2 \cite{sandler2018mobilenetv2} and EfficientNet \cite{tan2019efficientnet}. The accuracy of PmSGD is slightly different from those reported in \cite{sandler2018mobilenetv2, tan2019efficientnet} because we do not utilize tricks such as AutoAugment \cite{cubuk2018autoaugment} that are orthogonal to our methods. It is observed in Table \ref{table-imagenet-backbone-acc} that either PmSGD + LARS or DecentLaM achieves best performance with large batch-size (16K) across different models. However, DecentLaM has runtime speedup due to its efficient neighborhood-communication. For small-batch settings, DA-DmSGD and QG-DmSGD can also achieve the best accuracy for some models.

\vspace{1mm}
\noindent \textbf{Performance with different topologies.} We now examine how DecentLaM is robust to different topologies. To this end, we first organize all computing nodes into ring, mesh, symmetric exponential, or the bipartite random match topology, see Appendix \ref{app-topo} for details of these topologies. Next we test the performance of DecentLaM on ResNet-50 with these topologies and the results are in Table \ref{table-imagenet-resnet50-topo}. It is observed that DecentLaM has a consistent performance with different topologies. The ring topology is sparser than symmetric exponential topology. Interestly, it is observed to have a better accuracy in the 32K batch-size setting. It is conjectured that the ring topology can help escape from shallow local minimums when batch-size is large. We leave the justification as the future work. 

\vspace{1mm}
\noindent \textbf{Training time comparison}. The end-to-end training speed varies across different models and network bandwidth conditions. For the sake of brevity, we compare the runtime of PmSGD, DmSGD and DecentLaM in training ResNet-50 (ImageNet) with different batch sizes and network bandwidths. The speed-up of DmSGD/DecentLaM over PmSGD is consistent for other backbones and tasks. 
In Fig.~\ref{Fig:Imagenet-speed}, DecentLaM and DmSGD have equivalent runtime because they are based on the same partial averaging operation. However, they can achieve 1.2$\sim$1.9$\times$speed-up compared to PmSGD, which is consistent with \cite{assran2019stochastic}.

\begin{figure}[t!]
\vskip 0.2in
\centering
\includegraphics[width=0.235\textwidth]{./images/Imagenet-resnet50-speed-10gpbs.pdf} 
\includegraphics[width=0.235\textwidth]{./images/Imagenet-resnet50-speed.pdf} 

\caption{\small Runtime comparison on ResNet-50 with different batch sizes and network bandwidth (Left: 10Gbps; Right: 25Gbps). Each column indicates the averaged iteration runtime of 500 iterations. The thick part highlights the communication overhead.}
\label{Fig:Imagenet-speed}
\vskip -0.2in
\end{figure}

\subsection{Object Detection} 

We compared the aforementioned methods with well-known detection models, e.g. Faster-RCNN \cite{ren2016faster} and RetinaNet \cite{lin2017focal} on popular PASCAL VOC \cite{everingham2010pascal} and COCO \cite{lin2014microsoft} datasets. We adopt the MMDetection  \cite{chen2019mmdetection} framework as the building blocks and utilize ResNet-50 with FPN \cite{lin2017feature} as the  backbone network. We choose mean Average Precision (mAP) as the evaluation metric for both datesets. We used 8 GPUs (which are connected by the symmetric exponential topology) and set the total batch size as 256 in all detection experiments. Table \ref{table-detection-map} shows the performance of each algorithm. Compared with classification tasks, the total batch size in object detection cannot be set too large (typical object detection task sets batch size as $2$ within each GPU). For this reason, our proposed method just reaches a slightly higher mAP than other methods.

\begin{table}[t!]
\vskip 0.15in
\begin{center}
\begin{small}
\begin{sc}
\begin{tabular}{ccccc}
\toprule
    Dataset & \multicolumn{2}{c}{PASCAL VOC} & \multicolumn{2}{c}{COCO} \\
    Model & R-Net & F-RCNN & R-Net & F-RCNN \\

\midrule
PmSGD & 79.0 & 80.3 & 36.2 & 36.5   \\ 
PmSGD+LARS & 78.5 & 79.8 & 35.7 & 36.2 \\
DmSGD & 79.1 & 80.5 & 36.1 & 36.4  \\
DA-DmSGD & 79.0 & 80.5 & 36.4 & 37.0 \\
DecentLaM  & $\mathbf{79.3}$ & $\mathbf{80.7}$ & $\mathbf{36.6}$ & $\mathbf{37.1}$ \\

\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vskip -0.1in
\caption{Comparision of aforementioned methods with different models on PASCAL VOC and COCO datasets. R-Net and F-RCNN refer to RetinaNet and Faster-RCNN respectively.}
\label{table-detection-map}
\vskip -0.2in
\end{table}

\section{Conclusion} 
\label{sec:conclusion}
We investigated the performance degradation in large-batch DmSGD and proposed DecentLaM to remove the momentum-incurred bias. Theoretically, we demonstrate the convergence improvement in smooth convex and non-convex scenarios. Empirically, experimental results of various models and tasks validate our theoretical findings.

{\small
\bibliographystyle{ieee_fullname}
