# Gradient Tracking: A Unified Approach to Smooth Distributed Optimization

Jingwang Li and Housheng Su J. Li and H. Su are with the Key Laboratory of
Imaging Processing and Intelligence Control, School of Artificial Intelligence
and Automation, Huazhong University of Science and Technology, Wuhan 430074,
China. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this work, we study the classical distributed optimization problem over
digraphs, where the objective function is a sum of smooth local functions.
Inspired by the implicit tracking mechanism proposed in our earlier work, we
develop a unified algorithmic framework from a pure primal perspective, i.e.,
UGT, which is essentially a generalized gradient tracking method and can unify
most existing distributed optimization algorithms with constant step-sizes. It
is proved that two variants of UGT can both achieve linear convergence if the
global objective function is strongly convex. Finally, the performance of UGT
is evaluated by numerical experiments.

###### Index Terms:

Gradient tracking, distributed optimization, unified framework.

##  I Introduction

We consider the classical distributed optimization problem

$\displaystyle\min_{x\in\mathbb{R}^{m}}$ $\displaystyle
F(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$ (P1)

over a network consisting of $n$ agents, where
$f_{i}(x):\mathbb{R}^{m}\rightarrow\mathbb{R}$ is differentiable and only
known by agent $i$. It is assumed that P1 has at least an optimal solution.
The communication topology among agents is modeled by a digraph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{1,2,\cdots,n\\}$ is the vertex set,
$\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ is the edge set, and
$(i,j)\in\mathcal{E}$ if agents $i$ can receive information from agent $j$.
Due to its promising applications on many areas, such as machine learning,
distributed control and sensor networks [1], P1 has drawn lots of research
interests and varieties of distributed algorithms have been proposed in the
past decades, to name a few, distributed subgradient method [2], EXTRA [3],
DLM [4], NIDS [5], Exact diffusion [6], and numerous gradient tracking methods
[7, 8, 9, 10, 11, 12], includes DIGing [7, 8], ATC-Tracking [9, 10], and Aug-
DGM [11, 12]. In this work, we aim to develop a general algorithmic framework
which can unify existing algorithms. Some efforts have been made towards that
goal, for example, [13] unifies DIGing and EXTRA, [14] unifies Exact diffusion
and NIDS, and the two primal-dual frameworks proposed in [15] and [16] can
unify most existing algorithms. However, the two primal-dual frameworks, which
are the most general frameworks as far as we know, both rely on the symmetry
of weight matrices, which is not necessary for many algorithms [8, 7, 9, 10,
11, 12, 6].

The above observation inspires us to ask that if there exists a more general
framework, which does not require the symmetry of weight matrices. In [15] and
[16], gradient tracking algorithms [7, 8, 9, 10, 11, 12] are seen as primal-
dual methods, where the symmetry of weight matrices is further assumed.
However, the convergence of all these gradient tracking methods do not rely on
the symmetry of weight matrices. When the symmetry of weight matrices is
absent, in fact, we can not treat gradient tracking algorithms as primal-dual
methods, which is also pointed out in [7]. Different from [15] and [16], our
framework is built from a pure primal perspective and does not rely on the
symmetry of weight matrices. The key in developing the proposed framework is
that we regard most existing distributed algorithms with constant step-sizes
as gradient tracking methods but with different kinds of tracking mechanisms:
explicit tracking and implicit tracking. To be more specific, the tracking of
the global gradient exists generally in most distributed algorithms with
constant step-sizes. Though some algorithms do not have the explicit gradient
tracking structure [3, 4, 6, 5, 17], they still possess certain implicit
structure that can track the global gradient, which we call the implicit
tracking mechanism. The idea originates from our earlier work [18], where the
implicit tracking mechanism is proposed and further used to design efficient
algorithms for distributed constraint-coupled optimization problems.
Therefore, our framework can be seen as a generalized gradient tracking
method, which is the reason we call it unified gradient tracking (UGT).

Our major contributions are summarized as follows:

  1. 1.

We offer a new and unified perspective for understanding existing distributed
optimization algorithms with constant step-sizes, i.e., most distributed
optimization algorithms with constant step-sizes can be seen as gradient
tracking methods in essence, which leads to the birth of UGT.

  2. 2.

UGT can unify most existing distributed algorithms with constant step-sizes,
without assuming the symmetry of weight matrices. In this sense, UGT is more
general than the primal-dual frameworks proposed in [15] and [16]. Meanwhile,
the permission of asymmetric weight matrices implies that UGT can be applied
to digraphs, which is remarkably different from [15] and [16]. Furthermore,
the linear convergence of UGT can be guaranteed when $f_{i}(x)$ is smooth and
$F(x)$ is strongly convex, without the need of the strong convexity even
convexity of $f_{i}(x)$. However, the linear convergences of the primal-dual
frameworks proposed in [15] and [16] both rely on the strong convexity of
$f_{i}(x)$.

  3. 3.

As a generalized gradient tracking method, we can easily obtain lots of
different versions of UGT, benefiting from its special structure. In numerical
experiments, it is found that some versions of UGT have far better performance
than classical gradient tracking algorithms.

Notations: Let $\mathbf{1}_{n}$ and ${I}_{n}$ be the vector of $n$ ones and
the identity matrix with dimension $n$ respectively. Note that we might not
give the dimension explicitly if it could be inferred from the context. For
$x\in\mathbb{R}^{m}$, $\|x\|$ denotes its Euclidean norm and
$\mathbf{1}_{n}x=\mathbf{1}_{n}\otimes x$. For $A\in\mathbb{R}^{m\times n}$,
$\|A\|$ and $\text{det}[A]$ denote its spectral norm and determinant
respectively.

##  II Unified Gradient Tracking

TABLE I:  Special cases of UGT. CTA and ATC denote CTA and ATC algorithms respectively. E and I denote explicit tracking and implicit tracking algorithms respectively. $\mathbf{W}=W\otimes I_{m}$, $\mathbf{L}=L\otimes I_{m}$, where $W$ and $L$ are the weight matrix and the Laplacian matrix associated with the communication topology respectively. $c>0$ is a tunable parameter. Algorithms | Tracking type | $\mathbf{W}_{1}$ | $\mathbf{W}_{2}$ | $\beta$
---|---|---|---|---
A TC | DIGing[8, 7] | E | $\mathbf{W}$ | $\mathbf{W}$ | $0$
EXTRA[3] | I | $\frac{\mathbf{I}+\mathbf{W}}{2}$ | $\frac{\mathbf{I}+\mathbf{W}}{2}$ | $1$
DLM[4] | I | $\mathbf{I}-c\mathbf{L}$ | $\mathbf{I}-c\mathbf{L}$ | $1$
[17] | I | $\mathbf{W}$ | $\mathbf{I}-c(\mathbf{I}-\mathbf{W})$ | $1$
C TA | ATC tracking[9, 10] | E | $\mathbf{W}$ | $\mathbf{W}$ | $0$
Aug-DGM[11, 12] | E | $\mathbf{W}^{2}$ | $\mathbf{I}-(\mathbf{I}-\mathbf{W})^{2}$ | $1$
Exact diffusion[6] | I | $\frac{\mathbf{I}+\mathbf{W}}{2}$ | $\frac{\mathbf{I}+\mathbf{W}}{2}$ | $1$
NIDS[5] | I | $\mathbf{I}-c(\mathbf{I}-\mathbf{W})$ | $\mathbf{I}-c(\mathbf{I}-\mathbf{W})$ | $1$

Let us first consider the centralized gradient descent method:

$\displaystyle x^{k+1}=x^{k}-\alpha\nabla F(x^{k}),$ (1)

where $\alpha>0$ is a constant step-size. As is well known, when $F(x)$ is
convex, 1 can converge to the optimal solution of P1 if $\alpha$ is
appropriate. Under the distributed scenario, however, the global gradient
$\nabla F(x^{k})$ is not accessible for agents, hence 1 can not be applied.
Note that P1 is equivalent to

$\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{mn}}$ $\displaystyle
f(\mathbf{x})=\sum_{i=1}^{n}f_{i}(x_{i}),$ (P2) s.t. $\displaystyle
x_{1}=x_{2}=\cdots=x_{n},$

when $\mathcal{G}$ is strongly connected, where
$\mathbf{x}=[x_{1}^{T},\cdots,x_{n}^{T}]^{T}$. Let $x^{*}$ be an optimal
solution of P1, then $\mathbf{x}^{*}=\mathbf{1}_{n}\otimes x^{*}$ is an
optimal solution of P2, vice versa. Consequently, we can solve P1 by
equivalently solving P2 via the well-known distributed gradient method [2]:

$\displaystyle\mathbf{x}^{k+1}=\mathbf{W}\mathbf{x}^{k}-\alpha(k)\nabla
f(\mathbf{x}^{k}),$ (2)

where $\alpha(k)>0$ is the time-variant step-size, $\mathbf{W}=W\otimes
I_{m}$, and $W\in\mathbb{R}^{n\times n}$ is a weight matrix associated with
$\mathcal{G}$. The convergence of 2 can be guaranteed with some assumptions
about $\alpha(k)$ and $W$, one of whom is
$\lim_{k\rightarrow\infty}\alpha(k)\rightarrow 0$. In fact, 2 can not converge
exactly to $\mathbf{x}^{*}$ without the above condition (for example, let
$\alpha(k)$ be a constant), since $\nabla f_{i}(x^{*})\neq 0$ in general.
Obviously the diminishing step-size $\alpha(k)$ will slow down the convergence
rate greatly, hence there is a dilemma: using a constant step-size, the
convergence rate is fast but the exact convergence can not be guaranteed;
using a diminish step-size, the exact convergence can be guaranteed but the
convergence rate is slow. To get rid of the dilemma, we can resort to the
discrete-time dynamic average consensus (DAC) algorithm [19]

$\displaystyle\mathbf{g}^{k+1}=\mathbf{W}\mathbf{g}^{k}+\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k})$ (3)

to track the global gradient. Along 3, theoretically, $\mathbf{g}^{k}$ will
converge to the global gradient $\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(x_{i}^{k})$, hence $\mathbf{g}^{k}$ can be seen as the inexact global
gradient. Based on the above gradient tracking approach, many algorithms with
constant step-sizes have been proposed [8, 7, 9, 10, 11, 12], one of whom is
DIGing [7, 8], a Combine-then-Adapt (CTA) algorithm written as

$\displaystyle\mathbf{x}^{k+1}$
$\displaystyle=\mathbf{W}\mathbf{x}^{k}-\mathbf{g}^{k},$
$\displaystyle\mathbf{g}^{k+1}$
$\displaystyle=\mathbf{W}\mathbf{g}^{k}+\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k})),$

whose Adapt-then-Combine (ATC) counterpart, i.e., ATC tracking [9, 10], is
given as

$\displaystyle\mathbf{x}^{k+1}$
$\displaystyle=\mathbf{W}(\mathbf{x}^{k}-\mathbf{g}^{k}),$
$\displaystyle\mathbf{g}^{k+1}$
$\displaystyle=\mathbf{W}\mathbf{g}^{k}+\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k})).$

Benefiting from the gradient tracking approach, DIGing and ATC tracking can
converge exactly to $\mathbf{x}^{*}$ even using a constant step-size, since
the inexact global gradient $\mathbf{g}^{k}$ will converge to $0$ as
$\mathbf{x}^{k}$ approaches $\mathbf{x}^{*}$.

