# Optimized Receiver Design for Entanglement-Assisted Communication using BPSK

Rahul Bhadani  Department of Electrical and Computer Engineering, The
University of Alabama in Huntsville, USA<EMAIL_ADDRESS><EMAIL_ADDRESS>Ivan B. Djordjevic  Department of Electrical &
Computer Engineering, The University of Arizona, Tucson, USA
College of Optical Sciences, The University of Arizona, Tucson, USA
<EMAIL_ADDRESS>
###### Abstract

The use of pre-shared entanglement in entanglement-assisted communication
offers a superior alternative to classical communication, especially in the
photon-starved regime and highly noisy environments. In this paper, we analyze
the performance of several low-complexity receivers that use optical
parametric amplifiers. The simulations demonstrate that receivers employing an
entanglement-assisted scheme with phase-shift-keying modulation can outperform
classical capacities. We present a 2x2 optical hybrid receiver for
entanglement-assisted communication and show that it has a roughly 10% lower
error probability compared to previously proposed optical parametric
amplifier-based receivers for more than 10 modes. However, the capacity of the
optical parametric amplifier-based receiver exceeds the Holevo capacity and
the capacities of the optical phase conjugate receiver and 2x2 optical hybrid
receiver in the case of a single mode. The numerical findings indicate that
surpassing the Holevo and Homodyne capacities does not require a large number
of signal-idler modes. Furthermore, we find that using unequal priors for BPSK
provides roughly three times the information rate advantage over equal priors.

##  I Introduction

Quantum Information Processing (QIP) has seen tremendous progress in recent
decades, with multiple research directions exploring quantum sensing, covert
communication, quantum cryptography, and more. A quantum channel is used to
transfer quantum information from one party (known as Alice) to another party
(known as Bob). In the case of a perfect channel, the quantum information is
transferred intact, but if the channel is noisy, the quantum information
undergoes some changes. Quantum channels can also be used to transmit
classical information. Additionally, if the channel is noisy within certain
limitations, the quantum channel can be used to share entanglement between
Alice and Bob. The use of pre-shared entanglement can enhance classical
capacity and protect against an adversary, commonly referred to as Eve Holevo
and Werner (2001); Holevo (2002); Bennett  _et al._ (2002); Shi  _et al._
(2020); Zhuang (2021). Recent experiments have shown that even in
entanglement-breaking scenarios, the rate of entanglement-assisted (EA)
communication can be much higher than communication without entanglement Zhang
_et al._ (2015); Hao  _et al._ (2021). The ratio $\frac{C_{\text{EA}}}{C}$,
where $C_{\text{EA}}$ is the entanglement-assisted capacity and $C$ is the
Holevo-Schumacher-Westmoreland (HSW) capacity in the classical regime,
diverges logarithmically with the inverse of the signal power over a lossy and
noisy bosonic channel Holevo (2002).

Recent efforts have been made to design receivers for EA communication, where
authors have utilized the Gaussian approximation of the cumulative
distribution function to calculate the Bit Error Rate (BER) Guha (2009); Shi
_et al._ (2020); Zhuang (2021); Djordjevic (0114). The previously proposed
receiver design is limited to a demonstration using Binary Phase-Shift Keying
(BPSK) with repetition coding over more than $10^{6}$ bosonic modes that
occupy the entire C-band and a portion of the L-band.

In this work, we analyze the receiver design for entanglement-assisted (EA)
communication using Optical Parametric Amplifiers (OPAs) introduced in
Djordjevic (0114) and expand upon previous results to determine the optimality
of the receiver design. We show that EA communication does not need to occupy
the entire C-band. Additionally, we analyze a 2x2 optical hybrid-based
receiver for EA communication that is suitable for implementation in
integrated optics and quantum nanophotonics. In our scheme, optical phase
conjugation is performed on the transmitter side when signal photons are
brighter, rather than on the receiver side where the signal photons are buried
in noise and highly attenuated. A comparison of phase conjugation on the
transmitted side versus the receiver side can be found in Djordjevic (2021a).

We further propose an optimized hypothesis testing scheme and demonstrate
numerically that the optimized receiver design provides a superior
communication capacity compared to capacity without entanglement assistance.
When using the BPSK modulation format to represent digital information, we
find that non-equal priors perform at least three times better in terms of
information rate compared to an equal prior encoding scheme. The development
presented in this work is an extension of Bhadani (2021).

The rest of the paper is organized as follows. In Section II, we provide a
brief review of entanglement-assistance with mathematical formalism necessary
for the rest of the paper. In Section III, we present an overview of the
receiver design schemes for entanglement-assisted communication, including the
optical parametric amplifier-based receiver design with threshold detection,
the optical phase conjugation receiver, and the 2x2 optical hybrid-based joint
receiver proposed in previous work Djordjevic (0114). These receiver designs
are then evaluated in Section IV.

### Notations Used in the Paper

$\ket{\cdot}$ is used for ket-notation in quantum mechanics, equivalent to a
vector notation in linear algebra. The Hermitian conjugate of the vector,
$\bra{\cdot}$, is referred to as bra-notation. The scalar product of two
vectors $\ket{\psi_{1}}$ and $\ket{\psi_{2}}$ is denoted by
$\bra{\psi_{1}}\ket{\psi_{2}}$. Additionally, the ket-notation $\ket{\alpha}$
represents a coherent state of amplitude $\alpha$. The imaginary unit or a
complex number $\sqrt{-1}$ is represented by $j$. Random variables $X$ and $Y$
denote the input and detected states, respectively. The measurement operator
is represented by $\Pi$. Shannon’s entropy is denoted by $H(\cdot)$ and mutual
information is represented by $I(\cdot,\cdot)$. Probabilities are written as
$p$, while conditional probabilities are represented as $p_{Y|X}$ and
conditioned on $Y$ given $X$. The binomial coefficient is represented by
$\binom{M}{N}$. The tensor product is represented by $\otimes$ and the
cumulative distribution function of a statistical distribution is represented
by $\mathcal{F}$.

##  II Entanglement Assisted Classical Communication Concept

Quantum entanglement is a phenomenon where two particles are strongly
correlated, such that the state of one particle immediately provides
information about the state of the other particle, no matter how far apart
they are. These particles, such as photons or electrons, are individual
systems, but they remain connected even when separated by vast distances,
forming a composite system Plenio and Vedral (1998); Shao-Ming  _et al._
(2010); Eisert (2006). As an example, given two basis vectors
$\\{\ket{0}_{A},\ket{1}_{A}\\}$ in Hilbert space ${\mathcal{H}}_{A}$ and
$\\{\ket{0}_{B},\ket{1}_{B}\\}$ in Hilbert space ${\mathcal{H}}_{B}$, then the
following is an entangled state:

$\begin{split}\cfrac{1}{\sqrt{2}}(\ket{0}_{A}\otimes\ket{1}_{B}-\ket{1}_{A}\otimes\ket{0}_{B})\end{split}$
(1)

When a composite system is in the state (1), it is impossible to attribute
either system $A$ or $B$ a definite pure state. Although the von Neumann
entropy of the whole state is zero, the entropy of the subsystem is greater
than zero, indicating the systems are entangled.

Compared to classical communication, entanglement enhances communication by
increasing the number of messages that can be sent perfectly over the
channels, resulting in higher one-shot zero-error capacity and increased
security Miller (2011). However, Miller (2011)doesn’t explain what kind of
measurement device and receiver scheme the experimentalists used. Theoretical
proofs and discussions of entanglement-assisted communication can be found in
Bennett  _et al._ (1999); Giovannetti  _et al._ (2003); Cubitt  _et al._
(2010). A laboratory experiment demonstrating the superiority of entanglement-
assisted communication was recently conducted in Hao  _et al._ (2021).

In entanglement-assisted classical communication, entangled states can be
distributed through either optical fibers or satellites and stored in quantum
memories. The classical data is transmitted by Alice using the signal photon
of the entangled pair, which is affected by noise and loss in the quantum
channel. On the receiver side, Bob uses the idler photon of the entangled pair
to determine what was transmitted by employing an optimal quantum receiver.
The overall design is illustrated in Figure 1. Error correction can be applied
to the quantum states to restore the transmitted information and mitigate the
effects of decoherence.

Figure 1: An illustration showing the concept of EA communication. EA-assisted
communication is enabled by either fiber-optic-based distribution of
entanglement or entanglement distribution through satellites. The information
is transmitted through a lossy and noisy Bosonic channel.

##  III Receiver Design for EA Communication

In entanglement-assisted communication, two-mode Gaussian states are generated
through spontaneous parametric down-conversion (SPDC) of entangled-photon
pairs Lopez-Mago (2012); Christ  _et al._ (2013). The SPDC source is a
broadband source with a number of modes $M=T_{m}W$, where $W$ is the phase-
matching bandwidth and $T_{m}$ is the measurement interval and generates $M$
independent pairs of signal-idler photons in space and time denoted by their
annihilation operators ${{\hat{a}}_{s}^{(m)},{\hat{a}}_{i}^{(m)}}$, with
$m\in[1,M]$. These pairs are prepared in identical entangled two-mode squeezed
vacuum (TMSV) states, which can be represented in a Fock state basis as in
Equation (2)

$\begin{split}\ket{\psi}_{si}=\sum_{n=0}^{\infty}\sqrt{\cfrac{N_{s}^{n}}{(N_{s}+1)^{n+1}}}\ket{n}_{s}\ket{n}_{i}\end{split}$
(2)

where $N_{s}$ is the mean photon number in the signal mode. The mean photon
number for the idler mode is $N_{i}=N_{s}$ Mauerer  _et al._ (2009); Guha
(2009). TMSV belongs to a class of Gaussian states, where an $M$-mode Gaussian
state $\hat{\rho}$ consisting of modes ${{\hat{a}}^{(m)},m\in[1,M]}$ is
characterized by the mean and variance of their respective quadrature field
operators such that ${\hat{a}}^{(m)}={\hat{p}}^{(m)}+j{\hat{q}}^{(m)}$. The
covariance matrix for a TMSV state is given by

$\begin{split}\Lambda_{\text{TMSV}}&=\begin{bmatrix}2N_{s}+1&0&C&0\\\
0&2N_{s}+1&0&-C\\\ C&0&2N_{s}+1&0\\\ 0&-C&0&2N_{s}+1\end{bmatrix}\\\
&=\begin{bmatrix}(2N_{s}+1){\mathbf{I}}&C{\mathbf{Z}}\\\
C{\mathbf{Z}}&(2N_{s}+1){\mathbf{I}}\end{bmatrix}\end{split}$ (3)

where $C=2\sqrt{N_{s}(N_{s}+1)}$, ${\mathbf{I}}$ and ${\mathbf{Z}}$ are
$2\times 2$ Pauli matrices. Other two Pauli matrices are ${\mathbf{X}}$ and
${\mathbf{Y}}$111https://qiskit.org/documentation/stubs/qiskit.quantum_info.Pauli.html
Wilde (2013).

If we consider the Phase-Shift Keying (PSK) modulation scheme for
communication, then mathematically, we can use the unitary operator
${\hat{U}}_{\theta}=e^{j\theta{\hat{a}}^{\dagger}{\hat{a}}}$ to denote the
rotation of the base annihilation operator ${\hat{a}}$. In transmitting
information using entangled photons generated from SPDC, the signal photon of
the signal-idler pair is used while the idler is pre-shared before
transmission occurs. In order to transmit information, Alice modulates the
signal ${\hat{a}}_{s^{\prime}}$ using a phase modulator to apply a rotation of
$\theta$. The signal then passes through a thermal, lossy Bosonic quantum
channel. The received photon mode (after passing through the communication
channel) at Bob’s end is denoted by
${\hat{a}}_{R}={\hat{a}}_{R^{\prime}}e^{j\theta}$ where
${\hat{a}}_{R^{\prime}}$ is the base photon mode at the receiving end. Bob
uses the undisturbed idler part of the pre-shared entangled photon pair and an
optimal quantum detector to perform hypothesis testing and determine which
symbol was transmitted. For simplicity, we will drop the mode notation from
the annihilation operator. Under the phase-encoding scheme, the covariance
matrix of the return-idler pair ${{\hat{a}}_{R},{\hat{a}}_{I}}$ is given by

$\begin{split}\begin{bmatrix}(2N_{R}+1){\mathbf{I}}&C_{\eta}Re[e^{j\theta}({\mathbf{Z}}-j{\mathbf{X}})]\\\
C_{\eta}Re[e^{j\theta}({\mathbf{Z}}-j{\mathbf{X}})]&(2N_{I}+1){\mathbf{I}}\end{bmatrix}\end{split}$
(4)

where $N_{R}=\eta N_{s}+N_{B}$, $C_{\eta}=2\sqrt{\eta N_{s}(N_{s}+1)}$, $\eta$
is the transmittivity of the Bosonic channel, and $N_{B}$ is the mean photon
number of the thermal mode. In the case of a pre-shared entangled state, the
idler is assumed to be undisturbed as it has been shared through fiber optics
or satellite and is stored in quantum memory. In such a case, attenuation
experienced by the idler is negligible. Hence, at the receiver side, the idler
mean photon number $N_{I}=N_{i}=N_{s}$. As the signal mode passes through a
thermal lossy bosonic channel, the signal mode is altered and referred to as
the return mode on the receiver side with mean photon number $N_{R}$.

###  III.1 OPA-based receiver with threshold detection

A joint detection receiver for state discrimination of EA communication
consists of an optical parametric amplifier (OPA). On the receiver side, an
optical parametric amplifier (OPA) is used to combine the return-idler pair,
as shown in Figure 2. The return and idler modes are evolved as given by
Heisenberg’s picture Ou (2017):

$\begin{split}{\hat{u}}&=\sqrt{G}{\hat{a}}_{R}+\sqrt{G-1}{\hat{a}}_{I}^{\dagger}\\\
{\hat{v}}&=\sqrt{G}{\hat{a}}_{I}+\sqrt{G-1}{\hat{a}}_{R}^{\dagger}\end{split}$
(5)

where $G$ is the gain of the OPA, such that $G=1+\epsilon$ and $\epsilon<<1$.

Figure 2: Operating Principle of Optical Parametric Amplifier (OPA): At the
receiver end, parametric amplification is applied to the return-idler pair
with gain $G$. Error probability of discrimination is higher at ${\hat{u}}$,
hence the photon detection is made ${\hat{v}}$.

OPA receiver can be used to combine and amplify the return-idler pair using a
strong local pump. This gives rise to Equation (5). At the output ports, a
photodetector is used for photon counting, and a threshold detection rule is
applied to make state discrimination. We further assume an ideal OPA, where
the gain $G$ is fixed.

