\section{Introduction}

To facilitate full-space smart radio environment, the novel concept of simultaneously transmitting and reflecting reconfigurable intelligent surfaces (STAR-RISs)~\cite{liu_star,xu_star,IOS,added,mu_star} has been recently proposed. Unlike the reflecting-only RISs or known as intelligent reflecting surfaces (IRSs), STAR-RISs are capable of supporting simultaneous transmission and reflection\footnote{Here, transmission refers to the physical process of signal penetrating the surface.}. Thus, the wireless signal can propagate to both sides of the surface while its amplitude and phase are beneficially controlled during the transmission and reflection.
In~\cite{xu_star}, the authors proposed a hardware model and two channel models for employing STAR-RISs to assist downlink communications.
Although the benefits of STAR-RISs have been demonstrated, existing works mainly focused on the STAR-RIS-aided downlink transmission. Recall the fact that the full-space coverage can be provided by STAR-RISs. However, it is not yet clear how wireless signals can be manipulated when the signals incident on both sides of the surface simultaneously. This is practically relevant to the uplink communication scenario, where multiple users surrounding the STAR-RIS have to upload their information to the base station (BS).

\textcolor{black}{
Against the above background, this work compliments the downlink signal model we proposed in~\cite{xu_star} and provides the hardware and signal models for
STAR-RIS under dual-sided signal incidence.
Exploiting electromagnetic (EM) theory, we confirm that STAR-RISs are able to simultaneously reconfigure the propagation of signals incident on different sides. In this letter, we use the term \textit{dual-sided} STAR-RISs to distinguish this dual-side working mode with the single-sided signal incident working mode.}
Specifically, for the case where the surface impedance of each element can be characterized with scalars, we prove that the transmission and reflection coefficients on both sides are identical, meaning that each STAR-RIS element is symmetrical. Based on the proposed models, a STAR-RIS-aided two-user uplink communication system is investigated with non-orthogonal multiple access (NOMA) and orthogonal multiple access (OMA).
\textcolor{black}{Due to the ability to beneficially adjust the power ratio of the uploaded signals between users on transmission and reflection sides of the STAR-RIS, STAR-RIS-aided uplink NOMA is capable of achieving higher gain over conventional reflecting-only RIS-aided NOMA.}
We provide the new channel statistics for the double-Rician cascaded channels. Moreover, closed-form expressions are given for the outage probabilities of uplink users within the high-SNR regime.