DIGing and ATC tracking, as well as another gradient tracking algorithm Aug-
DGM, have an explicit state variable $\mathbf{g}^{k}$ to track the global
gradient, which is the reason we call them explicit gradient tracking
algorithms. Besides these explicit gradient tracking algorithms, there also
exist lots of other distributed algorithms, like EXTRA, NIDS, Exact diffusion,
and so forth. Though they do not possess the explicit gradient tracking
structure, we found that they do have an implicit one, hence they can also be
seen as gradient tracking algorithms, but with the implicit tracking approach.
The implicit tracking mechanism (approach) is first proposed in [18], which is
employed to develop efficient algorithms for distributed constraint-coupled
optimization problems. Specifically speaking, [18] offers a new perspective to
understand a classical continuous-time distributed optimization algorithm
[20], which is given as

$\displaystyle\dot{\mathbf{x}}$ $\displaystyle=-\alpha\nabla
f(\mathbf{x})-\mathbf{z}-\beta\mathbf{L}\mathbf{x},$ (4)
$\displaystyle\dot{\mathbf{z}}$
$\displaystyle=\alpha\beta\mathbf{L}\mathbf{x}.$

In [20], it is observed that

$\displaystyle\dot{\mathbf{x}}=-\alpha\nabla
f(\mathbf{x})-\beta\mathbf{L}\mathbf{x}$

cannot converge to the optimal solution of P2 since local gradients are
generally different. Based on this observation, the integral feedback term
$\mathbf{z}$ is designed to correct the error among agents caused by local
gradients.

Different from [20], 4 is derived from a brand-new way in [18]. Concretely
speaking, it is easy to verify that

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(x_{i})=\mathbf{0},$ (5)
$\displaystyle x_{i}=x_{j},\ i,j\in\mathcal{V}$

is a sufficient and necessary condition for $x_{i}=x^{*}$, $i\in\mathcal{V}$.
Furthermore, 5 is equivalent to

$\displaystyle x_{i}=\frac{1}{n}\sum_{j=1}^{n}(x_{j}-\nabla f_{j}(x_{j})),\
i\in\mathcal{V}.$

Therefore, if each agent $i$ takes the following dynamics:

$\displaystyle\dot{x}_{i}(t)$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}(x_{j}-\nabla f_{j}(x_{j}))-x_{i}(t)$
(6) $\displaystyle=-\frac{1}{n}\sum_{j=1}^{n}\nabla
f_{j}(x_{j}(t))-\left(x_{i}(t)-\frac{1}{n}\sum_{j=1}^{n}x_{j}(t)\right),$

obviously $x_{i}(t)$ will converge to $x^{*}$. Though 6 is not distributed, it
is natural to apply the continuous-time DAC algorithm proposed in [21] to
track $\frac{1}{n}\sum_{j=1}^{n}(x_{j}-\nabla f_{j}(x_{j}))$ distributedly:

$\displaystyle\dot{\mathbf{x}}$
$\displaystyle=-\alpha(\mathbf{x}-(\mathbf{x}-\nabla
f(\mathbf{x})))-\mathbf{z}-\beta\mathbf{L}\mathbf{x},$
$\displaystyle\dot{\mathbf{z}}$
$\displaystyle=\alpha\beta\mathbf{L}\mathbf{x},$

which is exactly 4. As a distributed version of 6, $\alpha\nabla
f_{i}(x_{i})+z_{i}$ can be naturally seen as asgent $i$’s estimation of the
global gradient $\frac{1}{n}\sum_{j=1}^{n}\nabla f_{j}(x_{j}(t))$. In other
words, 4 can still be seen as a kind of gradient tracking algorithm, but with
the implicit tracking approach, where $\alpha\nabla f(\mathbf{x})+\mathbf{z}$
plays the role in tracking the global gradient. Compared with explicit
gradient tracking algorithms, such as DIGing and ATC tracking, there is no
explicit state variable to track the global gradient in 4, which is the reason
we call the tracking approach used in 4 the implicit tracking approach.

As mentioned before, the implicit tracking approach is used in the algorithm
design for distributed constraint-coupled optimization problems in [18].
Different from [18], we focus on the classical set-up P1 and develop a unified
algorithmic framework for it, with the help of a brand-new understanding of
existing distributed optimization algorithms that the implicit tracking
mechanism offers.

Besides the continuous-time algorithm 4, the implicit tracking mechanism
exists generally in many discrete-time algorithms, like EXTRA, NIDS, and Exact
diffusion. Though these algorithms do not have an explicit state variable to
track the global gradient, it is feasible to transform them to explicit
tracking forms. Let us take EXTRA and Exact diffusion as CTA and ATC examples
respectively. EXTRA updates as

$\displaystyle\mathbf{x}^{k+2}$
$\displaystyle=2\widetilde{\mathbf{W}}\mathbf{x}^{k+1}-\widetilde{\mathbf{W}}\mathbf{x}^{k}-\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k})),$

where $\widetilde{\mathbf{W}}=\frac{\mathbf{I}+\mathbf{W}}{2}$. Define

$\displaystyle\mathbf{g}^{k+1}=-\widetilde{\mathbf{W}}(\mathbf{x}^{k+1}-\mathbf{x}^{k})+\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k})),$

we have

$\displaystyle\mathbf{x}^{k+1}=\widetilde{\mathbf{W}}\mathbf{x}^{k}-\mathbf{g}^{k}$

and

$\displaystyle\mathbf{g}^{k+1}=$
$\displaystyle\widetilde{\mathbf{W}}\mathbf{x}^{k}-\widetilde{\mathbf{W}}\left(\widetilde{\mathbf{W}}\mathbf{x}^{k}-\mathbf{g}^{k}\right)+\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k}))$ $\displaystyle=$
$\displaystyle\widetilde{\mathbf{W}}\mathbf{g}^{k}+\left(\mathbf{I}-\widetilde{\mathbf{W}}\right)\widetilde{\mathbf{W}}\mathbf{x}^{k}+\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k})),$

then we can obtain the explicit tracking form of EXTRA:

$\displaystyle\mathbf{x}^{k+1}$
$\displaystyle=\widetilde{\mathbf{W}}\mathbf{x}^{k}-\mathbf{g}^{k},$
$\displaystyle\mathbf{g}^{k+1}$
$\displaystyle=\widetilde{\mathbf{W}}\mathbf{g}^{k}+(\mathbf{I}-\widetilde{\mathbf{W}})\widetilde{\mathbf{W}}\mathbf{x}^{k}+\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k})).$

Exact diffusion updates as

$\displaystyle\mathbf{x}^{k+2}=\widetilde{\mathbf{W}}(2\mathbf{x}^{k+1}-\mathbf{x}^{k}-\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k}))).$

Define

$\displaystyle\mathbf{g}^{k+1}=\mathbf{x}^{k}-\mathbf{x}^{k+1}+\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k})),$

we have

$\displaystyle\mathbf{x}^{k+1}=\widetilde{\mathbf{W}}(\mathbf{x}^{k}-\mathbf{g}^{k})$

and

$\displaystyle\mathbf{g}^{k+1}$
$\displaystyle=\mathbf{x}^{k}-\widetilde{\mathbf{W}}(\mathbf{x}^{k}-\mathbf{g}^{k})+\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k}))$
$\displaystyle=\widetilde{\mathbf{W}}\mathbf{g}^{k}+(\mathbf{I}-\widetilde{\mathbf{W}})\mathbf{x}^{k}+\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k})),$

then the explicit tracking form of Exact diffusion is given as

$\displaystyle\mathbf{x}^{k+1}$
$\displaystyle=\widetilde{\mathbf{W}}(\mathbf{x}^{k}-\mathbf{g}^{k}),$
$\displaystyle\mathbf{g}^{k+1}$
$\displaystyle=\widetilde{\mathbf{W}}\mathbf{g}^{k}+(\mathbf{I}-\widetilde{\mathbf{W}})\mathbf{x}^{k}+\alpha(\nabla
f(\mathbf{x}^{k+1})-\nabla f(\mathbf{x}^{k})).$

Apart from EXTRA and Exact diffusion, many other distributed optimization
algorithms also have the implicit gradient tracking structure and we can
transform them to explicit tracking forms, which inspires the design of the
unified framework. Our unified framework, i.e., UGT, has two variants, one is
CTA-UGT:

$\displaystyle\mathbf{x}^{k+1}$
$\displaystyle=\mathbf{W}_{1}\mathbf{x}^{k}-\mathbf{g}^{k},$
$\displaystyle\mathbf{g}^{k+1}$
$\displaystyle=\mathbf{W}_{2}\mathbf{g}^{k}+\beta(\mathbf{I}-\mathbf{W}_{2})\mathbf{W}_{1}\mathbf{x}^{k}$
$\displaystyle\quad+\alpha(\nabla f(\mathbf{x}^{k+1})-\nabla
f(\mathbf{x}^{k})),$

and another one is ATC-UGT:

$\displaystyle\mathbf{x}^{k+1}$
$\displaystyle=\mathbf{W}_{1}(\mathbf{x}^{k}-\mathbf{g}^{k}),$
$\displaystyle\mathbf{g}^{k+1}$
$\displaystyle=\mathbf{W}_{2}\mathbf{g}^{k}+\beta(\mathbf{I}-\mathbf{W}_{2})\mathbf{x}^{k}$
$\displaystyle\quad+\alpha(\nabla f(\mathbf{x}^{k+1})-\nabla
f(\mathbf{x}^{k})),$

where $\beta\geq 0$ is a tunable parameter, $\mathbf{W}_{1}=W_{1}\otimes
I_{m}$, $\mathbf{W}_{2}=W_{2}\otimes I_{m}$, $W_{1}$ and $W_{2}$ are weight
matrices, and $\mathbf{g}^{0}=\alpha\nabla f(\mathbf{x}^{0})$. By choosing
different $\mathbf{W}_{1}$, $\mathbf{W}_{2}$, and $\beta$, UGT can recover
most existing algorithms, as shown in Table I.

###### Remark 1

As a matter of fact, UGT is a generalized gradient tracking algorithm.
Compared with the two classical gradient tracking algorithms (DIGing and ATC
tracking), UGT has an extra term: for CTA-UGT, it is
$\beta(\mathbf{I}-\mathbf{W}_{2})\mathbf{W}_{1}\mathbf{x}^{k}$; for ATC-UGT,
it is $\beta(\mathbf{I}-\mathbf{W}_{2})\mathbf{x}^{k}$, which we call the
modified term. It is worth noting that the introduce of the modified term does
not increase the number of communication rounds in each iteration, which is
obvious for ATC-UGT, while for CTA-UGT, we only need to notice that the
updating of $\mathbf{g}^{k}$ can be rewritten as

$\displaystyle\mathbf{g}^{k+1}$
$\displaystyle=(1-\beta)\mathbf{W}_{2}\mathbf{g}^{k}+\beta\left[\mathbf{g}^{k}+(\mathbf{I}-\mathbf{W}_{2})\mathbf{x}^{k+1}\right]$
$\displaystyle\quad+\alpha(\nabla f(\mathbf{x}^{k+1})-\nabla
f(\mathbf{x}^{k})),$

hence the number of communication rounds of CTA-UGT in each iteration is still
$2$.

###### Remark 2