The photodetector outputs are designated as ${\hat{u}}$ and ${\hat{v}}$ at two
ports, referred to as the return and idler outputs, respectively. For each
output, the mean photon number is given by the expectation
$\expectationvalue{{\hat{u}}^{\dagger}{\hat{u}}}$ or
$\expectationvalue{{\hat{v}}^{\dagger}{\hat{v}}}$, depending on whether
threshold detection is made at the signal output port or idler output port.
The photocurrent operators and their expectations are given by Equation (6)
and Equation (7).

$\begin{split}{\overline{N}}_{1}(\theta)&=\expectationvalue{{\hat{u}}^{\dagger}{\hat{u}}}=G(\eta
N_{s}+N_{B})\\\ &+(G-1)(1+N_{s})+2\cos\theta\sqrt{G(G-1)}\sqrt{\eta
N_{s}(N_{s}+1)}\end{split}$ (6)
$\begin{split}{\overline{N}}_{2}(\theta)&=\expectationvalue{{\hat{v}}^{\dagger}{\hat{v}}}=GN_{s}+(G-1)(1+\eta
N_{s}+N_{B})\\\ &+2\cos\theta\sqrt{G(G-1)}\sqrt{\eta
N_{s}(N_{s}+1)}\end{split}$ (7)

The derivation is provided in Appendix VIII.

For practical communication, consider that information is encoded using
repetition codewords that employ binary phase-shift keying (BPSK) modulation
with phases $\theta\in{0,\pi}$. Decoding BPSK can be modeled as hypothesis
testing: if hypothesis $H_{0}$ is true, then the BPSK symbol with $\theta=0$
was transmitted, and if hypothesis $H_{1}$ is true, then the symbol with
$\theta=\pi$ was transmitted. In this paper, we do not discuss optimal
encoding, which is beyond the scope of this paper. However, BPSK is a suitable
choice for weak signals, as it is power-efficient Lefevre (1989).

To allow for efficient error correction, repeated PSK codewords consisting of
$M$ signal-idler pairs are used in EA communication Shi  _et al._ (2020). In a
joint-detection scheme, the receiver mixes all $M$ received modes and counts
the total number of photons at the output ports. The joint detection state in
this case becomes an $M$-fold tensor product $\rho^{\otimes M}$, with
identical zero-mean thermal states, and the per-mode mean photon number is
given by ${\overline{N}}_{1}(\theta)$ or ${\overline{N}}_{2}(\theta)$,
depending on which output port of the OPA we use. An optimum joint measurement
for state discrimination requires photon counting at an output port and thus
deciding between two hypotheses using the total photon number $N$ over $M$
modes Guha (2009); Tan  _et al._ (2008). Under such a scenario, the
probability mass function (pmf) is negative binomial with mean
$M{\overline{N}}(\theta)$ and standard deviation
$\sigma(\theta)=\sqrt{M{\overline{N}}(\theta)({\overline{N}}(\theta)+1)}$,
given by Guha (2009); Tan  _et al._ (2008):

$\begin{split}P_{\text{OPA}}(n|\theta;M,i)=\binom{n+M-1}{n}\bigg{(}\tfrac{{\overline{N}}_{i}(\theta)}{1+{\overline{N}}_{i}(\theta)}\bigg{)}^{n}\bigg{(}\tfrac{1}{1+{\overline{N}}_{i}(\theta)}\bigg{)}^{M}\end{split}$
(8)

where $i\in{1,2}$, and $\binom{n+M-1}{n}$ is the binomial coefficient.

Equation (8) can be approximated as a Gaussian distribution with mean
$M{\overline{N}}_{i}(\theta)$ and standard deviation
$\sigma(\theta)=\sqrt{M{\overline{N}}_{i}(\theta)({\overline{N}}_{i}(\theta)+1)}$
for sufficiently large $M$ (see Appendix VII). At the detector end, we use
threshold detection and decide in favor of $H_{0}$ if the total number of
photons detected is $N>N_{\text{th}}(\theta)$, otherwise we choose $H_{1}$ for
$N\leq N_{\text{th}}(\theta)$, where $N_{\text{th}}(\theta)$ is the threshold
number of photons, which is a function of the phase $\theta$. A suitable value
for the threshold number of photons is chosen according to the scheme
described later in Section IV.

###  III.2 Optical Phase Conjugation Receiver with Threshold Detection

OPA can also be used differently, where the return ${\hat{a}}_{R}$ mode
interacts with the vacuum mode ${\hat{a}}_{v}$ to produce
$\sqrt{G}{\hat{a}}_{v}+\sqrt{G-1}{\hat{a}}_{R}^{\dagger}$, which becomes
${\hat{a}}_{c}=\sqrt{2}{\hat{a}}_{v}+{\hat{a}}_{R}^{\dagger}$ for $G=2$. By
mixing the idler with ${\hat{a}}_{c}$ using a 50-50 beamsplitter, we get two
modes $\cfrac{1}{\sqrt{2}}({\hat{a}}_{c}\pm{\hat{a}}_{I})$. The outputs from
the two arms are fed to a balanced detector, and their difference is measured
as a photocurrent. We call this the Optical Phase Conjugate Receiver (OPC
receiver). Consider the schematic of the OPC receiver shown in Figure 3.

Figure 3: Operating Principle of Optical Phase Conjugate (OPC) receiver:
signal interacts with the vacuum followed by mixing with idler using 50-50
beamsplitter and a balanced detection is applied using photodetectors.

For the case of BPSK, the mean photon operators of two output arms of
beamsplitters are given by

$\begin{split}{\hat{a}}_{A/B}^{\dagger}{\hat{a}}_{A/B}&=\cfrac{1}{2}\bigg{[}(G-1){\hat{a}}_{R}{\hat{a}}_{R}^{\dagger}\pm\sqrt{G-1}{\hat{a}}_{R}{\hat{a}}_{I}\\\
&\pm\sqrt{G-1}{\hat{a}}_{I}^{\dagger}{\hat{a}}_{R}^{\dagger}+{\hat{a}}_{I}^{\dagger}{\hat{a}}_{I}\bigg{]}\\\
&\text{with $+$ sign for arm A and $-$ sign for arm B.}\end{split}$ (9)

In Equation (9), ${\hat{a}}_{v}$ term doesn’t appear as it denotes the vacuum
mode.

We adopt a joint-detection scheme similar to the one adopted for the OPA
receiver discussed in Section III.1, containing $M$ modes for error
correction. The difference in the mean photon number detected at the two
photodetectors of the OPC is converted to a photocurrent with a photocurrent
operator ${\hat{k}}$ given by Equation (10), setting $G=2$.

$\begin{split}{\hat{k}}&={\hat{a}}_{A}^{\dagger}{\hat{a}}_{A}-{\hat{a}}_{B}^{\dagger}{\hat{a}}_{B}=\sqrt{G-1}{\hat{a}}_{R}{\hat{a}}_{I}+\sqrt{G-1}{\hat{a}}_{I}^{\dagger}{\hat{a}}_{R}^{\dagger}\\\
N_{\text{OPC}}(\theta)&=\expectationvalue{{\hat{k}}}=2\cos\theta\sqrt{\eta
Ns(Ns+1)}\\\ &\text{as,~{}}{\hat{a}}_{R}={\hat{a}}_{R^{\prime}}e^{j\theta},\\\
&~{}\expectationvalue{{\hat{a}}_{R^{\prime}}{\hat{a}}_{I}}=\sqrt{\eta
N_{s}(N_{s}+1)},~{}{\hat{a}}_{R}{\hat{a}}_{R}^{\dagger}={\hat{a}}_{R}^{\dagger}{\hat{a}}_{R}+I\end{split}$
(10)

The variance $\sigma^{2}_{\text{OPC}}$ is given by Equation (11), setting
$G=2$.

$\begin{split}\sigma^{2}_{\text{OPC}}(\theta)&=\expectationvalue{{\hat{k}}^{2}}-\expectationvalue{{\hat{k}}}^{2}\\\
&=N_{s}(\eta N_{s}+N_{B}+1)+(N_{s}+1)(\eta N_{s}+N_{B}+1)\\\ &-2(\eta
N_{s}(N_{s}+1))\cos 2\theta-4(\eta N_{s}(N_{s}+1))\cos^{2}\theta\end{split}$
(11)

At the detector end, the decision scheme uses threshold detection, similar to
the OPA-based receiver design discussed in Section III.1.

###  III.3 2x2 Optical Hybrid-based Joint Receiver with Threshold Detection

Figure 4: Receiver configuration of a 2 × 2 optical hybrid-based joint
balanced detection receiver.

In this section, we describe a practical receiver design using a 2x2 optical
hybrid for EA communication. An optical hybrid-based joint detection scheme is
suitable for EA communication as it can be directly implemented in integrated
optics and quantum nanophotonics. For a two-dimensional constellation, a 2x2
optical hybrid receiver can be used, as shown in Figure 4. A detailed
discussion of the optical hybrid receiver design can be found in Djordjevic
(0114), where Gaussian modulation has also been discussed. The scattering
matrix ${\mathcal{S}}$ of the 2x2 optical hybrid is described by Equation (12)

$\begin{split}{\mathcal{S}}=\begin{bmatrix}e^{j\phi_{1}}\sqrt{1-\kappa}&&\sqrt{1-\kappa}\\\
\sqrt{1-\kappa}&&e^{j\phi_{2}}\sqrt{\kappa}\end{bmatrix}\end{split}$ (12)

where $\kappa$ is the power-splitting ratio of Y-junction in a 2x2 optical
hybrid; and $\phi_{1},$ and $\phi_{2}$ are phase shift parameters Guan  _et
al._ (2017). Return and idler at the receiver are transformed based on the
scattering matrix given in Equation (13).

$\begin{split}\begin{bmatrix}\hat{A}_{R}\\\
\hat{A}_{I}\end{bmatrix}={\mathcal{S}}\begin{bmatrix}\hat{a}_{R}\\\
\hat{a}_{I}\end{bmatrix}.\end{split}$ (13)

We consider equal power splitting set by $\kappa=0.5$ and write the scattering
matrix as

$\begin{split}\begin{bmatrix}\hat{A}_{R}\\\
\hat{A}_{I}\end{bmatrix}=\cfrac{1}{\sqrt{2}}\begin{bmatrix}e^{j\phi_{1}}&&1\\\
1&&e^{j\phi_{2}}\end{bmatrix}\begin{bmatrix}\hat{a}_{R}\\\
\hat{a}_{I}\end{bmatrix}\end{split}$ (14)

For BPSK, ${\hat{a}}_{R}={\hat{a}}_{R^{\prime}}e^{j\theta}$ with
$\theta\in\\{0,\pi\\}$. The photocurrent operator is given by

$\begin{split}{\hat{i}}_{\text{OH}}&=\cfrac{1}{2}e^{-j\theta}(e^{-j\phi_{1}}-e^{j\phi_{2}}){\hat{a}}_{R^{\prime}}^{\dagger}{\hat{a}}_{I}+\cfrac{1}{2}e^{j\theta}(e^{j\phi_{1}}-e^{-j\phi_{2}}){\hat{a}}_{I}^{\dagger}{\hat{a}}_{R^{\prime}}\end{split}$
(15)

The expectation of photocurrent is given by

$\begin{split}N_{\text{OH}}&=\expectationvalue{{\hat{i}}_{\text{OH}}}=\cfrac{1}{2}e^{-j\theta}\sqrt{\eta
N_{s}(N_{s}+1)}(e^{-j\phi_{1}}-e^{j\phi_{2}})\\\
&+\cfrac{1}{2}e^{j\theta}\sqrt{\eta
N_{s}(N_{s}+1)}(e^{j\phi_{1}}-e^{-j\phi_{2}})\end{split}$ (16)

In this paper, we consider a special case of 2x2 optical hybrid receiver where
$\phi_{1}=0$ and $\phi_{2}=\pi$, for which, $N_{\text{OH}}=2\sqrt{\eta
N_{s}(N_{s}+1)}\cos\theta$. The variance of the photocurrent operator is given
by

$\begin{split}\sigma^{2}_{\text{OH}}&=\expectationvalue{{\hat{i}}_{\text{OH}}^{2}}-\expectationvalue{{\hat{i}}_{\text{OH}}}^{2}\\\
&=\cfrac{1}{4}|e^{j\phi_{1}}-e^{-j\phi_{2}}|^{2}(2N_{R}N_{I}+N_{R}+N_{I})\\\
&+\cfrac{\eta
N_{s}(N_{s}+1)}{4}\bigg{[}\bigg{(}\expectationvalue{e^{-2j\theta}}-e^{-2j\theta}\bigg{)}(e^{-j\phi_{1}}-e^{j\phi_{2}})^{2}\bigg{]}\\\
&+\cfrac{\eta
N_{s}(N_{s}+1)}{4}\bigg{[}\bigg{(}\expectationvalue{e^{2j\theta}}-e^{2j\theta}\bigg{)}(e^{j\phi_{1}}-e^{-j\phi_{2}})^{2}\bigg{]}\\\
&-\cfrac{\eta
N_{s}(N_{s}+1)}{2}e^{-j\theta}e^{j\theta}|e^{j\phi_{1}}-e^{-j\phi_{2}}|^{2}\end{split}$
(17)

For equal prior BPSK symbols, $\expectationvalue{e^{\pm 2j\theta}}=(e^{\pm
2j\cdot 0}+e^{\pm 2j\cdot\pi})/2=1$. For non-equal prior symbols with priors
$p_{0}$ and $p_{1}$, $\expectationvalue{e^{\pm 2j\theta}}$ is calculated as
$p_{0}e^{\pm 2j\cdot 0}+p_{1}e^{\pm 2j\cdot\pi}$ which is still 1. Further,
regardless of phase value $\theta\in\\{0,\pi\\}$ for BPSK symbols, $e^{\pm
2j\theta}=\cos 2\theta$. Putting these values in Equation (17), and
considering special case of $\phi_{1}=0$ and $\phi_{2}=\pi$, the variance for
BPSK is

$\begin{split}\sigma^{2}_{\text{OH}}(\theta)&=(2N_{R}N_{I}+N_{R}+N_{I})\\\
&+2\eta N_{s}(N_{s}+1)(1-\cos 2\theta)-2\eta N_{s}(N_{s}+1)\end{split}$ (18)