\section{EM-Based Modeling for Dual-Sided STAR-RISs}
In prior studies, two complex coefficients, namely, the transmission and reflection (T\&R) coefficients, are introduced to characterize the \textit{STAR} feature of each element~\cite{xu_star}.
However, these two coefficients are derived by assuming that the signals only incident from one side of the surface and there is no signal incident from the other side. The signal model is generally unknown for the case where there are wireless signals simultaneously incident on both sides of the STAR-RIS, namely \emph{dual-sided incidence}. To fill this knowledge gap, in this section,
we provide a signal model for \textit{dual-sided} STAR-RISs. Since the `STAR' process occurs on each side, we introduce two pairs of coefficients in the following general signal model.
\begin{figure}[h!]
    \begin{center}
        \includegraphics[scale=0.4]{mac_fig/RandT.eps}
        \caption{A general signal model for dual-sided STAR-RISs}
        \label{randt}
    \end{center}
\end{figure}

\begin{theorem}
As illustrated in Fig.~\ref{randt}, for vertically polarized wireless signals, the signals radiating from the $m$th element towards \textit{Space A} ($s'_A$) and towards \textit{Space B} ($s'_B$) \textcolor{black}{are linear superposition of the incident signals ($s_{A/B}$):}
\textcolor{black}{
\begin{align}\label{signal_model}
    s'_A = \sum_{\theta \in \Theta_A}R^A_m(\theta) \cdot s_A(\theta) + \sum_{\theta \in \Theta_B }T^{B,A}_m(\theta) \cdot s_B(\theta), \\
    s'_B = \sum_{\theta \in \Theta_A}T^{A,B}_m(\theta) \cdot s_A(\theta) + \sum_{\theta \in \Theta_B}R^B_m(\theta) \cdot s_B(\theta),
\end{align}
}where $T^{A,B}_m(\theta)$ and $T^{B,A}_m(\theta)$ are the transmission coefficients from \textit{Space A/B} to \textit{Space B/A}, $R^{A/B}_m(\theta)$ is the reflection coefficient for \textit{Space A/B}, subscript $m$ denote the $m$th STAR element, \textcolor{black}{$\theta$ is the incidence angle of the signal, and $\Theta_A$ and $\Theta_B$ are the set of angles of the incident signals from Space A and Space B}, respectively.
\begin{proof}
The key for this proof is to demonstrate that the received signals are the linear superposition of the incident signals from different directions. According to \cite{estakhri2016wave}, for STAR-RIS that is electrically thin, the EM response can be equivalently described using surface electric and magnetic currents $\mathbf{J}_s$ and $\mathbf{K}_s$.
\textcolor{black}{
Note that the direction of $\mathbf{K}_s$ is determined through the curl right-hand rule, which is illustrated in Fig.~\ref{ele}.}
Considering passive STAR-RIS elements, these currents are excited by the total EM field $\mathbf{E}_{tot},\mathbf{H}_{tot}$, and scaled by the electric admittance ($\overline{\overline{\mathbf{Y}}}_e$) and magnetic impedance ($\overline{\overline{\mathbf{Z}}}_m$) tensors at each element, i.e., $\mathbf{J}_s = \overline{\overline{\mathbf{Y}}}_e \cdot \mathbf{E}_{tot}$ and $\mathbf{K}_s = \overline{\overline{ \mathbf{Z}}}_m \cdot \mathbf{H}_{tot}$. As illustrated in Fig.~\ref{ele}, the electric current density $\mathbf{J}_s$ generates fields $\mathbf{E}^J$, $\mathbf{H}^J_1$, and $\mathbf{H}^J_2$ while the magnetic current density $\mathbf{K}_s$ generates fields $\mathbf{E}^K_1$, $\mathbf{E}^K_2$, and $\mathbf{H}^K$. The magnitude of the radiating field, $\mathbf{E}^J$ and $\mathbf{E}^K$, are proportional to the strength of $\mathbf{J}_s$ and $\mathbf{K}_s$. Thus, \textcolor{black}{for signals with the same polarization,} the received field can be expressed as the linear combination of the incident fields $\mathbf{E}^{inc}_1$ and $\mathbf{E}^{inc}_2$. Finally, by using the fact that the signal $s_{A/B}$ is the proportional to the magnitude of the corresponding electric field, i.e., $s_{A/B} = ||\textbf{E}^{inc}_{A/B}||_2$, the theorem is derived.
\end{proof}
\end{theorem}

\begin{figure}[h!]
    \begin{center}
        \includegraphics[scale=0.3]{mac_fig/append_n}
        \caption{Schematic of the STAR-RIS element under EM wave incidence.}
        \label{ele}
    \end{center}
\end{figure}

\begin{figure*}[t!]
\centering
\subfigure[Purely transmitting configuration (connecting \textit{Space A/B})]{\label{sysa}
\includegraphics[width= 2in]{mac_fig/pureT.eps}}
\subfigure[Purely reflecting configuration (separating \textit{Space A/B})]{\label{sysb}
\includegraphics[width= 2in]{mac_fig/pureR.eps}}
\caption{Signal model for purely transmitting and purely reflecting.}\label{nice0}
\end{figure*}

\subsection{A Hardware Model for Symmetrical Dual-Sided STAR-RISs}
For a general scenario, the T\&R coefficients for the two sides can be different, i.e., $T^{A,B}_m \neq T^{B,A}_m$ and $R^A_m\neq R^B_m$. However, for the case where the surface impedances can be characterized with scalars~\cite{estakhri2016wave}, the elements have symmetrical EM response for the two directions, \textcolor{black}{i.e., $T^{A,B}_m = T^{B,A}_m$ and $R^A_m = R^B_m$.}
Following the method as adopted in~\cite{sci_rep,xu_correlated}, we separately study the radiation of electric and magnetic currents\footnote{Here, the magnetic current refers to the equivalent magnetic current generated by the vortex currents~\cite{old}.}. The schematic illustration of the STAR-RIS under EM incidence on both sides is presented in Fig.~\ref{ele}.
In \textit{Space A/B}, the total electrical radiation comes from the contributions of these induced electric fields and the overall incident fields $\mathbf{E}^{inc}_1$ and $\mathbf{E}^{inc}_2$.
The strengths of the surface electric and magnetic currents are proportional to the sum of the incident and radiated fields at the STAR-RIS~\cite{sci_rep}.
Thus, the density of the electric and magnetic currents are respectively given by:
\begin{align}\label{js}
    \mathbf{J}_s &= (\mathbf{E}^{inc}_1+\mathbf{E}^{inc}_2+\mathbf{E}^J)/Z_e,\\ \label{ks}
    \mathbf{K}_s &=(\mathbf{H}^{inc}_1-\mathbf{H}^{inc}_2+\mathbf{H}^K)Z_m,
\end{align}
where $Z_e$ and $Z_m$ are the scalar electric and magnetic impedance of the $m$th element, respectively.
To solve the generated electric fields $\mathbf{E}^{J}$ and $\mathbf{E}^{K}$, we consider the following boundary conditions.
The boundary conditions~\cite{rothwell2018electromagnetics} of EM field at the surface can be expressed as $\hat{z}\times (\mathbf{H}^J_2-\mathbf{H}^J_1)\hat{y} = \mathbf{J}_s\hat{x}$ and \textcolor{black}{ $\hat{z}\times(\mathbf{E}^K_1 - \mathbf{E}^K_2)\hat{x}=\mathbf{K}_s\hat{y}$}. Thus, we can obtain the following:
\begin{align}
&\mathbf{E}^{J} = -\frac{\eta(\mathbf{E}^{inc}_1+\mathbf{E}^{inc}_2)}{2Z_e+\eta},\\
&\mathbf{E}^{K}_1 = - \mathbf{E}^{K}_2 = \frac{Z_m(\mathbf{E}^{inc}_1-\mathbf{E}^{inc}_2)}{Z_m+2\eta},
\end{align}
where $\eta$ is the free space wave impedance.

For a receiver located in \textit{Space A/B}, the received signal strength is proportional to the square of the overall received electric field. As illustrated in Fig.~\ref{ele}, for \textit{Space A}, we collect all the wave vectors going towards the left, i.e., $\mathbf{k}^{inc}_2$, $\mathbf{k}^{J}_1$, and $\mathbf{k}^{K}_1$. Thus, the overall electric field propagating towards \textit{Space A/B} through the $m$th STAR element can be calculated as follows:
\begin{align}
\begin{split}
    \mathbf{E}^{rec}_{A} &= \mathbf{E}^J + \mathbf{E}^K_{1} + \mathbf{E}^{inc}_{2} =
    \underbrace{\big( \frac{Z_m}{Z_m+2\eta}-\frac{\eta}{2Z_e+\eta}\big)}_{R_m}\mathbf{E}^{inc}_{1}
    \\&+\underbrace{\big( \frac{2Z_e}{2Z_e+\eta} - \frac{Z_m}{Z_m+2\eta}\big)}_{T_m}\mathbf{E}^{inc}_{2}. \label{ea}
    \end{split}
\end{align}
Similarly, the overall electric field propagating towards \textit{Space B} is as follows:
\begin{align}
\begin{split}
    \mathbf{E}^{rec}_B &= \mathbf{E}^J + \mathbf{E}^K_2 + \mathbf{E}^{inc}_1 =
    \underbrace{\Big(\frac{2Z_e}{2Z_e+\eta} - \frac{Z_m}{Z_m+2\eta} \Big)}_{T_m}\mathbf{E}^{inc}_1
    \\&+\underbrace{\Big( \frac{Z_m}{Z_m+2\eta}-\frac{\eta}{2Z_e+\eta}\Big)}_{R_m}\mathbf{E}^{inc}_2.
    \end{split}\label{eb}
\end{align}

Next, exploiting \eqref{ea} and \eqref{eb}, the signal model for dual-sided STAR-RIS can be established.

\subsection{Signal Modeling for Symmetrical Dual-Sided STAR-RIS Elements}
According to \eqref{ea} and \eqref{eb}, we have the following theorem.

\begin{theorem}
For symmetrical dual-sided STAR-RISs, the signals radiating from the $m$th element towards \textit{Space A} ($s'_A$) and towards \textit{Space B} ($s'_B$) are as follows:
\begin{align}\label{spa}
    s'_A = R_m \cdot s_A + T_m \cdot s_B, \\ \label{spb}
    s'_B = T_m \cdot s_A + R_m \cdot s_B,
\end{align}
where
\begin{align} \label{ttm}
    T_m = \frac{2Z_e}{2Z_e+\eta} - \frac{Z_m}{Z_m+2\eta},\\ \label{rrm}
    R_m = \frac{Z_m}{Z_m+2\eta}-\frac{\eta}{2Z_e+\eta}
\end{align}
are the T\&R coefficients for each STAR-RIS element.
\begin{proof}
\textcolor{black}{
The proof of this theorem is based on the boundary conditions and the density of the electric and magnetic currents given in \eqref{js} and \eqref{ks}. Exploiting these characteristics, the field in both \textit{Space A} and \textit{Space B} were given in \eqref{ea} and \eqref{eb}.
Then, by using the fact that the received signal $s'_{A/B}$ is the proportional to the magnitude of the received electric field, i.e., $s'_{A/B} = ||\textbf{E}^{rec}_{A/B}||_2$, \eqref{ea} and \eqref{eb} can be rewritten into the forms as in \eqref{spa} and \eqref{spb}, respectively.}
\end{proof}
\end{theorem}

\begin{comment}
\begin{corollary}
For the purely transmitting or purely reflecting scenario, the received signal in \textit{Space A} and \textit{Space B} are respectively given as follows:
\begin{equation}\label{c1eq1}
    s'_A = T_ms_B,\  s'_B = T_ms_A,
\end{equation}
for purely transmitting where $T_m = \frac{2Z_e}{2Z_e+\eta} - \frac{Z_m}{Z_m+2\eta}$ and
\begin{equation}\label{c1eq2}
    s'_A = R_m s_A,\  s'_B = R_m s_B,
\end{equation}
for purely reflecting, where $R_m = \frac{Z_m}{Z_m+2\eta}-\frac{\eta}{2Z_e+\eta}$.

\begin{proof}
For the purely transmitting scenario, the surface impedance of each element need to satisfy $\frac{Z_m}{Z_m+2\eta}=\frac{\eta}{2Z_e+\eta}$~\cite{estakhri2016wave}. By substituting this equation into \eqref{ea} and \eqref{eb}, \eqref{c1eq1} can be derived. Similarly \eqref{c1eq2} can be derived by plugging $\frac{2Z_e}{2Z_e+\eta} = \frac{Z_m}{Z_m+2\eta}$ in \eqref{ea} and \eqref{eb}.
\end{proof}

\end{corollary}

\end{comment}

\begin{figure}[b!]
    \begin{center}
        \includegraphics[scale=0.25]{mac_fig/sys_model.eps}
        \caption{System model for the dual-sided STAR-RIS-aided uplink communication system.}
        \label{sys_fig}
    \end{center}
\end{figure}

\section{Performance Evaluation for A Dual-Sided STAR-RIS Uplink System}
Based on the above signal model, we evaluate the performance of a dual-sided STAR-RIS-aided uplink communication system. \textcolor{black}{We consider the two-user case and the employment of two fundamental multiple access schemes, i.e., OMA and NOMA.
}

\subsection{System Model}

We study the application scenario where a symmetrical \textit{dual-sided} STAR-RIS is deployed to assist the uplink communication.
\textcolor{black}{
To reveal the fundamental performance limit and to obtain closed-form results, we consider a two-user setup.}
We term the user which uploads the information via the reflection link as user $r$ and the user which uploads the information via the transmission link as user $t$. The direct link between the users and BS are assumed to be blocked.
\textcolor{black}{
The STAR-RIS has $M$ elements whose complex-valued T\&R coefficients are given according to \eqref{ttm} and \eqref{rrm}. For convenience, in the following, we rewrite these coefficients in terms of their amplitudes and phase-shift arguments, i.e., $T_m = \beta^T_m e^{j\phi^T_m}$ and $R_m = \beta^R_m e^{j\phi^R_m}$, $m \in \{1,2,\cdots, M \}$.
}
The links between the $m$th STAR-RIS element and the BS, $h_m$, is assumed to follow Rician distribution, i.e., $|h_m| \sim \mathcal{R}(K_h,\Omega_h)$, where $K_h$ and $\Omega_h$ are the shape and scale parameters of the Rician distribution. The links between the $m$th STAR-RIS element and the users, $g^t_m$ and $g^r_m$, also follow Rician distribution, i.e., $|g^\chi_m|\sim \mathcal{R}(K^\chi_g,\Omega^\chi_g)$, where the notation $\chi\in\{t,r\}$ is an indicator representing the corresponding values for user $t$ or user $r$.
For the multiple access schemes, we first consider NOMA and then consider conventional OMA as a baseline.

\subsection{NOMA}\label{sec_noma}
In NOMA, the two users upload their information to the BS via the same time/frequency resource blocks. The channel conditions of users depend on the choice of $T_m$ and $R_m$. According to the proposed signal model, the signal received at BS can be expressed as follows:
\begin{equation}\label{y}
    y = \sum_{m=1}^M g^r_m  h_m \beta^R_m e^{j\phi^R_m}  \sqrt{p} s_r
     + \sum_{m=1}^M g^t_m  h_m \beta^T_m e^{j\phi^T_m}  \sqrt{p} s_t + n_0,
\end{equation}
where $s_r$ and $s_t$ are the message of user $r$ and user $t$, respectively, $p$ is the transmit power of the uplink users, and $n_0$ is the additive white Gaussian noise at the BS with variance $\sigma^2_0$. Withough loss of generality, we assume user $r$ is closer to the STAR-RIS and has a higher channel gain than user $t$.
At the BS, the signal of user $r$ is decoded first by treating the other signal as interfering noise, and the corresponding signal-to-interference-plus-noise ratio (SINR) is given by:
\begin{equation}\label{sinrk}
    \mathrm{SINR}_r = \frac{p \big|\sum_{m=1}^M g^r_m  h_m \beta^R_m e^{j\phi^R_m}\big|^2}{p \big| \sum_{m=1}^M g^t_m  h_m \beta^T_m e^{j\phi^T_m} \big|^2 + \sigma^2_0}.
\end{equation}
\textcolor{black}{
Then, the signal of user $t$ can be decoded after carrying out successive interference cancellation (SIC). Consider imperfect SIC, only a portion of the signal from user $r$ can be successfully cancelled. Thus, the signal of user $t$ has the following SINR:
\begin{equation}\label{snr0}
    \mathrm{SINR}_t = \frac{p\big| \sum_{m=1}^M g^t_m  h_m \beta^T_m e^{j\phi^T_m} \big|^2
    }{\alpha_0\cdot p\big| \sum_{m=1}^M g^t_m  h_m \beta^T_m e^{j\phi^T_m} \big|^2 + \sigma^2_0},
\end{equation}
where $\alpha_0\in[0,1]$ is the error propagation factor which characterizes the quality of the SIC, i.e., $\alpha_0=0$ corresponds to perfect SIC and $\alpha_0=1$ corresponds to the case where no cancellation is performed.
}
\subsection{New Channel Statistics}
New channel statistics can be obtained for the considered STAR-RIS-aided uplink system. Since the overall channel distribution is highly sensitive on the choice of $T_m$ and $R_m$, we consider the performance achieved by configuring $\phi^T_m$ and $\phi^R_m$ according to the cophase condition~\cite{di2019smart}. Moreover, we assume that the amplitudes, $\beta^T_m$ and $\beta^R_m$, are uniform across the entire STAR-RIS, i.e., $\beta^{T/R}_m = \beta^{T/R}, \ \forall m\in \{1,2,\cdots, M\}$. According to \eqref{sinrk} and \eqref{snr0}, under cophasing phase shift, the overall uplink channel for the two users can be expressed as follows:
\begin{align}\label{Hr}
    H_{r/t} &= \sum_{m=1}^M\beta^{R/T}|h_m|\cdot |g^{r/t}_m|.
\end{align}
Note that $\phi^{R/T}_m$  are chosen to align the phases of each terms in the sum of \eqref{Hr}. Next, we study the distribution of $|H_r|$, $|H_t|$, $\mathrm{SINR}_r$, and $\mathrm{SNR}_t$.

\begin{lemma}
Each term in the summation of \eqref{Hr} is the product of two Rician variables. Let $X^r_m = |h_m||g^r_m|$ and $X^t_m = |h_m||g^t_m|$, their probability density functions (PDFs) are given as follows:
\begin{align}\label{pro_rician}
\begin{split}
    &f_{|X^\chi_m|}(x) = \frac{x}{\beta_h\beta^\chi_g} e^{-(K_h+K^\chi_g)}\\
    &\cdot\sum_{i=0}^\infty\sum_{l=0}^\infty\frac{\big(\frac{\alpha_h\sqrt{x}}{2\beta_h} \big)^{2i}\big(\frac{\alpha^\chi_g\sqrt{x}}{2\beta^\chi_g} \big)^{2l}}{i!l!\Gamma(i+1)\Gamma(l+1)}
     \big(\frac{\beta_h}{\beta^\chi_g}\big)^{\frac{i-l}{2}}K_{i-l}\big(\frac{x}{\sqrt{\beta_h\beta^\chi_g}}\big),
    \end{split}
\end{align}
where $\alpha^2_{h}=\frac{K_{h}\Omega_{h}}{K_{h}+1}$,$(\alpha^\chi_g)^2=\frac{K^\chi_g\Omega^\chi_g}{K^\chi_g+1}$, $\beta_{h}=\frac{\Omega_{h}}{2(K_{h}+1)}$
, $\beta^\chi_{g}=\frac{\Omega^\chi_g}{2(K^\chi_g+1)}$, $\Gamma(x)$ denotes the Gamma function, and $K_n$ is the modified Bessel function of the second kind.
\begin{proof}
The detailed proof for the PDF of the product of two Rician variables can be found in \cite{simon2002probability}.
\end{proof}
\end{lemma}

\subsection{Outage Probability}
In the considered system, the achievable rate of user $r$ is given by $R_r = \log_2(1+\mathrm{{SINR}_r})$.
Consider a fixed-rate transmission, the outage probability of user $r$ is given by:
\begin{equation}\label{pout_r}
    P^r_{out} = \mathrm{Pr}\{ \mathrm{SINR}_r < 2^{\Tilde{R}_r}-1 \}.
\end{equation}
For user $t$, the BS needs to subtract the decoded message from user $r$ first, then decode the remaining message, thus, the outage probability is given by:
\begin{equation}\label{pout_t}
    P^t_{out} = 1 - \mathrm{Pr}\{ \mathrm{SINR}_r > 2^{\Tilde{R}_r}-1, \mathrm{SNR}_t > 2^{\Tilde{R}_t}-1 \},
\end{equation}
where $\Tilde{R}_r$ and $\Tilde{R}_t$ are the target data rate for user $r$ and $t$, respectively.
However, the PDF of the SINR in \eqref{sinrk} is difficult to evaluate in closed-form expressions. To reveal more practical insights, we study the outage probabilities in the high transmit SNR regime\footnote{Here, the transmit SNR is $\gamma_{transmit} = p/\sigma^2_0$}.

\subsubsection{High Transmit SNR Regime}
For the high transmit SNR scenario, we assume that $p/\sigma^2_0 \gg 1$. Thus, the outage probabilities of user $r$ can be reduced to:
\begin{equation}\label{prout}
    P^r_{out} = \mathrm{Pr}\Big\{\frac{\big|\sum_{m=1}^M g^r_m  h_m \beta^R_m e^{j\phi^R_m}\big|^2}{\big| \sum_{m=1}^M g^t_m  h_m \beta^T_m e^{j\phi^T_m} \big|^2} < \gamma_r \Big\},
\end{equation}
where $\gamma_r = 2^{\Tilde{R}_r}-1$.
\textcolor{black}{Considering the impact of imperfect SIC, the outage probability of user $t$ is given as follows:
\begin{equation}\label{ptout}
    P^t_{out} = \begin{cases}
       \mathrm{Pr}\Big\{\frac{\big|\sum_{m=1}^M g^r_m  h_m \beta^R_m e^{j\phi^R_m}\big|^2}{\big| \sum_{m=1}^M g^t_m  h_m \beta^T_m e^{j\phi^T_m} \big|^2} \!<\! \gamma_r \Big\},\!&\text{if}\ \alpha_0^{-1} > 2^{\tilde{R}_t}\!-\!1 \\
      1,&\text{otherwise}.
    \end{cases}
\end{equation}
}
In the following theorem, we give the closed-form analytical result for the outage probabilities.
\begin{theorem}\label{t3}
In the high transmit SNR regime, the outage probability is given by:
\begin{align}\label{P_high_snr}
    P_{out} = \Phi\left(\frac{\mu^tx_0 - \mu^r}{\sigma^t\sigma^r\xi(x_0)} \right),
\end{align}
where $\Phi(y) = \int_{u=-\infty}^y \frac{1}{\sqrt{2\pi}}e^{-u^2/2} du$ is the error function, $\xi(x) = \sqrt{\frac{x^2}{(\sigma^r)^2}-\frac{2\rho x}{\sigma^r\sigma^t}+\frac{1}{(\sigma^t)^2}}$, \textcolor{black}{$\rho = \mathrm{Cov}(|H_r|,|H_t|)/(\sigma^r\sigma^t)$ is the correlation coefficient between $|H_r|$ and $|H_t|$}, $x_0 = \sqrt{\gamma_r}\beta^T/\beta^R$ is the threshold for the outage probability, $\mu^\chi = \frac{1}{4}\sqrt{\frac{\pi\Omega_{h}}{(K_{h}+1)}}L_{1/2}(-K_{h})\sqrt{\frac{\pi\Omega^\chi_{g}}{(K^\chi_{g}+1)}}L_{1/2}(-K^\chi_{g})$ is the expectation value of $|h_m||g^\chi_m|$, and $(\sigma^\chi)^2 = \Omega_h\Omega^\chi_g - (\mu^\chi)^2$ is its variance.
\begin{proof}
According to the central limit theorem, both $H_r$ and $H_t$ follow the normal distribution when $M$ is sufficiently large.
\textcolor{black}{
In the high transmit SNR regime, the outage probabilities in both \eqref{prout} and the successful case of \eqref{ptout} are reduced to $P_{out} = \mathrm{Pr}\{|H_r|/|H_t| < \sqrt{\gamma_r}\}$. According to \eqref{Hr}, $|H_r|$ and $|H_t|$ have common terms and we denote their correlation coefficient as $\rho$. According to \cite{ratio}, the cumulative distribution function (CDF) of the ratio between two correlated normal distributions can be expressed in terms of the error function.}
\end{proof}
\end{theorem}

\begin{remark}
As shown in \eqref{P_high_snr}, the analytical outage probabilities do not further decrease with the increase of the uploading transmit power $p$, this indicates that the outage probabilities of both users approach the same error floor.
\end{remark}

\textcolor{black}{
\begin{remark}
In Theorem~\ref{t3}, we use a normal distribution ($f_{\text{Gaus}}(x)$) to approximate the PDF of $|H_r|$ which the exact distribution ($f_{\text{exact}}(x)$) is the sum of $M$ cascaded Rician channels. The approximation error decreases with the increase of $M$. In the following table, we calcualted the Kullback–Leibler divergence (relative entropy) from $f_{\text{exact}}(x)$ to $f_{\text{Gaus}}(x)$, i.e., $D_{\text{KL}} = \int_{x=-\infty}^\infty f_{\text{Gaus}}(x)\cdot \log\left( \frac{f_{\text{Gaus}}(x)}{f_{\text{exact}}(x)}\right)$. It can be observed that $D_{\text{KL}}$ quickly diminishes after $M\geq 20$.
\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$M$ & 5      & 10     & 15       & 20                  & 25           \\ \hline
$D_{\text{KL}}$  & 4.0877 & 1.4109 & $1.4043$ & $7.2\times 10^{-3}$ & $5.9\times 10^{-3}$ \\ \hline
\end{tabular}
\caption{\textcolor{black}{Kullback–Leibler divergence from the exact distribution to the approximated normal distribution.}}
\label{tab:KL}
\end{table}
\end{remark}
}

\subsection{OMA Baseline}
In OMA, user $t$ and $r$ upload their messages via orthogonal time/frequency resource blocks. In terms of user outage probabilities, the outage probabilities for user $r$ and $t$ in OMA are given as follows:
\begin{align}
    &P^{r/t,\text{O}}_{out} = \mathrm{Pr}\{\mathrm{SNR}^{\text{O}}_{r/t} < 2^{2\Tilde{R}_{r/t}}-1 \}
\end{align}
where $\mathrm{SNR}^\text{O}_{r/t} = {p \big|\sum_{m=1}^M g^{r/t}_m  h_m  e^{j\phi^{R/T}_m}\big|^2}/ {\sigma^2_0}$ is the SNR for OMA. The closed-form analytical outage probabilities for OMA scenario can be obtained similar to those of NOMA scenario. Due to page limitation, we omit these analytical results and demonstrate them in simulations results.

\section{Numerical Results}\label{num}

\begin{figure}[b!]
    \begin{center}
        \includegraphics[scale=0.5]{mac_fig/pattern.eps}
        \caption{Radiation density of the STAR-RIS-aided uplink transmission.}
        \label{pattern}
    \end{center}
\end{figure}

In this section, simulation results are provided to investigate the performance of the STAR-RIS-aided uplink communication. For our simulations, we assume that the STAR-RIS is a uniform planar array consisting of $M$ elements. The spacing between adjacent elements is half of the carrier wavelength.
All STAR-RIS-user channels are modeled as Rician fading channels with path loss exponents of $\alpha = 2.2$ and the Rician factor of $K=1.3$ dB.

\begin{figure}[b!]
    \begin{center}
        \includegraphics[scale=0.5]{mac_fig/out_low_new.eps}
        \caption{\textcolor{black}{Comparing outage probabilities of OMA and NOMA with perfect/imperfect SIC.}}
        \label{op1}
    \end{center}
\end{figure}

In Fig.~\ref{pattern}, the power density is plotted for the considered uplink transmission where two users are located on different sides of the STAR-RIS where $M = 8\times 8$. The transmission power of the users are set to $p = 10$ dBm. The T\&R phase-shift coefficients are configured according to the cophase condition and the amplitudes are equal, i.e., $\beta^R=\beta^T = 1/\sqrt{2}$. It can be observed that the STAR-RIS significantly improves the signal strength at the location of the BS. However, there are still scattered beams on the other side of the STAR-RIS. These beams consist the signal of user $r$ that is transmitted (leaked) through the STAR-RIS and the signal of user $t$ that is reflected back.

In Fig.~\ref{op1}, the outage probabilities for NOMA and OMA are plotted where the target data rate for both users is set at $\tilde{R}_t = \tilde{R}_r = 1.5$ bit/s/Hz. The noise power for both users is set to $\sigma^2_0 = -50$ dBm and the transmit SNR is varied from $0$ to $10$ dB. Moreover, the amplitudes of the transmission coefficients of the elements are set to $\beta^T=0.2$.
By comparing the user outage probability of NOMA and OMA, it can be observed that the dual-sided STAR-RIS-aided uplink NOMA performs mostly better than STAR-RIS-aided OMA for both users. Thus, NOMA is a good candidate to exploit the \textit{STAR} capability of dual-sided STAR-RISs. In addition, for NOMA with imperfect SIC, the outage probability of user $r$ is unaffected while the outage probability of user $t$ is slightly higher than NOMA with perfect SIC. However, due to the presence of the error floor of uplink NOMA, the performance of NOMA starts to saturate after the transmit SNR is high. The dual-sided STAR-RIS is able to further lower this error floor as we will see in the next figure.

\begin{figure}[b!]
    \begin{center}
        \includegraphics[scale=0.5]{mac_fig/out_hight_new.eps}
        \caption{\textcolor{black}{Outage probabilities of NOMA in the high transmit SNR regime.}}
        \label{op2}
    \end{center}
\end{figure}
In Fig.~\ref{op2}, the outage probability error floor is plotted with the simulated outage probabilities for user $t$ and user $r$ employing NOMA.
\textcolor{black}{
In this simulation, we plot the outage probability for the uniform amplitude configuration and for the mode switching (MS) configuration. For the uniform amplitude configuration, the amplitude of the transmission coefficient are set as $0.25$, $0.2$, and $0.15$. For the MS configuration, $25\%$ of the elements are transmitting-only and the remaining elements are reflecting-only.
As can be observed, the MS configuration has the same error floor as the uniform amplitude configuration with $\beta^T = 0.25$. However, the error floor can only be achieved with higher transmit SNR for the MS configuration.
}
Moreover, the error floors for both users can be lowered by adjusting the power ratio between the reflection and transmission for the uniform amplitude configuration.

\section{Conclusions}
In this letter, we provided the hardware model and signal model for the \textit{dual-sided} STAR-RISs.
For the case where the STAR-RIS have surface electric and magnetic impedance, the elements have symmetrical T\&R coefficients.
We derived expressions for the outage probability of a STAR-RIS assisted two-user uplink communication system in high transmit SNR regime. The analytical and numerical results demonstrated the performance gain of NOMA over OMA. It is also revealed that the error floor for the uplink NOMA transmission can be lowered by adjusting the power ratios of STAR elements.

\bibliographystyle{IEEEtran}

\section{Mac Control}
\begin{figure}[h!]
    \begin{center}
        \includegraphics[scale=0.07]{mac_fig/MAC_RIS.jpg}
        \caption{STAR-RIS as a medium access controller for RF resources.}
        \label{sys1}
    \end{center}
\end{figure}
\begin{itemize}
    \item For wireless communications through the RF medium, there is a scarcity of medium access control. In today's communication system, transceivers of different applications shares the same physical transmission medium. Moreover, the medium is only divided into different cells based on physical distances or different frequency bands based on the carrier frequencies and bandwidths. However, due to the increased number or mobile devices, more and more terminals need to be accommodated within the urban area. In the same time, new wireless technologies are emerging which may take up more RF resource, such as RF sensing network for IoT, UAV local networks, and ...\\
    Consequently, there is a increasing need for a medium access controller to mitigate interference and collisions of the wireless channels.
\end{itemize}

\begin{comment}
\begin{figure*}[t!]
\centering
\subfigure[Time-Switching]{\label{sysa}
\includegraphics[width= 2in]{mac_fig/sys_a.eps}}
\subfigure[Unicast]{\label{sysb}
\includegraphics[width= 2in]{mac_fig/sys_b.eps}}
\subfigure[Multicast]{\label{sysc}
\includegraphics[width= 2.2in]{mac_fig/sys_c.eps}}
\caption{Illustration of the working modes of the full-duplex STAR-RISs}\label{nice}
\end{figure*}

As shown in Fig.~\ref{sysa}, for the time-switching double-sided unicast scenario, Tx1 and Tx2 transmit their signals to their corresponding receivers in separate time slots. In the first time slot, Tx1 sends message $s_1$ to Rx1, and the $m$th element is configured to transmit $s_1$ from \textit{Space A} to \textit{Space B} with transmission coefficient $T^{A,B}_m$. Similarly, in the second time slot, $s_2$ is transmitted from \textit{Space B} to \textit{Space A} with transmission coefficient $T^{B,A}_m$. Because $s_1$ and $s_2$ are transmitted in different time slots, $T^{A,B}_m$ and $T^{B,A}_m$ can be independently configured. To sum up, we have the following signal model for STAR-RIS:
\subsubsection*{Case 1}
For the time-switching double-sided unicast scenario, the STAR-RIS elements can be modeled using the following transmission coefficients:
\begin{equation}
    T^{A,B}_m = \beta^{A,B}_m e^{j\phi^{A,B}_m} \text{, and  } T^{B,A}_m = \beta^{B,A}_m e^{j\phi^{B,A}_m},
\end{equation}
where $\beta^{A,B}_m$ and $\beta^{B,A}_m\in [0,1]$ are the amplitudes of the corresponding transmission coefficients, $\phi^{A,B}_m$ and $\phi^{B,A}_m \in[0,2\pi)$ are the phases of the transmission coefficients in time slot 1 and 2, respectively.
\end{comment}

Different from the single source case which have been previously studied, the T\&R coefficients on the two sides of the $m$th element can be defined as follows:
\begin{align}\label{tab1}
    T^{A,B}_m &= ({E}^J+{E}^K_2+{E}^{inc}_1)/{E}^{inc}_1, \\
    T^{B,A}_m &= ({E}^J+{E}^K_1+{E}^{inc}_2)/{E}^{inc}_2, \\
    R^{A}_m &= ({E}^J+{E}^K_1+{E}^{inc}_2)/{E}^{inc}_1, \\ \label{rb1}
    R^{B}_m &= ({E}^J+{E}^K_2+{E}^{inc}_1)/{E}^{inc}_2,
\end{align}
where $E^J = ||\mathbf{E}^J||_2$,  $E^K_1 = ||\mathbf{E}^K_1||_2$, $E^K_2 = ||\mathbf{E}^K_2||_2$, $E^{inc}_1 = ||\mathbf{E}^{inc}_1||_2$, and $E^{inc}_2 = ||\mathbf{E}^{inc}_2||_2$ are the magnitudes of the corresponding electric field at the $m$th element.

\begin{theorem}\label{t1}
Given incident signals on both sides ($E^{inc}_1$ and $E^{inc}_2$), a STAR-RIS element can be modeled using the following coefficients:
\begin{align}\label{tab}
    &T^{A,B}_m = T^0_m + \beta R^0_m,\\ \label{tba}
    &T^{B,A}_m = T^0_m + (1/\beta) R^0_m,\\ \label{ra}
    &R^{A}_m = R^0_m + \beta T^0_m,\\ \label{rb}
    &R^{B}_m = R^0_m + (1/\beta) T^0_m,
\end{align}
where $T^0_m = \frac{2Z_e}{2Z_e+\eta} - \frac{Z_m}{Z_m+2\eta}$, $R^0_m = \frac{Z_m}{Z_m+2\eta}-\frac{\eta}{2Z_e+\eta}$, $\eta$ is the free space wave impedance, and $\beta = E^{inc}_2/E^{inc}_1$ is the ratio between the amplitudes of the incident electric fields.
\begin{proof}
The boundary conditions~\cite{rNGfm99RfAqifzEoqjYY9NPszcDnpChRWu} of EM field at the surface can be expressed as $\hat{z}\times (\mathbf{H}^J_2-\mathbf{H}^J_1)\hat{y} = \mathbf{J}_s\hat{x}$ and $\hat{z}\times(\mathbf{E}^K_1 - \mathbf{E}^K_2)=\mathbf{K}_s\hat{y}$. Next, by considering \eqref{js} and \eqref{ks} with the boundary conditions, $E^J$ and $E^K_1$ in \eqref{tab1}-\eqref{rb1} can be expressed in terms of $Z_e$, $Z_m$, and $\eta$, i.e., we have the following:
\begin{align}\label{tab2}
    &E^J = \frac{-\eta(E^{inc}_1+E^{inc}_2)}{2Z_e+\eta},\\ \label{tab3}
    &E^K_1 = \frac{Z_m(E^{inc}_1-E^{inc}_2))}{Z_m+2\eta}.
\end{align}
Finally, by plugging \eqref{tab2} and \eqref{tab3} into \eqref{tab1}-\eqref{rb1}, the proof is finished.
\end{proof}
\end{theorem}

\begin{remark}
In \eqref{tab}-\eqref{rb}, $T^0_m$ and $R^0_m$ are the T\&R coefficients given a one-sided signal incidence. According to existing studies~\cite{xu_star,liu_star,mu_star}, the phases of $T^0_m$ and $R^0_m$, i.e., $\phi^T_m$ and $\phi^R_m$ can be independently configured while their amplitudes are constrained through the law of energy conservation, namely:
\begin{align}
    |T^0_m|^2+|R^0_m|^2 \leq 1\\
    \phi^T_m,\ \phi^R_m \in [0,2\pi).
\end{align}
For passive lossless STAR-RIS element, $\phi^T_m$ and $\phi^R_m$ are further correlated~\cite{xu_correlated}.
\end{remark}
The physical meaning of these coefficients can be understood through \eqref{tab}-\eqref{rb}: For general cases, $T^{A,B}_m \neq T^{B,A}$, and $R^A_m \neq R^B_m$. This is due to the asymmetric strengths of incident EM waves on the two sides. In the following, we present the signal models for STAR-RISs operating in purely transmitting, purely reflecting, and simultaneous transmitting and reflecting modes.


\section{Introduction}\label{sec:Intro}

\subsection{Brief Literature Review}\label{ssec:11}

Suppose $J : {\mathbb R}^n \rightarrow {\mathbb R}$ is a ${\cal C}^2$ strictly convex function,
and assume without loss of generality that its global minimum is at
${\boldsymbol \theta}^* = {\bf 0}$.
We discuss two types of iterative methods for computing the minimum.
In the first type,
\textit{every component} of the current guess is updated at each time step,
which might be called ``synchronous updating'' for want of a better phrase.
In this highly structured situation, it is possible to analyze the
behavior of the algorithms to great depth
using results from convex analysis.
In the second, the role of measurement errors / noise is explicitly
taken into account, and the analysis is based on stochastic approximation
theory.
In this subsection, we give a brief summary of the relevant literature for
each type of method.
Given that the literature in convex optimization is vast, our review
is quite narrowly focused on the papers that are directly relevant to
the specific class of problems studied here.

Since $J(\cdot)$ is strictly convex, a simple gradient descent algorithm
applied to \textit{error-free} measurements of the gradient
${\bf f}({\boldsymbol \theta}) = - \nabla J({\boldsymbol \theta})$ will converge to ${\boldsymbol \theta}^*$.
Further, momentum-based accelerated algorithms such as those of
Nesterov \cite{Nesterov-Dokl83},
Sutskever et al.\ \cite{Sutskever-et-al-PMLR13},
and Bengio \cite{Bengio-CoRR12} will achieve still faster convergence
compared to steepest descent.
In \cite{Mohammadi-et-al-ACC19}, the performance of these algorithms
is analyzed for the case where the gradients are corrupted by noise.
It is shown that the allowed bound on the noise depends on the condition
number $K$ of the convex function, and that the error bound for momentum-based
methods is larger than that for steepest descent by a factor of $\sqrt{K}$.
Thus the presence of noise in the gradient measurements largely negates the
advantages of momentum-based methods.
Other approaches such as ADAM \cite{Diederik-ADAM-arxiv14} can
also cope with noisy measurements of the gradient.
In \cite{Assran-Rabbat20} the authors study the behaviour of Nesterov's
method when there are errors in the gradient, and demonstrate that
sometimes the method can diverge.
There are other references as well, but these are an indicative sample.

In Deep Neural Networks, computing the gradient $\nabla J(\cdot)$ can
be computationally intensive.
Therefore another approach is to approximate the gradient by
\textit{first-order differences}, and then invoke stochastic
approximation theory initiated in \cite{Robbins-Monro51}.
As proposed in \cite{Kief-Wolf-AOMS52} and improved in \cite{Blum54},
one chooses the index $i$ to be updated, and then computes the quantity
\begin{equation}\label{eq:13}
y_{t+1,i} :=
\frac{ J({\boldsymbol \theta}_t - c_t {\bf e}_i) + \xi^-_{t+1,i}
-  ( J({\boldsymbol \theta}_t + c_t {\bf e}_i) + \xi^+_{t+1,i} } {2 c_t}
\end{equation}
as an approximation to $-[\nabla J({\boldsymbol \theta}_t)]_i$.
Here $c_t$ is called the ``increment,'' and
${\boldsymbol \xi}^-_{t+1}, {\boldsymbol \xi}^+_{t+1}$ are measurement errors that corrupt
in \eqref{eq:13} can be corrupted by noise.
In \cite{Blum54} it is shown that, under suitable conditions,
th sequence of iterations $\{ {\boldsymbol \theta}_t \}$ converges almost surely
to the unique stationary point of $J(\cdot)$.
It is worth noting that the analysis in \cite{Blum54} \textit{does not assume}
that $J(\cdot)$ is convex, only that there is a unique stationary point.
The above approach is sharpened in \cite{Bert-Tsi-SIAM00} to the case
where the function $J(\cdot)$ is not necessarily bounded below,
and/or there are multiple stationary points.
However, the iterations use a noise-corrupted exact gradient,
not an approximate gradient as in \eqref{eq:11}.
Note that computing this approximate gradient
requires either $2n$ \cite{Kief-Wolf-AOMS52} or $n+1$
\cite{Blum54} function evaluations at each iteration.
An alternative that requires just a few function evaluations at each
iteration (perhaps just one evaluation), consists
of choosing a random vector $\phi_t \in {\mathbb R}^n$ at each
iteration, and setting
\begin{equation}\label{eq:11}
\nabla J({\boldsymbol \theta}) \approx \frac{ J({\boldsymbol \theta} + c_t {\boldsymbol \phi}_) - J({\boldsymbol \theta}) }
{c_t} {\boldsymbol \phi} .
\end{equation}
This approach was (apparently) first proposed in \cite{Polyak87},
and studied further in \cite{Spall-TAC92,Nesterov-FCM17}.
In \eqref{eq:11}, the probability distribution of ${\boldsymbol \phi}$
is chosen to ensure that
\textit{every component} is nonzero with probability one.
The analysis in \cite{Nesterov-FCM17} assumes that there are no
measurement errors in computing $J(\cdot)$.
In contrast, the analysis in \cite{Spall-TAC92} follows earlier
approaches of \cite{Kief-Wolf-AOMS52,Blum54}, as in \eqref{eq:13},
in permitting noisy measurements of the function.
Moreover, the convergence analysis is based on stochastic approximation theory.

In all of the above and related papers, \textit{every component}
of the current guess is updated at each time instant.
In recent years, when the dimension $n$ is very large (which it is
in problems of deep learning and deep reinforcement learning),
some researchers have proposed the use of \textbf{coordinate gradient
descent}.
In this approach, at each instant of time $t$, an index $i \in [n]$
is chosen at random (or in some deterministic manner), and \textit{only
the $i$-th component} of ${\boldsymbol \theta}_t$ is updated, using
either the true gradient $\nabla J({\boldsymbol \theta}_t)$, or a noisy version thereof.
See \cite{Wright15} for a good survey, and \cite{Bach-et-al-aisats19}
for further analysis.
It is noteworthy that in all these papers, the measurements of the
gradient are assumed to be error-free.
The update rule can be expressed as
\begin{equation}\label{eq:12}
{\boldsymbol \theta}_{t+1} = {\boldsymbol \theta}_t + \beta_t {\bf e}_i \circ [ - \nabla J({\boldsymbol \theta}_t) + {\boldsymbol \xi}_{t+1} ] ,
\end{equation}
where ${\boldsymbol \xi}_{t+1}$ denotes the measurement error if any,
$\circ$ denotes the Hadamard, or componentwise, product,
${\bf e}_i$ denotes the elementary unit vector in row $i$ and zeros elsewhere,
and $\{ \beta_t \}$ is a predetermined sequence of step sizes.
Observe that, if $i$ assumes each value in $[n]$ with an equal
probability $1/n$, then
\begin{displaymath}
E \left[ {\bf e}_i \circ \nabla J({\boldsymbol \theta}_t) \right]
= \frac{1}{n} \nabla J({\boldsymbol \theta}_t) .
\end{displaymath}
In some circles, this approach is known as ``stochastic gradient descent''
(SGD);
see for example \cite{Wright15,Bach-et-al-aisats19}.
However, if ${\boldsymbol \xi}_t = {\bf 0}$ for all $t$,
then randomness arises only in choosing the index $i$ to be updated,
and everything else is deterministic.
With noise-free measurements, it is possible to carry out very detailed
analysis of the algorithm in \eqref{eq:12}.
Indeed, in \cite{Bach-et-al-aisats19} the analysis encompasses even some
nonconvex functions.

\subsection{Contributions of the Present Paper}\label{ssec:12}

When the dimension $n$ is very large, and only one component of ${\boldsymbol \theta}_t$
is updated at each $t$, then in essence one is trading off
the savings in memory calls against an increase in the number of iterations.
To illustrate, suppose that one wishes that on average, each component of
${\boldsymbol \theta}_t$ is updated $T$ times.
Then, on average, a total of $nT$ iterations would be required.
On the other side, if the entire $n$-dimensional vector is updated at
each $t$, then only $T$ iterations would be required, but at every
iteration an $n$-dimensional vector would have to be updated.
An intermediate approach, which could be called \textbf{Batch Stochastic
Gradient Descent (BSGD)}, would be to update \textit{some but not
necessarily all} components of ${\boldsymbol \theta}_t$ at each time instant.
Specifically, at each instant $t$,
one selects a \textit{set of indices} $S(t) \leq [n]$ to be updated.
If the available data consists of noisy measurements of the gradient,
we define
\begin{equation}\label{eq:15}
{\bf y}_{t+1} = - \nabla J({\boldsymbol \theta}_t) + {\boldsymbol \xi}_{t+1} .
\end{equation}
If the available data consists of approximate gradients based on
noisy function evaluations, then we define ${\bf y}_{t+1}$ as in \eqref{eq:13}.
In either case, the updating rule is
\begin{equation}\label{eq:19}
{\boldsymbol \theta}_{t+1} = {\boldsymbol \theta}_t + \beta_t {\bf e}_{S(t)} \circ {\bf y}_{t+1} ,
\end{equation}
where
\begin{displaymath}
[ {\bf e}_{S(t)} ]_i = \left\{ \begin{array}{ll} 1, & \mbox{if } i \in S(t) , \\
0,  & \mbox{if } i \not\in S(t) . \end{array} \right.
\end{displaymath}
In  component form, the updating rule in \eqref{eq:19} can be expressed as
\begin{equation}\label{eq:110}
\theta_{t+1,j} = \left\{ \begin{array}{ll}
\theta_{t,i} + \beta_t y_{t+1,i},
& \mbox{if } i \in S(t)  , \\
\theta_{t,j}, & \mbox{if } i \not\in S(t) . \end{array} \right.
\end{equation}
The choice of the update set $S(t)$ can be random; more details are given
in subsequent sections.

As mentioned above, previous surveys such as \cite{Wright15,Bach-et-al-aisats19}
study the case where $S(t)$ is a singleton set (possibly random) for each $t$.
The vector ${\bf y}_{t+1}$ can be either the exact gradient of a noise-corrupted
exact gradient.
The case where ${\bf y}_{t+1}$ is defined as in \eqref{eq:13},
and $S(t) = [n]$ for all $t$ (that is, all components are updated at each $t$),
is analyzed in \cite{Blum54}, and a simpler analysis is given in
\cite{MV-GES-SA-arxiv22}.
Attempts to extend either approach to the case of \textit{batch} updating
face two technical challenges:
First, while $-\nabla J({\boldsymbol \theta}_t)$ is always a descent direction, at least locally
near ${\boldsymbol \theta}_t$, batch-sampled gradients of the form
${\bf e}_{S(t)} \circ -\nabla J({\boldsymbol \theta}_t)$ are not descent directions in general.
In the analysis of ``coordinate gradient descent'' (where $|S(t)| = 1$
for all $t$), this difficulty is handled by restricting $J(\cdot)$
to be convex.
The second difficulty is that when $y_{t+1}$ is given by \eqref{eq:13},
we can write
\begin{displaymath}
y_{t+1,i} =
\frac{ J({\boldsymbol \theta}_t - c_t {\bf e}_i)  -  J({\boldsymbol \theta}_t + c_t {\bf e}_i)  } {2 c_t}
+ \frac{\xi^-_{t+1,i} - \xi^+_{t+1,i}  }
{2 c_t} .
\end{displaymath}
Thus, if we let $c_t \rightarrow 0$ as $t \rightarrow \infty$, then variance of the noise term
\textit{approaches infinity}.
To handle this difficulty, we adapt the approach of \cite{MV-GES-SA-arxiv22}
to batch updating.

In addition to the above-mentioned theoretical contributions, we have also
carried out extensive numerical computations to support the theoretical
claims.
We include as many computations as we can, subject to space limitations.

\section{Convergence Theorems for Batch Stochastic Gradient Descent}
\label{sec:Thms}

Throughout, we study strictly convex ${\cal C}^2$ functions $J: {\mathbb R}^n \rightarrow {\mathbb R}$.
By translating coordinates, it can be assumed that the global minimum
occurs at ${\boldsymbol \theta}^* = {\bf 0}$, and $J({\bf 0}) = 0$.
Further, it is assumed that there exist constants $0 < \underline{c} < \bar{c} < \infty$
such that
\begin{equation}\label{eq:21}
\underline{c} I_n \leq \nabla^2 J({\boldsymbol \theta}) \leq \bar{c} I_n ,
\end{equation}
where $I_n$ denotes the $n \times n$ identity matrix, and the notation
$A \leq B$ (when $A, B$ are symmetric matrices) denotes that $B-A$ is
positive semidefinite.

Until now we have not specified how the set $S(t)$ of indices to be updated
is chosen.
For this purpose, we introduce $n$ different
$\{0,1\}$-valued stochastic processes $\{ \kappa_{t,i} \}$ for $t \geq 0$ and
$i \in [n]$.
No assumptions are made regarding the relationship between $\{ \kappa_{t,i} \}$
and $\{ \kappa_{t,j} \}$ for $i \neq j$.
The significance of these processes, which we refer to as the ``update''
processes, is that at time $t$, the $i$-th component of ${\boldsymbol \theta}_t$
is updated if and only if $\kappa_{t,i} = 1$.
For each $t$, define
\begin{displaymath}
S(t) = \{ i \in [n] : \kappa_{t,i} = 1 \} .
\end{displaymath}

Now we state our two main theorems.

\begin{theorem}\label{thm:1}
Let $\{ {\cal F}_t \}$ be any filtration with respect
to which the processes $\{ {\boldsymbol \theta}_t \}$,
$\{ \kappa_{t,i} \}$ and $\{ {\boldsymbol \xi}_t \}$ are adapted.
Suppose the error process $\{ {\boldsymbol \xi}_t \}$ satisfies
\begin{equation}\label{eq:28}
E( {\boldsymbol \xi}_{t+1} | {\cal F}_t ) = 0 \mbox{ a.s.} , \; \forall t \geq 0 ,
\end{equation}
\begin{equation}\label{eq:29}
E( {\boldsymbol \xi}_{t+1}^2 | {\cal F}_t ) \leq d ( 1 + \nmeusq{{\boldsymbol \theta}_t} ) \mbox{ a.s.} , \; \forall t ,
\end{equation}
for some constant $d$.
Suppose $\{ \beta_t \}$ is a deterministic sequence of step sizes satisfying
\begin{equation}\label{eq:210}
\sum_{t=0}^\infty \beta_t^2 < \infty .
\end{equation}
Then the sequence of iterations $\{ {\boldsymbol \theta}_t \}$ is bounded almost surely.
If, in addition, we have
\begin{equation}\label{eq:211}
\sum_{t=0}^\infty \beta_{t,i} = \infty \mbox{ a.s.} , \; \forall i \in [n] ,
\end{equation}
where $\beta_{t,i} := \beta_t I_{ \{ i \in S(t) \} }$,
then ${\boldsymbol \theta}_t \rightarrow {\bf 0}$ almost surely as $t \rightarrow \infty$.
\end{theorem}

\begin{theorem}\label{thm:2}
Suppose \eqref{eq:28} and \eqref{eq:29} hold, and suppose further that
\begin{equation}\label{eq:212}
\sum_{t=0}^\infty \beta_t c_t < \infty ,
\sum_{t=0}^\infty (\beta_t/c_t)^2 < \infty .
\end{equation}
Then the sequence of iterations $\{ {\boldsymbol \theta}_t \}$ is bounded almost surely.
If, in addition, we have
\begin{equation}\label{eq:213}
\sum_{t=0}^\infty \beta_{t,i} = \infty \mbox{ a.s.} , \; \forall i \in [n] ,
\end{equation}
then ${\boldsymbol \theta}_t \rightarrow {\bf 0}$ almost surely as $t \rightarrow \infty$.
\end{theorem}

Note that \eqref{eq:210} and \eqref{eq:211} are analogous to the well-known
Robbins-Monro conditions introduced in \cite{Robbins-Monro51}, adjusted
for random step sizes.
Similarly, \eqref{eq:210} and \eqref{eq:212} are analogous to the
conditions introduced by Blum in \cite{Blum54}.

\section{Proofs}\label{sec:Proofs}

\subsection{Some Preliminaries on Convex Functions}\label{ssec:31}

We begin with a purely technical (and rather obvious)
result that facilitates the proofs.

\begin{lemma}\label{lemma:1}
Suppose $J$ is ${\cal C}^2$ and satisfies \eqref{eq:21}.
Then
\begin{enumerate}
\item[(i)] There exists a ${\cal C}^0$ function $H : {\mathbb R}^n \rightarrow {\mathbb R}^{n \times n}$
such that $H({\boldsymbol \theta})$ is symmetric for all ${\boldsymbol \theta} \in {\mathbb R}^n$, and
\begin{equation}\label{eq:22}
\nabla J({\boldsymbol \theta}) = H({\boldsymbol \theta}) {\boldsymbol \theta} , \; \forall {\boldsymbol \theta} \in {\mathbb R}^n ,
\end{equation}
\begin{equation}\label{eq:23}
\underline{c} I_n \leq H({\boldsymbol \theta}) \leq \bar{c} I_n , \; \forall {\boldsymbol \theta} \in {\mathbb R}^n .
\end{equation}
\item[(ii)] Suppose $S \subseteq [n]$.
Then
\begin{equation}\label{eq:24}
\IP{{\boldsymbol \theta}}{ {\bf e}_S \circ \nabla J({\boldsymbol \theta})} \geq \underline{c} \nmeusq{ {\bf e}_S \circ {\boldsymbol \theta}} ,
\; \forall {\boldsymbol \theta} \in {\mathbb R}^n .
\end{equation}
In particular
\begin{equation}\label{eq:25}
\theta_i [ \nabla J({\boldsymbol \theta})]_i \geq \underline{c} \theta_i^2 , \; \forall i \in [n] , {\boldsymbol \theta} \in {\mathbb R}^n .
\end{equation}
\item[(iii)] We also have that
\begin{equation}\label{eq:26}
\nmeu{\nabla J({\boldsymbol \theta})} \leq \bar{c} \nmeu{{\boldsymbol \theta}}
\end{equation}
\end{enumerate}
\end{lemma}

\begin{proof}
Since $\nabla J({\bf 0}) = {\bf 0}$ (because ${\bf 0}$ is the global minimum of $J(\cdot)$),
we can write
\begin{displaymath}
\nabla J({\boldsymbol \theta}) = \int_0^1 \frac{d}{d \lambda} \nabla J(\lambda {\boldsymbol \theta}) \; d \lambda
= \int_0^1 \nabla^2 J(\lambda {\boldsymbol \theta}) {\boldsymbol \theta} \; d \lambda .
\end{displaymath}
Hence \eqref{eq:22} holds with
\begin{displaymath}
H({\boldsymbol \theta}) = \int_0^1 \nabla^2 J(\lambda {\boldsymbol \theta}) \; d \lambda .
\end{displaymath}
Therefore
\begin{displaymath}
H({\boldsymbol \theta}) - \underline{c} I_n = \int_0^1 [ \nabla^2 J(\lambda {\boldsymbol \theta}) - \underline{c} I_n ] \; d \lambda
\geq 0 .
\end{displaymath}
The proof that $H({\boldsymbol \theta}) \leq \bar{c} I_n$ is similar.
To prove \eqref{eq:24}, rearrange indices and partition so that
\begin{displaymath}
{\bf e}_S \circ {\boldsymbol \theta} = \left[ \begin{array}{cc} {\boldsymbol \theta}_1 \\ {\bf 0} \end{array} \right] ,
H({\boldsymbol \theta}) = \left[ \begin{array}{cc} H_{11}({\boldsymbol \theta}) & H_{12}({\boldsymbol \theta}) \\
H_{21}({\boldsymbol \theta}) & H_{22}({\boldsymbol \theta}) \end{array} \right] .
\end{displaymath}
Then
\begin{eqnarray*}
\IP{{\boldsymbol \theta}}{ {\bf e}_S \circ \nabla J({\boldsymbol \theta})}
& = & \IP{{\bf e}_S \circ {\boldsymbol \theta}}{ {\bf e}_S \circ \nabla J({\boldsymbol \theta})} \\
& = & [ \begin{array}{cc} {\boldsymbol \theta}_1^\top & {\bf 0} \end{array} ]
\left[ \begin{array}{c} H_{11}({\boldsymbol \theta}) {\boldsymbol \theta}_1 \\ H_{21}({\boldsymbol \theta}) {\boldsymbol \theta}_1 \end{array} \right] \\
& = & {\boldsymbol \theta}_1^\top H_{11}({\boldsymbol \theta}) {\boldsymbol \theta}_1 \geq \underline{c} \nmeusq{{\boldsymbol \theta}_1}
= \underline{c} \nmeusq{ {\bf e}_S \circ {\boldsymbol \theta}} ,
\end{eqnarray*}
where the last step follows from the fact that $H_{11}({\boldsymbol \theta})$ is
a principal submatrix of $H({\boldsymbol \theta})$, and $H({\boldsymbol \theta}) \geq \underline{c} I_n$.
Now \eqref{eq:25} follows by choosing $S = \{ i \}$.
Finally, \eqref{eq:26} is a consequence of the right inequality in
\eqref{eq:23}.
\end{proof}

\subsection{Proof of Theorem \ref{thm:1}}

Our proof is based on the ``almost supermartingale lemma'' of Robbins \&
Siegmund \cite[Theorem 1]{Robb-Sieg71}.
That paper is rather difficult to locate, but a summary of it is also
found in a recent survey paper as \cite[Lemma 4.1]{Fran-Gram22}.
The result states the following:
\begin{lemma}\label{lemma:2}
Suppose $\{ z_t \} , \{ \delta_t \} , \{ \gamma_t \} , \{ \psi_t \}$ are
stochastic processes taking values in $[0,\infty)$, adapted to some
filtration $\{ {\cal F}_t \}$, satisfying
\begin{equation}\label{eq:27}
E(z_{t+1} | {\cal F}_t ) \leq (1 + \delta_t) z_t + \gamma_t - \psi_t \mbox{ a.s.}, \; \forall t .
\end{equation}
Define
\begin{equation}\label{eq:27a}
\Omega_0 := \{ \omega : \sum_{t=0}^\infty \delta_t(\omega) < \infty \}
\cap \{ \omega : \sum_{t=0}^\infty \gamma_t(\omega) < \infty \} .
\end{equation}
Then for all $\omega \in \Omega_0$, $\lim_{t \rightarrow \infty} z_t(\omega)$ exists, and in addition,
\begin{equation}\label{eq:27b}
\sum_{t=0}^\infty \psi_t(\omega) < \infty , \; \forall \omega \in \Omega_0 .
\end{equation}
In particular, if $P(\Omega_0) = 1$, then $\{ z_t \}$ is bounded almost surely.
\end{lemma}

\begin{proof}
First it is shown that, when \eqref{eq:210} holds, then $\{ {\boldsymbol \theta}_t \}$
is bounded almost surely.
We have from \eqref{eq:19}, \eqref{eq:28} and \eqref{eq:29} that
\begin{eqnarray*}
E( \nmeusq{{\boldsymbol \theta}_{t+1}} | {\cal F}_t )
& = & \nmeusq{{\boldsymbol \theta}_t} + \beta_t^2 \nmeusq{ {\bf e}_{S(t)} \circ \nabla J({\boldsymbol \theta}_t)} \\
& + & \beta_t^2 E( \nmeusq{{\boldsymbol \xi}_{t+1}} | {\cal F}_t ) \\
& - & 2 \beta_t \IP{ {\boldsymbol \theta}_t }{ {\bf e}_{S(t)} \circ \nabla J({\boldsymbol \theta}_t) } \\
& \leq & \nmeusq{{\boldsymbol \theta}_t} + \beta_t^2 [ \bar{c}^2 \nmeusq{{\boldsymbol \theta}_t}
+ d ( 1 + \nmeusq{{\boldsymbol \theta}_t} ) ] ,
\end{eqnarray*}
because
\begin{displaymath}
\IP{ {\boldsymbol \theta}_t }{ {\bf e}_{S(t)} \circ \nabla J({\boldsymbol \theta}_t) } \geq 0 .
\end{displaymath}
Now by Lemma \ref{lemma:2}, whenever \eqref{eq:210} holds, it follows that
$\nmeu{ {\boldsymbol \theta}_t }$ is bounded almost surely.
Define
\begin{displaymath}
\Omega_0 := \{ \omega : \sup_t \nmeu{ {\boldsymbol \theta}_t } < \infty \},
\end{displaymath}
and observe that $P(\Omega_0) = 1$.

Next, we analyze $\theta_{t+1,i}^2$ for each index $i \in [n]$.
We have, from the update rule \eqref{eq:110}, that
\begin{eqnarray*}
E( \theta_{t+1,i}^2 | {\cal F}_t )
& = & \theta_{t,i}^2 + \beta_{t,i}^2 [ \nabla J({\boldsymbol \theta}_t) ]_i^2 \\
& + & E( \xi_{t+1,i}^2 | {\cal F}_t )
- 2 \beta_{t,i} \theta_{t,i} [ \nabla J({\boldsymbol \theta}_t) ]_i \\
& \leq & \theta_{t,i}^2
+ \beta_{t,i}^2 [ \bar{c}^2 \nmeusq{{\boldsymbol \theta}_t} + d (1 + \nmeusq{{\boldsymbol \theta}_t}) ] \\
& - & 2\underline{c} \beta_{t,i} \theta_{t,i}^2 .
\end{eqnarray*}
Here we use \eqref{eq:24} and \eqref{eq:22}.
Now apply Lemma \ref{lemma:2} with
\begin{displaymath}
z_t = \theta_{t,i}^2 , \delta_t = 0 ,
\gamma_t = \beta_{t,i}^2 [ \bar{c}^2 \nmeusq{{\boldsymbol \theta}_t} + d (1 + \nmeusq{{\boldsymbol \theta}_t}) ] ,
\end{displaymath}
\begin{displaymath}
\psi_t = 2\underline{c} \beta_{t,i} \theta_{t,i}^2 .
\end{displaymath}
The summability of $\{ \delta_t \}$ is obvious.
As for $\{ \gamma_t \}$, observe that
\begin{eqnarray*}
\sum_{t=0}^\infty \gamma_t & = &
\sum_{t=0}^\infty \beta_{t,i}^2 [ \bar{c}^2 \nmeusq{{\boldsymbol \theta}_t}
+ d (1 + \nmeusq{{\boldsymbol \theta}_t}) ] \\
& \leq & \left( \sum_{t=0}^\infty \beta_t^2 \right)
\left( d + (\bar{c}^2 + d) \sup_t \nmeusq{{\boldsymbol \theta}_t (\omega) } \right) \\
& < &  \infty, \; \forall \omega \in \Omega_0 .
\end{eqnarray*}
Define
\begin{displaymath}
\Omega_1 := \{ \omega \in \Omega : \sum_{t=0}^\infty \beta_{t,i}(\omega) = \infty ,
\; \forall i \in [n] \} ,
\end{displaymath}
and observe that $P(\Omega_1) = 1$ due to  \eqref{eq:211}.
Then, for $\omega \in \Omega_0 \cap \Omega_1$, Lemma \ref{lemma:2} gives us
that there exists a $\eta_i(\omega) \geq 0$
such that $\theta_{t,i}^2(\omega) \rightarrow \eta_i(\omega)$ as $t \rightarrow \infty$, and
\begin{displaymath}
\sum_{t=0}^\infty \beta_{t,i}(\omega) \theta_{t,i}^2 (\omega) < \infty .
\end{displaymath}
Now suppose by way of contradiction that there exists an
$\omega^* \in \Omega_0 \cap \Omega_1$ such that $\eta_i(\omega^*) \geq 2 \epsilon > 0$.
Pick a finite $T = T_i$ such that $\theta_{t,i}^2(\omega) > \epsilon$ for all $t \geq T$.
Then
\begin{displaymath}
\sum_{t=T}^\infty \beta_{t,i}(\omega) \theta_{t,i}^2 (\omega)
\geq \epsilon \sum_{t=T}^\infty \beta_{t,i}(\omega) = \infty ,
\end{displaymath}
which is a contradiction.
Hence no such $\omega^*$ exists, and $\theta_{t,i}^2 \rightarrow 0$ for all
$\omega \in \Omega_0 \cap \Omega_1$.
The proof is concluded by observing that $P(\Omega_0 \cap \Omega_1) = 1$.
\end{proof}

\subsection{Proof of Theorem \ref{thm:2}}

The proof of Theorem \ref{thm:2} draws upon the approach put forth
in \cite{MV-GES-SA-arxiv22}, which is considerably simpler than that
in \cite{Blum54}.

\begin{proof}
Recall that $y_{t+1,i}$ as defined in \eqref{eq:13} can be equivalently
rewritten as
\begin{displaymath}
y_{t+1,i} =
\frac{ J({\boldsymbol \theta}_t - c_t {\bf e}_i)  -  J({\boldsymbol \theta}_t + c_t {\bf e}_i)  } {2 c_t}
+ \frac{\xi^-_{t+1,i} - \xi^+_{t+1,i}  }
{2 c_t} .
\end{displaymath}
Let us examine the first term.
Using Taylor's theorem, one can conclude that
\begin{displaymath}
y_{t+1,i}
= - [\nabla J({\boldsymbol \theta})]_i + 2 [ \nabla^2 J({\boldsymbol \theta} + \lambda_i {\bf e}_i)]_{ii} c_t ,
\end{displaymath}
for some $\lambda_i \in [-1,1]$.
Hence we can write $y_{t+1,i}$ of \eqref{eq:13} as
\begin{equation}\label{eq:30}
y_{t+1,i} = - [\nabla J({\boldsymbol \theta}_t)]_i + c_t r_{t,i} + \frac{1}{c_t} \xi_{t+1,i} ,
\end{equation}
so  that
\begin{equation}\label{eq:31}
{\bf y}_{t+1} = - \nabla J({\boldsymbol \theta}_t) + c_t {\bf r}_t + \frac{1}{c_t} {\boldsymbol \xi}_{t+1,i} ,
\end{equation}
where ${\boldsymbol \xi}_{t+1} = ( {\boldsymbol \xi}^-_{t+1} - {\boldsymbol \xi}^+_{t+1})/2$, and
\begin{displaymath}
r_{t,i} = 2 [ \nabla^2 J({\boldsymbol \theta} + \lambda_i {\bf e}_i)]_{ii} .
\end{displaymath}
Though ${\bf r}_t$ is random (because ${\boldsymbol \theta}_t$ is random),
the upper bound in \eqref{eq:21} guarantees that
\begin{displaymath}
| r_{t,i} | \leq 2 \bar{c} , \; \forall t .
\end{displaymath}
(Here we use the fact that for any matrix $A$, we have that
$A_{ii} \leq \nmS{A}$ for all $i \in [d]$, where $\nmS{\cdot}$ denotes
the spectral norm.)
Consequently $\nmeu{{\bf r}_t} \leq 2 \sqrt{n} \bar{c} =: M_0$, for all $t$.

Now let analyze the recursion \eqref{eq:110},
using the hypotheses \eqref{eq:28} and \eqref{eq:29}.
This gives
\begin{eqnarray*}
\nmeusq{{\boldsymbol \theta}_{t+1}} & = & \nmeusq{{\boldsymbol \theta}_t + \beta_t {\bf e}_{S(t)} \circ {\bf y}_{t+1}} \\
& = & \Vert {\boldsymbol \theta}_t + {\bf e}_{S(t)} \circ [ - \beta_t \nabla J({\boldsymbol \theta}_t) \\
& + & \beta_t c_t {\bf r}_t + (\beta_t/c_t) {\boldsymbol \xi}_{t+1} \Vert_2^2 .
\end{eqnarray*}
If we expand the Euclidean norm squared on the right side, we get
four square terms and six cross product terms.
Out of these six cross product terms, three become zero due to \eqref{eq:28}.
The conditional expectation of the remaining seven terms can be bounded using
\eqref{eq:29}, and the following bounds:
\begin{displaymath}
\nmeu{{\bf r}_t} \leq M_0 ,
\nmeu{\nabla J({\boldsymbol \theta}_t)} \leq \bar{c} \nmeu{{\boldsymbol \theta}_t} ,
\end{displaymath}
\begin{displaymath}
\IP{{\boldsymbol \theta}_t}{{\bf e}_{S(t)} \circ \nabla J({\boldsymbol \theta}_t)} \geq
\underline{c} \nmeusq{{\bf e}_{S(t)} \circ {\boldsymbol \theta}_t} .
\end{displaymath}
These substitutions lead to the following complicated expression which
we will simplify in stages.
\begin{eqnarray}
E( \nmeusq{{\boldsymbol \theta}_{t+1}} | {\cal F}_t ) & \leq &
\nmeusq{{\boldsymbol \theta}_t} [ 1 + \beta_t^2 \bar{c}^2 + (\beta_t/c_t)^2 d ] \nonumber \\
& + & \beta_t^2 c_t^2 M_0^2 + (\beta_t/c_t)^2 d \nonumber \\
& + & 2 \nmeu{{\boldsymbol \theta}_t} ( \beta_t c_t M_0 + \beta_t^2 c_t \bar{c} M_0 )
\nonumber \\
& - & 2 \beta_t \IP{{\boldsymbol \theta}_t}{{\bf e}_{S(t)} \circ \nabla J({\boldsymbol \theta}_t)} . \label{eq:32}
\end{eqnarray}
On the right side,
there are constant terms, linear terms, and quadratic terms in $\nmeu{{\boldsymbol \theta}_t}$.
To make things uniform,
we replace $\nmeu{{\boldsymbol \theta}_t}$ by its upper bound\footnote{Actually
$\nmeu{{\boldsymbol \theta}_t} \leq (1+\nmeusq{{\boldsymbol \theta}_t})/2$.
However, we drop the factor $2$ to keep the formulas less cluttered.}
$1 + \nmeusq{{\boldsymbol \theta}_t}$,
and $\beta_t \IP{{\boldsymbol \theta}_t}{{\bf e}_{S(t)} \circ \nabla J({\boldsymbol \theta}_t)} $ by its lower bound
$\beta_t \underline{c} \nmeusq{{\bf e}_{S(t)} \circ {\boldsymbol \theta}_t}$.
This gives
\begin{equation}\label{eq:32a}
E( \nmeusq{{\boldsymbol \theta}_{t+1}} | {\cal F}_t ) \leq \nmeusq{{\boldsymbol \theta}_t} ( 1 + p_{t,1}) + p_{t,2}
- 2 \beta_t \underline{c} \nmeusq{{\bf e}_{S(t)} \circ {\boldsymbol \theta}_t} ,
\end{equation}
where
\begin{displaymath}
p_{t,1} = \beta_t^2 \bar{c}^2
+ 2 ( \beta_t c_t M_0 + \beta_t^2 c_t \bar{c} M_0 ) + (\beta_t/c_t)^2 d ,
\end{displaymath}
\begin{displaymath}
p_{t,2} = 2 ( \beta_t c_t M_0 + \beta_t^2 c_t \bar{c} M_0 ) + \beta_t^2 c_t^2 M_0^2 .
\end{displaymath}
Define $p_t = \max \{ p_{t,1},p_{t,2} \}$.
Then we can replace \eqref{eq:32a} by
\begin{equation}\label{eq:33}
E( \nmeusq{{\boldsymbol \theta}_{t+1}} | {\cal F}_t ) \leq \nmeusq{{\boldsymbol \theta}_t} ( 1 + p_t) + p_t
- 2 \beta_t \underline{c} \nmeusq{{\bf e}_{S(t)} \circ {\boldsymbol \theta}_t} .
\end{equation}

To show that $\nmeu{{\boldsymbol \theta}_t}$ is bounded almost surely, we neglect
the term $- 2 \beta_t \underline{c} \nmeusq{{\bf e}_{S(t)} \circ {\boldsymbol \theta}_t}$, leading to
\begin{displaymath}
E( \nmeusq{{\boldsymbol \theta}_{t+1}} | {\cal F}_t ) \leq \nmeusq{{\boldsymbol \theta}_t} ( 1 + p_t) + p_t .
\end{displaymath}
So if we can establish that $\{ p_t \}$ is summable, then the
desired conclusion would follow from Lemma \ref{lemma:2}.
Recall the two hypotheses from \eqref{eq:212}, namely
\begin{displaymath}
\sum_{t=0}^\infty \beta_t c_t < \infty ,
\sum_{t=0}^\infty (\beta_t/c_t)^2 < \infty .
\end{displaymath}
So, if $\{ \beta_t c_t \}$ is summable, then it is also square-summable.
Moreover, since $\beta_t$ is bounded, the sequence $\{ \beta_t^2 c_t \}$
is also summable.
With these observations, we see that every term in  the definitions of
$p_{t,1}$ and $p_{t,2}$ is summable, whence so is $p_{t,i}$.
Therefore $\nmeu{{\boldsymbol \theta}_t}$ is bounded almost surely when \eqref{eq:212} holds.

Next, it  is shown that ${\boldsymbol \theta}_t \rightarrow {\bf 0}$ almost surely as $t \rightarrow \infty$ if,
in addition, \eqref{eq:213} holds.
For this purpose, we write out the update rule componentwise using
\eqref{eq:30}, namely
\begin{displaymath}
\theta_{t+1,i} = \theta_{t,i} - \beta_{t,i} [ \nabla J({\boldsymbol \theta})]_i + \beta_{t,i} c_t r_{t,i}
+ (\beta_{t,i}/c_t) \xi_{t+1,i} .
\end{displaymath}
Therefore
\begin{eqnarray}
E( \theta_{t+1,i}^2 | {\cal F}_t ) & \leq & \theta_{t,i}^2 + \beta_{t,i}^2 \bar{c}^2
\nmeusq{{\boldsymbol \theta}_t} \\
& + &\beta_{t,i}^2 c_t^2 M_0^2 \nonumber \\
& + & (\beta_{t,i}/c_t)^2 d (1 + \nmeusq{{\boldsymbol \theta}_t} )
\nonumber \\
& + & \beta_{t,i} c_t M_0 | \theta_{t,i} | + \beta_{t,i}^2 c_t \nmeu{{\boldsymbol \theta}_t}
\nonumber \\
& - & 2 \beta_{t,i} \underline{c} \theta_{t,i}^2 . \label{eq:33}
\end{eqnarray}
Since $\beta_{t,i}$ either equals $\beta_t$ or $0$, we can replace
\eqref{eq:33} by
\begin{eqnarray*}
E( \theta_{t+1,i}^2 | {\cal F}_t ) & \leq & \theta_{t,i}^2 + \beta_t^2 \bar{c}^2 \nmeusq{{\boldsymbol \theta}_t}
+ \beta_t^2 c_t^2 M_0^2 \\
& + & (\beta_t/c_t)^2 d (1 + \nmeusq{{\boldsymbol \theta}_t} )
\nonumber \\
& + & \beta_t c_t M_0 | \theta_{t,i} | + \beta_t^2 c_t \nmeu{{\boldsymbol \theta}_t}
- 2 \beta_{t,i} \underline{c} \theta_{t,i}^2 .
\end{eqnarray*}
Define
\begin{displaymath}
\Omega_0 := \{ \omega : \sup_t \nmeu{{\boldsymbol \theta}_t(\omega)} < \infty \} ,
\end{displaymath}
and observe that $P(\Omega_0) = 1$.
Now apply Lemma \ref{lemma:2} with
\begin{displaymath}
z_t = \theta_t^2 , \delta_t = 0 ,
\psi_t = 2 \beta_{t,i} \underline{c} \theta_{t,i}^2 ,
\end{displaymath}
\begin{eqnarray*}
\gamma_t & = & \beta_t^2 \bar{c}^2 \nmeusq{{\boldsymbol \theta}_t}
+ \beta_t^2 c_t^2 M_0^2 + (\beta_t/c_t)^2 d (1 + \nmeusq{{\boldsymbol \theta}_t} ) \\
& + & \beta_t c_t M_0 | \theta_{t,i} | + \beta_t^2 c_t \nmeu{{\boldsymbol \theta}_t} ,
\end{eqnarray*}
So long as $\omega \in \Omega_0$, all of these sequences are bounded.
Next, as before, define
\begin{displaymath}
\Omega_1 := \{ \omega \in \Omega : \sum_{t=0}^\infty \beta_{t,i}(\omega) = \infty ,
\; \forall i \in [n] \} ,
\end{displaymath}
Then, for $\omega \in \Omega_0 \cap \Omega_1$, we have that there exists an
$\eta_i$ such that $\theta_{t,i}^2(\omega) \rightarrow \eta_i(\omega)$ as $t \rightarrow \infty$, and
\begin{displaymath}
\sum_{t=0}^\infty \beta_{t,i} \theta_{t,i}^2 < \infty .
\end{displaymath}
As before, this implies that $\eta_i(\omega) = 0$ for all
$\omega \in \Omega_0 \cap \Omega_1$.
\end{proof}

\section{Computational Results}\label{sec:comp}

To validate the theory, we have conducted the following numerical experiment:
We set $J({\boldsymbol \theta}) = {\boldsymbol \theta}^\top A {\boldsymbol \theta}$, where $A$ is a $1,000 \times 1,000$
positive definite matrix with a condition number of 100, whose eigenvectors
are \textit{not} aligned closely with the elementary basis vectors;
that is, $A$ is far from being a diagonal matrix.
The computations were conducted in \textit{python} using NumPy and PyTorch
(for GPU Acceleration) libraries.
BSGD was implemented using approximate gradients with noisy
function valuations.
The conditions in \eqref{eq:212} (Blum's conditions) were satisfied by
choosing
\begin{displaymath}
c_t = \frac{c_0}{(1+(t/\tau))^q} , \beta_t = \frac{\beta_0}{(1+(t/\tau))^p}  ,
\end{displaymath}
where $\tau$ controls the rate of decay with respect to $t$.
To satisfy \eqref{eq:212}, the exponents $p,q$ must satisfy the conditions
\begin{displaymath}
p \leq 1 , p + q > 1 , p - q > 0.5 .
\end{displaymath}
Here we chose $\tau = 200$, $c_0 = 0.1, \beta_0 = 0.01$,
$p = 1, q = 0.02$.
To implement BSGD, we chose the processes $\kappa_{t,i}$ to be independent
binary random variables with $\Pr \{ \kappa_{t,i} = 1 \} = \rho$
for all $t,i$.
The ``rate'' $\rho$ was assigned various values to measure performance.
The noise was additive white Gaussian noise with various SNR.
The source code for the implementation is available
here.{\footnote{https://www.github.com/TUdayKiranReddy/BSGD}

Figure \ref{fig:1} shows that when measurements are noise-free,
and $\rho = 0.2$, that is, at each time instant, an averge of 20\%
of the components are updated.
All momentum-based methods converge, which is not surprising in view of
\cite{Nesterov-FCM17} (though in that paper \textit{all} components are updated
at each time).
BSGD also converges, albeit more slowly.
The surprise is that at a SNR of just 50db, all momentum-based methods
diverge.
\begin{figure}[h]
\begin{center}
\includegraphics[width=145mm]{asynchronous_comparisons_all_50dB}
\end{center}
\caption{Comparison of Momentum-Based Methods and BSGD
with no noise and with SNR = 50 dB.}
\label{fig:1}
\end{figure}

Figure \ref{fig:2} shows the convergence of BSGD with various values of
the rate $\rho$, ranging from $0.05$ to $0.20$.
Even with a fairly high SNR of 50dB, BSGD converged for all values of
$\rho$ studied.
\begin{figure}[h]
\begin{center}
\includegraphics[width=145mm]{bsgd_50db}
\end{center}
\caption{Convergence of BSGD at Various Rates $\rho$
with no noise and with SNR = 50 dB.}
\label{fig:2}
\end{figure}

In the final experiment, we compared BSGD with a constant increment
$c_t = 0.1$ for all $t$.
As expected, with a constant increment the iterations did not converge,
but oscillated.
In contrast, BSGD converged, at both 10dB noise and 20dB noise.
The results are shown in Figure \ref{fig:3}.
\begin{figure}[h]
\begin{center}
\includegraphics[width=145mm]{constant_v_blum_together}
\end{center}
\caption{Comparison of BSGD and Constant Step Size
with SNR = 10 dB and SNR = 20 dB.}
\label{fig:3}
\end{figure}

\section{Conclusions}\label{sec:Conc}

In this paper, we have introduced a very general class of Batch Stochastic
Gradient Desdent (BSGD) algorithms which include most existing stochastic
gradient methods as special cases.
The update direction can either be a noisy measurement of the exact
gradient, or a first-order approximation to the gradient based on
noisy function measurements.
The convergence of BSGD is established in both cases using stochastic
approximation theory.
Numerical experiments show that when as little as 5\% of the coordinates
are updated at each iteration, and approximate gradients are used, BSGD
still converges, while batch momentum-based convex optimization methods
diverge at quite low noise levels.
However, when noise-corrupted exact gradients are used, both BSGD
and batch momentum-based methods converge.
Existing theory of momentum-based algorithms does not apply to the
case of batch updating.
Hence this is a suitable topic for further research.

\input{ACC-Convex.bbl}

\end{document}