The parameter $\beta$ in the modified term plays a critical role in the
performance of UGT. In existing algorithms, there are only two possible values
of $\beta$: $0$ and $1$, as shown in Table I. Nevertheless, $\beta$ can be set
to any values, as long as the convergence can be guaranteed (the upper bound
of $\beta$ is derived in Section III). In our opinion, UGT with different
$\beta$ are essentially different algorithms, and whose convergence rates may
have huge differences in numerical experiments. Therefore, it is convenient to
develop efficient versions of UGT by choosing an appropriate value for
$\beta$.

(a) Directed circle graph

(b) Directed exponential graph with $e=2$

(c) Directed exponential graph with $e=4$

(d) Directed exponential graph with $e=6$

Figure 1: The convergence rates of different versions of CTA-UGT over
digraphs.

(a) Directed circle graph

(b) Directed exponential graph with $e=2$

(c) Directed exponential graph with $e=4$

(d) Directed exponential graph with $e=6$

Figure 2: The convergence rates of different versions of ATC-UGT over
digraphs.

(a) Circle graph

(b) Random graph with $p=0.05$

(c) Random graph with $p=0.1$

(d) Random graph with $p=0.3$

Figure 3: The convergence rates of different versions of CTA-UGT over
undigraphs.

(a) Circle graph

(b) Random graph with $p=0.05$

(c) Random graph with $p=0.1$

(d) Random graph with $p=0.3$

Figure 4: The convergence rates of different versions of ATC-UGT over
undigraphs.

##  III Convergence Analysis

We first give the following assumption about weight matrices $W_{1}$ and
$W_{2}$.

###### Assumption 1

$W_{1}$ and $W_{2}$ are primitive and doubly stochastic.

$W_{1}$ and $W_{2}$ are associated with $\mathcal{G}$. $W_{1}(W_{2})=[w_{ij}]$
can be constructed as: $w_{ii}>0$; $w_{ij}>0$ if $(i,j)\in\mathcal{E}$,
otherwise $w_{ij}=0$. Based on this constructed rule, $W_{1}$ and $W_{2}$ are
primitive if $\mathcal{G}$ is strongly connected. Given Assumption 1, $W_{1}$
and $W_{2}$ have the following property [8]:

$\displaystyle\sigma_{1}=$
$\displaystyle\left\|W_{1}-\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}\right\|\in(0,1),$
$\displaystyle\sigma_{2}=$
$\displaystyle\left\|W_{2}-\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}\right\|\in(0,1).$

Though the above property is derived under the assumption that $\mathcal{G}$
is undirected and connected in [8], it is trivial to prove it for our case by
feat of the Perron–Frobenius theory.

###### Remark 3

Different from [15] and [16], we do not assume the symmetry of $W$.
Consequently, Assumption 1 can not only be satisfied by undigraphs, but also
digraphs that permit doubly stochastic weight matrices, which is the reason we
use the digraph to model the communication topology. On the converse, the
communication topology can only be modeled by an undigraph in [15] and [16],
due to the symmetry of $W$.

###### Assumption 2

$F$ is $\mu$-strongly convex and $f_{i}$ is $l_{i}$-smooth, $i\in\mathcal{V}$.

Let $l=\min_{i\in\mathcal{V}}l_{i}$, $\bar{l}=\frac{1}{n}\sum_{i=1}^{n}l_{i}$,
$\eta=\min\\{|1-\alpha\mu|,|1-\alpha\bar{l}|\\}$, $\sigma_{1}\in(0,1)$ and
$\sigma_{2}\in(0,1)$ be the second largest singular values of $W_{1}$ and
$W_{2}$ respectively. Define two non-negative matrices as

$G_{1}(\alpha,\beta)=\left[\begin{array}[]{cccc}\sigma_{1}&1&0\\\
\raisebox{-9.75pt}{\leavevmode\hbox{\set@color{\ignorespaces\ignorespaces\leavevmode\hbox{\set@color\hskip
36.3346pt\leavevmode\hbox{\set@color$+\alpha l(1+\sigma_{1}+\alpha
l)$}\raisebox{12.0pt}{\leavevmode\hbox{\set@color\leavevmode\hbox{\set@color\ignorespaces$\beta\sigma_{1}(1+\sigma_{2})$}}}\hskip
36.3346pt}}}}&\sigma_{2}+\alpha l&(\alpha l)^{2}\\\ \alpha
l&0&\eta\end{array}\right]$

and

$G_{2}(\alpha,\beta)=\left[\begin{array}[]{cccc}\sigma_{1}&\sigma_{1}&0\\\
\raisebox{-9.75pt}{\leavevmode\hbox{\set@color{\ignorespaces\ignorespaces\leavevmode\hbox{\set@color\hskip
36.3346pt\leavevmode\hbox{\set@color$+\alpha l(1+\sigma_{1}+\alpha
l)$}\raisebox{12.0pt}{\leavevmode\hbox{\set@color\leavevmode\hbox{\set@color\ignorespaces$\beta(1+\sigma_{2})$}}}\hskip
36.3346pt}}}}&\sigma_{2}+\alpha l&(\alpha l)^{2}\\\ \alpha
l&0&\eta\end{array}\right].$

###### Theorem 1

Suppose Assumptions 1 and 2 hold and choose $\alpha>0$ and $\beta\geq 0$ such
that $\rho(G_{1}(\alpha,\beta))<1$, then $\mathbf{x}^{k}$ generated by CTA-UGT
converges to $\mathbf{x}^{*}$ with the R-linear rate
$O(\rho(G_{1}(\alpha,\beta)^{k})$. Furthermore, $\rho(G_{1}(\alpha,\beta))<1$
if

$0\leq\beta<\frac{(1-\sigma_{1})(1-\sigma_{2})}{\sigma_{1}(1+\sigma_{2})}$

and

$0<\alpha<\min\left\\{\frac{1-\sigma_{2}}{l},\frac{-b+\sqrt{b^{2}-4ac}}{2a}\right\\},$

where $a=l^{3}+\mu l^{2}$, $b=2\mu l$, and
$c=\mu[\beta\sigma_{1}(1+\sigma_{2})-(1-\sigma_{1})(1-\sigma_{2})]$.

###### Theorem 2

Suppose Assumptions 1 and 2 hold and choose $\alpha>0$ and $\beta\geq 0$ such
that $\rho(G_{2}(\alpha,\beta))<1$, then $\mathbf{x}^{k}$ generated by ATC-UGT
converges to $\mathbf{x}^{*}$ with the R-linear rate
$O(\rho(G_{2}(\alpha,\beta)^{k})$. Furthermore, $\rho(G_{2}(\alpha,\beta))<1$
if

$0\leq\beta<\frac{(1-\sigma_{1})(1-\sigma_{2})}{\sigma_{1}(1+\sigma_{2})}$

and

$0<\alpha<\min\left\\{\frac{1-\sigma_{2}}{l},\frac{-b+\sqrt{b^{2}-4ac}}{2a}\right\\},$

where $a=\sigma_{1}(l^{3}+\mu l^{2})$, $b=(1+\sigma_{1}^{2})\mu l$, and
$c=\mu[\beta\sigma_{1}(1+\sigma_{2})-(1-\sigma_{1})(1-\sigma_{2})]$.

For the sake of readability, the proofs of Theorems 1 and 2 are placed in the
appendix.

##  IV Numerical Experiments

In this section, we evaluate the performance of UGT by solving the following
quadratic programming problem:

$\displaystyle\min_{x\in\mathbb{R}^{m}}$ $\displaystyle
F(x)=\frac{1}{n}\sum_{i=1}^{n}x_{i}^{\top}Q_{i}x_{i}+c_{i}^{\top}x_{i},$

where $Q_{i}\in\mathbb{R}^{m\times m}$ is a positive definite matrix. In
particular, different kinds of graphs are considered, included four digraphs:
directed cycle graph, directed exponential graphs with $e=2,4,6$, and four
undigraphs: cycle graph, Erdos–Renyi random graphs with the connectivity
probability $p=0.05,0.1,0.3$. The directed exponential graph with $n$ nodes is
generated by the rule that each node $i$ can send information to the nodes
$(i+2^{j})\mod n$, $j=0,1,\cdots,e-1$. The weight matrices $W_{1}$ and $W_{2}$
are constructed by the Laplacian method [3].

In experiments, we set $m=2$ and $n=100$, then generate $Q_{i}$ and $c_{i}$
randomly. For each graph, we compare the convergence rates of two versions of
CTA-UGT (ATC-UGT): $\beta=0$ (which corresponds to traditional gradient
tracking algorithms) and $\beta=w$, where $w\geq 0$ is the constant chosen
according to the rule that maximizing the convergence rate of CTA-UGT (ATC-
UGT) for the given graph. For a given $\beta$, $\alpha$ is determined by the
same rule. The experiments results are presented in Figs. 1, 2, 3 and 4, where
the relative optimality gap is defined as
$\frac{\|\mathbf{x}(k)-\mathbf{x}^{*}\|}{\|\mathbf{x}(0)-\mathbf{x}^{*}\|}$.
It is easy to see that the latter usually has a far faster convergence rate,
especially when the graph is poorly connected.

##  V Conclusion

In this work, the classical distributed optimization problem is studied.
Inspired by the implicit tracking mechanism, UGT, a unified algorithmic
framework, is developed from a pure primal perspective, which can unify most
existing distributed optimization algorithms with constant step-sizes. When
the global objective function is strongly convex, we prove that two variants
of UGT can both achieve linear convergence. Finally, numerical experiments are
taken to evaluate the performance of UGT.

Since the proofs of Theorems 1 and 2 are quite similar, we only provide the
proof of the former for the sake of conciseness. We first give some lemmas
which are necessary for the subsequent convergence analysis. For CTA-UGT,
define

$\displaystyle\bar{\mathbf{x}}^{k}=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}x_{i}^{k},$
$\displaystyle\bar{\mathbf{g}}^{k}=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}g_{i}^{k},$
$\displaystyle\bar{\nabla}f(\mathbf{x}^{k})=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(x_{i}^{k}).$

###### Lemma 1

Suppose Assumption 1 holds, then

$\displaystyle\bar{\mathbf{x}}^{k+1}=$
$\displaystyle\bar{\mathbf{x}}^{k}-\bar{\mathbf{g}}^{k},$
$\displaystyle\bar{\mathbf{g}}^{k+1}=$
$\displaystyle\alpha\bar{\nabla}f(\mathbf{x}^{k+1}).$

Proof. The first equality is obvious. Note that
$\mathbf{1}^{\top}(\mathbf{I}-\mathbf{W}_{2})=0$, we have

$\displaystyle\bar{\mathbf{g}}^{k+1}=\bar{\mathbf{g}}^{k}+\alpha(\bar{\nabla}f(\mathbf{x}^{k+1})-\bar{\nabla}f(\mathbf{x}^{k})),$

then we can obtain the second equality since $\mathbf{g}^{0}=\alpha\nabla
f(\mathbf{x}^{0})$.

###### Lemma 2

[8] Suppose Assumption 1 holds, then

$\displaystyle\|\mathbf{W}_{1}\mathbf{x}-\mathbf{1}\bar{\mathbf{x}}\|\leq$
$\displaystyle\sigma_{1}\|\mathbf{x}-\mathbf{1}\bar{\mathbf{x}}\|,$
$\displaystyle\|\mathbf{W}_{2}\mathbf{x}-\mathbf{1}\bar{\mathbf{x}}\|\leq$
$\displaystyle\sigma_{2}\|\mathbf{x}-\mathbf{1}\bar{\mathbf{x}}\|.$