where $N_{R}=\eta N_{s}+N_{B}$ and $N_{I}=N_{s}$. Similar to OPA and OPC
receiver design, the decision scheme uses threshold detection for state
discrimination. Since the target of this paper is a highly noisy and lossy
environment, we choose $N_{B}=1$, $N_{s}=0.01$, $\eta=0.01$, and $G=1.1$ as a
representative of such a condition.

##  IV Evaluation of Entanglement-Assisted Communication Receivers

###  IV.1 Error Probability Calculation

The probability of error of state discrimination for the case of BPSK using
OPA is given by

$\begin{split}P_{E}&=p_{0}P_{\text{OPA}}\bigg{(}n<N_{\text{th}}|\theta=0;M,i\bigg{)}\\\
&+p_{1}\bigg{[}1-P_{\text{OPA}}\bigg{(}n<N_{\text{th}}|\theta=\pi;M,i\bigg{)}\bigg{]}.\end{split}$
(19)

An optimum value of $N_{\text{th}}$ can be found by equating individual error
term in Equation (19) which, for case of symbols with equal priors gives us
$N_{\text{th}}(\theta)=\cfrac{M(\sigma(\pi){\overline{N}}(0)+\sigma(0){\overline{N}}(\pi))}{(\sigma(\pi)+\sigma(0))}$.
Derivation of the optimum threshold for OPA is provided in Appendix VII that
uses Gaussian approximation.

However, for unequal priors, the optimum threshold $N_{\text{th}}$ is the one
that satisfies the condition

$\begin{split}p_{0}P_{\text{OPA}}&\bigg{(}n<N_{\text{th}}|\theta=0;M,i\bigg{)}\\\
&=p_{1}\bigg{[}1-P_{\text{OPA}}\bigg{(}n<N_{\text{th}}|\theta=\pi;M,i\bigg{)}\bigg{]}.\end{split}$
(20)

We solve Equation (20) for $N_{\text{th}}$ using grid search procedure and
plug into Equation (19) to calculate the error probability. In such a case,
there is no closed-form solution.

The joint detection can be made either at the idler output port or the signal
output port. The error probability of discrimination is higher at the return
port compared to detection made at the idler port, as shown in Figure 6. As a
result, our further analysis focuses solely on making joint detection at the
idler port and we drop the index $i$ from the probability notation moving
forward. We find that for the case of non-equal priors, the mean threshold
photon number $N_{\text{th}}$ for BPSK discrimination is higher for any
detection made at the return output port than at the idler output port (see
Figure 7). Note that even though the error probability $P_{E}$ in Equation
(19) is a convex function of $N_{\text{th}}$, it is a monotonic function of
the prior $p_{0}$, as shown in Figure 8, Figure 9, Figure 10, and Figure 11.
Hence, there does not exist an optimum prior that minimizes the probability of
error for state discrimination.

For the OPC receiver, we calculate the error probability by taking a Gaussian
approximation of photodetection statistics similar to Equation (19). This is
because we measure the difference of photocurrent obtained at the two arms of
the beamsplitter at the detection side (as shown in Figure 3). The Gaussian
approximation yields the probability of error formula given in Equation (21).

$\begin{split}P_{E}&=p_{0}{\mathcal{F}}_{\text{OPC}}\bigg{(}N_{\text{th}},M\cdot
N_{\text{OPC}}(0),\sqrt{M}\cdot\sigma_{\text{OPC}}(0)\bigg{)}\\\
&+p_{1}\bigg{[}1-{\mathcal{F}}_{\text{OPC}}\bigg{(}N_{\text{th}},M\cdot
N_{\text{OPC}}(\pi),\sqrt{M}\cdot\sigma_{\text{OPC}}(\pi)\bigg{)}\bigg{]}\end{split}$
(21)

In Equation (21), $N_{\text{OPC}}(\theta)$ and $\sigma_{\text{OPC}}$ are given
by Equations (10) and (11) respectively. ${\mathcal{F}}_{\text{OPC}}$ is
cumulative distribution function of a Gaussian distribution with mean $M\cdot
N_{\text{OPC}}(\theta)$ and standard deviation
$\sqrt{M}\cdot\sigma_{\text{OPC}}$.

Equation (21) is similar to Equation (19) but written explicitly using the
cumulative distribution function (CDF) notation. Like the OPA receiver, we can
calculate the optimum $N_{\text{th}}$ by equating the two terms of Equation
(21). From Figure 5, we see that the OPC receiver’s performance in terms of
error probability in discriminating BPSK symbols is better than that of the
OPA receiver. However, for a low number of modes $M$, OPA receivers with non-
equal priors still perform better than OPC receivers with equal priors and
perform similarly to OPC receivers with non-equal priors. Our evaluation
suggests that lower-complexity receivers like OPA receivers with fewer optical
components can provide superior information retrieval with a suitable choice
of prior.

The error probability of a 2x2 optical hybrid can be calculated using a
formula similar to the one in Equation (21) with means and variances from
Equations (16) and (18), respectively. From the error probability plot in
Figure 5, we see that the 2x2 optical hybrid offers a roughly $10\%$
improvement in BPSK state discrimination compared to the OPC receiver.

Figure 5: Symbol-by-symbol (separable) minimum error-probability measurement
on each return-idler mode pair at the idler output port. We find that unequal
priors have a lower error probability as compared to BPSK symbols with equal
prior. Figure 6: Symbol-by-symbol (separable) minimum error-probability
measurement on each return-idler mode pair at the return output port of the
OPA receiver. As compared to measurement made at the idler output port of the
OPA receiver, the error probability is higher at the return output port of the
OPA receiver. Figure 7: Optimal threshold for hypothesis testing at the output
port of OPA as a function of the number of modes. A higher threshold is
required when detection is made at the return output port (red line) compared
to the detection made at the idler output port of the OPA receiver (blue
line). Unequal prior were $p_{0}=0.45,p_{1}=0.55$. Plot was generated using
$N_{s}=0.01,N_{B}=1,\eta=0.01$. Figure 8: Surface plot of $P_{E}$ as a
function of prior $p_{0}$ and threshold mean photon number $N_{\text{th}}$
from Equation (19) for photodetection at idler output port for OPA receiver.
The plot was generated using $N_{s}=0.01,N_{B}=1,\eta=0.01$. These plots
reveal that for a fixed threshold, error probability is maximum at equal prior
while non-equal probable symbol seems to reduce error probability. Figure 9:
2D view of the surface plot from a alternative direction. Colormap denotes
error probability – darker color means lower error probability. Figure 10: 2D
view of the surface plot from a alternative direction. Colormap denotes error
probability – darker color means lower error probability. Figure 11: 2D view
of the surface plot from a alternative direction. Colormap denotes error
probability – darker color means lower error probability.

###  IV.2 Mutual Information Calculation

The Holevo capacityHolevo and Werner (2001); Holevo (2002) quantifies the
maximum amount of information, in bits per channel use, that can be sent over
a quantum channel when the use of entangled states at the input and arbitrary
measurements at the output are permitted. In the situation under consideration
in this work, the Holevo capacity evaluates to Equation (22)

$\begin{split}C=g(\eta N_{s}+N_{B})-g(N_{B})\end{split}$ (22)

where

$\begin{split}g(n)=(n+1)\log_{2}(n+1)-n\log_{2}(n)\end{split}$ (23)

is the entropy of the thermal state with mean photon number $n$. To write the
mutual information and, in turn, the capacity for entanglement-assisted
classical communication that requires symbol-by-symbol joint detection, we are
required to calculate the conditional probability distribution. Assuming that
the random variable $X$ denotes the transmitted symbols and $Y$ denotes the
detected symbols, we calculate the mutual information as follows: we first
calculate the conditional probabilities to complete the transition matrix.
Using the conditional probabilities, we can calculate the posteriors, which
are then used to calculate the conditional entropies, followed by the
calculation of the mutual information. The steps to calculate the mutual
information are provided in Equation (32) in Appendix IX.

The Shannon’s capacity for transmitting classical information with our EA
receivers can be calculated by taking the maximum of mutual information over
prior $p$ and threshold mean photon number $N_{\text{th}}$, i.e.

$\begin{split}C_{\text{EA}}=\max_{p,N_{\text{th}}}I(X;Y)\end{split}$ (24)

We find that symbols with equal priors maximize the mutual information, as
expected. We conducted a simulation study with a varying number of modes $M$
to optimize the mutual information as a function of the signal mean photon
number transmitted over a noisy Bosonic channel with $N_{B}=1$ and
transmittivity $\eta=0.01$. In Figure 12 and Figure 14, we present a
comparison of the capacities of various receiver designs proposed for the BPSK
constellation using Equation 24. At the same time, we also plot the capacity
of the Homodyne receiver, where the average number of photons received is
$4\eta N_{s}$ and the average number of noisy photons is $2N_{B}+1$. The
capacity of a Homodyne receiver is given by $C_{H}=0.5\log_{2}[1+4\eta
N_{s}/(2N_{B}+1)]$ Shapiro  _et al._ (2005); Takeoka and Guha (2014). As a
reference, we also plot the Holevo capacity, given by Equation (22). Note that
the Holevo capacity requires coherent states with Gaussian modulation. For EA
communication with the BPSK constellation, we find that joint receivers based
on OPA and OH proposed in this paper outperform the Holevo capacity, even for
a single mode, as shown in Figure 12 and Figure 13. We also conducted
simulation studies for a large number of modes. From our analysis and results,
shown in Figure 14, we conclude that for the proposed EA receiver design
employing a joint-detection scheme, a large number of signal-idler modes is
not required. For $M=1$, the OPA receiver’s performance is better than the OPC
receiver and 2x2 optical hybrid receiver. C-band operates at $35nm$, hence
$d\lambda=35nm$. The central wavelength, $\lambda=1550nm$. The typical
observation interval of symbols is $1\mu s$. Phase matching bandwidth of the
C-band is calculated as

$\begin{split}B=\cfrac{c}{\lambda^{2}}d\lambda=\cfrac{3\times
10^{8}}{(1550\times 10^{-9})^{2}}\cdot 35\times 10^{-9}=4.3704\times
10^{12}\end{split}$ (25)

Then the number of bosonic mode, $M$ for C-band is $4.3704\times 10^{12}\cdot
1\mu s=4.3704\times 10^{6}$. Hence if we were to use the number of modes in
the order of $10^{6}$, we would end up using C-band as was demonstrated in Shi
_et al._ (2020); Hao  _et al._ (2021). However, as we have shown above,
achieving a superior performance requires as little as $M=1$ if we choose
optimal values of prior and threshold mean photon.

We also compared our capacities with ultimate bound, i.e., entanglement-
assisted classical capacity $C_{\text{ultimate}}$ as described in Bennett  _et
al._ (2002); Djordjevic (2021b). To calculate the $C_{\text{ultimate}}$, we
adopted Equation (26) from Bennett  _et al._ (2002); Djordjevic (2021b) with
suitable modifications as per the use case described in Section III.
Entanglement-assisted classical capacity is given by

$\begin{split}C_{\text{ultimate}}=g(N_{s})+g(N_{R})-\bigg{(}g(\tfrac{\nu_{+}-1}{2})+g(\tfrac{\nu_{-}-1}{2})\bigg{)}\end{split}$
(26)

with $a=2N_{s}+1$, $b=2N_{R}+1$, $C_{\eta}=2\sqrt{\eta N_{s}(N_{s}+1)}$,
$\nu_{\pm}=\bigg{[}\sqrt{(a+b)^{2}-4C_{\eta}^{2}}\pm(b-a)\bigg{]}/2$, and
$g()$ has been defined in Equation (23). From Figure 12, it is evident that
further development in the receiver design is required to achieve performance
closer to the ultimate bound of the capacity given by Equation (26).

For a large number of modes, the 2x2 optical hybrid receiver performs better
in terms of capacity as shown in Figure 14. Previous work Shapiro  _et al._
(2005); Takeoka and Guha (2014) in this direction have not considered the use
of OH receivers. An OH receiver uses a balanced detector, similar to OPA to
distinguish the modulation which is more practical and efficient. Further, OH
is known to suppress noise as discussed in Shieh and Djordjevic (2009). It
could be argued that the capacity should be divided by the number of modes for
a scheme using multiple modes. However, in this paper, we are talking about
the overall receiver design’s capacity, rather than bits per mode. In
addition, we find that a number of modes greater than 1 may not be needed to
outperform the Holevo capacity, as seen from Figure 12. Thus, for a well-
designed receiver, repetition coding may not always be useful. This claim is
further corroborated by Figure 15.

Figure 12: Channel Capacity for BPSK state discrimination using different
receiver schemes for single mode. We see that even for a single mode,
entanglement assistance offers an advantage in terms of increasing the
capacity of the channel and beats the classical capacities such as Holevo
capacity and Homodyne Capacity. The plot was generated using
$N_{B}=1,\eta=0.01$. The red line curve denotes the theoretical ultimate
capacity that can be achieved through the entanglement-assistance. Figure 13:
Zoomed-in view to clearly illustrate that Holevo and Homodyne capacity are not
exactly the same. The plot was generated using $N_{B}=1,\eta=0.01$. Figure 14:
Channel Capacity for BPSK state discrimination using different receiver
schemes. We see that entanglement assistance offers an advantage in terms of
increasing the capacity of the channel. We chose the transmittivity of the
Bosonic channel as $\eta=0.01$ and the mean background photon as $N_{B}=1.0$.
In our numerical study, classical capacity stays below 0.07 bits per channel
use for mean signal photon $N_{s}<1.0$.

Additionally, we also plot the per-mode communication rate $R$, normalized by
the Holevo capacity for classical communication $C$, in Figure 15. The
communication rate $R$ is given by Equation (27).

$\begin{split}R=\cfrac{1+P_{e}\log_{2}(P_{e})+(1-P_{e})\log_{2}(1-P_{e})}{M}.\end{split}$
(27)

Equation (27) is based on symmetric hypothesis testing. We find that in terms
of the normalized communication rate, the OPA and OPC receivers perform almost
three times better in the photon-starved regime when BPSK symbols with non-
equal priors are used, compared to when BPSK symbols are equally likely. At
the same time, the 2x2 optical hybrid receiver for non-equal priors performs
roughly 2.5 times better, compared to BPSK with equal priors in the photon-
starved regime. Furthermore, the 2x2 optical hybrid receiver can outperform an
OPA-based receiver by as much as 30% in terms of information rate. Finally,
it’s worth noting that a large number of modes does not necessarily equate to
superior performance.

Figure 15: Information rate as a function of the number of modes $M$ for OPA
and OPC receiver. It is evident that as we increase the number of modes the
$R/C$ for equal and unequal priors attain the same values. Further, we see
better performance in terms of information rate when the number of modes is
low. The plot was generated using $N_{s}=0.01,N_{B}=1,\eta=0.01$.

###  IV.3 Discussion

It is expected that the order of error probability of two receiver designs
should be the reverse of the order of capacity when compared. We find that
this is not the case for OPA, OPC, and OH as evident from Figure 5 as well as
Figure 12 and Figure 14. The ordering in the error-probability plot and
capacity plot is only related when mutual information is optimized with
respect to the prior only. However, we optimize mutual information with
respect to the prior as well as threshold mean photon number as shown in
Equation 24. Hence, the usual ordering relationship is no longer applicable.
Further, as the number of modes increases, the probability distribution seen
in Equation 8 resembles more and more Gaussian. Thus the ordering of capacity
is altered as we move from the number of modes $M=1$ to higher modes. Thus,
with the higher number of modes, the OH receiver design has the best
performance, followed by OPC and then the OPA receiver. However, with $M=1$,
the best performance is obtained by using the OPA receiver, followed by the OH
receiver and then the OPC receiver.

##  V Concluding Remarks and Future Works

Entanglement is a unique phenomenon in quantum information science that can be
leveraged to design new types of sensors, allowing computing devices to solve
problems that are intractable for conventional computers. In communication
systems, the use of entanglement assistance offers a unique advantage in terms
of providing a better communication rate in low-photon number regimes. Pre-
shared entanglement can be used to surpass the performance of classical
capacities and the Holevo capacity in highly noisy and low-brightness
conditions. However, there are several challenges in terms of the practical
realization of entanglement, such as: (i) transmitting entanglement over long
distances is challenging, and (ii) the optimum quantum receiver to achieve
entanglement-assisted channel capacity has not yet been derived. Nevertheless,
simulation results indicate that even when entanglement is not perfect,
entanglement-assisted (EA) communication based on signal-idler pairs
outperforms the Holevo capacity and the capacities of classical channels.

In this paper, we analyze several low-complexity receiver designs employing
optical hybrids and balanced detectors. We demonstrate that for BPSK
modulation, a 2x2 optical hybrid-based joint detection can outperform the OPA
and optical phase-conjugation receivers. Numerical results demonstrate that we
do not need a large number of signal-idler modes to outperform the Holevo and
Homodyne capacities.

##  VI Disclosure

The authors declare no conflicts of interest.

## Appendix

##  VII Gaussian Approximation to Negative Binomial Photon Statistics

Although the photodetection statistics given by OPA receivers in Equations (8)
are of negative binomial nature, they can be computationally expensive to
calculate for large values of $M$. By recognizing that Equation (19) contains
cumulative distributions and approximating them as Gaussian distributions, we
can rewrite the equation as the error function (erf), which is commonly used
to write the cumulative distribution function of a Gaussian distribution:

$\begin{split}\cfrac{1}{2}\bigg{(}1+\textrm{erf}\bigg{(}\cfrac{N_{\text{th}}-M\cdot{\overline{N}}(0)}{\sqrt{2}\sqrt{M}\sigma(0)}\bigg{)}\bigg{)}&=1-\cfrac{1}{2}\bigg{(}1+\textrm{erf}\bigg{(}\cfrac{N_{\text{th}}-M\cdot{\overline{N}}(\pi)}{\sqrt{2}\sqrt{M}\sigma(\pi)}\bigg{)}\bigg{)}\\\
\Rightarrow\cfrac{1}{2}+\cfrac{1}{2}\textrm{erf}\bigg{(}\cfrac{N_{\text{th}}-M\cdot{\overline{N}}(0)}{\sqrt{2}\sqrt{M}\sigma(0)}\bigg{)}&=\cfrac{1}{2}-\cfrac{1}{2}\textrm{erf}\bigg{(}\cfrac{N_{\text{th}}-M\cdot{\overline{N}}(\pi)}{\sqrt{2}\sqrt{M}\sigma(\pi)}\bigg{)}\\\
\Rightarrow\textrm{erf}\bigg{(}\cfrac{N_{\text{th}}-M\cdot{\overline{N}}(0)}{\sqrt{2}\sqrt{M}\sigma(0)}\bigg{)}&=-\textrm{erf}\bigg{(}\cfrac{N_{\text{th}}-M\cdot{\overline{N}}(\pi)}{\sqrt{2}\sqrt{M}\sigma(\pi)}\bigg{)}\\\
\textrm{Considering that erf}(-x)=-\textrm{erf}(x)\\\ \textrm{and equating the
arguments of erf}\\\
N_{\text{th}}(\theta)=\cfrac{M(\sigma(\pi){\overline{N}}(0)+\sigma(0){\overline{N}}(\pi))}{(\sigma(\pi)+\sigma(0))}.\end{split}$
(28)

However, we should be aware of how we may misinterpret the true performance of
receivers due to approximation.

In Figure 16, we plot the difference between $C_{\text{Gaussian}}$ and
$C_{\text{NB}}$. $C_{\text{Gaussian}}$ represents the capacity of the OPA
receiver as discussed in Section III.1, where the photodetection statistics
are approximated as Gaussian. $C_{\text{NB}}$ represents the capacity using
the exact negative binomial distribution from Equation (8). Our calculations
have led us to the following observations: (i) the error of the approximation
increases as the signal mean photon number, $N_{s}$, increases; (ii) with the
Gaussian approximation, the capacity of the channel is overestimated compared
to its true value; (iii) as the number of modes increases, the error of the
approximation decreases. These observations are depicted in Figure 16.
Although the Gaussian approximation overestimates the capacity, the error is
of the order of $10^{-3}$, which is small compared to the value of the
capacity and enables faster numerical calculations.

Figure 16: Top: Capacity error in the case of OPA receiver as a result of
approximating negative binomial photodetection statistics to Gaussian. Bottom:
Capacity of OPA receiver with the number of modes $M=10$. We observe that with
Gaussian approximation, we overestimate Shannon’s capacity of the OPA receiver
for EA communication while discriminating against BPSK states.

##  VIII Derivation of Mean photon number for Optical Parametric Amplifier

In this section, we derive in detail, the mean photon number for OPA using
Equations from Section III.1.

$\begin{split}{\hat{u}}^{\dagger}{\hat{u}}&=(\sqrt{G}{\hat{a}}_{R}^{\dagger}+\sqrt{G-1}{\hat{a}}_{I})(\sqrt{G}{\hat{a}}_{R}+\sqrt{G-1}{\hat{a}}_{I}^{\dagger})\\\\[4.0pt]
&=G{\hat{a}}_{R}^{\dagger}{\hat{a}}_{R}+\sqrt{G(G-1)}{\hat{a}}_{R}^{\dagger}{\hat{a}}_{I}^{\dagger}+\sqrt{G(G-1)}{\hat{a}}_{I}{\hat{a}}_{R}+(G-1){\hat{a}}_{I}{\hat{a}}_{I}^{\dagger}\\\\[4.0pt]
&=G{\hat{a}}_{R}^{\dagger}{\hat{a}}_{R}+(\sqrt{G(G-1)})({\hat{a}}_{R}^{\dagger}{\hat{a}}_{I}^{\dagger}+{\hat{a}}_{I}{\hat{a}}_{R})+(G-1){\hat{a}}_{I}{\hat{a}}_{I}^{\dagger}\\\\[6.0pt]
\expectationvalue{{\hat{u}}^{\dagger}{\hat{u}}}&=G\expectationvalue{{\hat{a}}_{R}^{\dagger}{\hat{a}}_{R}}+(\sqrt{G(G-1)})(\expectationvalue{{\hat{a}}_{R}^{\dagger}{\hat{a}}_{I}^{\dagger}}+\expectationvalue{{\hat{a}}_{I}{\hat{a}}_{R}})+(G-1)\expectationvalue{{\hat{a}}_{I}{\hat{a}}_{I}^{\dagger}}\\\\[4.0pt]
&=GN_{R}+\sqrt{G(G-1)}(e^{j\theta}+e^{-j\theta})\sqrt{\eta
N_{s}(N_{s}+1)}+(G-1)(1+N_{I})\\\\[4.0pt]
&\text{As,~{}}{\hat{a}}_{R}={\hat{a}}_{R^{\prime}}e^{j\theta},~{}\expectationvalue{{\hat{a}}_{R^{\prime}}{\hat{a}}_{I}}=\sqrt{\eta
N_{s}(N_{s}+1)},\\\
&~{}{\hat{a}}_{I}{\hat{a}}_{I}^{\dagger}={\hat{a}}_{I}^{\dagger}{\hat{a}}_{I}+I,\text{(from
the commutative property of annihilation and creation operators)}\\\\[4.0pt]
&\text{Further, }N_{R}=\eta N_{s}+N_{B}~{}\text{after passing through a
channel}\\\ &\text{~{}~{}~{}~{}with mean thermal photon number
$N_{B}$}\\\\[4.0pt] &N_{I}=N_{s},~{}\text{As,}\text{~{}~{}idler is per-
shared}\\\\[4.0pt]
{\overline{N}}_{1}(\theta)=\expectationvalue{{\hat{u}}^{\dagger}{\hat{u}}}&=G(\eta
N_{s}+N_{B})+(G-1)(1+N_{s})\\\ &+2\cos\theta\sqrt{G(G-1)}\sqrt{\eta
N_{s}(N_{s}+1)}\end{split}$ (29)

Similarly,

$\begin{split}{\hat{v}}^{\dagger}{\hat{v}}&=(\sqrt{G}{\hat{a}}_{I}^{\dagger}+\sqrt{G-1}{\hat{a}}_{R})(\sqrt{G}{\hat{a}}_{I}+\sqrt{G-1}{\hat{a}}_{R}^{\dagger})\\\\[4.0pt]
\expectationvalue{{\hat{v}}^{\dagger}{\hat{v}}}&=GN_{I}+2\cos\theta\sqrt{G(G-1)}\sqrt{\eta
N_{s}(N_{s}+1)}+(G-1)(1+N_{R})\\\\[4.0pt]
{\overline{N}}_{2}(\theta)=\expectationvalue{{\hat{v}}^{\dagger}{\hat{v}}}&=GN_{s}+(G-1)(1+\eta
N_{s}+N_{B})+2\cos\theta\sqrt{G(G-1)}\sqrt{\eta N_{s}(N_{s}+1)}\end{split}$
(30)

##  IX Mutual Information Calculation

In this section, at a very high level, we provide a calculation of how mutual
information can be calculated. The values of $P_{\text{OPA}}$ can be plugged
from Equation 8. We can first write the conditional probabilities, assuming
that the random variable $X$ denotes the transmitted symbols and $Y$ denotes
the detected symbols:

$\begin{split}p_{y|x}(Y=0|X=0)&=1-P_{\text{OPA}}(n<N_{\text{th}}|\theta=0;M)\\\
p_{y|x}(Y=1|X=1)&=P_{\text{OPA}}(n<N_{\text{th}}|\theta=\pi;M)\\\
p_{y|x}(Y=0|X=1)&=1-P_{\text{OPA}}(n<N_{\text{th}}|\theta=\pi;M)\\\
p_{y|x}(Y=1|X=0)&=P_{\text{OPA}}(n<N_{\text{th}}|\theta=0;M)\\\
p_{y}(Y=0)&=p_{0}p_{y|x}(Y=0|X=0)+p_{1}p_{y|x}(Y=0|X=1)\\\
p_{y}(Y=1)&=p_{0}p_{y|x}(Y=1|X=0)+p_{1}p_{y|x}(Y=1|X=1)\end{split}$ (31)

Using conditional probabilities, we can obtain mutual information as follows.

$\begin{split}H(Y|X=0)&=-p_{y|x}(Y=0|X=0)\log_{2}(p_{y|x}(Y=0|X=0))\\\
&-p_{y|x}(Y=1|X=0)\log_{2}(p_{y|x}(Y=1|X=0))\\\
H(Y|X=1)&=-p_{y|x}(Y=0|X=1)\log_{2}(p_{y|x}(Y=0|X=1))\\\
&-p_{y|x}(Y=1|X=1)\log_{2}(p_{y|x}(Y=1|X=1))\\\
H(Y|X)&=p_{0}H(Y|X=0)+p_{1}H(Y|X=1)\\\
H(Y)&=-p_{y}(Y=0)\log_{2}(p_{y}(Y=0))\\\ &-p_{y}(Y=1)\log_{2}(p_{y}(Y=1))\\\
I(X;Y)&=H(Y)-H(Y|X)\end{split}$ (32)

The mutual information can be used to calculate the capacity using Equation
24.