###### Lemma 3

$\displaystyle\|\mathbf{x}-\mathbf{1}\bar{\mathbf{x}}\|\leq\|\mathbf{x}\|.$

Proof.

$\displaystyle\|\mathbf{x}-\mathbf{1}\bar{\mathbf{x}}\|^{2}$
$\displaystyle=\|\mathbf{x}\|^{2}+\|\mathbf{1}\bar{\mathbf{x}}\|^{2}-2\sum_{i=1}^{n}x_{i}^{\top}\bar{\mathbf{x}}$
$\displaystyle=\|\mathbf{x}\|^{2}+\|\mathbf{1}\bar{\mathbf{x}}\|^{2}-2n\bar{\mathbf{x}}^{\top}\bar{\mathbf{x}}$
$\displaystyle\leq\|\mathbf{x}\|^{2},$

which completes the proof.

###### Lemma 4

[8] Suppose Assumption 2 holds, then

$\|x-\alpha\nabla F(x)-x^{*}\|\leq\eta\|x-x^{*}\|,$

where $\eta=\min\\{|1-\alpha\mu|,|1-\alpha\bar{l}|\\}$.

###### Lemma 5

[22] Consider a nonnegative and irreducible matrix
$B=[b_{ij}]\in\mathbb{R}^{3\times 3}$ which satisfies that
$b_{ii}<\lambda^{*}$, where $\lambda^{*}>0$ and $i=1,2,3$. Then
$\rho(B)<\lambda^{*}$ iff $\text{det}[\lambda^{*}I-B]>0$.

Proof of Theorem 1. According to CTA-UGT and Lemma 1, we have

$\displaystyle\|\mathbf{x}^{k+1}-\mathbf{1}\bar{\mathbf{x}}^{k+1}\|$ (7)
$\displaystyle=\|\mathbf{W}_{1}\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}-(\mathbf{g}^{k}-\mathbf{1}\bar{\mathbf{g}}^{k})\|$
$\displaystyle\leq\sigma_{1}\|\mathbf{x}-\mathbf{1}\bar{\mathbf{x}}\|+\|\mathbf{g}^{k}-\mathbf{1}\bar{\mathbf{g}}^{k}\|,$

where the inequality holds due to Lemma 2.

Notice that

$\displaystyle\|(\mathbf{I}-\mathbf{W}_{2})\mathbf{W}_{1}\mathbf{x}^{k}\|$
$\displaystyle=\|\mathbf{W}_{2}\mathbf{W}_{1}\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}-(\mathbf{W}_{1}\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k})\|$
$\displaystyle\leq(1+\sigma_{2})\|\mathbf{W}_{1}\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}\|$
$\displaystyle\leq(1+\sigma_{2})\sigma_{1}\|\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}\|,$

where the two inequalities hold because of Assumptions 1 and 2, then we have

$\displaystyle\|\mathbf{g}^{k+1}-\mathbf{1}\bar{\mathbf{g}}^{k+1}\|$
$\displaystyle\leq\|\mathbf{W}_{2}\mathbf{g}^{k}-\mathbf{1}\bar{\mathbf{g}}^{k}\|+\beta\|(\mathbf{I}-\mathbf{W}_{2})\mathbf{W}_{1}\mathbf{x}^{k}\|$
$\displaystyle\quad+\|\alpha(\nabla f(\mathbf{x}^{k+1})-\nabla
f(\mathbf{x}^{k}))-\mathbf{1}(\bar{\mathbf{g}}^{k+1}-\bar{\mathbf{g}}^{k})\|$
$\displaystyle\leq\sigma_{2}\|\mathbf{g}^{k}-\mathbf{1}\bar{\mathbf{g}}^{k}\|+(1+\sigma_{2})\sigma_{1}\|\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}\|$
$\displaystyle\quad+\|\alpha(\nabla f(\mathbf{x}^{k+1})-\nabla
f(\mathbf{x}^{k}))\|$
$\displaystyle\leq\sigma_{2}\|\mathbf{g}^{k}-\mathbf{1}\bar{\mathbf{g}}^{k}\|+(1+\sigma_{2})\sigma_{1}\|\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}\|$
$\displaystyle\quad+\alpha l\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|,$

where the second inequality holds due to Lemmas 1 and 3 and the last
inequality holds since $f$ is $l$-smooth. In addition, we have

$\displaystyle\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|$
$\displaystyle=\|\mathbf{W}_{1}\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}-(\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k})-\mathbf{g}^{k}\|$
$\displaystyle\leq(1+\sigma_{1})\|\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}\|+\|\mathbf{g}^{k}\|$

and

$\displaystyle\|\mathbf{g}^{k}\|$
$\displaystyle\leq\|\mathbf{g}^{k}-\mathbf{1}\bar{\mathbf{g}}^{k}\|+\|\mathbf{1}\bar{\mathbf{g}}^{k}-\mathbf{1}\alpha\nabla
F(\bar{\mathbf{x}}^{k})\|$ $\displaystyle\quad+\alpha\|\mathbf{1}\nabla
F(\bar{\mathbf{x}}^{k})-\mathbf{1}\nabla F(x^{*})\|$
$\displaystyle\leq\|\mathbf{g}^{k}-\mathbf{1}\bar{\mathbf{g}}^{k}\|+\alpha
l\|\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}\|+\alpha
l\sqrt{n}\|\bar{\mathbf{x}}^{k}-x^{*}\|,$

where the letter holds because

$\displaystyle\|\bar{\mathbf{g}}^{k}-\alpha\nabla F(\bar{\mathbf{x}}^{k})\|$
$\displaystyle=\alpha\left\|\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(x_{i}^{k})-\nabla f_{i}(\bar{\mathbf{x}}^{k})\right\|$ (8)
$\displaystyle\leq\alpha
l\sum_{i=1}^{n}\frac{\|x_{i}^{k}-\bar{\mathbf{x}}^{k}\|}{n}$
$\displaystyle\leq\alpha
l\sqrt{\sum_{i=1}^{n}\frac{\|x_{i}^{k}-\bar{\mathbf{x}}^{k}\|^{2}}{n}}$
$\displaystyle\leq\frac{\alpha
l}{\sqrt{n}}\|\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}\|.$

It follows that

$\displaystyle\|\mathbf{g}^{k+1}-\mathbf{1}\bar{\mathbf{g}}^{k+1}\|$ (9)
$\displaystyle\leq[(1+\sigma_{2})\sigma_{1}+\alpha l(1+\sigma_{1}+\alpha
l)]\|\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}\|$
$\displaystyle\quad+(\sigma_{2}+\alpha
l)\|\mathbf{g}^{k}-\mathbf{1}\bar{\mathbf{g}}^{k}\|+(\alpha
l)^{2}\sqrt{n}\|\bar{\mathbf{x}}^{k}-x^{*}\|.$

Based on Lemma 1, we have

$\displaystyle\|\bar{\mathbf{x}}^{k+1}-x^{*}\|$ (10)
$\displaystyle\leq\|\bar{\mathbf{x}}^{k}-\alpha\nabla
F(\bar{\mathbf{x}}^{k})-x^{*}\|+\|\alpha\nabla
F(\bar{\mathbf{x}}^{k})-\bar{\mathbf{g}}^{k}\|$
$\displaystyle\leq\eta\|\bar{\mathbf{x}}^{k}-x^{*}\|+\frac{\alpha
l}{\sqrt{n}}\|\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}\|,$

where the last inequality holds because of Lemmas 4 and 8.

Combining LABEL:bx, LABEL:19 and LABEL:20, we can obtain that

$\displaystyle\mathbf{e}^{k+1}\leq G_{1}(\alpha,\beta)\mathbf{e}^{k},$

where

$\mathbf{e}^{k}=\left[\begin{array}[]{c}\|\mathbf{x}^{k}-\mathbf{1}\bar{\mathbf{x}}^{k}\|\\\
\|\mathbf{g}^{k}-\mathbf{1}\bar{\mathbf{g}}^{k}\|\\\
\sqrt{n}\|\bar{\mathbf{x}}^{k}-x^{*}\|\end{array}\right].$

If $G_{1}$ is nonnegative, i.e., all entities of $G_{1}$ are nonnegative, we
have

$\mathbf{e}^{k+1}\leq\rho(G_{1})^{k}\mathbf{e}^{0},$

which means that CTA-UGT converges linearly if $\rho(G_{1})<1$.

According to Lemma 5, to guarantee $\rho(G_{1})<1$, we first need to assure
$0\leq g_{ii}<1$, which holds when
$0<\alpha<\frac{1-\sigma_{2}}{l}<\frac{1}{l}$, since $\sigma_{1}<1$ and
$\eta=1-\alpha\mu$ if $\alpha<\frac{1}{l}<\frac{1}{\bar{l}}$. Furthermore, we
must guarantee that $\text{det}[I-G_{1}]>0$. Note that

$\displaystyle\text{det}[I-G_{1}]$ $\displaystyle=-(\alpha
l)^{3}+(1-\eta)[-(\alpha l)^{2}-2\alpha l$
$\displaystyle\quad+(1-\sigma_{1})(1-\sigma_{2})-\beta\sigma_{1}(1+\sigma_{2})],$

hence it must hold that

$\displaystyle(\alpha l)^{3}+\alpha\mu[(\alpha l)^{2}+2\alpha
l+\beta\sigma_{1}(1+\sigma_{2})$
$\displaystyle\quad-(1-\sigma_{1})(1-\sigma_{2})]<0,$

which is equivalent to

$\alpha^{2}l^{3}+\mu[(\alpha l)^{2}+2\alpha
l+\beta\sigma_{1}(1+\sigma_{2})-(1-\sigma_{1})(1-\sigma_{2})]<0,$

rearranging it gives that

$\displaystyle\alpha^{2}(l^{3}+\mu l^{2})+2\mu
l\alpha+\mu[\beta\sigma_{1}(1+\sigma_{2})$ (11)
$\displaystyle\quad-(1-\sigma_{1})(1-\sigma_{2})]<0.$

Recall the expressions of $a$, $b$, and $c$ in Theorem 1 and
$\beta<\frac{(1-\sigma_{1})(1-\sigma_{2})}{\sigma_{1}(1+\sigma_{2})}$, then 11
can be guaranteed by letting

$\alpha<\frac{-b+\sqrt{b^{2}-4ac}}{2a},$

which finishes the proof.