## References

  * Holevo and Werner (2001) A. S. Holevo and R. F. Werner, Physical Review A 63, 032312 (2001).
  * Holevo (2002) A. S. Holevo, Journal of Mathematical Physics 43, 4326 (2002).
  * Bennett  _et al._ (2002) C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, IEEE Transactions on Information Theory 48, 2637 (2002).
  * Shi  _et al._ (2020) H. Shi, Z. Zhang, and Q. Zhuang, Physical Review Applied 13, 034029 (2020).
  * Zhuang (2021) Q. Zhuang, arXiv preprint arXiv:2103.11054 (2021).
  * Zhang  _et al._ (2015) Z. Zhang, S. Mouradian, F. N. Wong, and J. H. Shapiro, Physical review letters 114, 110506 (2015).
  * Hao  _et al._ (2021) S. Hao, H. Shi, W. Li, J. H. Shapiro, Q. Zhuang, and Z. Zhang, Physical Review Letters 126, 250501 (2021).
  * Guha (2009) S. Guha, in  _2009 IEEE International Symposium on Information Theory_ (IEEE, 2009) pp. 963–967.
  * Djordjevic (0114) I. B. Djordjevic, IEEE Photonics Journal 13, 1 (June 2021, Article ID: 7500114).
  * Djordjevic (2021a) I. B. Djordjevic, IEEE Access 9, 168930 (2021a).
  * Bhadani (2021) R. Bhadani, “Optimal receiver design for quantum communication,” (2021).
  * Plenio and Vedral (1998) M. B. Plenio and V. Vedral, Contemporary physics 39, 431 (1998).
  * Shao-Ming  _et al._ (2010) F. Shao-Ming, S. Albeverio, A. Cabello, N. Jing, and D. Goswami, Advances in Mathematical Physics 2010 (2010).
  * Eisert (2006) J. Eisert, arXiv preprint quant-ph/0610253 (2006).
  * Miller (2011) J. Miller, Physics Today 64, 15 (2011).
  * Bennett  _et al._ (1999) C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, Physical Review Letters 83, 3081 (1999).
  * Giovannetti  _et al._ (2003) V. Giovannetti, S. Lloyd, L. Maccone, and P. W. Shor, Physical review letters 91, 047901 (2003).
  * Cubitt  _et al._ (2010) T. S. Cubitt, D. Leung, W. Matthews, and A. Winter, Physical Review Letters 104, 230503 (2010).
  * Lopez-Mago (2012) D. Lopez-Mago,  _Implementation of a two-photon michelson interferometer for quantum optical coherence tomography_ , Ph.D. thesis, Instituto Technologico y de Estudios Superiores de Monterrey (2012).
  * Christ  _et al._ (2013) A. Christ, A. Fedrizzi, H. Hübel, T. Jennewein, and C. Silberhorn, in  _Single-Photon Generation and Detection_, Experimental Methods in the Physical Sciences, Vol. 45, edited by A. Migdall, S. V. Polyakov, J. Fan, and J. C. Bienfang (Academic Press, 2013) pp. 351–410.
  * Mauerer  _et al._ (2009) W. Mauerer, M. Avenhaus, W. Helwig, and C. Silberhorn, Physical Review A 80, 053815 (2009).
  * Wilde (2013) M. M. Wilde,  _Quantum information theory_ (Cambridge University Press, 2013).
  * Ou (2017) Z. J. Ou,  _Quantum optics for experimentalists_ (World Scientific Publishing Company, 2017).
  * Lefevre (1989) D. Lefevre, Cynetics corporation (1989).
  * Tan  _et al._ (2008) S.-H. Tan, B. I. Erkmen, V. Giovannetti, S. Guha, S. Lloyd, L. Maccone, S. Pirandola, and J. H. Shapiro, Physical review letters 101, 253601 (2008).
  * Guan  _et al._ (2017) H. Guan, Y. Ma, R. Shi, X. Zhu, R. Younce, Y. Chen, J. Roman, N. Ophir, Y. Liu, R. Ding, _et al._ , Optics Express 25, 28957 (2017).
  * Shapiro  _et al._ (2005) J. Shapiro, S. Guha, and B. Erkmen, Journal of Optical Networking 4, 501 (2005).
  * Takeoka and Guha (2014) M. Takeoka and S. Guha, Physical Review A 89, 042309 (2014).
  * Djordjevic (2021b) I. B. Djordjevic, IEEE Access 9, 42604 (2021b).
  * Shieh and Djordjevic (2009) W. Shieh and I. Djordjevic, in  _OFDM for Optical Communications_, edited by W. Shieh and I. Djordjevic (Academic Press, Oxford, 2009) pp. 263–294.


10 1

Математические основы и численные методы моделирования Mathematical modeling
and numerical simulation

00.00.2022. 00.00.2022.

519.8 An Approach for Non-Convex Uniformly Concave Structured Saddle Point
Problem ††thanks: Исследование выполнено при поддержке Министерства науки и
высшего образования Российской Федерации (госзадание) № 075-00337-20-03, номер
проекта 0714-2020-0005.The research is supported by the Ministry of Science
and Higher Education of the Russian Federation (Goszadaniye) №
075-00337-20-03, project No. 0714-2020-0005.

Мохаммад С. Алкуса M. S. Alkousa Mohammad S. Alkousa 1]Московский физико-
технический институт, Россия, 141701, Московская обл., г. Долгопрудный,
Институтский пер., 9 [1]Moscow Institute of Physics and Technology, Russia,
141701, Moscow region, Dolgoprudny, Institutskiy per., 9

2]Национальный исследовательский университет «Высшая школа экономики», Россия,
101000, г. Москва, ул. Мясницкая, д. 20 [2]HSE University, Russia, 101000,
Moscow, Myasnitskaya St., 20

Александр В. Гасников A. V. Gasnikov Alexander A. Gasnikov 3]212705, г.
Москва, Большой Каретный переулок, д.19 стр. 1, Институт проблем управления
РАН им. А.А. Харкевича [3]Institute for Information Transmission Problems of
the Russian Academy of Sciences (Kharkevich Institute) 4]3385000, Республика
Адыгея, г. Майкоп, ул. Первомайск, д. 208, Кавказский математический центр
Адыгейского государственного университета [4]Caucasus Mathematical Center,
Adyghe State University, Maikop, Russia

Павел Е. Двуреченский P. E. Dvurechensky Pavel E. Dvurechensky 5]Weierstrass
Institute for Applied Analysis and Stochastics, Берлин, 10117 Германия
[5]Weierstrass Institute for Applied Analysis and Stochastics, Berlin, 10117
Germany

Абдурахмон А. Садиев A. A. Sadiev Abdurakhmon A. Sadiev

Лама Я. Разук L. Y. Razouk Lama Y. Razouk 6]Tartous University, Department of
Mathematics, Tartous, Сирия [6]Tartous University, Department of Mathematics,
Tartous, Syria

# Подход к решению невыпуклой равномерно вогнутой седловой задачи со
структурой

М. С. Алкуса<EMAIL_ADDRESS>[  [  А. В. Гасников
<EMAIL_ADDRESS>[  [  П. Е. Двуреченский<EMAIL_ADDRESS>[  А. А. Садиев<EMAIL_ADDRESS>Л. Я. Разук<EMAIL_ADDRESS>[

###### Abstract

В последнее время седловым задачам уделяется большое внимание благодаря их
мощным возможностям моделирования для множества задач из различных областей.
Приложения этих задач встречаются во многочисленных современных прикладных
областях, таких как робастная оптимизация, распределенная оптимизация, теория
игр и приложения машинного обучения такие, как например минимизация
эмпирического риска или обучение генеративно-состязательных сетей. Поэтому
многие исследователи активно работают над разработкой численных методов для
решения седловых задач в самых разных предположениях. Данная статья посвящена
разработке численного метода решения седловых задач в невыпуклой равномерно-
вогнутой постановке. В этой постановке считается, что по группе прямых
переменных целевая функция может быть невыпуклой, а по группе двойственных
переменных задача является равномерно вогнутой (это понятие обобщает понятие
сильной вогнутости). Был изучен более общий класс седловых задач со сложной
композитной структурой и Гёдьдерово непрерывными производными высшего порядка.
Для решения рассматриваемой задачи был предложен подход, при котором мы сводим
задачу к комбинации двух вспомогательных оптимизационных задач отдельно для
каждой группы переменных: внешней задачи минимизации и внутренней задачи
максимизации. Для решения внешней задачи минимизации мы используем адаптивный
градиентный метод, который применим для невыпуклых задач, а также работает с
неточным оракулом, который генерируется путем неточного решения внутренней
задачи максимизации. Для решения внутренней задачи максимизации мы используем
обобщенный ускоренный метод с рестартами, который представляет собой метод,
объединяющий методы ускорения высокого порядка для минимизации выпуклой
функции, имеющей Гёльдерово непрерывные производные высшего порядка. Важной
компонентой проведенного анализа сложности предлагаемого алгоритма является
разделение оракульных сложностей на число вызовов оракула первого порядка для
внешней задачи минимизации и оракула более высокого порядка для внутренней
задачи максимизации. Более того, оценивается сложность всего предлагаемого
подхода.

###### keywords:

Седловая задача

###### keywords:

невыпуклая оптимизация

###### keywords:

равномерно выпуклая функция

###### keywords:

неточный оракул

###### keywords:

метод высшего порядка

Recently, saddle point problems have received much attention due to their
powerful modeling capability for a lot of problems from diverse domains.
Applications of these problems occur in many applied areas, such as robust
optimization, distributed optimization, game theory, and many applications in
machine learning such as empirical risk minimization and generative
adversarial networks training. Therefore, many researchers have actively
worked on developing numerical methods for solving saddle point problems in
many different settings. This paper is devoted to developing a numerical
method for solving saddle point problems in the non-convex uniformly-concave
setting. We study a general class of saddle point problems with composite
structure and Hölder-continuous higher-order derivatives. To solve the problem
under consideration, we propose an approach in which we reduce the problem to
a combination of two auxiliary optimization problems separately for each group
of variables, outer minimization problem w.r.t. primal variables, and inner
maximization problem w.r.t the dual variables. For solving the outer
minimization problem, we use the Adaptive Gradient Method, which is applicable
for non-convex problems and also works with an inexact oracle that is
generated by approximately solving the inner problem. For solving the inner
maximization problem, we use the Restarted Unified Acceleration Framework,
which is a framework that unifies the high-order acceleration methods for
minimizing a convex function that has Hölder-continuous higher-order
derivatives. Separate complexity bounds are provided for the number of calls
to the first-order oracles for the outer minimization problem and higher-order
oracles for the inner maximization problem. Moreover, the complexity of the
whole proposed approach is then estimated. Saddle point problem non-convex
optimization uniformly convex function inexact oracle higher-order method

## 1\. Introduction

Due to their numerous applications, saddle point (or minimax) problems have
recently gained significant interest in many fields, including robust
optimization [Ben-Tal et al., 2009, Namkoong, Duchi, 2016], empirical risk
minimization [Tan et al., 2018, Zhang, Lin, 2015], statistics [Berger, 2013],
distributed non-convex optimization [Lu et al., 2019], game theory [Myerson,
2013, Nouiehed et al., 2019] and many applications of machine learning,
including reinforcement learning [Dai et al., 2018], adversarial learning
[Sinha et al., 2020], learning exponential families [Dai et al., 2019], fair
statistical inference [Madras et al., 2018, Xu et al., 2018], generative
adversarial networks [Zhang, 2021, Lei et al., 2020, Sanjabi et al., 2018],
domain adversarial training [Zhang, 2021], Wasserstein robust models [Sinha et
al., 2020], robust learning over multiple domains [Qian et al., 2019], off-
policy reinforcement learning [Huang, Jiang, 2021], prediction and regression
problems [Taskar et al., 2005]. Most of these applications require solving a
saddle point problem in which the objective function is non-convex in one
variable and strongly-concave (or in general uniformly-concave) in another
variable. For the saddle point problems, there is a long history of studies.
Recently, in the last years, many researchers have actively worked on the
development of numerical methods for solving these problems in many different
settings.

The general setting of saddle point problems, which is Non-Convex Concave
(without strong concavity assumption), is extensively explored in a lot of
works [Kong, Monteiro, 2021, Nouiehed et al., 2019, Ostrovskii et al., 2021,
Thekumparampil et al., 2019, Zhang, 2020]. The work [Nouiehed et al., 2019],
was the first providing non-asymptotic convergence rates for non-convex
concave problems without assuming special structure of the objective function.
The authors of [Thekumparampil et al., 2019] proposed an algorithm for the
general smooth non-convex concave saddle point problem with complexity
$\widetilde{\mathcal{O}}\left(\varepsilon^{-3}\right)$.111Here and below we
use the notation $\mathcal{O}(\cdot)$ to denote non-asymptotic upper bounds up
to constant factors. More precisely, $a=\mathcal{O}(b)$ means that there exist
a constant $C$ such that $a\leqslant Cb$. We use
$\widetilde{\mathcal{O}}(\cdot)$ for the same purposes, but when the constant
$C$ may include polylogarithmic factors of the parameters of interest, e.g.,
the desired accuracy $\varepsilon$ and confidence probability $\sigma$. The
same complexity for a simple two-time-scale inexact proximal point algorithm
was proved in [Yang et al., 2020(b)]. In [Zhang, 2020], a single-loop
algorithm ’’Smoothed GDA’’ (which is an iterative algorithm where each
iteration step has a closed form update) was proposed with iteration
complexity $\mathcal{O}\left(\varepsilon^{-2}\right)$ for the special case of
the general non-convex concave problems, which is equivalent to the problem of
minimizing the point-wise maximum of a finite collection of functions. The
complexity $\mathcal{O}\left(\varepsilon^{-2}\right)$ improves other
complexities, such as $\mathcal{O}\left(\varepsilon^{-2.5}\right)$ for triple-
loop algorithms [Ostrovskii et al., 2021, Lin et al., 2020(b)] and
$\mathcal{O}\left(\varepsilon^{-3.5}\right)$ for double-loop algorithms
[Nouiehed et al., 2019]. Also, non-convex concave saddle point problems via
zeroth-order algorithms were studied in [Xu et al., 2021], where the authors
proposed a zeroth-order alternating randomized gradient projection algorithm
for smooth non-convex concave problems.

Under the strong concavity assumption, several algorithms were proposed for
the non-convex-strongly-concave (NC-SC) class of problems, including GDmax
[Nouiehed et al., 2019], GDA [Lin et al., 2020(a)], alternating GDA [Boţ,
Böhm, 2020, Xu et al., 2020, Yang et al., 2020(a)]. Recently, in [Lin et al.,
2020(b)], the authors proposed an accelerated algorithm for smooth NC-SC and
non-convex concave minimax problems. This algorithm achieves the best
dependency on the condition number by combining proximal point algorithm with
accelerated gradient descent. Namely, it achieves a gradient complexity bound
of $\widetilde{\mathcal{O}}\left(\sqrt{\kappa}\varepsilon^{-2}\right)$ which
improves upon the best known bound
$\widetilde{\mathcal{O}}\left(\kappa^{2}\varepsilon^{-2}\right)$ [Lin et al.,
2020(a)]. Another line of research is devoted to solving NC-SC minimax
problems under additional structural properties [Diakonikolas et al., 2021,
Lin et al., 2021, Song et al., 2021, Yang et al., 2020(a)]. For more details
in the recent works in NC-SC in different settings, including the general and
average-smooth finite-sum settings, see [Zhang et al., 2021, Luo et al., 2020,
Ostrovskii et al., 2021, Luo, Chen, 2021] and references therein.

Despite this active line of research for different settings of saddle point
problems, to the best of our knowledge, the case when the objective function
is non-convex in one variable and uniformly concave in another variable
instead of strong concavity assumption (where the strong concavity case is a
spacial case of the inform concavity, see Definition Necessary Auxiliary
Statements below), still are not investigated. Therefore, we address this
setting of the problem in this paper that is devoted to the development of a
numerical method for solving saddle point problems in the non-convex
uniformly-concave setting. Moreover, we study a more general class of saddle
point problems with composite structure and Hölder-continuous higher-order
derivatives. In order to solve the problem under consideration, we propose an
approach, in which we reduce the problem to a combination of two auxiliary
optimization problems separately for each group of variables: outer and inner
problems. For solving the outer minimization problem, we use the Adaptive
Gradient Method [Dvurechensky, 2017], which is applicable for non-convex
problems and also works with inexact oracle. For solving the inner
maximization problem, we use the Restarted Unified Acceleration Framework
[Song et al., 2019], which is a framework, that unifies the high-order
acceleration methods for minimizing a convex function that has Hölder-
continuous higher-order derivatives. Separate bounds are provided for the
number of calls to the first-order oracles for the outer minimization problem
and higher-order oracles for inner maximization problem. Moreover, the
complexity of the whole proposed approach is then estimated.

The paper consists of the introduction, conclusion, and two main sections. In
Section 2, we present the problem statement, its connected assumptions, and
some necessary facts that will be used in the proposed approach. In Section 3,
we present the proposed approach in order to solve the considered saddle point
problem by applying Adaptive Gradient Method [Dvurechensky, 2017] and
Restarted Unified Acceleration Framework [Song et al., 2019]. When analyzing
the proposed approach, separate complexity bounds are provided for the number
of calls to the first-order oracles for the outer minimization and higher-
order oracles for the inner maximization problems. Moreover, the complexity of
the whole proposed approach is then estimated.

## 2\. Preliminaries and Problem Statement

### Problem Formulation and Assumptions

We focus on the following structured composite saddle point problem

$\displaystyle\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\left\\{S(x,y):=F(x,y)-h(y)+r(x)\right\\},$
(1)

in the case when $\mathcal{X}\subseteq\mathbb{R}^{n_{x}}$ is a compact convex
set, and $\mathcal{Y}=\mathbb{R}^{n_{y}}$. The function
$h:\mathcal{Y}\to\mathbb{R}$ is differentiable and uniformly convex (see
Definition Necessary Auxiliary Statements, below), the function
$r:\mathcal{X}\to\mathbb{R}$ is a simple (maybe non-smooth) convex function,
e.g. $\|x\|_{1}$. Note that when $h(y)=r(x)=0,\;\forall
x\in\mathcal{X},\forall y\in\mathcal{Y}$, we obtain a problem which is a
special (unstructured) case of problem (1). We assume that the function
$F(\cdot,y)$, for every $y\in\mathcal{Y}$, is possibly non-convex in the
primal variable $x\in\mathcal{X}$, and $F(x,\cdot)$ for every
$x\in\mathcal{X}$ is concave in the dual variable $y\in\mathcal{Y}$. Thus the
function $S(x,y)$ will be non-convex uniformly concave (NC-UC), for every
$x\in\mathcal{X}$ and $y\in\mathcal{Y}$. Moreover, we assume that the $p$-th
derivatives of $F$ with respect to its variables satisfy the Hölder condition
(in other words, the function $F$ has $(p,\nu)$–Hölder-continuous derivatives,
for some $\nu\in[0,1],p\in\\{1,2,\ldots\\}$). More precisely, for arbitrary
$x,x^{\prime}\in\mathcal{X}$, $y,y^{\prime}\in\mathcal{Y}$, the following
inequalities hold (here and in what follows, the norm $\|\cdot\|$ denotes the
Euclidean norm)

$\displaystyle\left\|\nabla_{x}^{p}F(x,y)-\nabla_{x}^{p}F(x^{\prime},y)\right\|\leqslant
L_{xx}\|x-x^{\prime}\|^{\nu},$ (2)
$\displaystyle\left\|\nabla_{x}^{p}F(x,y)-\nabla_{x}^{p}F(x,y^{\prime})\right\|\leqslant
L_{xy}\|y-y^{\prime}\|^{\nu},$ (3)
$\displaystyle\left\|\nabla_{y}^{p}F(x,y)-\nabla_{y}^{p}F(x^{\prime},y)\right\|\leqslant
L_{yx}\|x-x^{\prime}\|^{\nu},$ (4)
$\displaystyle\left\|\nabla_{y}^{p}F(x,y)-\nabla_{y}^{p}F(x,y^{\prime})\right\|\leqslant
L_{yy}\|y-y^{\prime}\|^{\nu},$ (5)

where $L_{xx},L_{yy},L_{xy},L_{yx}>0$.

Let

$\displaystyle\widehat{S}(x,y):=F(x,y)-h(y).$ (6)

and

$\displaystyle g(x):=\max_{y\in\mathcal{Y}}\widehat{S}(x,y).$ (7)

Then, the problem (1) can be rewritten as follows

$\displaystyle\min_{x\in\mathcal{X}}\\{g(x)+r(x)\\}.$ (8)

Let

$\displaystyle
y^{*}(x)\in\arg\max_{y\in\mathcal{Y}}\widehat{S}(x,y)\quad\forall
x\in\mathcal{X}$ (9)

be a solution of the maximization problem (7). Then

$\displaystyle
g(x)=\widehat{S}\left(x,y^{*}(x)\right)=F\left(x,y^{*}(x)\right)-h\left(y^{*}(x)\right).$
(10)

For an arbitrary $x\in\mathcal{X}$ and some $\hat{\delta}\geqslant 0$, the
point $\widetilde{y}_{\hat{\delta}}(x)\in\mathcal{Y}$ is called a
$\hat{\delta}$-approximate solution of problem (7) if

$\displaystyle
g(x)-\widehat{S}\left(x,\widetilde{y}_{\hat{\delta}}(x)\right)=\widehat{S}(x,y^{*}(x))-\widehat{S}\left(x,\widetilde{y}_{\hat{\delta}}(x)\right)\leqslant\hat{\delta}.$

### Necessary Auxiliary Statements

In order to solve the considered problem (1), we propose an approach that uses
several auxiliary results and algorithms as building blocks. In what follows,
we present these auxiliary results, whereas the used algorithms in the
proposed approach will be presented in the next section.

We say that differentiable function $f$ is uniformly convex of degree
$q\geqslant 2$ on a convex set $Q\subseteq domf$ if for some constant
$\sigma_{q}>0$ it satisfies the following inequality:

$\displaystyle f(y)\geqslant f(x)+\langle\nabla
f(x),y-x\rangle+\frac{\sigma_{q}}{q}\|y-x\|^{q},\quad\forall x,y\in Q.$

We note that the uniformly convex functions of degree $q=2$ are strongly
convex with $\sigma_{2}$ as the strong convexity parameter.

The next lemma gives us the main properties of the function $g$ defined in (7)
and the mapping $y^{*}$ defined in (9).

######  Lemma 1.

Let $h:\mathbb{R}^{n_{y}}\to\mathbb{R}$ be a uniformly convex function of
degree $q\geqslant 2$ with constant $\sigma_{q}>0$, and the function $F$ have
$(1,\nu)$-Hölder-continuous derivative with respect to the variable
$x\in\mathcal{X}$, for $\nu\in[0,1]$. Then the mapping $y^{*}(\cdot)$
satisfies the Hölder condition on the set $\mathcal{X}$. Also, $\nabla g$ is
Hölder-continuous with Hölder constant
$L_{\nu}(g):=L_{xy}\left(\frac{qL_{xy}}{\sigma_{q}}\right)^{\frac{\nu}{q-\nu}}+L_{xx}D_{0}^{\frac{\nu(q-\nu-1)}{q-\nu}}$
and Hölder exponent $\nu_{g}:=\frac{\nu}{q-\nu}$, where
$D_{0}=\sup_{x,x^{\prime}\in\mathcal{X}}\|x^{\prime}-x\|$.

Proof: Similarly to [Alkousa et al., 2020]. Since $\widehat{S}(x_{1},\cdot)$
is uniformly concave of degree $q$ with constant $\sigma_{q}$, for arbitrary
$x_{1},x_{2}\in\mathcal{X}$, we have

$\displaystyle\|y^{*}(x_{1})-y^{*}(x_{2})\|^{q}\leqslant\frac{q}{\sigma_{q}}\left(\widehat{S}(x_{1},y^{*}(x_{1}))-\widehat{S}(x_{1},y^{*}(x_{2}))\right).$

On the other hand, since $y^{*}(x_{2})$ attains the maximum to
$\widehat{S}(x_{2},\cdot)$, then
$\widehat{S}(x_{2},y^{*}(x_{1}))-\widehat{S}(x_{2},y^{*}(x_{2}))\leqslant 0$.
Therefore, we can write

$\displaystyle\begin{split}\widehat{S}(x_{1},y^{*}(x_{1}))&-\widehat{S}(x_{1},y^{*}(x_{2}))\leqslant\widehat{S}(x_{1},y^{*}(x_{1}))-\widehat{S}(x_{1},y^{*}(x_{2}))-\widehat{S}(x_{2},y^{*}(x_{1}))+\widehat{S}(x_{2},y^{*}(x_{2}))=\\\
&=\left(F(x_{1},y^{*}(x_{1}))-F(x_{1},y^{*}(x_{2}))\right)-\left(F(x_{2},y^{*}(x_{1}))-F(x_{2},y^{*}(x_{2}))\right)\\\
&=\int_{0}^{1}\langle\nabla_{x}F(x_{1}+t(x_{2}-x_{1}),y^{*}(x_{1}))-\nabla_{x}F(x_{1}+t(x_{2}-x_{1}),y^{*}(x_{2})),x_{2}-x_{1}\rangle
dt\\\
&\leqslant\|\nabla_{x}F(x_{1}+t(x_{2}-x_{1}),y^{*}(x_{1}))-\nabla_{x}F(x_{1}+t(x_{2}-x_{1}),y^{*}(x_{2}))\|\cdot\|x_{2}-x_{1}\|\\\
&\leqslant
L_{xy}\|y^{*}(x_{1})-y^{*}(x_{2})\|^{\nu}\cdot\|x_{2}-x_{1}\|,\end{split}$

where in the last inequality we used (3) for $p=1$. Thus, we have the
following inequality

$\displaystyle\|y^{*}(x_{2})-y^{*}(x_{1})\|\leqslant\left(\frac{qL_{xy}}{\sigma_{q}}\right)^{\frac{1}{q-\nu}}\|x_{2}-x_{1}\|^{\frac{1}{q-\nu}},\quad\forall
x_{1},x_{2}\in\mathcal{X},$

which means that $y^{*}(\cdot)$ satisfies the Hölder condition on
$\mathcal{X}$.

Similarly to [Nouiehed et al., 2019], we find

$\displaystyle\nabla
g(x)=\nabla_{x}\widehat{S}(x,y^{*}(x))=\nabla_{x}F(x,y^{*}(x)),\quad\forall
x\in\mathcal{X}.$ (11)

Further, from (11), we have

$\displaystyle\|\nabla g(x_{1})$ $\displaystyle-\nabla
g(x_{2})\|=\|\nabla_{x}F(x_{1},y^{*}(x_{1}))-\nabla_{x}F(x_{2},y^{*}(x_{2}))\|=$
$\displaystyle=\|\nabla_{x}F(x_{1},y^{*}(x_{1}))-\nabla_{x}F(x_{1},y^{*}(x_{2}))+\nabla_{x}F(x_{1},y^{*}(x_{2}))-\nabla_{x}F(x_{2},y^{*}(x_{2}))\|$
$\displaystyle\leqslant\|\nabla_{x}F(x_{1},y^{*}(x_{1}))-\nabla_{x}F(x_{1},y^{*}(x_{2}))\|+\|\nabla_{x}F(x_{1},y^{*}(x_{2}))-\nabla_{x}F(x_{2},y^{*}(x_{2}))\|$
$\displaystyle\leqslant
L_{xy}\|y^{*}(x_{1})-y^{*}(x_{2})\|^{\nu}+L_{xx}\|x_{1}-x_{2}\|^{\nu}$
$\displaystyle\leqslant
L_{xy}\left(\frac{qL_{xy}}{\sigma_{q}}\right)^{\frac{\nu}{q-\nu}}\|x_{1}-x_{2}\|^{\frac{\nu}{q-\nu}}+L_{xx}\|x_{1}-x_{2}\|^{\nu}$
$\displaystyle=L_{xy}\left(\frac{qL_{xy}}{\sigma_{q}}\right)^{\frac{\nu}{q-\nu}}\|x_{1}-x_{2}\|^{\frac{\nu}{q-\nu}}+L_{xx}\|x_{1}-x_{2}\|^{\frac{\nu}{q-\nu}}\cdot\|x_{1}-x_{2}\|^{\frac{\nu(q-\nu-1)}{q-\nu}}$
$\displaystyle\leqslant\left(L_{xy}\left(\frac{qL_{xy}}{\sigma_{q}}\right)^{\frac{\nu}{q-\nu}}+L_{xx}D_{0}^{\frac{\nu(q-\nu-1)}{q-\nu}}\right)\cdot\|x_{1}-x_{2}\|^{\frac{\nu}{q-\nu}}.$

This means, that $\nabla g$ is Hölder-continuous with the Hölder constant

$L_{\nu}(g)=L_{xy}\left(\frac{qL_{xy}}{\sigma_{q}}\right)^{\frac{\nu}{q-\nu}}+L_{xx}D_{0}^{\frac{\nu(q-\nu-1)}{q-\nu}},$

and the Hölder exponent $\nu_{g}=\frac{\nu}{q-\nu}$. ∎

## 3\. Used Algorithms and The Proposed Approach

When solving the considered saddle point problem (1), as we saw, we deal with
two problems, the outer is a minimization problem and the inner is a
maximization problem. Using an iterative method for the outer problem requires
solving the inner problem numerically in each iteration. Let us first mention
some methods, that will be used in order to solve the outer and inner
optimization problems.

### Algorithm for the outer minimization problem:

For the outer minimization problem (8), we will use an algorithm that was
proposed in [Dvurechensky, 2017, Bogolubsky et al., 2016]. This algorithm
(listed as Algorithm 1 below) is a first-order method and it was developed for
composite non-convex minimization problems with inexact oracle. Moreover, it
is universal with respect to Hölder parameters of the problem. Firstly, let us
introduce some fundamental concepts, connected with Algorithm 1.

Let $d:\mathcal{X}\rightarrow\mathbb{R}$ be a prox-function (distance
generating function), i.e. it is continuous, convex on $\mathcal{X}$ and

  1. 1.

admits a continuous selection of subgradients $\nabla d(x)$, in
$x\in\mathcal{X}^{\circ}$, where $\mathcal{X}^{\circ}\subseteq\mathcal{X}$ is
the set of all $x$ such that $\nabla d(x)$ exists.

  2. 2.

$d$ is $1$-strongly convex with respect to the norm $\|\cdot\|$, i.e.

$\displaystyle d(y)\geqslant d(x)+\langle\nabla
d(x),y-x\rangle+\frac{1}{2}\|y-x\|^{2},\quad\forall\;x\in\mathcal{X}^{\circ},y\in\mathcal{X}.$

The corresponding Bregman divergence is defined as

$V_{z}(x)=d(x)-d(z)-\left\langle\nabla d(z),x-z\right\rangle,\quad\forall
x\in\mathcal{X},z\in\mathcal{X}^{\circ}.$

In particular, in the standard proximal setup (i.e. Euclidean setup) we can
choose $d(x)=\frac{1}{2}\|x\|_{2}^{2}$ (Euclidean prox function), leading to
$V_{z}(x)=\frac{1}{2}\|x-z\|_{2}^{2}$.

Now, let we consider the following minimization problem

$\displaystyle\min_{x\in\mathcal{X}}\\{f(x)=\xi(x)+\zeta(x)\\},$ (12)

where $\zeta(x)$ is a simple convex function, and $\xi(x)$ is a non-convex
function, endowed with an inexact first-order oracle (see Definition Algorithm
for the outer minimization problem:, below), and has Hölder-continuous
gradient on $\mathcal{X}$, with constant $L_{\nu}$ and exponent $\nu$.

([Dvurechensky, 2017]) We say that a function $\xi(x)$ is equipped with an
inexact first-order oracle on a set $\mathcal{X}$ if there exists
$\delta_{u}>0$ and at any point $x\in\mathcal{X}$ for any number
$\delta_{c}>0$ there exists a constant $L(\delta_{c})\in(0,+\infty)$ and one
can calculate $\widetilde{\xi}(x,\delta_{c},\delta_{u})$ and
$\widetilde{g}(x,\delta_{c},\delta_{u})$ satisfying

$\left|\xi(x)-\widetilde{\xi}(x,\delta_{c},\delta_{u})\right|\leqslant\delta_{c}+\delta_{u},$

and

$\xi(y)-\left(\widetilde{\xi}(x,\delta_{c},\delta_{u})-\langle\widetilde{g}(x,\delta_{c},\delta_{u}),y-x\rangle\right)\leqslant\frac{L(\delta_{c})}{2}\|x-y\|^{2}+\delta_{c}+\delta_{u},\quad\forall
y\in\mathcal{X}.$

######  Remark 2.

By Lemma 1, we have

$\|\nabla g(x_{1})-\nabla g(x_{2})\|\leqslant
L_{\nu}(g)\|x_{1}-x_{2}\|^{\nu_{g}},\quad\forall x_{1},x_{2}\in\mathcal{X}.$

Then

$g(z)\leqslant g(x)+\langle\nabla
g(x),z-x\rangle+\frac{L_{\nu}(g)}{1+\nu_{g}}\|x-z\|^{1+\nu_{g}},\quad\forall
x,z\in\mathcal{X}.$

Now, for all $x\in\mathcal{X}$ and $\delta>0$, we have (see [Nesterov, 2015],
Lemma 2),

$g(z)-\left(g(x)-\langle\nabla
g(x),z-x\rangle\right)\leqslant\frac{L(\delta)}{2}\|x-z\|^{2}+\delta,\quad\forall
z\in\mathcal{X},$

where

$\displaystyle
L(\delta)=\left(\frac{1-\nu_{g}}{1+\nu_{g}}\cdot\frac{2}{\delta}\right)^{\frac{1-\nu_{g}}{1+\nu_{g}}}\cdot\left(L_{\nu}(g)\right)^{\frac{2}{1+\nu_{g}}}.$
(13)

Thus, according to the Definition Algorithm for the outer minimization
problem:, $\left(g(x),\nabla g(x)\right)$ is an inexact first-order oracle
with $\delta_{u}=0,\delta_{c}=\delta$, and $L(\delta)$ given by (13). Note
that, if $\left(g(x),\nabla g(x)\right)$ can only be calculated inexactly,
then their approximations will again be an inexact first-order oracle.

([Dvurechensky, 2017]) Let $\mathbb{E}$ be a finite-dimensional real vector
space and $\mathbb{E}^{*}$ be its dual. Assume that we are given
$\delta_{pc}>0,\gamma>0,\bar{x}\in\mathcal{X}^{\circ}$ and
$\eta\in\mathbb{E}^{*}$. We call a point
$\widetilde{x}=\widetilde{x}(\bar{x},\eta,\gamma,\delta_{pc},\delta_{pu})\in\mathcal{X}^{\circ}$,
an inexact composite prox-mapping iff for any $\delta_{pc}>0$ we can calculate
$\widetilde{x}$ and there exists $s\in\partial\zeta(\widetilde{x})$ such that
it holds that

$\displaystyle\left\langle\eta+\frac{1}{\gamma}\left(\nabla
d(\widetilde{x})-\nabla
d(\bar{x})\right)+s,z-\widetilde{x}\right\rangle\geqslant-\delta_{pc}-\delta_{pu},\quad\forall
z\in\mathcal{X},$

and we write

$\displaystyle\widetilde{x}={\arg\min_{x\in\mathcal{X}}}^{\delta_{pc}+\delta_{pu}}\left\\{\langle\eta,x\rangle+\frac{1}{\gamma}V_{\bar{x}}(x)+\zeta(x)\right\\}.$

Algorithm 1 Adaptive Gradient Method for Problems with Inexact Oracle
[Dvurechensky, 2017].

0: starting point $x_{0}\in\mathcal{X}^{\circ}$, accuracy $\varepsilon>0$,
initial guess $L_{0}>0$, $\delta_{u}>0$ and $\delta_{pu}>0$.

1: Set $k=0$.

2: repeat

3: Set $M_{k}=L_{k}/2$.

4: repeat

5: Set $M_{k}=2M_{k},\delta_{c,k}=\delta_{pc,k}=\frac{\varepsilon}{20M_{k}}$.

6: Calculate $\widetilde{\xi}\left(x_{k},\delta_{c,k},\delta_{u}\right)$ and
$\widetilde{g}\left(x_{k},\delta_{c,k},\delta_{u}\right)$.

7: Calculate  $\displaystyle
z_{k}={\arg\min_{x\in\mathcal{X}}}^{\delta_{pc,k}+\delta_{pu}}\left\\{\left\langle\widetilde{g}\left(x_{k},\delta_{c,k},\delta_{u}\right),x\right\rangle+M_{k}V_{x_{k}}(x)+\zeta(x)\right\\}.$

8: Calculate $\widetilde{\xi}\left(z_{k},\delta_{c,k},\delta_{u}\right)$.

9: until
$\displaystyle\widetilde{\xi}\left(z_{k},\delta_{c,k},\delta_{u}\right)\leqslant\widetilde{\xi}\left(x_{k},\delta_{c,k},\delta_{u}\right)+\left\langle\widetilde{g}\left(x_{k},\delta_{c,k},\delta_{u}\right),z_{k}-x_{k}\right\rangle+\frac{M_{k}}{2}\left\|z_{k}-x_{k}\right\|^{2}++\frac{\varepsilon}{10M_{k}}+2\delta_{u}.$

10: Set $x_{k+1}=z_{k},L_{k+1}=M_{k}/2$ and $k=k+1$.

11: until $\min_{i\in
1,\ldots,k}\left\|M_{i}\left(x_{i}-x_{i+1}\right)\right\|\leqslant\varepsilon$.

11: The point $x_{K+1}$, such that $K=\arg\min_{i\in
1,\ldots,k}\left\|M_{i}\left(x_{i}-x_{i+1}\right)\right\|$.

In [Dvurechensky, 2017], for Algorithm 1, it was proved that if
$L(\delta_{c})$ in Definition Algorithm for the outer minimization problem:,
is given by

$\displaystyle
L\left(\delta_{c}\right)=\left(\frac{1-\nu}{1+\nu}\cdot\frac{2}{\delta_{c}}\right)^{\frac{1-\nu}{1+\nu}}L_{\nu}^{\frac{2}{1+\nu}},\quad\delta_{c}>0,\;\text{and}\;\nu\in(0,1].$

Then after

$\displaystyle\mathcal{O}\left(\frac{L_{\nu}^{\frac{1}{\nu}}\left(f(x_{0})-f^{*}\right)}{\varepsilon^{\frac{1+\nu}{2\nu}}}\right)$
(14)

iterations of Algorithm 1, it holds that

$\displaystyle\left\|M_{k}(x_{K}-x_{K+1})\right\|^{2}\leqslant\varepsilon.$

### Algorithm for the inner maximization problem:

For the inner maximization problem (7), when $\mathcal{Y}=\mathbb{R}^{n_{y}}$,
we will use the Restarted Unified Acceleration Framework (Restarted UAF) [Song
et al., 2019], see Algorithm 2 below. The Restarted UAF algorithm was proposed
in [Song et al., 2019] for uniformly convex functions, it represents a general
restart scheme for such general class of problems. The Unified Acceleration
Framework (UAF) [Song et al., 2019], is a framework, that unifies the high-
order acceleration methods for minimizing a convex function that has Hölder-
continuous derivatives. The iteration complexities of instances of both the
UAF and the Restarted UAF match existing lower bounds in most important cases
[Grapiglia, Nesterov, 2019]. Let us here mention briefly the statements of the
algorithm Restarted UAF, in order to solve the following composite
optimization problem

$\displaystyle\min_{y\in\mathbb{R}^{n_{y}}}\\{f(y)=\varphi(y)+\psi(y)\\},$
(15)

where $\varphi,\psi$ are convex functions. Assume that

  1. 1.

Assumption 1: the function $\varphi$ has $(p,\nu)$-Hölder-continuous
derivatives, with the constant of smoothness $L>0$. This means

$\left\|\nabla^{p}\varphi(y)-\nabla^{p}\varphi(y^{\prime})\right\|\leqslant
L\|x-y\|^{\nu},\quad\forall y,y^{\prime}\in\mathbb{R}^{n_{y}},$

where $\nu\in[0,1]$ and $p\in\\{1,2,\ldots\\}$.

  2. 2.

Assumption 2: the objective function $f$ is uniformly convex of degree
$q\geqslant 2$ and constant $\sigma_{q}>0$.

For the problem (15), let $\mathcal{A}_{m}(y)$ denote the output of an
algorithm $\mathcal{A}$ after $m$ iterations with an input $y$, which
satisfies

$\displaystyle
f\left(\mathcal{A}_{m}(y)\right)-f\left(y_{*}\right)\leqslant\frac{c_{\mathcal{A}}\left\|y-y_{*}\right\|^{\nu}}{m^{r}},$
(16)

for some constants $r>0,\nu>0,c_{\mathcal{A}}>0$, and $y_{*}$ is a solution of
(15).

Let $R>0$ be a constant such that $\|y_{0}-y_{*}\|\leqslant R$, where $y_{0}$
is the starting point of algorithm $\mathcal{A}$. We define

$\displaystyle
m_{0}=\left[\left(\frac{2^{q}qc_{\mathcal{A}}R^{\nu-q}}{\sigma_{q}}\right)^{\frac{1}{r}}\right],\quad
k_{0}=\begin{cases}{\left[\frac{1}{q}+\frac{\nu}{q}\log_{2}(R)+\frac{1}{\nu-q}\log_{2}\left(\frac{qc_{\mathcal{A}}}{\sigma_{q}}\right)\right],}&q<\nu\\\
+\infty\qquad\qquad\qquad\qquad\qquad\qquad\quad\,,&q\geqslant\nu\end{cases}$
(17)

Algorithm 2 Restarted Unified Acceleration Framework (Restarted UAF) [Song et
al., 2019].

0: $q\geqslant 2$, starting point $y_{0}\in\mathbb{R}^{n_{y}}$,
$K\in\mathbb{Z}_{+}$, an algorithm $\mathcal{A}$ satisfying (16), constants
$m_{0}$ and $k_{0}$ which defined in (17).

1: Set $z_{0}=y_{0}$.

2: for $k=0,1,\ldots,K-1$ do

3: if $k\leqslant k_{0}-1$ then

4: $m_{k}=\left[m_{0}2^{-\frac{\nu-q}{r}k}\right]$.

5: $z_{k+1}=\mathcal{A}_{m_{k}}\left(z_{k}\right)$.

6: else

7: $z_{k+1}=\mathcal{A}_{1}\left(z_{k}\right)$.

8: end if

9: end for

9: $y_{K}:=z_{K}$.

In [Song et al., 2019], for the Algorithm 2, it was proved the following
result.

Under assumptions 1 and 2 above, to achieve an $\varepsilon$-solution of the
problem (15) by Algorithm 2 with $\mathcal{A}$ being UAF, the number of
iterations we need is at most

$\displaystyle\mathcal{O}\left(\left(\frac{L}{\sigma_{q}}\right)^{\frac{2}{3(p+\nu)-2}}\log\left(\frac{1}{\varepsilon}\right)\right)\quad\text{if}\;\;q=p+\nu,$
$\displaystyle\mathcal{O}\left(\left(\frac{L}{\sigma_{q}}\right)^{\frac{2}{3(p+\nu)-2}}+\log\log\left(\left(\frac{\sigma_{q}^{p+\nu}}{L^{q}}\right)^{\frac{1}{p+\nu-q}}\frac{1}{\varepsilon}\right)\right)\quad\text{if}\;\;q<p+\nu,$
$\displaystyle\mathcal{O}\left(\left(\frac{L}{\sigma_{q}}\right)^{\frac{2}{3(p+\nu)-2}}\left(\frac{\sigma_{q}}{\varepsilon}\right)^{\frac{2(q-p-\nu)}{q(3(p+\nu)-2)}}\right)\quad\text{if}\;\;q>p+\nu.$

### The Proposed Approach:

We are now in a position to combine all the building blocks and present our
proposed approach. For solving the considered saddle point problem (1), we
reduce it to a combination of two auxiliary optimization problems separately
for each group of variables: outer and inner problems, which are (8) and (7)
respectively. By using Algorithms 1 and 2 we propose the following approach.

Approach 1: The outer minimization problem (8) is solved via ‘‘Adaptive
Gradient Method for Problems with Inexact Oracle’’ (Algorithm 1), and in each
iteration of Algorithm 1, the inner maximization problem (7) is solved via
‘‘Restarted Unified Acceleration Framework’’ (Algorithm 2).

Recall that the objective function $S(x,y)=F(x,y)-h(y)+r(x),\forall
x\in\mathcal{X},y\in\mathcal{Y}=\mathbb{R}^{n_{y}}$, in the considered problem
(1), is non-convex in $x$, and uniformly concave in $y$ via the uniform
convexity of $h$. The function $F$ has $(1,\nu)$-Hölder-continuous derivatives
with respect to the primal variable $x$ and it has $(p,\nu)$-Hölder-continuous
derivatives with respect to the dual variable $y$, for
$\nu\in[0,1],p\in\\{1,2,\ldots\\}$, (see (2)—(5)). Let
$\widehat{L}=\max\\{L_{yx},L_{yy}\\}$.

For the complexity of the proposed approach, we find that from (14), the
Algorithm 1 will perform
$\mathcal{O}\left(\frac{(L_{\nu}(g))^{\frac{1}{\nu_{g}}}\Delta}{\varepsilon^{\frac{1+\nu_{g}}{2\nu_{g}}}}\right)$
steps (first-order oracle), where $\Delta=g_{0}-g_{*}$ is the difference
between the value of the function $g$ at the initial point and its minimal
value, and $L_{\nu}(g),\nu_{g}$ are given in Lemma 1. At each step of
Algorithm 1, Algorithm 2 will perform at most the following number of
iterations, dependently on $p,\nu$ and $q$ (the degree of the uniform
convexity of the function $h$):

$\displaystyle\mathcal{O}\left(\left(\frac{\widehat{L}}{\sigma_{q}}\right)^{\frac{2}{3(p+\nu)-2}}\log\left(\frac{1}{\varepsilon}\right)\right)\quad\text{if}\;\;q=p+\nu,$
$\displaystyle\mathcal{O}\left(\left(\frac{\widehat{L}}{\sigma_{q}}\right)^{\frac{2}{3(p+\nu)-2}}+\log\log\left(\frac{1}{\varepsilon}\left(\frac{\sigma_{q}^{p+\nu}}{{\widehat{L}}^{q}}\right)^{\frac{1}{p+\nu-q}}\right)\right)\quad\text{if}\;\;q<p+\nu,$
$\displaystyle\mathcal{O}\left(\left(\frac{\widehat{L}}{\sigma_{q}}\right)^{\frac{2}{3(p+\nu)-2}}\left(\frac{\sigma_{q}}{\varepsilon}\right)^{\frac{2(q-p-\nu)}{q(3(p+\nu)-2)}}\right)\quad\text{if}\;\;q>p+\nu.$

From the previous, we can see that the proposed approach is universal, in the
sense of the order of smoothness of the objective function, where the
considered class of problems contains more classes of problems as a special
case, dependently on the values of the parameters $p,\nu$, and $q$.

Summarizing, we have the following theorem, which gives the complexity of the
proposed approach for solving the structured saddle point problem under
consideration in the case when $q$, i.e., the degree of uniform concavity of
the objective function (1), equals $p+\nu$, which gives the better complexity.

By applying the proposed Approach 1, in the case when $q=p+\nu$, we obtain an
$\varepsilon$-solution of the problem (8) (which is equivalent to the problem
(1)), after
$\mathcal{O}\left(\frac{(L_{\nu}(g))^{\frac{1}{\nu_{g}}}\Delta}{\varepsilon^{\frac{1+\nu_{g}}{2\nu_{g}}}}\right)$
calls of the first-order oracle and

$\widetilde{\mathcal{O}}\left(\frac{(L_{\nu}(g))^{\frac{1}{\nu_{g}}}\Delta}{\varepsilon^{\frac{1+\nu_{g}}{2\nu_{g}}}}\cdot\left(\frac{\widehat{L}}{\sigma_{q}}\right)^{\frac{2}{3(p+\nu)-2}}\right)$

calls of higher-order oracle, where
$\widetilde{\mathcal{O}}(\cdot)=\mathcal{O}(\cdot)$ up to a logarithmic factor
in $\log(\varepsilon^{-1})$.

## 4\. Conclusions

In this paper, we developed a numerical method for solving a more general
class of saddle point problems with composite structure and Hölder-continuous
gradients, in the non-convex-uniformly-concave setting. We reduce the
considered problem to a combination of two auxiliary optimization problems
separately for each group of variables, namely, outer minimization problem
(which is solved by the Adaptive Gradient Method applicable for non-convex
problems and works with inexact oracle [Dvurechensky, 2017]) and inner
maximization problem (which is solved by the Restarted Unified Acceleration
Framework, which unifies high-order acceleration methods for minimizing a
convex function that has Hölder-continuous higher-order derivative [Song et
al., 2019]). We provided separate bounds for the number of calls to oracles
for the outer and inner problems. Moreover, the complexity of the whole
proposed approach is then estimated. As a future work it is planned to study
the similar considered class of problems under the Polyak-Lojasiewicz
condition instead of the non-convexity for the function with respect to the
primal variable for the minimization problem, also to generalize the proposed
approach for the non-Euclidean setting, and conduct numerical results for some
applications and compare the results with other known approaches.

## References

  * [Alkousa et al., 2020] Alkousa M. S., Gasnikov A. V., Dvinskikh D. M., Kovalev D. A., Stonyakin F. S. Accelerated methods for saddle-point problem // Computational Mathematics and Mathematical Physics. —2020. — Vol. 60, No. 11. —P. 1787–1809.
  * [Ben-Tal et al., 2009] Ben-Tal A., Ghaoui L. E., Nemirovski A. Robust optimization. Princeton university press, 2009. — 576 p.
  * [Berger, 2013] Berger J. O. Statistical decision theory and Bayesian analysis. Springer Series in Statistics, Springer, New York, NY, 2013. — 618 p.
  * [Boţ, Böhm, 2020] Boţ R. I., Böhm A. Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems // arXiv preprint — 2020. https://arxiv.org/pdf/2007.13605.pdf
  * [Bogolubsky et al., 2016] Bogolubsky L., Dvurechensky P., Gasnikov A. et al. Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods // Advances in Neural Information Processing Systems 29 / Lee D. D., Sugiyama M., Luxburg U. V. et al. (ed.). — Curran Associates, Inc., 2016. — P. 4914–4922.
  * [Dai et al., 2019] Dai B., Dai H., Gretton A., Song L., Schuurmans D., He N. Kernel exponential family estimation via doubly dual embedding // In The 22nd International Conference on Artificial Intelligence and Statistics —2019. — P. 2321–2330.
  * [Dai et al., 2018] Dai B, Shaw A., Li L., Xiao L., He N., Liu Z., Chen J., Song L. SBEED: Convergent reinforcement learning with nonlinear function approximation // In International Conference on Machine Learning —2018. — P. 1125–1134.
  * [Diakonikolas et al., 2021] Diakonikolas J., Daskalakis C., Jordan M. Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization // In International Conference on Artificial Intelligence and Statistics —2021. — P. 2746–2754.
  * [Dvurechensky, 2017] Dvurechensky P. Gradient method with inexact oracle for composite nonconvex optimization // arXiv preprint — 2017. https://arxiv.org/pdf/1703.09180.pdf
  * [Grapiglia, Nesterov, 2019] Grapiglia G. N., Nesterov Yu. Tensor methods for minimizing functions with Höder continuous higher-order derivatives // SIAM J. Optim. — 2019. — Vol. 30, No. 4, — P. 2750–2779.
  * [Huang, Jiang, 2021] Huang J., Jiang N. On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction // arXiv preprint — 2021. https://arxiv.org/pdf/2106.00993.pdf
  * [Kong, Monteiro, 2021] Kong W., Monteiro R. D. C. An accelerated inexact proximal point method for solving nonconvex-concave min-max problems // arXiv preprint — 2021. https://arxiv.org/pdf/1905.13433.pdf
  * [Lei et al., 2020] Lei Q., Lee J., Dimakis A., Daskalakis C. SGD Learns One-Layer Networks in WGANs // In International Conference on Machine Learning — 2020. — P. 5799–5808.
  * [Lin et al., 2021] Lin Q., Rafique H., Liu M., Yang T. First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems // Journal of Machine Learning Research — 2021. — Vol. 22, —P. 1–34.
  * [Lin et al., 2020(a)] Lin T., Jin C., Jordan M. On gradient descent ascent for nonconvex concave minimax problems // In International Conference on Machine Learning —2020, — P. 6083–6093.
  * [Lin et al., 2020(b)] Lin T., Jin C., Jordan M. Near-optimal algorithms for minimax optimization // Proceedings of Machine Learning Research — 2020. — Vol. 125, —P. 1–42. http://proceedings.mlr.press/v125/lin20a/lin20a.pdf
  * [Lu et al., 2019] Lu S., Tsaknakis I., Hong M. Block alternating optimization for non-convex min-max problems: algorithms and applications in signal processing and communications // In ICASSP 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) — 2019. — P. 4754–4758.
  * [Luo, Chen, 2021] Luo L., Chen C. Finding second-order stationary point for nonconvex strongly-concave minimax problem // arXiv preprint — 2021. https://arxiv.org/pdf/2110.04814.pdf
  * [Luo et al., 2020] Luo L., Ye H., Huang Z., Zhang T. Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems // NeurIPS — 2020. https://arxiv.org/pdf/2001.03724.pdf
  * [Madras et al., 2018] Madras D., Creager E., Pitassi T., Zemel R. Learning adversarially fair and transferable representations // In International Conference on Machine Learning — 2018. — P. 3384–3393.
  * [Myerson, 2013] Myerson R.B. Game theory. Harvard university press, 2013. — 600 p.
  * [Namkoong, Duchi, 2016] Namkoong H., Duchi J.C. Stochastic gradient methods for distributionally robust optimization with f-divergences // NeurIPS —2016. — Vol. 29, P. 2208–2216.
  * [Nesterov, 2015] Nesterov Yu. Universal gradient methods for convex optimization problems// Math. Program. —2015. — Vol. 152(1), P. 381–404.
  * [Nouiehed et al., 2019] Nouiehed M., Sanjabi M., Huang T., Lee J.D., Razaviyayn M. Solving a class of non-convex min-max games using iterative first order methods // NeurIPS — 2019. https://proceedings.neurips.cc/paper/2019/file/25048eb6a33209cb5a815bff0cf6887c-Paper.pdf
  * [Ostrovskii et al., 2021] Ostrovskii D. M., Barazandeh B., Razaviyayn M. Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain // arXiv preprint — 2021. https://arxiv.org/pdf/2110.03950.pdf
  * [Ostrovskii et al., 2021] Ostrovskii D. M., Lowy A., Razaviyayn M. Efficient search of first-order nash equilibria in nonconvex-concave smooth min-max problems // SIAM Journal on Optimization — 2021. — Vol. 31, No. 4, p —2508–2538.
  * [Qian et al., 2019] Qian Q., Zhu S., Tang J., Jin R., Sun B., Li H. Robust optimization over multiple domains // In Proceedings of the AAAI Conference on Artificial Intelligence — 2019.— Vol. 33, P. 4739–4746.
  * [Sanjabi et al., 2018] Sanjabi M., Ba J., Razaviyayn M., Lee D.J. On the convergence and robustness of training gans with regularized optimal transport // NeurIPS — 2018. — https://proceedings.neurips.cc/paper/2018/file/5a9d8bf5b7a4b35f3110dde8673bdda2-Paper.pdf
  * [Sinha et al., 2020] Sinha A., Namkoong H., Volpi R., Duchi J. Certifying some distributional robustness with principled adversarial training // arXiv preprint — 2020. https://arxiv.org/pdf/1710.10571.pdf
  * [Song et al., 2019] Song c., Jiang Y., Ma Y. Unified Acceleration of High-Order Algorithms under Hölder Continuity and Uniform Convexity // arXiv preprint — 2019. https://arxiv.org/pdf/1906.00582.pdf
  * [Song et al., 2021] Song C., Zhou Z., Zhou Y., Jiang Y., Ma Y. Optimistic dual extrapolation for coherent non-monotone variational inequalities // arXiv preprint — 2021. https://arxiv.org/pdf/2103.04410.pdf
  * [Tan et al., 2018] Tan C., Zhang T., Ma S., Liu J. Stochastic primal-dual method for empirical risk minimization with o(1) per-iteration complexity // NeurIPS — 2018. https://proceedings.neurips.cc/paper/2018/file/08048a9c5630ccb67789a198f35d30ec-Paper.pdf
  * [Taskar et al., 2005] Taskar B., Julien S. L., Jordan M. Structured prediction via the extragradient method// NeurIPS — 2005.— P. 1345–1352.
  * [Thekumparampil et al., 2019] Thekumparampil K., Jain P., Netrapalli P., Oh S. Efficient algorithms for smooth minimax optimization // NeurIPS — 2019. https://papers.nips.cc/paper/2019/file/05d0abb9a864ae4981e933685b8b915c-Paper.pdf
  * [Xu et al., 2018] Xu D., Yuan S., Zhang L., Wu X. FairGAN: Fairness-aware generative adversarial networks // In 2018 IEEE International Conference on Big Data (Big Data) — 2018.— P. 570–575.
  * [Xu et al., 2021] Xu Z., Shen J., Wang Z., Dai Y. Zeroth-order alternating randomized gradient projection algorithms for general nonconvex-concave minimax problems // arXiv preprint — 2021. https://arxiv.org/pdf/2108.00473.pdf
  * [Xu et al., 2020] Xu Z., Zhang H., Xu Y., Lan G.  A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems // arXiv preprint — 2020. https://arxiv.org/pdf/2006.02032.pdf
  * [Yang et al., 2020(a)] Yang J., Kiyavash N., He N. Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems // NeurIPS — 2020. https://proceedings.neurips.cc/paper/2020/file/0cc6928e741d75e7a92396317522069e-Paper.pdf
  * [Yang et al., 2020(b)] Yang J., Zhang S., Kiyavash N., He N. A Catalyst Framework for Minimax Optimization // NeurIPS — 2020. https://proceedings.neurips.cc/paper/2020/file/3db54f5573cd617a0112d35dd1e6b1ef-Paper.pdf
  * [Zhang, 2021] Zhang G. Understanding minimax optimization in modern machine learning // UWSpace — 2021. http://hdl.handle.net/10012/17157
  * [Zhang, 2020] Zhang J., Xiao P., Sun R., Luo Z.Q. A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems // NeurIPS — 2020. https://proceedings.neurips.cc/paper/2020/file/52aaa62e71f829d41d74892a18a11d59-Paper.pdf
  * [Zhang et al., 2021] Zhang S., Yang J., Guzmán C., Kiyavash N., He N. The complexity of nonconvex-strongly-concave minimax optimization // arXiv preprint — 2021. https://arxiv.org/pdf/2103.15888.pdf
  * [Zhang, Lin, 2015] Zhang Y., Lin X. Stochastic primal-dual coordinate method for regularized empirical risk minimization// In International Conference on Machine Learning — 2015.— P. 353–361.