## References

  * [1] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson, “A survey of distributed optimization,” Annual Reviews in Control, vol. 47, pp. 278–305, 2019.
  * [2] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009.
  * [3] W. Shi, Q. Ling, G. Wu, and W. Yin, “Extra: An exact first-order algorithm for decentralized consensus optimization,” SIAM Journal on Optimization, vol. 25, no. 2, pp. 944–966, 2015.
  * [4] Q. Ling, W. Shi, G. Wu, and A. Ribeiro, “Dlm: Decentralized linearized alternating direction method of multipliers,” IEEE Transactions on Signal Processing, vol. 63, no. 15, pp. 4051–4064, 2015.
  * [5] Z. Li, W. Shi, and M. Yan, “A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates,” IEEE Transactions on Signal Processing, vol. 67, no. 17, pp. 4494–4506, 2019.
  * [6] K. Yuan, B. Ying, X. Zhao, and A. H. Sayed, “Exact diffusion for distributed optimization and learning—part i: Algorithm development,” IEEE Transactions on Signal Processing, vol. 67, no. 3, pp. 708–723, 2018.
  * [7] A. Nedic, A. Olshevsky, and W. Shi, “Achieving geometric convergence for distributed optimization over time-varying graphs,” SIAM Journal on Optimization, vol. 27, no. 4, pp. 2597–2633, 2017.
  * [8] G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1245–1260, 2017.
  * [9] P. Di Lorenzo and G. Scutari, “Next: In-network nonconvex optimization,” IEEE Transactions on Signal and Information Processing over Networks, vol. 2, no. 2, pp. 120–136, 2016.
  * [10] G. Scutari and Y. Sun, “Distributed nonconvex constrained optimization over time-varying digraphs,” Mathematical Programming, vol. 176, no. 1, pp. 497–544, 2019.
  * [11] J. Xu, S. Zhu, Y. C. Soh, and L. Xie, “Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes,” in 2015 54th IEEE Conference on Decision and Control (CDC), pp. 2055–2060, IEEE, 2015.
  * [12] A. Nedić, A. Olshevsky, W. Shi, and C. A. Uribe, “Geometrically convergent distributed optimization with uncoordinated step-sizes,” in 2017 American Control Conference (ACC), pp. 3950–3955, IEEE, 2017.
  * [13] D. Jakovetić, “A unification and generalization of exact distributed first-order methods,” IEEE Transactions on Signal and Information Processing over Networks, vol. 5, no. 1, pp. 31–46, 2018.
  * [14] A. Sundararajan, B. Van Scoy, and L. Lessard, “A canonical form for first-order distributed optimization algorithms,” in 2019 American Control Conference (ACC), pp. 4075–4080, IEEE, 2019.
  * [15] S. A. Alghunaim, E. Ryu, K. Yuan, and A. H. Sayed, “Decentralized proximal gradient algorithms with linear convergence rates,” IEEE Transactions on Automatic Control, 2020.
  * [16] J. Xu, Y. Tian, Y. Sun, and G. Scutari, “Distributed algorithms for composite optimization: Unified framework and convergence analysis,” IEEE Transactions on Signal Processing, 2021.
  * [17] S. A. Alghunaim, K. Yuan, and A. H. Sayed, “A linearly convergent proximal gradient algorithm for decentralized optimization,” Advances In Neural Information Processing Systems 32 (Nips 2019), vol. 32, no. CONF, 2019.
  * [18] J. Li and H. Su, “Implicit tracking-based distributed constraint-coupled optimization,” arXiv preprint arXiv:2201.07627, 2022.
  * [19] M. Zhu and S. Martínez, “Discrete-time dynamic average consensus,” Automatica, vol. 46, no. 2, pp. 322–329, 2010.
  * [20] S. S. Kia, J. Cortés, and S. Martínez, “Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication,” Automatica, vol. 55, pp. 254–264, 2015.
  * [21] S. S. Kia, J. Cortés, and S. Martinez, “Dynamic average consensus under limited control authority and privacy requirements,” International Journal of Robust and Nonlinear Control, vol. 25, no. 13, pp. 1941–1966, 2015\.
  * [22] S. Pu and A. Nedić, “Distributed stochastic gradient tracking methods,” Mathematical Programming, vol. 187, no. 1, pp. 409–457, 2021.


Structure Functions and Parton Densities: a Session Summary

Benjamin Nachman1$\star$, Katarzyna Wichmann2 and Pia Zurita3

1 Physics Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720,
USA

2 DESY, Notkestrasse 85, 22607 Hamburg, Germany

3 Institut fur̈ Theoretische Physik, Universität Regensburg, 93040 Regensburg,
Germany

*<EMAIL_ADDRESS>
Proceedings for the XXVIII International Workshop
on Deep-Inelastic Scattering and Related Subjects,
Stony Brook University, New York, USA, 12-16 April 2021
10.21468/SciPostPhysProc.?

## Abstract

Studies of fragmentation and parton density functions are a core component of
research in high energy particle and nuclear physics. These quantities are
inherently interesting as a probe of the quantum nature of the strong force
and are also essential ingredients to additional studies in high energy
scattering experiments. These proceedings provide an overview of the state of
the art in this area, as presented at the Deep-Inelastic Scattering Conference
in the Spring of 2021.

###### Contents

  1. 1 Introduction
  2. 2 Overview of Parton Density Functions
    1. 2.1 Expanding the fitted data set
    2. 2.2 DIS off heavy-nuclei
    3. 2.3 DIS with deuterium targets
    4. 2.4 Other topics related to proton PDFs
  3. 3 Nuclear PDFs
  4. 4 TMD PDFs
  5. 5 Lattice PDFs
  6. 6 Experimental Probes
  7. 7 Structure functions beyond PDFs

##  1 Introduction

This document summarises the topics discussed in the parallel session
_Structure Functions and Parton Densities_. Therefore, it does not aim at
being a detailed description of the presented results, which can be found in
the accompanying articles of these proceedings. Instead we would like to
provide the readers with a list of the key points, and encourage them to read
the corresponding contributions.

##  2 Overview of Parton Density Functions

The luminosity upgrade of the LHC [1] and the upcoming Electron-Ion Collider
[2] will provide measurements of unprecedented precision. In order to have
meaningful comparisons between data and theory, observables in the pQCD
framework will require a more precise knowledge of the cross-section for both
the perturbative and non-perturbative components. The former advances slowly,
with higher order calculations requiring the computation of an ever increasing
number and types of diagrams, while for the latter several sources of
improvements are being explored. Recent results addressing both sides of the
picture were shown in this conference.

For the perturbative side, preliminary results towards the calculation of the
next-to-next-to-next-to-next-to leading order ($N^{4}LO$) DIS cross-section
and four-loop splitting functions were presented. The method relies on
obtaining the Mellin moments by reducing the calculation to a set of master
integrals, which in turn can be used to reconstruct the coefficient functions.
At the time of the presentation the result of the three loop calculation were
yet to be compared with the already known one for finite Mellin momenta [3, 4,
5, 6], the following step being the four loop.

More loops in the QCD perturbative expansion also means that, at some point,
the magnitude of the QED contribution will be comparable to the one from QCD.
A new approach for the treatment of these terms, equally applicable to the
extraction of collinear and transverse momentum dependent parton distribution
functions, was presented [7]. In it, the radiative corrections are resummed
into sets of universal lepton and fragmentation/jet distributions.

As much as higher order calculations are necessary, increasing the precision
of the non-perturbative parton distribution functions (PDFs) is equally
important. While the computation of PDFs from first principles is experiencing
significant improvements in the field of Lattice QCD (see Sec. 5 for the
latest results), we still rely on global fits to the world data for their
extraction. In this session several groups have presented improvements to
their analyses. The changes can roughly be split into three categories: adding
more data, taking into account nuclear corrections to processes involving
heavy nuclei as targets, and considering the nuclear corrections in the case
of deuterium targets. The last two points have already been included in
previous releases of the PDF fits and will not mentioned in the following.

###  2.1 Expanding the fitted data set

One of the paths to better constrain the PDFs is the inclusion of more data,
which can provide constraints in previously unexplored regions and/or, if the
novel data have a higher precision, help reduce the uncertainties. The CTEQ-
TEA group presented a comparison of their CT18 NNLO [8] and accompanying
alternative analyses that include the most recent LHC data, with emphasis on
dealing with tensions among data sets and properly characterising the goodness
of the fit [9].

In the same line, the CJ group introduced the efforts towards the update of
their PDF set CJ15 [10]. The ongoing study incorporates data from DIS at JLAB
at both $6$ and $12$ GeV, electroweak boson production at LHC and RHIC, Drell-
Yan at RHIC, and preliminary Drell-Yan data from SeaQuest. These last two have
a significant impact in the up and down sea quarks distributions. The RHIC
data is compatible within uncertainties with the Drell-Yan measurement of E866
in the $x<0.3$ region. The preliminary SeaQuest data and the one from E866 do
not overlap in the high $x$ region, which translates to quite different
behaviours of the $\bar{d}/\bar{u}$ ratio in the CJ analysis.

Adding new data is also the basis for the update of the MSHT (formerly MMHT,
formerly MRST) group. The MSHT20 set [11] including the final Tevatron data,
the combined HERA data from DIS, and some of the vector boson production,
inclusive jets and top quark measured at the LHC. A fraction of the LHC data
has been shown to have significant tension among them and thus were not
considered. The fit was done fully at NNLO (if possible) with NLO QED
corrections whenever required, and using more flexible functional forms for
the PDFs, which increased the number of parameters to determine but reduced
tensions between data sets. The new parametrisation coupled with the extended
data set resulted in the reduction of the uncertainty bands of all species,
and changes in the shape of the down valence and strange distributions, and in
the $\bar{d}-\bar{u}$ difference.

Equally, the JAM collaboration has presented a new analysis including the
latest electroweak boson production data from LHC. These play a crucial role
in constraining the up and down sea distributions. This new extraction was
focused on exploring the high-$x$ region by lowering the invariant mass cut
from the usual $W^{2}\sim 10\text{ GeV}^{2}$ to $W^{2}=3\text{ GeV}^{2}$. In
order to achieve a good description of the high-$x$, low $W^{2}$ data, higher
twist corrections, including target mass corrections, were needed. Nuclear
effects for the DIS data off deuterium were also considered (see Subsec. 2.3).

The NNPDF collaboration presented the ongoing work towards the NNPDF4.0 set,
an update of their previous installment NNPDF3.1 [12]. The number of points
fitted has been extended with the single top, $W+$jet, isolated photon, and
di-jets measurements at the LHC. The DIS$+$jet data from HERA were also
considered by means of a re-weighting technique. The main differences include,
among others, having a parametrisation for the charm quark and its NNLO mass
corrections, a new parametrisation, a new optimisation strategy based on
gradient descent algorithms and positivity constraints for the gluon and light
flavours PDFs[13]. For the latter there was a dedicated talk on the positivity
of the PDFs in the $\bar{MS}$ scheme ($\bf ID=396$). Some exceptions aside,
the fit has an overall good quality, with the LHC data playing a crucial role
in separating the non-strange sea quarks. However it is noticed that the
flavour separation strongly depends on having an intrinsic or a perturbative
charm distribution, the former being preferred as it provides a better
description of the LHC data. The code used to produce this PDF set is also to
be publicly available.

A different approach to improve the PDFs has been proposed in recent years by
the JAM collaboration. Instead of using only inclusive data, they advocate for
the simultaneous determination of the collinear PDFs and fragmentation
functions (FFs). Here the group presented their results for fitting pion, kaon
and charged hadron production and proton PDFs, using a multi-step fitting
procedure [14]. The inclusion of SIDIS data impacts the sea distributions, in
particular that of the strange quark which is suppressed with respect to the
case of not having the kaon data in the fit.

In addition to updates from the PDF fitting groups, multiple experiments also
presented detailed studies of PDF fits, highlighting their unique
contributions to global constraints. For example, the ATLAS Collaboration
presented a new PDF fit [34] using $W/Z$ and $W/Z$+jets data from the LHC Run
1 combined with HERA data. The addition of $V$+jets data significantly reduces
the uncertainty and the new fit shows more strangeness suppression than older
fits. High-$x$ studies were presented by the Zeus Collaboration [35]. The LHCb
Collaboration discussed their contributions to the quark PDFs at high-$x$ with
both their primary $pp$ collision data as well as their fixed-target collision
data using the Measuring Overlap with Gas (SMOG) system [36].

###  2.2 DIS off heavy-nuclei

Another issue to be addressed is the problem of disentangling the different
parton flavours, which are linked both by their specific combinations in the
observables and the scale evolution. This can be done by including in the fits
data that are sensitive to other, linearly independent, combinations of PDFs.
To this purpose the charged current (CC) DIS process with the exchange of a
$W^{+/-}$ boson is an ideal candidate. However most of the data available
comes from the collision of neutrino beams with fixed nuclear targets, which
not only limits the kinematic coverage of the data but also introduces the
problem of correctly quantifying the nuclear effects. Moreover, tension exists
between data sets (see Sec. 3) which hints at the non-universality of nuclear
effects.

In the case of the NNPDF collaboration, they are considering these corrections
in NNPDF4.0, in the form of theoretical uncertainties as opposed to the
traditional approach of modifying the computed central values using nuclear
PDFs or theoretical models. The procedure consists on comparing the values of
the nuclear observables computed with and without the nNNPDF2.0 set, and
adding them to the fit in the form of a theoretical nuclear covariance matrix
[15]. The overall result, together with the modifications due to deuterium
targets (see Subsec. 2.3), is a significant improvement in the quality of the
fit, which highlights the relevance of nuclear effects to the improvement of
proton PDFs.

###  2.3 DIS with deuterium targets

A different approach to solve the flavour decomposition problem is to use
neutron data, under the form of deuterium beams/targets. While in this case
the nuclear effects are smaller than for CC DIS, the fact remains that
deuterium is a bound nucleus and, when aiming for a high precision extraction
of the proton PDFs, this can not be overlooked.

The CTEQ and CJ groups have presented a detailed study of the impact of the
nuclear corrections in deuterium in their corresponding fits [16], using the
Hessian sensitivity method [17]. In the case of CT18NNLO, the cut on the
invariant mass $W$ in DIS restricts the impact of including nuclear
modifications, though the description of some observables does improve. By
contrast, as the CJ15 fit has a less stringent kinematic cut and thus the
sensitivity to the modeled nuclear effects is more striking, with the
$\chi^{2}$ decreasing $\sim 5\%$.

The nuclear modifications for deuterium targets were also newly addressed in
the update studies of the JAM and NNPDF collaborations mentioned above. In the
case of the JAM collaboration different implementations of the corrections
using theoretical models from Nuclear Physics were used, all giving
consistently similar fits. The NNPDF collaboration used instead an iterative
procedure that permits to determine both the deuteron and proton PDFs, the
latter with deuteron uncertainties. While the impact is less significant than
the one found for the CC data, they are nonetheless relevant when aiming for
higher precision in the proton distributions.

###  2.4 Other topics related to proton PDFs

The significant changes in the analyses of the proton PDF of CT and MSHT have
compelled to perform a benchmarking exercise with these two PDF sets and
NNPDF3.1. Preliminary results using a reduced data set common to the three PDF
extractions, with emphasis on the future precision physics at the LHC, have
been presented. With the limited amount of data a good agreement is observed
and progress has been made towards a future combination of the individual PDF
extractions into a PDF4LHC21 set.

##  3 Nuclear PDFs

The correct characterisation of nuclear effects in the parton distributions is
important not only due to their relevance in the determination of the proton
PDFs and as baseline for new phenomena in heavy-ion collisions. Ultimately,
the world around us is composed of nucleons bound together in more complex
structures and therefore the nPDFs, that condense in a few parameters the
behaviour of partons inside nuclei, are interesting on their own right.

Dedicated studies of nPDFs have existed for decades now, the extractions done
in the same framework as the free proton PDFs, and having them as guidance.
The nuclear effects are generally added as a modification of a baseline PDFs,
either by expanding the parametrisation or multiplying it by a factor, in both
cases with a dependence on the atomic mass number $A$. In this conference
three of the groups presented new results: EPPS and NNPDF the status of their
updates, nCTEQ specific studies to extend the nCTEQ15 analysis. As before, we
will mention only the changes with respect to their previous work.

The EPPS group has extended the data set of EPPS16 [18] by including the JLAB
NC DIS data, the full CMS di-jets data (replacing the previously used forward-
backward ratio), $D^{0}$ meson production from LHCb and the $W$ boson
production from CMS in the Run2. All the LHC data considered are from $p+Pb$
collisions. The high precision JLAB data are perfectly described taking into
account leading target-mass corrections, with no hints of tensions with the
assumption of isospin validity, confirming previous results [19]. Regarding
the $D^{0}$ production, both the forward and backward data are very well
accommodated in the fit. The $W$ boson data is equally well described and does
not seem to provide extra constraints with respect to those imposed by the
Run1 and CC DIS. As for the di-jets data, the ratio to the $p+p$ reference was
fitted. Significant tension was found between the highest forward rapidity
bins and all other data in the fit despite implementing a more flexible
functional form. Beyond having more data and parameters, the new study
includes for the first time the proton uncertainties by fitting the nuclear
modifications separately for each error set of their chosen proton PDF
baseline. While these are not dominant for most experiments considered and can
be reduced by using ratios instead of absolute cross-sections, they become
sizable for some observables. The overall effect on the nPDFs is some
reduction of the uncertainty bands in the sea sector and, more importantly, a
better constraint of the gluon density at high-$x$, pointing to a real anti-
shadowing (enhancement) effect.

The NNPDF collaboration has presented the current status of their next
instalment of medium modified distributions: nNNPDF3.0. The have now performed
a NNLO fit, including $D^{0}$ meson data from LHCb, and electroweak boson
production and di-jet data from CMS, in $p+Pb$ collisions at the LHC, the last
two using K-factors. Their proton baseline is also updated to the NNPDF4.0 set
(see Subsec. 2.1 for details). As it happens in the EPPS analysis, the extreme
rapidity bins of the di-jet data can not be accommodated and a reasonable fit
would require their removal. While the use of the missing correlated
uncertainties might play a role here, studies performed with nNNPDF2.0 [20]
and their baseline NNPDF3.1 suggest that the main problem is the inability of
the latter to describe the $p+p$ di-jet data. Further investigations and the
incorporation of the $Z$ and $W$ production data from ATLAS are ongoing.

From their part, the nCTEQ group have presented three studies, each addressing
different aspects for improvement. One of them, in collaboration with the CJ
group, touches upon the use of available data from NC DIS in the high-$x$
region, in particular the high precision JLAB $6\text{ GeV}$ data, and the
impact on the valence quark distributions (D=452). By relaxing the cuts on
virtuality and invariant mass more data enters in this _nCTEQ15-HIX_ fit [21],
in a kinematical region where higher twists effects become relevant. In
particular those considered are target-mass corrections and non-perturbative
multi-quark interactions. The impact of modelling the nuclear effect in
deuterium in the same way as the CJ group is also considered. Fits including
only one type of correction or both of them show a significant improvement in
the quality of the fit w.r.t. no modifications, with the deuterium dominating
the decrease of the $\chi^{2}$. Preliminary results considering data with
$x<0.7$ present a change of up to $20\%$ in the $0.6<x<0.7$ region, especially
for the up and down densities.

The second topic address by the nCTEQ group was the determination of the
strange nPDF. In a previous study where the compatibility of the LHC
electroweak boson data in $p+Pb$ collisions with the nCTEQ15 fit was analysed,
the parametrisation of the strange distribution was found to be too
restrictive. More parameters were needed to accommodate the data into the fit,
with a consequent change in shape. The work presented studies in detail the
compatibility of the CC DIS data (not included in nCTEQ15), the tensions among
the different measurements and the impact on flavour separation [25].
Specifically, the dimuon data from CCFR and NuTev, and the NuTev, CDHSW and
Chorus data were considered. It is known that a fraction of the NuTeV cross-
section has significant tensions with the other experiments. This is
particularly true if the correlated uncertainties are not taken into account.
In this work, including the fully correlated uncertainties of the NuTeV data
falls short at removing the tensions, which remain for $x\lesssim 0.1$ and
$x\sim 0.6$. However the main source of incompatibility, defined with a
certain criterion, is the low-$x$ data and their exclusion from the fit gives
a consistent result. They do have a significant effect in the shape of the
nuclear strange PDF, e.g. $f^{Fe}_{s}$ being a factor two larger at $x\sim
10^{-3}$ when the low-$x$ data are not removed. While the inclusion of the LHC
data does indeed reduce the uncertainty of the gluon nPDF, the shape of the
strange density remains largely unknown.

Before the LHC di-jet data became available, the only direct constraint over
the gluon density included in the nPDF fits came from single hadron production
(SIH) in $d+Au$ collisions at RHIC. For this observable the gluon and quark
densities enter at the same order in the calculation and thus are ideal to
access the gluon nPDF. The down side of it is, aside from possible final state
nuclear effects, that it strongly depends on the set of fragmentation
functions (FFs) used to describe how a parton coming out of the hard
interaction fragments into the detected hadron. With many FF sets available
and new precise data from ALICE, the nCTEQ collaboration presented a detailed
analysis of the modifications of nPDFs when including SIH data into the nPDF
fits nCTEQ15 and nCTEQ15WZ (with electroweak boson production from LHC). In
general, equally good fits can be obtained with all FFs considered, of course
the resulting nPDFs being different. The most impact is seen in the gluon and
strange distributions, with enhancement for $x\sim 10^{-3}$ [22].

##  4 TMD PDFs

Collinear PDFs accurately describe a large variety of processes involving
proton initial states with transverse energy comparable to the momentum
transfer. However, the proton structure is more complicated and a growing
number of measurements are sensitive to the transverse momentum of the partons
within the proton. In particular, when the transverse momentum of the outgoing
partons is much smaller than the momentum transfer, all the way down to scales
of order $\Lambda_{\text{QCD}}$, collinear PDFs are insufficient for
describing the data. This can be remedied with the introduction of transverse
momentum dependent PDFs (TMD PDFs), which are of significant interest to the
particle and nuclear physics communities. While TMD PDFs were a component of
many talks, there was a dedicated session about theoretical and
phenomenological aspects of these objects, as well as global fits at DIS.
These talks spanned theory developments to global fits, to event simulations
using TMD evolution [37]. For example the first determination of TMD photon
densities with the Parton Branching method was presented [38]. The photon
distribution was generated perturbatively without intrinsic photon component
using fits to inclusive DIS HERA data. These TMDs give a good description of
the CMS dilepton mass measurements at $\sqrt{s}=13$ TeV for masses between 15
to 3000 GeV .

There were also presentations showing dedicated experimental measurements
probing TMD PDFs. The COMPASS Collaboration showed new preliminary results for
unpolarised Semi-Inclusive DIS of muons on protons. For the TMD physics two
observables in unpolarized SIDIS are particularly interesting: azimuthal
asymmetries and transverse momentum distributions, both presented by COMPASS.
Both observables were measured over a wide kinematic range of $Q^{2}$, $x$ and
$W$. There is a lot of theoretical work to reproduce the experimental
distributions, the dependence on $Q^{2}$ is expected from the predictions and
the behaviour as a function of $W$ can be studied using the COMPASS new
results.

The H1 Collaboration measured the NC jet production as a function of the jet
transverse momentum and pseudorapidity, as well as lepton-jet momentum
imbalance $q_{T}$ and azimuthal angle correlation [39]. The cross sections
were compared to TMD calculations which, without free parameters, described
the data over wide kinematic range. In comparison with the collinear
predictions, the TMD calculation gives a better description at low $q_{T}$ and
the collinear calculation at large $q_{T}$. The H1 data can be used to
constrain matching between TMD and collinear pQCD frameworks.

Yet another another measurement sensitive to unpolarized TMD PDFs was
presented by the STAR Collaboration. Preliminary results on differential $Z$
cross section as a function of the $Z$ transverse momentum were compared to
various TMD PDFs. The data are reasonably described by these calculations and
shows a possibility to constrain them further.

##  5 Lattice PDFs

The collinear PDFs can be formally defined in terms of matrix elements of
specific bi-local operators on the light cone. However, these can not be
analytically calculated and we have to recur to global fits such as the ones
mentioned in Sec. 2. In Lattice QCD the computation of parton densities from
first principles is also not feasible as long as this definition is used, as
the light-cone distances shrink to the origin in Euclidean space-time.
Nonetheless, parton densities (collinear, unintegrated, generalised) from the
Lattice are starting to become a reality due to several approaches being
implemented [26]. While there are several options, we focus here in the two
that were part of the session.

On the one hand we have the _pseudo_ -PDFs [27]. They generalise the PDFs onto
spacelike intervals and are defined as the Fourier transforms of the Ioffe-
time distributions (ITD) [28, 29]; in the limit of the interval going to zero
and with appropriate matching conditions, one recovers the collinear PDFs.
This means that if the interval is small its inverse plays a role similar to
the renormalization parameter of the scale dependent PDFs (with some
differences). One can then write evolution equations for the reduced ITD. The
HadStruct collaboration has presented the results needed to calculate the
matrix elements and the matching condition for obtaining the gluon PDFs in the
pseudo-PDF approach [30]. Using the external field method [31], the gluon-
gluon and gluon-quark kernels were computed. By parametrising the collinear
gluon and singlet quark combination, the values of the parametres can be found
by fitting to the Lattice results for the matrix elements.

The same group has also presented the determination of the nucleon valence
quark distribution using a pion mass of $m_{\pi}=350$ MeV and lattice spacing
$a=0.091$ fm, and applying different techniques for the computation of the
matrix elements. The real part of the inverse Fourier transform, which gives
the valence distributions, was performed by writing the valence PDF as an
Euler Beta function multiplied by a polynomial of degree one, the parameters
determined by the Lattice matrix elements. The result is a PDF that closely
resembles in shape, but overshoots, the fitted PDFs for $x>0.1$. In the
$x<0.1$ region the comparison is significantly worse, though there is no
agreement between the PDF sets either.

On the other hand we have the _quasi_ -PDFs, also defined as the Fourier
transform of the ITD with respect to an space-like separation that only has
one spatial component, in the frame in which the proton momentum is in that
particular direction [32]. The collinear PDFs are recovered from the quasi-
PDFs by taking the limit of infinite proton momentum. The Lattice Parton
Collaboration presented a self-renormalization method to deal with the
divergence that appears in the calculation of the quasi-light-front correlator
in the context of the Large Momentum Effective Field Theory (LaMET) [33]. The
main idea of this model independent approach is to perform the extraction of
the renormalization factor and residual contribution directly from the matrix
element.

In the contect of quasi-PDFs, the determination of pion valence PDFs and
electromagnetic form factors were presented. For the PDFs the calculation was
performed using the physical pion mass, which was found to have a limited
impact on the distributions. The reconstruction of the x-dependence of the
PDFs was done with the the first few moments, extracted using both the NLO and
NNLO matching formulas. The latter gave a far better agreement with the pion
PDFs obtained from fits than the former. The pion form factors and charge
radius were also computed, in good agreement with the measured data. Further
improvements are under consideration, including the possible use of a matching
formula that incorporates resummation, and the extraction of higher moments.

##  6 Experimental Probes

Production of $W$ and $Z$ bosons in proton-proton collisions and fixed target
experiments provides stringent tests of calculations based on SM and gives
access to quark and antiquark content of the proton. Here especially
interesting is the antiquark flavor asymmetry in the proton, measured as the
the ratio $\bar{d}/\bar{u}$, where the high $x$ region $x>0.3$ is of
particular importance. The SeaQuest Collaboration measured the Drell-Yan muon
pair production using a proton beam at an energy of $120$ GeV and liquid
hydrogen and deuterium targets [40]. The cross section ratio of the deuterium
and hydrogen data were measured in the wide rage of $x$ for $0.13<x<0.45$ and
were used as an input to extract the $\bar{d}/\bar{u}$ ratio in this region.
For $0.35<x<0.45$ this is a first measurement of the antiquark flavor
asymmetry in the proton. In the whole measured $x$ range $\bar{d}/\bar{u}>1$.
This results were compared with various theoretical models. They agree well
with the predictions of the meson-baryon model [41] as well as with the
predictions of the statistical parton distributions [42]. The STAR experiment
at RHIC presented a complementary measurement of the $W$ and $Z/\gamma^{*}$
differential and total cross sections in p+p collisions at $\sqrt{s}=500$ GeV
and $510$ GeV [43]. These measurements were taken at high $Q^{2}$ and
$0.1<x<0.3$ and can serve as input into global analyses to provide constraints
on the sea quark distributions. Another set of measurements important in
constraining distributions of the valence and sea quarks in the proton was
provided by the CMS Collaborations, obtained in proton-proton collisions at
$\sqrt{s}=13$ TeV. It included measurements of the Drell-Yan processes [44],
$Z$ differential cross sections [45] and the study of the $W$ boson rapidity,
helicity, double-differential cross sections and charge asymmetry [46].
Additionally various rare decay channels of the $W$ were explored, including
decays into three pions [47] and a pion and a photon [48]. This wide range of
results also allows probing perturbative and non-perturbative QCD effects and
rare decay channels, as well as provides valuable input to improve theoretical
models. The data are used to test various MC approaches and their validity at
different corners of the LHC phase-space.

A complement to dilepton processes is processes involving pairs of quarks and
gluons. While jet cross sections are among the first measurements performed at
hadron colliders, we heard important updates from STAR and ATLAS on high-$x$
physics where statistics are limited. In particular, STAR presented a new
measurement of the inclusive dijet cross section, extending previous results
with polarized $pp$ collisions [49]. These measurements have important
constraint power for the high-$x$ behavior of the gluon PDF. The ATLAS
Collaboration presented a variety of measurements of the $t\bar{t}$
differential cross section. This included a new result using $\sqrt{s}=5.02$
TeV [50], which provides an interesting data point for comparing with the
larger LHC datasets collected at $\sqrt{s}=7,8$, and $13$ TeV. These data
provide a consistent picture across center of mass energies and have
constraining power to distinguish between various PDF sets.

As the namesake of the DIS conference series, it was exciting to also hear
updates from high energy lepton-hadron collisions. The COMPASS experiment at
CERN presented a variety of results on semi-inclusive deep inelastic (SIDIS)
and deeply virtual Compton scattering. These data provide powerful insight
into azimuthal asymmetries and TMD PDFs. New data with a proton target are now
being analyzed and preliminary results were discussed in the context of the
measured energy spectra and angular asymmetries. The H1 Collaboration also
presented a new result sensitive to TMD PDFs, in DIS at higher $Q^{2}$ with
azimuthal decorrelations using jets [51]. This measurement reports the
differential cross section of jets in the Born-level configuration. One
particularlly interestin feature of this new measurement is that it involved
the first machine learning-based unfolding [52] in particle or nuclear
physics. With this technique, spectra can be corrected for detector effects
without binning and in a large number of dimensions simultaneously.

##  7 Structure functions beyond PDFs

Collinear and un-integrated distributions functions are not the only way of
describing the measurements. If one is interested in phenomena occurring in
regions where pQCD is not fully tested/applicable or its use is inconvenient,
other perspectives can become a more suitable choice. In this section we
summarise two presentations that take this approach: the first one for photon
initiated processes at the LHC, the second one for the study of the DIS
structure functions in the low $x$ and $Q^{2}$ region that will be covered at
the EIC.

As discussed in Sec. 2, the increasing precision at the LHC is reaching the
stage at which QED processes become as relevant as the pure QCD ones. For some
observables the photon initiated processes play a key role, the LHC
effectively acting as a $\gamma+\gamma$ collider. The computation of these
contributions can be done in two ways. One approach is to determine the photon
content of the proton by means of a photon PDF, to be extracted from fits.
This has been and is done with high precision at LO in $\alpha_{s}$, but this
feature does not translate well to the calculation of observables, with scale
dependence uncertainties washing away the precision of the photon PDF. A
second alternative avoids this problem altogether, by not introducing an extra
distribution. Instead, the $p\to\gamma+X$ vertex (with $X$ anything) is
written in terms of the proton structure function. In the work presented in
this session showed the phenomenology of inclusive photon-initiated lepton
production [23] and exclusive processes with rapidity gaps, and their
implementation in Monte Carlo Event Generators.

Extracting the DIS one photon exchange cross-section from measurements
requires a good understanding of the radiative corrections that alter the
kinematics of the initial and final particles with respect to the those
entering/leaving the hard interaction. This, in turn, calls for a good
theoretical calculation of the structure functions $F_{2}$ and $F_{L}$. The
latter, that emerges from the exchange of a longitudinally polarised virtual
photon, dominates the low-$x$ region. As in $F_{L}$ the quark and gluon PDFs
enter at the same order in the perturbative expansion, measuring it would in
principle enable us to study the gluon density, at least for low values of $x$
where it dominates the cross-section. Unfortunately the extraction of $F_{L}$
is inherently non trivial and data for $x<0.01$ are scarce. There are several
theoretical models, with different ingredients and assumptions, that aim to
describe the structure functions in the low-$x$ region, and the EIC will have
the power to discriminate between them. In this line, there was a presentation
of a model that extends the structure functions in the experimentally
reachable low-$x$, low $Q^{2}$ region. The work is an update of the model
proposed in [24], where the extrapolation is based on the photon-gluon fusion
process with the quarks masses taken into account and an explicit higher twist
effect depending on the transverse momentum of the quarks and the integrated
gluon PDF. The use of a more sophisticated model for the higher twist term and
recent sets of proton PDFs gives an overall adequate description of the
$F_{L}$ data from H1, with the LO PDF giving a better agreement. As seen in
the original work, the model severely undershoots the data available at
$x>0.01$.

## Acknowledgements - instead of Outlook and Summary

We would like to thank the DIS conference organizers for the opportunity to
chair the WG1 session and all of the speakers and participants for an
interesting and stimulating atmosphere. We were originally asked to chair the
session at the 2020 iteration of the workshop and we appreciate everyone’s
patience and understanding as we tried to organize a useful virtual session in
2021 due to the Covid-19 pandemic.

#### Funding information

P. Zurita is supported by the Deutsche Forschungs-gemeinschaft (DFG, German
Research Foundation) - Research Unit FOR 2926, grant number 409651613. B.
Nachman is supported by the U.S. Department of En- ergy (DOE), Office of
Science under contract DE-AC0205CH11231.

## References

  * [1] B. Schmidt, J. Phys. Conf. Ser. 706 (2016) no.2, 022002 doi:10.1088/1742-6596/706/2/022002
  * [2] R. Abdul Khalek, A. Accardi, J. Adam, D. Adamiak, W. Akers, M. Albaladejo, A. Al-bataineh, M. G. Alexeev, F. Ameli and P. Antonioli, et al. [arXiv:2103.05419 [physics.ins-det]].
  * [3] S. Moch, J. A. M. Vermaseren and A. Vogt, Nucl. Phys. B 688 (2004), 101-134 doi:10.1016/j.nuclphysb.2004.03.030 [arXiv:hep-ph/0403192 [hep-ph]].
  * [4] A. Vogt, S. Moch and J. A. M. Vermaseren, Nucl. Phys. B 691 (2004), 129-181 doi:10.1016/j.nuclphysb.2004.04.024 [arXiv:hep-ph/0404111 [hep-ph]].
  * [5] J. Ablinger, A. Behring, J. Blümlein, A. De Freitas, A. von Manteuffel and C. Schneider, Nucl. Phys. B 890 (2014) 48 doi:10.1016/j.nuclphysb.2014.10.008 [arXiv:1409.1135 [hep-ph]].
  * [6] J. Ablinger, A. Behring, J. Blümlein, A. De Freitas, A. von Manteuffel and C. Schneider, Nucl. Phys. B 922 (2017) 1 doi:10.1016/j.nuclphysb.2017.06.004 [arXiv:1705.01508 [hep-ph]].
  * [7] T. Liu, W. Melnitchouk, J. W. Qiu and N. Sato, [arXiv:2008.02895 [hep-ph]].
  * [8] T. J. Hou, J. Gao, T. J. Hobbs, K. Xie, S. Dulat, M. Guzzi, J. Huston, P. Nadolsky, J. Pumplin and C. Schmidt, et al. Phys. Rev. D 103 (2021) no.1, 014013 doi:10.1103/PhysRevD.103.014013 [arXiv:1912.10053 [hep-ph]].
  * [9] K. Kovařík, P. M. Nadolsky and D. E. Soper, Rev. Mod. Phys. 92 (2020) no.4, 045003 doi:10.1103/RevModPhys.92.045003 [arXiv:1905.06957 [hep-ph]].
  * [10] A. Accardi, L. T. Brady, W. Melnitchouk, J. F. Owens and N. Sato, Phys. Rev. D 93 (2016) no.11, 114017 doi:10.1103/PhysRevD.93.114017 [arXiv:1602.03154 [hep-ph]].
  * [11] S. Bailey, T. Cridge, L. A. Harland-Lang, A. D. Martin and R. S. Thorne, Eur. Phys. J. C 81 (2021) no.4, 341 doi:10.1140/epjc/s10052-021-09057-0 [arXiv:2012.04684 [hep-ph]].
  * [12] R. D. Ball et al. [NNPDF], Eur. Phys. J. C 77 (2017) no.10, 663 doi:10.1140/epjc/s10052-017-5199-5 [arXiv:1706.00428 [hep-ph]].
  * [13] A. Candido, S. Forte and F. Hekhorn, JHEP 11 (2020), 129 doi:10.1007/JHEP11(2020)129 [arXiv:2006.07377 [hep-ph]].
  * [14] E. Moffat et al. [Jefferson Lab Angular Momentum (JAM)], Phys. Rev. D 104 (2021) no.1, 016015 doi:10.1103/PhysRevD.104.016015 [arXiv:2101.04664 [hep-ph]].
  * [15] R. D. Ball, E. R. Nocera and R. L. Pearson, Eur. Phys. J. C 81 (2021) no.1, 37 doi:10.1140/epjc/s10052-020-08826-7 [arXiv:2011.00009 [hep-ph]].
  * [16] A. Accardi, T. J. Hobbs, X. Jing and P. M. Nadolsky, Eur. Phys. J. C 81 (2021) no.7, 603 doi:10.1140/epjc/s10052-021-09318-y [arXiv:2102.01107 [hep-ph]].
  * [17] T. J. Hobbs, B. T. Wang, P. M. Nadolsky and F. I. Olness, Phys. Rev. D 100 (2019) no.9, 094040 doi:10.1103/PhysRevD.100.094040 [arXiv:1904.00022 [hep-ph]].
  * [18] K. J. Eskola, P. Paakkinen, H. Paukkunen and C. A. Salgado, Eur. Phys. J. C 77 (2017) no.3, 163 doi:10.1140/epjc/s10052-017-4725-9 [arXiv:1612.05741 [hep-ph]].
  * [19] H. Paukkunen and P. Zurita, Eur. Phys. J. C 80 (2020) no.5, 381 doi:10.1140/epjc/s10052-020-7971-1 [arXiv:2003.02195 [hep-ph]].
  * [20] R. Abdul Khalek, J. J. Ethier, J. Rojo and G. van Weelden, JHEP 09 (2020), 183 doi:10.1007/JHEP09(2020)183 [arXiv:2006.14629 [hep-ph]].
  * [21] E. P. Segarra, T. Ježo, A. Accardi, P. Duwentäster, O. Hen, T. J. Hobbs, C. Keppel, M. Klasen, K. Kovařík and A. Kusina, et al. Phys. Rev. D 103 (2021) no.11, 114015 doi:10.1103/PhysRevD.103.114015 [arXiv:2012.11566 [hep-ph]].
  * [22] P. Duwentäster, L. A. Husová, T. Ježo, M. Klasen, K. Kovařík, A. Kusina, K. F. Muzakka, F. I. Olness, I. Schienbein and J. Y. Yu, [arXiv:2105.09873 [hep-ph]].
  * [23] L. A. Harland-Lang, [arXiv:2101.04127 [hep-ph]].
  * [24] B. Badelek, J. Kwiecinski and A. Stasto, Z. Phys. C 74 (1997), 297-306 doi:10.1007/s002880050391 [arXiv:hep-ph/9603230 [hep-ph]].
  * [25] K. F. Muzakka, P. Duwentäster, T. J. Hobbs, T. Ježo, M. Klasen, K. Kovařík, A. Kusina, J. G. Morfín, F. I. Olness and R. Ruiz, et al. [arXiv:2107.13235 [hep-ph]].
  * [26] K. Cichy and M. Constantinou, Adv. High Energy Phys. 2019 (2019), 3036904 doi:10.1155/2019/3036904 [arXiv:1811.07248 [hep-lat]].
  * [27] A. V. Radyushkin, Phys. Rev. D 96 (2017) no.3, 034025 doi:10.1103/PhysRevD.96.034025 [arXiv:1705.01488 [hep-ph]].
  * [28] B. L. Ioffe, Phys. Lett. B 30 (1969), 123-125 doi:10.1016/0370-2693(69)90415-8
  * [29] V. Braun, P. Gornicki and L. Mankiewicz, Phys. Rev. D 51 (1995), 6036-6051 doi:10.1103/PhysRevD.51.6036 [arXiv:hep-ph/9410318 [hep-ph]].
  * [30] I. Balitsky, W. Morris and A. Radyushkin, Phys. Lett. B 808 (2020), 135621 doi:10.1016/j.physletb.2020.135621 [arXiv:1910.13963 [hep-ph]].
  * [31] I. I. Balitsky and V. M. Braun, Nucl. Phys. B 311 (1989), 541-584 doi:10.1016/0550-3213(89)90168-5
  * [32] X. Ji, Phys. Rev. Lett. 110 (2013), 262002 doi:10.1103/PhysRevLett.110.262002 [arXiv:1305.1539 [hep-ph]].
  * [33] Y. K. Huo et al. [Lattice Parton Collaboration (LPC)], Nucl. Phys. B 969 (2021), 115443 doi:10.1016/j.nuclphysb.2021.115443 [arXiv:2103.02965 [hep-lat]].
  * [34] ATLAS Collaboration, (2021), [arXiv:2101.05095 [hep-ex]].
  * [35] ZEUS Collaboration, Phys. Rev. D. 101 (2020) 112009 doi:10.1103/PhysRevD.101.112009 [arXiv:2003.08742 [hep-ex]].
  * [36] LHCb Collaboration, Phys. Rev. Lett. 122 (2019) 132002 doi:10.1103/PhysRevLett.122.132002 [arXiv:1810.07907 [hep-ex]].
  * [37] F. Hautmann et al., JHEP 01 (2018) 070 doi:10.1007/JHEP01(2018)070 [arXiv:1708.03279 [hep-ph]].
  * [38] H. Jung, S. Taheri Monfared and T. Wening, Phys. Lett. B 817 (2021) 136299 doi:10.1016/j.physletb.2021.136299 [arXiv:2102.01494 [hep-ph]].
  * [39] H1prelim-21-031
  * [40] SeaQuest Collaboration, J. Dove, et al., Nature 590 (2021) 7847, 561-565 doi:10.1038/s41586-021-03282-z [arXiv:2103.04024 [hep-ph]].
  * [41] M. Alberg and G. A.Miller, Phys. Rev. C 100 (2019) 3, 035205 doi:10.1103/PhysRevC.100.035205 [arXiv:1712.05814 [nucl-th]].
  * [42] E. Basso et al., Nucl. Phys. A 948 (2016) 63-77 doi:10.1016/j.nuclphysa.2016.02.001 [arXiv:1509.07988 [hep-ph]].
  * [43] STAR Collaboration, J. Adam et al., Phys. Rev. D 103 (2021) 012001 doi:10.1103/PhysRevD.103.012001 [arXiv:2011.04708 [nucl-ex]].
  * [44] CMS Collaboration, A. M. Sirunyan et al., JHEP 12 (2019) 059 doi:10.1007/JHEP12(2019)059 [arXiv:1812.10529 [hep-ex]].
  * [45] CMS Collaboration, A. M. Sirunyan et al., JHEP 12 (2019) 061 doi:10.1007/JHEP12(2019)061 [arXiv:1909.04133 [hep-ex]].
  * [46] CMS Collaboration, A. M. Sirunyan et al., Phys. Rev. D 102 (2020) 092012 doi:10.1103/PhysRevD.102.092012 [arXiv:2008.04174 [hep-ex]].
  * [47] CMS Collaboration, A. M. Sirunyan et al., Phys. Rev. Lett. 122 (2019) 151802 doi:10.1103/PhysRevLett.122.151802 [arXiv:1901.11201 [hep-ex]].
  * [48] CMS Collaboration, A. M. Sirunyan et al., Phys.Lett. B 819 (2021) 136409 doi:10.1016/j.physletb.2021.136409 [arXiv:2011.06028 [hep-ex]].
  * [49] STAR Collaboration, L. Adamczyk et al., Phys. Rev. D 95 (2017) 071103 doi: 10.1103/PhysRevD.95.071103 [arXiv:1610.06616 [hep-ex]]
  * [50] ATLAS Collaboration, ATLAS-CONF-2021-003.
  * [51] H1 Collaboration, H1prelim-21-031
  * [52] A. Andreassen, E. Metodiev, P. Komiske, B. Nachman, J. Thaler, Phys. Rev. Lett. 124 (2020) 182001 doi:10.1103/PhysRevLett.124.182001 [arXiv:1911.09107 [hep-ph]].