A.5: Assume the Hessian of \(\psi \)  is Lipschitz, i.e., there exists \(L_{\psi } > 0\)  such that:

\(\Vert \nabla ^{2}\psi (y) - \nabla ^2\psi (x)\Vert  \le L_{\psi } \Vert y-x\Vert  \quad \forall x,y \in \mathbb {R}^{n}.\) 
Concrete examples of functions satisfying Assumption REF  are given in Section . If Assumption REF [A.5] holds, then we have:

\(|\psi (y) - \psi (x) - \langle \nabla \psi (x),y-x\rangle - \dfrac{1}{2}\langle \nabla ^2 \psi (x)(y-x),y-x\rangle | \le \dfrac{L_{\psi }}{6} \Vert y-x\Vert ^3 \quad \forall x,y \in \mathbb {R}^{n}.\) 
If Assumptions REF  and REF  hold, in order to ensure descent in function values for algorithm RCGD, \(H_{F_{k}}\)  can be computed as follows:
Stepsize Choice 1:1.  Choose \(H_{f,U_{i_k}}> \dfrac{L_{i_{k}}}{2}\)  and compute \(\alpha _{k}\)  as the positive root of second order equation in \(\alpha \) :

\(\dfrac{L_{\psi }}{6} \alpha ^{2} + \left( \dfrac{H_{\psi }}{2} \Vert x_{k}\Vert ^{p} + H_{f,U_{i_k}}\right) \alpha - \Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert  = 0. \vspace*{-5.69046pt}\) 
2.  Define

\(H_{F_{k}}= \frac{H_{\psi }}{2}\Vert x_{k}\Vert ^p + \frac{L_{\psi }}{6} \alpha _{k} + H_{f,U_{i_k}}. \vspace*{-5.69046pt}\) 

We can easily see that there exists a root \(\alpha _{k} \ge 0\)  satisfying the second order equation (REF ). Hence, \(H_{F_{k}}\)  is well-defined. Note that from (REF ), we have:
\(\left(\dfrac{L_{\psi }}{6} \alpha _{k} + \dfrac{H_{\psi }}{2} \Vert x_{k}\Vert ^{p} + H_{f,U_{i_k}}\right) \alpha _{k} = \Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert .\) 
From (REF ), we further get:

\(\Vert d_{k}\Vert  = \dfrac{1}{H_{F_{k}}}\Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert  = \dfrac{\Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert }{\frac{H_{\psi }}{2}\Vert x_{k}\Vert ^p + \frac{L_{\psi }}{6} \alpha _{k} + H_{f,U_{i_k}}} = \alpha _{k}. \) 
If Assumptions REF  and REF  hold and \(H_{F_{k}}\)  is updated as in Stepsize Choice 1, then the iterates of algorithm RCGD satisfy the descent:
\(\mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \le F(x_{k}) - \dfrac{\eta _{\min }}{2} \mathbb {E}[\Vert d_{k}\Vert ^2 \ | \ x_{k}].\) 
From Assumption REF [A.5], we have:

\(\psi (x_{k+1}) \le \psi (x_{k}) + \langle \nabla \psi (x_{k}),U_{i_{k}}d_{k}\rangle + \dfrac{1}{2}\langle \nabla ^2 \psi (x_{k})U_{i_{k}}d_{k},U_{i_{k}}d_{k}\rangle + \dfrac{L_{\psi }}{6} \Vert d_{k}\Vert ^3.\) 
Combining the previous inequality with (REF ), we obtain:

\(&&f(x_{k+1}) + \psi (x_{k+1}) \le f(x_{k}) + \langle \nabla f(x_{k}), U_{i_k}d_{k} \rangle + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \psi (x_{k+1}) \\&&\le f(x_{k}) + \langle U_{i_{k}}^{T}\nabla F(x_{k}), d_{k} \rangle + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \psi (x_{k}) + \dfrac{1}{2}\langle U_{i_{k}}^{T}\nabla ^2 \psi (x_{k})U_{i_{k}}d_{k},d_{k}\rangle + \dfrac{L_{\psi }}{6} \Vert d_{k}\Vert ^3.\) 
Further, from (REF ), we have:

\(&& F(x_{k+1}) \nonumber \\&& \le F(x_{k}) - H_{F_{k}}\Vert d_{k}\Vert ^{2} + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \dfrac{1}{2}\langle U_{i_{k}}^{T}\nabla ^2 \psi (x_{k})U_{i_{k}}d_{k},d_{k}\rangle + \dfrac{L_{\psi }}{6} \Vert d_{k}\Vert ^3  \\&& \le F(x_{k}) - H_{F_{k}}\Vert d_{k}\Vert ^{2} + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \dfrac{1}{2} \Vert U_{i_{k}}^{T}\nabla ^2 \psi (x_{k})U_{i_{k}}\Vert  \Vert d_{k}\Vert ^2 + \dfrac{L_{\psi }}{6} \Vert d_{k}\Vert ^3. \nonumber \) 
From Assumption REF [A.4], we obtain:

\(F(x_{k+1}) \le F(x_{k}) - H_{F_{k}}\Vert d_{k}\Vert ^{2} + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \dfrac{H_{\psi }}{2} \Vert  x_{k}\Vert ^p \Vert d_{k}\Vert ^2 + \dfrac{L_{\psi }}{6} \Vert d_{k}\Vert ^3.\vspace*{-2.84544pt}\) 
From (REF ) and (REF ), we have \(H_{F_{k}}= \frac{L_{\psi }}{6} \Vert d_{k}\Vert  + \frac{H_{\psi }}{2} \Vert x_{k}\Vert ^{p} + H_{f,U_{i_k}}\) . Then, from (REF ) and (REF ), we get:

\(F(x_{k+1}) \le F(x_{k}) - \left( H_{f,U_{i_k}}- \frac{L_{i_{k}}}{2}\right) \Vert d_{k}\Vert ^2 \le F(x_{k}) - \frac{\eta _{\min }}{2} \Vert d_{k}\Vert ^2. \) 
Taking expectation in the previous inequality w.r.t. \(x_{k}\) , the lemma is proved.
Note that from (REF ), we have:

\(\frac{\eta _{\min }}{2} \sum _{j = 0}^{k} \Vert d_{j}\Vert ^2\le \sum _{j = 0}^{k} F(x_{j}) - F(x_{j+1}) \le F(x_{0}) - F^{*} < \infty .\vspace*{-2.84544pt}\) 
This implies that \(\Vert d_{j}\Vert  \rightarrow 0\)  as \(j\rightarrow \infty \) . Hence, there exists \(B_{1} > 0\)  such that:

\(\Vert d_{k}\Vert  \le B_{1} \quad \forall k \ge 0. \vspace*{-1.42271pt}\) 
In order to prove next lemma, we assume that the sequence \((x_{k})_{k\ge 0}\)  generated by RCGD algorithm is bounded, i.e., there exists \(B_{2} > 0\)  such that:

\(\Vert x_{k}\Vert  \le B_{2} \quad \forall k \ge 0. \vspace*{-1.42271pt}\) 
Let assumptions of Lemma REF  hold. Additionally, let the sequence \((x_{k})_{k\ge 0}\)  generated by algorithm RCGD be bounded. Then, the following descent holds:

\(\mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \le F(x_{k}) - \dfrac{\eta _{\min }}{2N (\frac{H_{\psi }}{2}B_2^p + \frac{L_{\psi }}{6} B_1 + H_{f,\max })^2} \Vert \nabla F(x_{k})\Vert ^2 .\) 
From Lemma REF  and (REF ), we have:

\(\mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \le F(x_{k}) - \dfrac{\eta _{\min }}{2} \mathbb {E}\left[\frac{1}{H_{F_{k}}^2}\Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert ^2 \ | \ x_{k}\right].\vspace*{-2.84544pt}\) 
Combining (REF ) and (REF ), we get that \(\alpha _{k} \le B_{1}\) . Further, from (REF ), (REF ) and (REF ), we have
\( H_{F_{k}}\le \dfrac{H_{\psi }}{2}B_2^p + \dfrac{L_{\psi }}{6} B_1 + H_{f,\max }. \) 
This implies that:

\(\mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \le F(x_{k}) - \dfrac{\eta _{\min } \cdot \mathbb {E}\left[\Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert ^2 \ | \ x_{k}\right]}{2\left( \frac{H_{\psi }}{2}B_2^p + \frac{L_{\psi }}{6} B_1 + H_{f,\max }\right)^2}.\vspace*{-1.42271pt}\) 
Since
\( \mathbb {E}[\Vert  U^{T}_{i_{k}} \nabla F(x_{k})\Vert ^2 \ | \ x_{k} ] = \dfrac{1}{N} \Vert \nabla F(x_{k})\Vert ^2\) ,
the statement follows.
Bounded Hessian
If Assumptions REF  and REF [A.4] hold, then in order to ensure the descent in function values for algorithm RCGD, \(H_{F_{k}}\)  can be computed as:
Stepsize Choice 2:1.  Choose \(H_{f,U_{i_k}}> \dfrac{L_{i_{k}}}{2}\)  and compute \(\alpha _{k}\)  as the positive root of the following polynomial in \(\alpha \) :

\(2^{p-1} H_{\psi }\alpha ^{p+1} + (2^{p-1} H_{\psi }\Vert x_{k}\Vert ^{p} + H_{f,U_{i_k}})\alpha - \Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert  = 0. \vspace*{-2.84544pt}\) 
2.  Define:

\(H_{F_{k}}= 2^{p-1} H_{\psi }\Vert x_{k}\Vert ^p + 2^{p-1} H_{\psi }\alpha _{k}^p + H_{f,U_{i_k}}. \vspace*{-2.84544pt}\) 

Note that \(\alpha _{k} \ge 0\)  and thus \(H_{F_{k}}\)  is well-defined. Indeed, consider:

\(h(\alpha ) = 2^{p-1} H_{\psi }\alpha ^{p+1} + (2^{p-1} H_{\psi }\Vert x_{k}\Vert ^{p} + H_{f,U_{i_k}})\alpha - \Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert  \vspace*{-2.84544pt}\) 
and \(w_{k} = \dfrac{1}{H_{f,U_{i_k}}} \Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert \) . If \(\Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert  \ne 0\) , then we have \(h(w_{k}) > 0\)  and \(h(0) < 0\) . Since \(h\)  is continuous on \([0,w_{k}]\) , then there exists \(\alpha _{k} \in (0,w_{k})\)  such that \(h(\alpha _{k}) = 0\) . Moreover, since \(h^{\prime }(\alpha ) > 0\)  for all \(\alpha \in (0,+\infty )\) , then \(h\)  is strictly increasing on \((0,+\infty )\) . Hence, there exist exactly one \(\alpha _{k} > 0\)  satisfying (REF ). Moreover, if \(\Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert  = 0\) , we have \(\alpha _{k} = 0\) . Note that from (REF ), we have:

\(\left(2^{p-1}H_{\psi }\alpha _{k}^{p} + 2^{p-1}H_{\psi }\Vert x_{k}\Vert ^{p} + H_{f,U_{i_k}}\right) \alpha _{k} = \Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert .\vspace*{-2.84544pt}\) 
Hence, from (REF ), we get:

\(\Vert d_{k}\Vert  = \dfrac{1}{H_{F_{k}}}\Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert  = \dfrac{\Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert }{2^{p-1}H_{\psi }\alpha _{k}^{p} + 2^{p-1}H_{\psi }\Vert x_{k}\Vert ^{p} + H_{f,U_{i_k}}} = \alpha _{k}. \vspace*{-2.84544pt}\) 
If Assumptions REF  and REF [A.4] hold, and \(H_{F_{k}}\)  is updated as in Stepsize Choice 2, then the iterates of algorithm RCGD satisfy the descent:
\(\mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \le F(x_{k}) - \dfrac{\eta _{\min }}{2} \mathbb {E}[\Vert d_{k}\Vert ^2 \ | \ x_{k}].\) 
Since \(\psi \)  is differentiable, from the mean value theorem there exists \(y_k \in [x_{k},x_{k} + U_{i_k}d_{k}]\)  such that
\(\psi (x_{k+1}) - \psi (x_{k}) = \langle \nabla \psi (y_{k}), U_{i_{k}}d_{k}\rangle \) .
Combining the last equality with (REF ), we obtain:

\(f(x_{k+1}) + \psi (x_{k+1}) &\le & f(x_{k}) + \langle \nabla f(x_{k}), U_{i_k}d_{k} \rangle + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \psi (x_{k+1}) \\&=& f(x_{k}) + \psi (x_{k}) + \langle \nabla \psi (y_{k}) + \nabla f(x_{k}), U_{i_{k}}d_{k}\rangle + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2.\vspace*{-2.84544pt}\) 
Using (REF ), we further have:

\(F(x_{k+1}) \le F(x_{k}) + \langle U_{i_{k}}^{T}\left( \nabla \psi (y_{k}) - \nabla \psi (x_{k})\right) , d_{k}\rangle - H_{F_{k}}\Vert d_{k}\Vert ^2 + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2. \) 
Moreover, from the mean value theorem there exists \(\bar{x}_k \in [x_{k},y_{k}]\)  such that:
\(U^{T}_{i_k}(\nabla \psi (y_{k}) - \nabla \psi (x_{k})) = U^{T}_{i_k}\nabla ^2 \psi (\bar{x}_k)(y_{k} - x_{k}) = U^{T}_{i_k}\nabla ^2 \psi (\bar{x}_k) U_{i_{k}}\left( y^{(i_{k})}_{k} - x_{k}^{(i_{k})}\right). \) 
Note that \(\bar{x}_k = (1-\mu ) x_{k} + \mu y_{k} \)  for some \(\mu \in [0,1]\) . From Assumption REF [A.4], we obtain:

\(\langle U_{i_{k}}^{T}\left( \nabla \psi (y_{k}) - \nabla \psi (x_{k})\right) , d_{k}\rangle &=& \left\langle U^{T}_{i_k}\nabla ^2 \psi (\bar{x}_k) U_{i_k}\left( y^{(i_{k})}_{k} - x_{k}^{(i_{k})}\right), d_{k}\right\rangle \\&\le & \Vert U^{T}_{i_k}\nabla ^2 \psi (\bar{x}_k) U_{i_k}\Vert  \Vert y_{k} -x_{k}\Vert  \Vert d_{k}\Vert  \\&\le & H_{\psi }\Vert (1-\mu ) x_{k} + \mu y_{k}\Vert ^{p} \Vert y_{k} - x_{k}\Vert  \Vert d_{k}\Vert .\) 
Since \(y_k \in [x_{k},x_{k}+U_{i_k}d_{k}]\) , then \(y_{k} = (1-\tau )x_{k} + \tau \left( x_{k} + U_{i_k}d_{k}\right)\)  for some \(\tau \in [0,1]\)  and \(\Vert y_{k} - x_{k}\Vert  \le \Vert d_{k}\Vert \) . Moreover, from convexity of \(\Vert \cdot \Vert ^{p}\)  for \(p \ge 1\) , we get:

\(&& \langle U_{i_{k}}^{T}\left(\nabla \psi (y_{k}) - \nabla \psi (x_{k})\right) , d_{k}\rangle \\&& \le H_{\psi }\left( (1-\mu ) \Vert x_{k}\Vert ^p + \mu \Vert y_{k}\Vert ^{p}\right) \Vert d_{k}\Vert ^2 \\&& = H_{\psi }\left( (1-\mu ) \Vert x_{k}\Vert ^p + \mu \Vert (1-\tau )x_{k} + \tau \left( x_{k} + U_{i_k}d_{k}\right)\Vert ^{p}\right) \Vert d_{k}\Vert ^2 \\&& \le H_{\psi }\left( (1-\mu ) \Vert x_{k}\Vert ^p + \mu (1-\tau )\Vert x_{k}\Vert ^p + \mu \tau \Vert  x_{k} + U_{i_k}d_{k}\Vert ^{p}\right) \Vert d_{k}\Vert ^2.\) 
Since \(\mu ,\tau \in [0,1]\)  and \(\Vert a + b\Vert ^p \le 2^{p-1} \Vert a\Vert ^p + 2^{p-1} \Vert b\Vert ^p\)  for \(p \ge 1\) , we get:
\(\langle U_{i_{k}}^{T}\left(\nabla \psi (y_{k}) - \nabla \psi (x_{k})\right) , d_{k}\rangle &\le & H_{\psi }\left( (1+(2^{p-1} -1)\mu \tau ) \Vert x_{k}\Vert ^p + 2^{p-1} \mu \tau \Vert d_{k}\Vert ^{p}\right) \Vert d_{k}\Vert ^2\\ &\le & 2^{p-1} H_{\psi }\Vert x_{k}\Vert ^{p}\Vert d_{k}\Vert ^2 + 2^{p-1} H_{\psi }\Vert d_{k}\Vert ^{p+2}.\) 
Combining the inequality above with (REF ), we obtain:

\(F(x_{k+1}) \le F(x_{k}) + 2^{p-1} H_{\psi }\Vert x_{k}\Vert ^{p}\Vert d_{k}\Vert ^2 + 2^{p-1} H_{\psi }\Vert d_{k}\Vert ^{p+2} - H_{F_{k}}\Vert d_{k}\Vert ^2 + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2.\) 
From (REF ) and (REF ), we have \(H_{F_{k}}= 2^{p-1} H_{\psi }\Vert d_{k}\Vert ^{p} + 2^{p-1} H_{\psi }\Vert x_{k}\Vert ^{p} + H_{f,U_{i_k}}\) . Hence, from (REF ) and (REF ), we get:

\(F(x_{k+1}) \le F(x_{k}) - \left( H_{f,U_{i_k}}- \frac{L_{i_{k}}}{2}\right) \Vert d_{k}\Vert ^2 \le F(x_{k}) - \frac{\eta _{\min }}{2} \Vert d_{k}\Vert ^2.\) 
Taking expectation of both sides of this inequality w.r.t. \(x_{k}\) , the lemma is proved. \(\Box \)
Let assumptions of Lemma REF  hold. Additionally, let the sequence \((x_{k})_{k\ge 0}\)  generated by algorithm RCGD be bounded. Then, the following descent holds:
\(\mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \le F(x_{k}) - \dfrac{\eta _{\min }}{2N (2^{p-1}H_{\psi }B_1^{p} + 2^{p-1}H_{\psi }B_2^{p} + H_{f,\max })^2} \Vert \nabla F(x_{k})\Vert ^2,\) 
where \(B_{1}\)  and \(B_{2}\)  are defined in (REF ) and (REF ), respectively.
The proof of this lemma is similar to Lemma REF .

Lipschitz Hessian
If Assumptions REF  and REF [A.5] hold, in order to ensure the descent in function values for algorithm RCGD, \(H_{F_{k}}\)  can be computed as:
Stepsize Choice 3:1.  Choose \(H_{f,U_{i_k}}> \dfrac{L_{i_{k}}}{2}\)  and compute \(\alpha _{k}\ge 0\)  root of the second order equation:

\(\dfrac{L_{\psi }}{6} \alpha ^{2} + \left( \dfrac{L_{\psi }}{2} \Vert x_{k}-x_{0}\Vert  + \dfrac{1}{2} \Vert \nabla ^2 \psi (x_{0})\Vert  + H_{f,U_{i_k}}\right) \alpha - \Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert  = 0. \vspace*{-2.84544pt}\) 
2.  Update
\(\vspace*{-2.84544pt}H_{F_{k}}= \frac{L_{\psi }}{2}\Vert x_{k}-x_{0}\Vert  + \frac{1}{2}\Vert \nabla ^2 \psi (x_{0})\Vert  + \frac{L_{\psi }}{6} \alpha _{k} + H_{f,U_{i_k}}\vspace*{-2.84544pt}\) 

Note that this stepsize strategy requires computation of \(\nabla ^2 \psi \)  only in \(x_{0}\) . Moreover, from (REF ), we have:
\(\left(\dfrac{L_{\psi }}{6} \alpha _{k} + \dfrac{L_{\psi }}{2} \Vert x_{k}-x_{0}\Vert  + \dfrac{1}{2} \Vert \nabla ^2 \psi (x_{0})\Vert  + H_{f,U_{i_k}}\right) \alpha _{k} = \Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert .\) 
Hence, by (REF ), we get:

\(\Vert d_{k}\Vert  = \dfrac{\Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert }{\frac{L_{\psi }}{2} \Vert x_{k}-x_{0}\Vert  + \frac{1}{2} \Vert \nabla ^2 \psi (x_{0})\Vert + \frac{L_{\psi }}{6} \alpha _{k} + H_{f,U_{i_k}}} = \alpha _{k}. \vspace*{-2.84544pt}\) 
We can easily see that there exist \(\alpha _{k} \ge 0\)  satisfying (REF ). Hence, \(H_{F_{k}}\)  is well-defined.


If Assumptions REF  and REF [A.5] hold and \(H_{F_{k}}\)  is updated as in Stepsize Choice 3, then the iterates of algorithm RCGD satisfy the descent:
\(\mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \le F(x_{k}) - \dfrac{\eta _{\min }}{2} \mathbb {E}[\Vert d_{k}\Vert ^2 \ | \ x_{k}].\) 
From Assumption REF , Assumption REF [A.5] and (REF ), we have:

\(F(x_{k+1}) &\le & F(x_{k}) - H_{F_{k}}\Vert d_{k}\Vert ^{2} + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \dfrac{1}{2}\langle \nabla ^2 \psi (x_{k})U_{i_{k}}d_{k},U_{i_{k}}d_{k}\rangle + \dfrac{L_{\psi }}{6} \Vert d_{k}\Vert ^3 \\&\le & F(x_{k}) - H_{F_{k}}\Vert d_{k}\Vert ^{2} + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \dfrac{1}{2}\Vert \nabla ^2 \psi (x_{k})\Vert  \Vert d_{k}\Vert ^2 + \dfrac{L_{\psi }}{6} \Vert d_{k}\Vert ^3 \\&\le & F(x_{k}) - H_{F_{k}}\Vert d_{k}\Vert ^{2} + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \dfrac{L_{\psi }}{6} \Vert d_{k}\Vert ^3 \\&& + \dfrac{1}{2}\left(\Vert \nabla ^2 \psi (x_{k})-\nabla ^2 \psi (x_{0})\Vert  + \Vert \nabla ^2 \psi (x_{0})\Vert \right) \Vert d_{k}\Vert ^2 \\&\le & F(x_{k}) - H_{F_{k}}\Vert d_{k}\Vert ^{2} + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \dfrac{L_{\psi }}{6} \Vert d_{k}\Vert ^3 \\&& + \dfrac{1}{2}\left(L_{\psi }\Vert x_{k}-x_{0}\Vert  + \Vert \nabla ^2 \psi (x_{0})\Vert \right) \Vert d_{k}\Vert ^2.\) 
From (REF ) and (REF ), we have \(H_{F_{k}}= \frac{L_{\psi }}{6} \Vert d_{k}\Vert  + \frac{L_{\psi }}{2} \Vert x_{k}-x_{0}\Vert  + \frac{1}{2} \Vert \nabla ^2 \psi (x_{0})\Vert  + H_{f,U_{i_k}}\) . Hence, by (REF ) and (REF ) we get:

\(F(x_{k+1}) \le F(x_{k}) - \left( H_{f,U_{i_k}}- \frac{L_{i_{k}}}{2}\right) \Vert d_{k}\Vert ^2 \le F(x_{k}) - \frac{\eta _{\min }}{2} \Vert d_{k}\Vert ^2.\) 
Taking the expectation of both sides of the inequality w.r.t. \(x_{k}\) , the lemma is proved.
Let assumptions of Lemma REF  holds. Additionally, let the sequence \((x_{k})_{k\ge 0}\)  generated by algorithm RCGD be bounded. Then, the following descent holds:

\(\mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \le F(x_{k}) - C\Vert \nabla F(x_{k})\Vert ^2 ,\) 
with \(C = \dfrac{\eta _{\min }}{2N \left(L_{\psi }\left( \frac{B_1}{6} + \frac{B_2}{2} + \frac{1}{2}\Vert x_{0}\Vert  \right) + \frac{1}{2}\Vert \nabla ^2 \psi (x_{0})\Vert  + H_{f,\max }\right)^2 }\) , where \(B_{1}\)  and \(B_{2}\)  are defined in (REF ) and (REF ), respectively.
The proof of this Lemma is similar to Lemma REF .

Function \(\psi \)  concave along coordinates
In this section, we do not assume the function \(\psi \)  to be
twice differentiable. We just require \(\psi \)  to be differentiable and concave function along coordinates as stated in the next assumption. Therefore, this case covers difference of convex (DC) programming problems and our algorithm RCGD is new in this context.
Assumption  
Assume that the function \(\psi \)  is differentiable and concave along coordinates, that is:

\(\psi (x + U_{i}d) \le \psi (x) + \langle U_{i}^{T}\nabla \psi (x), d\rangle \quad \forall d \in \mathbb {R}^{n_{i}}, x\in \mathbb {R}^{n}, i =1:N.\) 

If Assumptions REF  and REF  hold, in order to ensure the descent in function values for algorithm RCGD, \(H_{F_{k}}\)  can be computed as follows:
Stepsize Choice 4:1.  Choose \(H_{f,U_{i_k}}> \dfrac{L_{i_{k}}}{2}\)  and update

\(H_{F_{k}}= H_{f,U_{i_k}}. \vspace*{-2.84544pt}\) 

If Assumptions REF  and REF  hold and \(H_{F_{k}}\)  is updated as in Stepsize Choice 4, then the iterates of algorithm RCGD satisfy the descent:
\(\mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \le F(x_{k}) - \dfrac{\eta _{\min }}{2NH_{f,\max }^2} \Vert \nabla F(x_{k})\Vert ^2.\) 
Since \(\psi \)  is concave along coordinates, we have:

\(\psi (x_{k+1}) \le \psi (x_{k}) + \langle U_{i_{k}}^{T}\nabla \psi (x_{k}), d_{k}\rangle .\) 
Combining the inequality above with (REF ), we obtain:

\(&& f(x_{k+1}) + \psi (x_{k+1}) \nonumber \\&& \le f(x_{k}) + \langle \nabla f(x_{k}), U_{i_k}d_{k} \rangle + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2 + \psi (x_{k}) + \langle U_{i_{k}}^{T}\nabla \psi (x_{k}), d_{k}\rangle \nonumber \\&& \le F(x_{k}) + \langle U_{i_{k}}^{T}\nabla F(x_{k}), d_{k} \rangle + \frac{L_{i_{k}}}{2} \Vert d_{k}\Vert ^2. \) 
From (REF ) and (REF ), we have \(H_{f,U_{i_k}}d_{k} = -U_{i_{k}}^{T}\nabla F(x_{k})\) . By (REF ) and (REF ), we get:

\(F(x_{k+1}) \le F(x_{k}) - \left( H_{f,U_{i_k}}- \frac{L_{i_{k}}}{2}\right) \Vert d_{k}\Vert ^2 \le F(x_{k}) - \frac{\eta _{\min }}{2H_{f,U_{i_k}}^2} \Vert U^{T}_{i_{k}} \nabla F(x_{k})\Vert ^2.\vspace*{-2.84544pt}\) 
Using (REF ) and taking expectation of both sides of the inequality w.r.t. \(x_{k}\) , we have:

\(\mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \le F(x_{k}) - \dfrac{\eta _{\min }}{2H_{f,\max }^2} \mathbb {E}\left[\Vert  U^{T}_{i_{k}} \nabla F(x_{k})\Vert ^2 \ | \ x_{k}\right].\vspace*{-5.69046pt}\) 
Since
\( \mathbb {E}[\Vert  U^{T}_{i_{k}} \nabla F(x_{k})\Vert ^2 \ | \ x_{k} ] = \dfrac{1}{N} \Vert \nabla F(x_{k})\Vert ^2\) , the statement follows.
Note that in the previous lemma we don't need to require the sequence \((x_{k})_{k\ge 0}\)  to be bounded. Next we provide sufficient conditions when the sequences generated by our two random coordinate descent algorithms are bounded.

Sufficient conditions for bounded iterates
Note that Lemmas , REF , REF , REF  and REF  prove that the sequence \(\left(F(x_{k})\right)_{k\ge 0}\)  generated by the algorithms RCPG or RCGD (with appropiate stepsize rules) is nonincreasing, i.e., \(F(x_{k+1}) \le F(x_{k})\)  for all \(k \ge 0\) . However, in order to prove Lemmas , REF , REF  and REF , we need to assume that the sequence \((x_{k})_{k\ge 0}\)  is bounded. In this section we present sufficient conditions for boundedness. One natural example is when the level set is bounded:

\(\mathcal {L}_{F}(x_{0})=\left\lbrace x: \,F(x)\le F(x_{0}) \right\rbrace .\) 
Note that uniformly convex functions have bounded level sets. Indeed, if \(F\)  is uniformly convex, with constant \(q>1\) , then it satisfies [1]}:

\(F(y) \ge F(x) + \langle \nabla F(x), y - x \rangle + \frac{\sigma _q (q-1)}{q} \Vert y - x\Vert ^{\frac{q}{q-1}} \quad \forall x, y \in \mathbb {R}^{n}. \vspace*{-2.84544pt}\) 
Then, for \(x = x^{*}\)  and \(y \in \mathcal {L}_{F}(x_{0})\) , we have

\(\frac{\sigma _q (q-1)}{q} \Vert x^{*} - y\Vert ^{\frac{q}{q-1}} \le F(y) - F(x^{*}) \le F(x^0) - F(x^{*}) < \infty .\vspace*{-2.84544pt}\) 
Moreover, note that if \(F\)  is uniformly convex, then it has a unique minimizer. In the next lemma we show that if \(f\)  is nonconvex and \(\psi \)  uniformly convex with constant \(q\in (1,2)\) , then the level set \(\mathcal {L}_{F}(x_{0})\)  is bounded.
Let \(\mathcal {X}^{*}\)  be the set of optimal solutions of problem (REF ). Assume \(\psi \)  differentiable and uniformly convex function with constant \(q\in (1,2)\)  and the function \(f\)  satisfies Assumption REF [A.1]. Then:

\(\Vert x -x^{*}\Vert  \le \max \left\lbrace \! \left(\dfrac{(2(F(x_{0}) - F(x^{*}))+ L) q}{2(q-1)\sigma _{q}}\right)^{\frac{q-1}{2-q}}\!\!, 1 \right\rbrace \\ \;\; \forall x \in \mathcal {L}_{F}(x_{0}), x^{*} \in \mathcal {X}^{*}. \) 
Moreover, if \(\mathcal {X}^{*}\)  is bounded, then the level set \(\mathcal {L}_{F}(x_{0})\)  is also bounded
We prove (REF ) by contradiction. Assume for some \(\bar{x} \in \mathcal {L}_{F}(x_{0})\)  and \(x^{*} \in \mathcal {X}^{*}\)  that

\(\Vert \bar{x} -x^{*}\Vert  > \max \left\lbrace \left(\dfrac{(2(F(x_{0}) - F(x^{*}))+ L) q}{2(q-1)\sigma _{q}}\right)^{\frac{q-1}{2-q}}, 1 \right\rbrace . \) 
Then,
\( \Vert \bar{x} -x^{*}\Vert ^{\frac{2-q}{q-1}} > \dfrac{(2(F(x_{0}) - F(x^{*}))+ L) q}{2(q-1)\sigma _{q}}, \) 
or equivalently:

\(\dfrac{(q-1)\sigma _{q}}{q} \Vert \bar{x} -x^{*}\Vert ^{\frac{2-q}{q-1}} > \dfrac{L}{2} + F(x_{0}) - F(x^{*}) \ge \dfrac{L}{2}. \) 
Since \(\psi \)  is uniformly convex, we have:

\(\psi (x) \ge \psi (y) + \langle \nabla \psi (y), x - y \rangle + \frac{\sigma _q (q-1)}{q} \Vert y - x\Vert ^{\frac{q}{q-1}} \quad \forall x, y \in \mathbb {R}^{n}.\vspace*{-2.84544pt}\) 
Taking \(y=x^{*}\)  and \(x=\bar{x}\) , we get:

\(\dfrac{\sigma _q (q-1)}{q} \Vert \bar{x} - x^{*}\Vert ^{\frac{q}{q-1}} \le \psi (\bar{x}) - \psi (x^{*}) - \langle \nabla \psi (x^{*}), \bar{x} - x^{*} \rangle . \vspace*{-2.84544pt}\) 
From Assumption REF [A.1] and Lemma 2 in [2]}, we have:

\(- \dfrac{L}{2} \Vert \bar{x} - x^{*}\Vert ^{2} \le f(\bar{x}) - f(x^{*}) - \langle \nabla f(x^{*}),\bar{x} -x^{*} \rangle , \vspace*{-2.84544pt}\) 
where \(L = N L_{\max }\)  and \(L_{\max } = \max _{i=1:N} L_{i}\) . Using the optimality condition for the problem (REF ), we have \(\nabla f(x^{*}) + \nabla \psi (x^{*})=0\) , hence by (REF ) and (REF ), we get:

\(\dfrac{\sigma _q (q-1)}{q} \Vert \bar{x} - x^{*}\Vert ^{\frac{q}{q-1}} \le F(\bar{x}) - F(x^{*}) + \dfrac{L}{2} \Vert \bar{x} - x^{*}\Vert ^{2} .\vspace*{-2.84544pt}\) 
Since \(\bar{x} \in \mathcal {L}_{F}(x_{0})\) , we have:

\(F(x_{0}) - F(x^{*}) \ge F(\bar{x}) - F(x^{*}) \ge \left( \dfrac{\sigma _q (q-1)}{q} \Vert \bar{x} - x^{*}\Vert ^{\frac{2-q}{q-1}} - \dfrac{L}{2}\right) \Vert \bar{x} - x^{*}\Vert ^{2}.\) 
Combining the inequality above with (REF ), we get:
\(\dfrac{\sigma _q (q-1)}{q} \Vert \bar{x} - x^{*}\Vert ^{\frac{2-q}{q-1}} - \dfrac{L}{2} > \left( \dfrac{\sigma _q (q-1)}{q} \Vert \bar{x} - x^{*}\Vert ^{\frac{2-q}{q-1}} - \dfrac{L}{2}\right) \Vert \bar{x} - x^{*}\Vert ^{2}, \) 
or equivalently

\(\dfrac{\sigma _q (q-1)}{q} \Vert \bar{x} - x^{*}\Vert ^{\frac{2-q}{q-1}} \left( 1 - \Vert \bar{x} - x^{*}\Vert ^{2}\right) \ge \dfrac{L}{2}\left( 1 - \Vert \bar{x} - x^{*}\Vert ^{2}\right).\) 
From (REF ), we have \(1 - \Vert \bar{x} - x^{*}\Vert ^{2} < 0\) , hence
\(\dfrac{\sigma _q (q-1)}{q} \Vert \bar{x} - x^{*}\Vert ^{\frac{2-q}{q-1}} \le \dfrac{L}{2}. \) 
Therefore, relation (REF ) is a contradiction with (REF ). Hence (REF ) is proved.

Convergence analysis: nonconvex case
Recall that Lemmas , REF , REF , REF  and REF  show that the sequence \(\left(F(x_{k})\right)_{k\ge 0}\)  generated by the algorithms RCPG or RCGD satisfy the following descent for some appropriate constant \(C>0\) :
\(F(x_{k}) - \mathbb {E}[F(x_{k+1}) \ | \ x_{k}] \ge C\Vert \nabla F(x_{k})\Vert ^2. \) 
Sublinear convergence
Based on the descent inequality above, which we proved without computing the full prox of \(\psi \)  or requiring the full gradient \(\nabla F\)  to be Lipschitz continuous, as usually considered in the existing literature, we derive in this section convergence rates for our algorithms depending on the properties of \(F\) .


Let \((x_{k})_{k\ge 0}\)  be generated by the algorithms RCPG or RCGD. If (REF ) holds, then we have the following sublinear rate in expectation:

\(k \cdot \min _{0\le i\le k-1} \mathbb {E} \left[ \Vert \nabla F(x_{i})\Vert ^2 \right] \le \sum _{i=0}^{k-1} \mathbb {E} \left[ \Vert \nabla F(x_{i})\Vert ^2 \right] \le \dfrac{F(x_{0}) - F^{*}}{C}. \vspace*{-2.84544pt}\) 
Taking the expectation in the inequality (REF ), w.r.t. \(\lbrace x_{0},...,x_{k-1}\rbrace \) , we have
\(\mathbb {E}[F(x_{k+1})] \le \mathbb {E}[F(x_{k})] - C \cdot \mathbb {E}[\Vert \nabla F(x_{k})\Vert ^2]\) .
This implies that
\(C \sum _{i=0}^{k-1} \mathbb {E}[\Vert \nabla F(x_{i})\Vert ^2] \le \sum _{i=0}^{k-1} \left( \mathbb {E}[F(x_{i})] - \mathbb {E}[F(x_{i+1})] \right) \le F(x_{0}) - F^{*},\) 
which proves our statement.
Choose accuracy level \(\epsilon > 0\)  and confidence level \(\rho \in (0,1)\) . Let the sequence \((x_{k})_{k\ge 0}\)  generated by the algorithms RCPG or RCGD satisfies (REF ). If
\(k \ge \dfrac{F(x_{0}) - F_{*}}{\epsilon \rho C}, \) 
then
\( \mathbb {P}\left[ \displaystyle \min _{0\le i\le k-1} \Vert \nabla F(x_{i})\Vert ^2 \le \epsilon \right] \ge 1 - \rho .\) 
Since
\( \displaystyle k \min _{0\le i\le k-1} \Vert \nabla F(x_{i})\Vert ^2 \le \sum _{i=0}^{k-1} \Vert \nabla F(x_{i})\Vert ^2\) ,
we have that

\(\mathbb {P} \left[ \min _{0\le i\le k-1} \Vert \nabla F(x_{i})\Vert ^2 \ge \epsilon \right] \le \mathbb {P} \left[ \dfrac{1}{k} \sum _{i=0}^{k-1} \Vert \nabla F(x_{i})\Vert ^2 \ge \epsilon \right] . \) 
Further, from Markov inequality and basic properties of expectation, we get:

\(\mathbb {P} \left[ \sum _{i=0}^{k-1} \Vert \nabla F(x_{i})\Vert ^2 \ge k \epsilon \right] \le \dfrac{1}{k \epsilon } \mathbb {E}\left[ \sum _{i=0}^{k-1} \Vert \nabla F(x_{i})\Vert ^2 \right] \le \dfrac{1}{k \epsilon } \sum _{i=0}^{k-1} \mathbb {E}\left[ \Vert \nabla F(x_{i})\Vert ^2 \right]. \) 
Combining the previous relations, we obtain:

\(\mathbb {P} \left[ \min _{0\le i\le k-1} \Vert \nabla F(x_{i})\Vert ^2 \ge \epsilon \right] \le \dfrac{F(x_{0}) - F^{*}}{k \epsilon C} \le \rho ,\) 
which proves our statement.

Better convergence under KL
In this section we derive convergence rates for our algorithms when the objective function \(F\)  satisfies the KL property (REF ) (in particular, \(F\)  is uniformly convex). Let us denote the set of limit points of the sequence \((x_{k})_{k\ge 0}\)  by \(\Omega (x_{0})\) . Next lemma derives some basic properties for \(\Omega (x_{0})\) .
Let the sequence \((x_{k})_{k\ge 0}\)  generated by algorithms RCPG or RCGD, respectively, be bounded. If Assumption REF  and descent (REF ) hold, then \(\Omega (x_{0})\)  is compact set, \(F\)  is constant on \(\Omega (x_{0})\)  a.s., and \(\mathbb {E}[\nabla F(\Omega (x_{0}))]=0\) .
Since the sequence \((x_{k})_{k\ge 0}\)  is bounded, this implies that the set \(\Omega (x_{0})\)  is also bounded. Closeness of \(\Omega (x_{0})\)  also follows observing that \(\Omega (x_{0})\)  can be viewed as an intersection of closed sets, i.e., \(\Omega (x_{0}) = \cap _{j \ge 0} \cup _{\ell \ge j} \lbrace x_{k}\rbrace \) . Hence \(\Omega (x_{0})\)  is a compact set. Let us prove that \(F\)  is constant on \(\Omega (x_{0})\)  a.s. From Theorem REF , we have:

\(\sum _{j=0}^{k} \left(\mathbb {E}\left[\Vert \nabla F(x_{j})\Vert \right]\right)^2 \le \sum _{j=0}^{k} \mathbb {E}\left[\Vert \nabla F(x_{j})\Vert ^2\right] \le \dfrac{F(x_{0}) - F^{*}}{C} < \infty .\vspace*{-5.69046pt}\) 

This implies that:
\(\lim _{j \rightarrow \infty } \mathbb {E}[\Vert \nabla F(x_{j})\Vert ] = 0. \vspace*{-5.69046pt}\) 
Moreover, we have that \(F(x_{k})_{k\ge 0}\)  is monotonically decreasing and since \(F\)  is assumed bounded from below by \(F^{*} > - \infty \) , it converges, let us say to \(F_{*} > - \infty \) , i.e., \(F(x_{k}) \overset{a.s.}{\rightarrow }F_{*}\)  as \(k \rightarrow \infty \) , and \(F_{*} \ge F^{*}\) .
On the other hand, let \(x_{*}\)  be a limit point of \((x_{k})_{k\ge 0}\) , i.e., \(x_{*} \in \Omega (x_{0})\) . This means that there is a subsequence \((x_{\bar{k}})_{\bar{k}\ge 0}\)  of \((x_{k})_{k\ge 0}\) 
such that \(x_{\bar{k}} \overset{a.s.}{\rightarrow }x_{*}\)  as \(\bar{k} \rightarrow \infty \) . Since \(f\)  and \(\psi \)  are continuous, it follows that \(F(x_{\bar{k}}) \overset{a.s.}{\rightarrow }F(x_{*})\) . This implies that \(F(x_{*}) = F_{*}\) , a.s. Finally, let us prove that \(\mathbb {E}[\nabla F(\Omega (x_{0}))] = 0\) . Note that, since \(F\)  is diferentiable and \(x_{\bar{k}} \overset{a.s.}{\rightarrow }x_{*}\) , then we have \(\Vert \nabla F(x_{\bar{k}})\Vert  \overset{a.s.}{\rightarrow }\Vert \nabla F(x^{*})\Vert \) . Moreover, from (REF ), we have \(\mathbb {E}[\Vert \nabla F(x_{\bar{k}})\Vert ] < + \infty \) . Using basic probability arguments, we obtain:
\(\mathbb {E}[\Vert \nabla F(x_{\bar{k}})\Vert ] \rightarrow \mathbb {E}[\Vert \nabla F(x^{*})\Vert ]\) . Combining it with (REF ), we get \(\mathbb {E}[\Vert \nabla F(x_{*})\Vert ] = 0\) .
Let the sequence \((x_{k})_{k\ge 0}\)  be generated by algorithms RCPG or RCGD, respectively. If the descent (REF ) holds and \(F\)  satisfies the KL property (REF ) on \(\Omega (x_{0})\) , with \(q \in (1,2]\) , then we have the followings rates in function values:
(i) If \(q\in (1,2)\) , we have the following sublinear rate:

\(\mathbb {E}[F(x_{k}) - F_{*}] \le \dfrac{F(x_{0}) - F_{*}}{\left(\frac{(2-q)}{q} C \sigma _{q}^{-\frac{2}{q}} (F(x_{0})-F_{*})^{\frac{2-q}{q}} \cdot k + 1 \right)^{\frac{q}{2-q}}}.\vspace*{-2.84544pt}\) 
(ii) If \(q=2\) , we have the following linear rate:

\(\mathbb {E}[F(x_{k}) - F_{*}] \le (1- C \sigma _{2}^{-1})^{k} \left( F(x_{0}) - F_{*}\right).\vspace*{-2.84544pt}\) 
Combining the descent inequality (REF ) with KL property (REF ), we get:

\(\left(F(x_{k}) - F_{*}\right)^{\frac{2}{q}} \le \sigma _{q}^{\frac{2}{q}} \Vert \nabla F(x_{k})\Vert ^{2} \le \left(\dfrac{\sigma _{q}^{\frac{2}{q}}}{C}\right)\left( F(x_{k}) - \mathbb {E}[F(x_{k+1}) \ | \ x_{k}]\right). \vspace*{-2.84544pt}\) 
Since for \(q \in (1,2]\) , \(t \mapsto t^{\frac{2}{q}}\)  is a convex function on \(\mathbb {R}_+\) , then taking the expectation in both sides of the inequality (REF ) w.r.t. \(\lbrace x_{0},...,x_{k-1}\rbrace \) , we get the following recurrence:

\(\mathbb {E}[F(x_{k}) - F_{*}] - \mathbb {E}[F(x_{k+1}) - F_{*}] \ge C \sigma _{q}^{-\frac{2}{q}} \mathbb {E}[F(x_{k}) - F_{*}]^{\frac{2}{q}}. \vspace*{-2.84544pt}\) 
First, consider \(q\in (1,2)\)  and define \(\gamma = C \sigma _{q}^{-\frac{2}{q}}\) .
Multiplying both sides of the inequality (REF ) by \(\gamma ^{\frac{q}{2-q}}\) , we obtain \(\Delta _{k} - \Delta _{k+1} \ge (\Delta _{k})^{\frac{2}{q}} \) , with \(\Delta _{k} = \gamma ^{\frac{q}{2-q}} \mathbb {E}[F(x_{k}) - F_{*}]\) . Considering the first inequality of Lemma 9 in [3]} for \(\zeta = \frac{2-q}{q}>0\) , we get:

\(& \Delta _{k} \le \dfrac{\Delta _{0}}{\left( \zeta k\Delta _{0}^{\zeta } + 1\right)^\frac{1}{\zeta }} \iff \\& \gamma ^{\frac{q}{2-q}}\mathbb {E}[F(x_{k}) - F_{*}] \le \dfrac{ \gamma ^{\frac{q}{2-q}}\left(F(x_{0}) - F_{*}\right)}{\left( \frac{k(2-q)}{q} \left( \gamma ^{\frac{q}{2-q}}\left(F(x_{0}) - F_{*}\right)\right) ^{\frac{2-q}{q}} + 1\right)^\frac{q}{2-q}} \iff \\& \mathbb {E}[F(x_{k}) - F_{*}] \le \dfrac{ F(x_{0}) - F_{*}}{\left( \frac{k(2-q)}{q} \gamma \left(F(x_{0}) - F_{*}\right)^{\frac{2-q}{q}} + 1\right)^\frac{q}{2-q}},\vspace*{-5.69046pt}\) 
proving the first statement of the theorem. Second, if \(q=2\) , by Lemma 9 in [3]} and (REF ), we have: \(\mathbb {E}[F(x_{k})- F_*] \le \left(1-\dfrac{C}{\sigma _{2}}\right)^{k} (F(x_{0}) - F_*),\) 
that is (REF ).
Next, we derive convergence rates in probability. The next proof follows similar arguments as in [5]}. For completeness we give a proof in Appendix.
Let \(\Delta _{0}, \zeta > 0\)  and \(0 < \epsilon < \Delta _{0}\) , with \(\epsilon \in (0,1)\) , and consider a nonnegative, nonincreasing sequence of (discrete) random variables \(\left(\Delta _{k}\right) _{k\ge 0}\)  satisfying:

\(\mathbb {E} [\Delta _{k+1} | \Delta _{k}] \le \Delta _{k} - \Delta _{k}^{\zeta + 1} \quad \forall k \ge 0. \) 
Choose confidence level \(\rho \in (0,1)\) . If
\(K \ge \dfrac{1}{\zeta }\left(\dfrac{1}{\epsilon ^{\zeta }} - \dfrac{1}{ \Delta _{0}^{\zeta }}\right) + 2 + \dfrac{1}{\epsilon ^{\zeta }}\log \dfrac{1}{\rho }, \;\; \text{then} \quad \mathbb {P}\left[\Delta _{k} \le \epsilon \right] \ge 1 - \rho . \) 
Choose accuracy level \(\epsilon \in (0,1)\)  and confidence level \(\rho \in (0,1)\) . Let \((x_{k})_{k\ge 0}\)  be generated by the algorithms RCPG or RCGD, assume that (REF ) holds and \(F\)  satisfies the KL property (REF ) on \(\Omega (x_{0})\) , with \(q \in (1,2]\) . If \(q\in (1,2)\)  and

\(k \ge \dfrac{q}{2-q} \left( \dfrac{1}{\epsilon ^{\frac{2-q}{q}}} - \frac{\sigma _{q}^{\frac{2}{q}}}{ C \left(F(x_{0}) - F_{*}\right)^{\frac{2-q}{q}}}\right) + 2 + \dfrac{1}{\epsilon ^{\frac{2-q}{q}}}\log \dfrac{1}{\rho },\vspace*{-2.84544pt}\) 
or if \(q=2\)  and

\(k \ge \dfrac{\sigma _{2}}{C} \log \left( \dfrac{F(x_{0}) - F_{*}}{\epsilon \rho }\right), \) 
then
\( \mathbb {P}[F(x_{k}) - F_{*} \le \epsilon ] \ge 1 - \rho . \) 
If \(q\in (1,2)\)  and \(F\)  satisfies the KL property (REF ), then from (REF ) we have:

\(\mathbb {E}[F(x_{k+1}) - F_{*} \ | \ x_{k}] \le \left(F(x_{k}) - F_{*}\right) - \left(C \sigma _{q}^{-\frac{2}{q}}\right) \left(F(x_{k}) - F_{*}\right)^{\frac{2}{q}}. \) 
Multiplying both sides of the inequality (REF ) by \(\left(C \sigma _{q}^{-\frac{2}{q}}\right)^{\frac{q}{2-q}}\) , we get
\(\mathbb {E} [\Delta _{k+1} | x_{k}] \le \Delta _{k} - \Delta _{k}^{\frac{2}{q}} \) ,
with \(\Delta _{k} = \left( C \sigma _{q}^{-\frac{2}{q}} \right)^{\frac{q}{2-q}} \left(F(x_{k}) - F_{*}\right)\) . Using Lemma REF , with \(\zeta = \frac{2-q}{q} \ge 0\) , we obtain the first statement. For \(q=2\) , from Markov inequality and (REF ), we have:

\(\mathbb {P}[F(x_{k}) - F_{*} \ge \epsilon ] \le \dfrac{1}{\epsilon } \mathbb {E} [F(x_{k}) - F^{*}] \le \dfrac{1}{\epsilon } (1-C \sigma _{2}^{-1})^{k} \left( F(x_{0}) - F_{*}\right).\vspace*{-2.84544pt}\) 
Using (REF ), we obtain
\( \mathbb {P}[F(x_{k}) - F_{*} \ge \epsilon ] \le \rho . \)

Convergence analysis: convex case
In this section we assume that the composite objective function \(F= f + \psi \)  is convex. Note that we do not need to impose convexity on \(f\)  and \(\psi \)  separately. Denote the set of optimal solutions of (REF ) by \(X^{*}\)  and let \(x^{*}\)  be an element of this set. Define also:

\(R = \max _{k \ge 0} \min _{x^{*} \in X^{*}} \Vert x_{k} - x^{*}\Vert  < \infty .\vspace*{-2.84544pt}\) 
Let \((x_{k})_{k\ge 0}\)  be generated by algorithms RCPG or RCGD. If (REF ) holds and \(F\)  is convex, then the following sublinear rate in function values holds:
\(\mathbb {E}[F(x_{k}) - F(x^{*})] \le \dfrac{\left(F(x_{0}) - F(x^{*})\right) R^2 }{C\left(F(x_{0}) - F(x^{*})\right)k + R^2}. \) 
Since \(F\)  is convex, we have:
\(F(x^{*}) - F(x_{k}) \ge \langle \nabla F(x_{k}), x^{*} - x_{k+1} \rangle &\ge & - \Vert  \nabla F(x_{k})\Vert  \Vert x_{k+1} - x^{*} \Vert  \ge - \Vert  \nabla F(x_{k})\Vert  R.\) 
Hence,
\( \Vert \nabla F(x_{k})\Vert  \ge \dfrac{F(x_{k}) - F(x^{*})}{R}. \) 
Combining this inequality with (REF ), we get:

\(\left(F(x_{k}) - F(x^{*})\right) - \mathbb {E}[F(x_{k+1}) - F(x^{*}) \ | \ x_{k} ] \ge C \dfrac{\left( F(x_{k}) - F(x^{*})\right)^{2}}{R^{2}}. \) 
Since \(t \mapsto t^{2}\)  is convex function, then taking the expectation on both sides of the inequality (REF ) w.r.t. \(\lbrace x_{0},...,x_{k-1}\rbrace \) , we obtain:

\(\mathbb {E}[F(x_{k}) - F(x^{*})] - \mathbb {E}[F(x_{k+1}) - F(x^{*})] \ge C \dfrac{\mathbb {E}[F(x_{k}) - F(x^{*})]^{2}}{R^{2}}.\) 
Multiplying both sides by \(C/R^{2}\) , we further get:
\(\dfrac{C \cdot \mathbb {E}[F(x_{k}) - F(x^{*})]}{R^{2}} - \dfrac{C \cdot \mathbb {E}[F(x_{k+1}) - F(x^{*})]}{R^{2}} \ge \left[\dfrac{C \cdot \mathbb {E}[F(x_{k}) - F(x^{*})]}{R^{2}}\right]^{2}.\) 
Denote
\(\Delta _{k} = \dfrac{C \cdot \mathbb {E}[F(x_{k}) - F(x^{*})]}{R^{2}}\) . Therefore, we obtain the following recurrence:
\(\Delta _{k} - \Delta _{k+1} \ge \left(\Delta _{k}\right)^{2}.\) 
From Lemma 9 in [3]}, we obtain:

\(\dfrac{C \cdot \mathbb {E}[F(x_{k}) - F(x^{*})]}{R^{2}} \le \dfrac{C\left(F(x_{0}) - F(x^{*})\right)}{C\left(F(x_{0}) - F(x^{*})\right) k + R^2} .\) 
which proves our statement.
Choose accuracy level \(\epsilon \in (0,1)\)  and confidence level \(\rho \in (0,1)\) . Let \((x_{k})_{k\ge 0}\)  be generated by the algorithms RCPG or RCGD and assume that the descent (REF ) holds. If \(F\)  is convex function and
\(k \ge \dfrac{1}{\epsilon }\left( 1+\log \dfrac{1}{\rho }\right) + 2 - \dfrac{R^2}{C(F(x_{0}) - F^{*})},\) 
then
\(\mathbb {P}[F(x_{k}) - F^{*} \le \epsilon ] \ge 1 - \rho .\) 
Multiplying both sides of (REF ) by \(C/R^{2}\) , we obtain:
\( \mathbb {E}[\Delta _{k+1} \ | \ x_{k} ] \le \Delta _{k} - \Delta _{k}^{2},\) 
with \( \Delta _{k} = \dfrac{C \left( F(x_{k}) - F(x^{*})\right) }{R^{2}}\) . Using Lemma REF  with \(\zeta =1\) , the statement follows.

Numerical simulations
In the numerical experiments we consider two applications: the subproblem in the cubic Newton method [7]} and the orthogonal matrix factorization problem [8]}. Next, we describe these problems, provide some implementation details and present the numerical results.
Cubic Newton
In the first set of experiments, we consider solving the subproblem in the cubic Newton method, an algorithm which is supported by global efficiency estimates for general classes of optimization problems [7]}. In each iteration of the cubic Newton one needs to minimize an objective function of the form:

\(\min _{x \in \mathbb {R}^{n}} F(x) := \frac{1}{2} \langle Ax, x \rangle + \langle b, x \rangle + \frac{M}{6} \Vert x \Vert ^3,\vspace*{-2.84544pt}\) 
where \(A \in \mathbb {R}^{n\times n}, b\in \mathbb {R}^{n}\)  and \(M>0\)  are given. Note that the function \(\psi (x) = \frac{M}{6} \Vert x \Vert ^3\)  is uniformly convex with \(\sigma _3 = \frac{M}{4}\) , but it is nonseparable and twice differentiable. Moreover, in this case \(f(x) = \langle b, x \rangle + \frac{1}{2} \langle Ax, x \rangle \)  is smooth. Hence, this problem fits into our general model (REF ) and we can use algorithm RCPG to solve it. Moreover, this problem satisfies Assumption REF , as we will see later. Therefore we can also use the algorithm RCGD with Stepsize Choice 1 (i.e., equation (REF )) for solving the problem (REF ). We compare our two algorithms with the algorithms proposed in [10]} and [1]} for the same problem. In the simulations we use the stopping criteria:

\(\Vert \nabla F(x_{k})\Vert  \le 10^{-2}.\vspace*{-5.69046pt}\) 
In Tables REF  and REF , “**" means that the corresponding algorithm needs more than 5 hours to solve the problem. For the symmetric matrix \(A\) , we consider the eigenvalues of \(A\)  ordered as \(\lambda _{1}(A) \ge \cdots \ge \lambda _{n}(A)\) .
Implementation details for RCPG algorithm:
Note that at each iteration of RCPG for solving problem (REF ) we need to solve a subproblem of the form:
\(d_{k} = \arg \min _{d \in \mathbb {R}^{n_{i_{k}}}} \langle U_{i_{k}}^{T}\nabla f(x_{k}), d \rangle + \frac{H_{f,U_{i_k}}}{2} \Vert d\Vert ^2 + \frac{M}{6} \Vert x_{k} + U_{i_{k}}d\Vert ^3.\) 
As proved in [3]}, solving the previous subproblem is equivalent to finding a root of the following fourth order equation:

\(&& \dfrac{M^{2}}{4} \mu ^{4} + H_{f,U_{i_k}}M \mu ^{3} + \left(H_{f,U_{i_k}}^{2} - \dfrac{M^{2}}{4} \sum _{j \ne i_{k}} \Vert x_{k}^{(j)}\Vert ^{2} \right) \mu ^{2} - H_{f,U_{i_k}}M \sum _{j \ne i_{k}} \Vert x_{k}^{(j)}\Vert ^{2} \mu \nonumber \\&& - \Vert H_{f,U_{i_k}}x_{k}^{(i_{k})} - (U_{i_{k}}U_{i_{k}}^{T}\nabla f(x))_{i_{k}}\Vert ^{2} - H_{f,U_{i_k}}^2 \sum _{j \ne i_{k}}\Vert x_{k}^{(j)}\Vert ^{2} = 0,\vspace*{-2.84544pt}\) 
where \(x_{k} = (x_{k}^{(1)},\cdots ,x_{k}^{(n)})^{T}\) , compute a positive root \(\mu _k\)  and then for update use
\(d_{k} = -\dfrac{2U_{i_{k}}^{T}\nabla f(x_{k}) + \mu _k M U_{i_{k}}^{T}x_{k}}{2H_{f,U}+ \mu M}\) . In our implementations \(N=n\) , i.e., we update a coordinate per iteration. Moreover, we take \(H_{f,U_{i_k}}= |U^{T}_{i_k}AU_{i_k}|\) .
Implementation details for RCGD algorithm:
Note that the Hessian of \(\psi \) , \(\nabla ^2 \psi (x) = \dfrac{M}{2}\dfrac{xx^{T}}{\Vert x\Vert } + \dfrac{M}{2} \Vert x\Vert I_{n}\) , satisfies the following inequality \(\Vert U_{i_{k}}^{T}\nabla ^2 \psi (x)U_{i_{k}}\Vert  \le M \Vert x\Vert \) . Thus, Assumption REF [A.4] holds with \(p=1\)  and \(H_{\psi }= M\) . Moreover, Assumption REF [A.5] holds with \(L_{\psi } = M\) , see [13]}. Therefore, we can apply the RCGD method, with \(H_{F_{k}}\)  given by the Stepsize Choice 1 (i.e., equation (REF )), for solving the problem (REF ). Note that according to the Stepsize Choice 1 we need to solve the following second order equation in each iteration:

\(\dfrac{M}{6} \alpha ^{2} + \left( \dfrac{M}{2} \Vert x_{k}\Vert  + H_{f,U_{i_k}}\right) \alpha - \Vert U_{i_{k}}^{T} \nabla F(x_{k})\Vert  = 0,\) 
compute a positive root \(\alpha _k\)  and then take
\(H_{F_{k}}= \frac{M}{2}\Vert x_{k}\Vert  + \frac{M}{6} \alpha _{k} + H_{f,U_{i_k}}\) . In RCGD-1 we take \(H_{f,U_{i_k}}= 0.51 \cdot \Vert U^{T}_{i_k}AU_{i_k}\Vert \) , while in RCGD-2 we choose \(H_{f,U_{i_k}}= \Vert U^{T}_{i_k}AU_{i_k}\Vert \) . In both cases, we implement RCGD with the number of blocks \(N=n\)  (i.e., updating one coordinate per iteration) and \(N=1\)  (i.e., a full gradient descent method).
Implementation details for algorithms in [10]} and [1]}:
We compare our algorithms RCPG and RCGD with the methods proposed in [10]} and [1]} for the same problem (REF ). Note that, since RCPG with N=1 recovers Algorithm (4.8) in [1]} (initially developed for convex problems), now with our results we can also apply this method to nonconvex problems (REF ). Recall that the update rule in [10]} is given by:

\(x_{k+1} = (I - \eta A - \dfrac{M}{2}\eta \Vert x_{k}\Vert I)x_{k} - \eta b,\) 
with \(0 < \eta \le \dfrac{1}{4\Vert A\Vert  + 2MR}\)  and \(R = \dfrac{\Vert A\Vert }{M} + \sqrt{\dfrac{\Vert A\Vert ^2}{M^2} + \dfrac{2\Vert b\Vert }{M}}\) . Moreover, the update rule in [1]} is given by:

\(x_{k+1} = \dfrac{2}{2H + M \mu } (Hx_{k} -Ax_{k}-b),\) 
with \(\Vert A\Vert  \le H\)  and \(\mu \ge 0\)  taken as the solution of the second order equation:

\(\dfrac{M}{2}\mu ^2 + H \mu - \Vert Hx_{k} -Ax_{k}-b\Vert  = 0.\vspace*{-5.69046pt}\) 
In our implementations we use the parameters \(\eta = 1/(4\Vert A\Vert  + 2MR)\)  and \(H = \Vert A\Vert \) .
In the first set of tests, the vector \(b\in \mathbb {R}^{n}\)  was generated from a standard normal distribution \(\mathcal {N}(0,1)\)  and the matrix \(A \in \mathbb {R}^{n \times n}\)  was generated as \(A = Q^{T}BQ\) , where \(Q \in \mathbb {R}^{n \times n}\)  is an orthogonal matrix and \(B \in \mathbb {R}^{n \times n}\)  is a diagonal matrix. Following [10]}, the starting point in the first set of tests is chosen as:

\(x_{0} = -r\dfrac{b}{\Vert b\Vert }, \text{ with } r = -\dfrac{b^{T}Ab}{M\Vert b\Vert ^2} + \sqrt{\left( \dfrac{b^{T}Ab}{M\Vert b\Vert ^2}\right)^2 + \dfrac{2\Vert b\Vert }{M}}.\) 
The results are presented in Table REF , reporting the number of full iterations (ITER) and CPU time in seconds (CPU) for each algorithm. As one can see from Table REF , RCGD with \(N=n\)  has a better performance than RCPG and algorithms in [10]} and [1]}. Moreover, for \(H_{f,U_{i_k}}= 0.51 \cdot \Vert U^{T}_{k}AU_{k}\Vert \)  the performance is further improved.
| c| c | c| c| c | c | c | c |
8|c|\(B =\)  diag\((10^4,1,\cdots ,1)\)
2|c|n  3|c|\(10^3\)   3|c|\(10^4\)
2|c|M  1  0.1  0.01  1  0.1  0.01
1* RCPG (N=n)  ITER  46  237  471  18  18  34
 CPU  10.1  53.9  55.4  16.7  21  29
1*RCGD-1 (N=n)  ITER  37  142  257  17  19  39
 CPU  5.3  21.1  17.4  14.7  19.1  31.8
1*RCGD-2 (N=n)  ITER  46  233  472  17  21  33
 CPU  6.4  34.1  36.4  14.4  21  26.6
1*RCGD-1 (N=1)  ITER  3315  15963  32915  2953  6544  19312
 CPU  5.35  25.55  57.51  125.4  449.7  766.7
1*RCGD-2 (N=1)  ITER  6499  31301  64542  5789  12831  37868
 CPU  10.5  49.5  117.5  260.5  885.9  1503.6
1*[10]}  ITER  51989  250414  516356  46309  102648  302955
 CPU  83.4  398.6  879.8  2007  7102.1  16157
1*[1]}  ITER  6501  31304  64543  5793  12833  37870
 CPU  10.6  50.1  103.6  259.8  886.3  1504.9
8|c| \(B =\)  diag(\(10^4\) ,randn(n-1,1)).
2|c|n  3|c|\(10^3\)   3|c|\(10^4\)
2|c|M  1  0.1  0.01  1  0.1  0.01
1* RCPG (N=n)  ITER  208  667  595  18  100  100
 CPU  34.5  96.6  86.7  18.5  105.7  96.2
1*RCGD-1 (N=n)  ITER  92  359  360  17  90  86
 CPU  14.2  31.7  31.5  16.1  84.8  66.9
1*RCGD-2 (N=n)  ITER  170  553  679  19  88  123
 CPU  27.9  48.5  59.8  18  85.9  112.2
1*RCGD-1 (N=1)  ITER  17692  236203  218380  6725  88532  104002
 CPU  83.2  397.7  300.3  465.1  5941.9  4954.9
1*RCGD-2 (N=1)  ITER  34677  463002  428077  13180  173520  203852
 CPU  78.3  777.9  585.9  903.2  11665  13723
1*[10]}  ITER  277315  3702840  3423626  105379
 CPU  1251.4  6560.6  4802.9  7121.2  **  **
1*[1]}  ITER  34678  463002  428077  13180  173520  203852
 CPU  156.9  834.3  722.9  901.2  12250  14245
Full iterations (ITER) and CPU time in seconds (CPU) for algorithms RCPG, RCGD, [10]} and [1]} for cubic Newton subproblem.

In the second set of experiments we want to find the smallest eigenvalue of an indefinite matrix. As proved in [10]}, if a matrix \(A\)  has at least one negative eigenvalue, we can use formulation (REF ) with \(b = 0\)  to find the smallest eigenvalue. We compare our two algorithms with the algorithm from [1]} and the power method. We consider matrices \(A\)  from University of Florida Sparse Matrix Collection [32]} and also matrices generated randomly (i.e., \(A = Q^{T}BQ\) , with \(Q\)  orthogonal and \(B \in \mathbb {R}^{n \times n}\)  diagonal). The starting point \(x_{0}\)  was generated from a standard normal distribution \(\mathcal {N}(0,1)\) . Table REF  shows the number of full iterations (ITER), CPU time in seconds (CPU) and the eigenvalue found by each method (EIG). As one can see, RCGD method with \(H_{f,U_{i_k}}= 0.51 \cdot \Vert U^{T}_{k}AU_{k}\Vert \)  has the best performance. Moreover, coordinate descent methods are faster on random data. Finally, Tables REF  and REF  show that coordinate descent methods perform better when the gap \(\lambda _{1}(A) - \lambda _{2}(A)\)  is large.
| c | c| c| c| c | c |
2|c|Group  IPSO  VDOL  2|c|Arenas
2|c|Name  HTC 336 4438  hangGlider 4  PGPgiantcompo  email
2|c|n  226340  15561  10680  1133
1* RCPG (N=n)
 ITER   795  106  241
 CPU  **  1147.7  92.4  13.7
 EIG   -238.8073  -12.0607  -8.4598
1*RCGD-1 (N=n)
 ITER   597  108  332
 CPU  **  653.9  58.6  5.6
 EIG   -238.8073  -12.0608  -8.4598
1*RCGD-2 (N=n)
 ITER   884  108  295
 CPU  **  955.7  58.6  4.7
 EIG   -238.8073  -12.0607  -8.4598
1*RCGD-1 (N=1)
ITER  1168578  33535  275  1128
 CPU  6401.2  8.7  0.08  0.08
 EIG  -1.0068  -238.8073  -12.0607  -8.4598
1*RCGD-2 (N=1)
 ITER  2301606  65389  447  1732
 CPU  12646  15.5  0.13  0.09
 EIG  -1.0067  -238.8073  -12.0607  -8.4598
1*[1]}
 ITER  2301609  65389  446  1731
 CPU  13107  16.2  0.13  0.1
 EIG  -1.0067  -238.8073  -12.0607  -8.4598
1*Power Method
 ITER  1531779  39852  686  2572
crit = \(10^{-7}\)   CPU  11143  10.8  0.18  0.18
 EIG  -1.0271  -238.8073  -12.0607  -8.4598
2|c| Type of Matrix B  2c\(B =\)  diag\((10^4,-\text{rand}(n-1,1))\)   2|c|\(B =\)  diag\((10^4,\text{randn}(n-1,1))\)
2|c| n  \(10^3\)   \(10^4\)   \(10^3\)   \(10^4\)
2|c| Smallest Eigenvalue  -0.9995  -1  -3.2459  -3.5934
1* RCPG (N=n)
 ITER  2767  290  223  134
 CPU  335.5  618.4  62.8  110.9
 EIG  -0.9980  -0.9968 -3.2458  -3.5934
1*RCGD-1 (N=n)
 ITER  1016  188  143  154
CPU  73.1  400.9  13.6  124.5
 EIG  -0.9984  -0.9963  -3.2459  -3.5933
1*RCGD-2 (N=n)
 ITER  2012  294  258  244
 CPU  144.7  639.3  24.3  195.8
 EIG  -0.9985  -0.9964  -3.2459  -3.5934
1*RCGD-1 (N=1)
 ITER  471907   71269  158476
 CPU  561.5  **  314.5  6432
 EIG  -0.9950   -3.2459  -3.5933
1*RCGD-2 (N=1)
 ITER  925220   139702  310633
 CPU 1101.4  **  622.8  14183
 EIG  -0.9950   -3.2459  -3.5933
1*[1]}
 ITER  925220   139702
 CPU  1210.1  ** 598.5  **
 EIG  -0.9950   -3.2459
1*Power Method
 ITER    148562
crit = \(10^{-7}\)   CPU  **  **  1147.7  **
 EIG    -3.2459
Full iterations (ITER), CPU time in seconds (CPU) and eigenvalue (EIG) found by algorithms RCPG, RCGD, Power Method and [1]} for the eigenvalue problem.

Matrix factorization
Finally, we consider the penalized orthogonal matrix factorization problem, see also [8]}:
\(\min _{(W,V)} F(W,V) = \min _{(W,V)} \dfrac{1}{2} \Vert  X - WV\Vert ^{2}_{F} + \dfrac{ \lambda }{2} \Vert I-VV^{T}\Vert ^2_{F}, \) 
with \(W \in \mathbb {R}^{m\times r}\)  and \(V \in \mathbb {R}^{r \times n}\) . Let us define:
\(f(W,V) = \dfrac{1}{2} \Vert  X - WV\Vert ^{2}_{F} \quad \text{ and } \quad \psi (W,V) = \dfrac{ \lambda }{2} \Vert I-VV^{T}\Vert ^2_{F}.\) 
Then, one can easily compute:
\(\nabla _{W} f(W,V) = WVV^{T} - XV^{T} \;\; \text{ and } \;\; \nabla ^{2}_{WW} f(W,V)Z = ZVV^{T}.\) 
Thus, \(\nabla f\)  is Lipschitz continuous w.r.t. \(W\) , with constant \(L_{1}(V) = \Vert VV^{T}\Vert _{F}\) . Similarly, one has:
\(\nabla _{V} f(W,V) = W^{T}WV - W^{T}X \text{ and } \nabla ^{2}_{VV} f(W,V)Z = W^{T}WZ.\) 
Therefore, \(\nabla f\)  is also Lipschitz continuous w.r.t. \(V\) , with constant Lipschitz \(L_{2}(W) = \Vert W^{T}W\Vert _{F}\) . On the other hand, \(\nabla _{V} \psi (W,V) = 2 \lambda (VV^{T}V - V)\)  and thus
\(\nabla ^2_{VV} \psi (W,V)Z = 2 \lambda (ZV^{T}V + VZ^{T}V + VV^{T}Z - Z).\) 
Therefore, we get the following bound on the Hessian:
\(\langle Z, \nabla ^2_{V} \psi (W,V)Z \rangle = \langle Z, 2 \lambda (ZV^{T}V + VZ^{T}V + VV^{T}Z - Z) \rangle \le 6\lambda \Vert Z\Vert _{F}^{2} \Vert V\Vert _{F}^{2}.\) 
This shows that \( \nabla ^2_{V} \psi (\cdot )\)  satisfies Assumption REF [A.4], with \(p=2\)  and \(H_{\psi } = 6\lambda \) . Note that if we assume that there exist \(\bar{L}_{1}, \bar{L}_{2} > 0 \)  such that \(L_{1}(V) \le \bar{L}_{1}\)  and \(L_{2}(W) \le \bar{L}_{2}\) , then Lemmas REF  and REF  are still valid.
Therefore, we can solve problem (REF ) using algorithm RCGD with Stepsize Choice 2 (i.e., equation (REF )) to update \(V\) . Moreover, since \(\nabla F\)  is Lipschitz continuous w.r.t. \(W\) , we can use algorithm RCGD to also update \(W\) . Thus, the iterations of algorithm RCGD are given by:
\(W_{k+1} &=& W_{k} - \dfrac{1}{H_{f,W}(V_{k})}(W_{k}V_{k}V_{k}^{T} - XV_{k}^{T}), \\V_{k+1} &=& V_{k} - \dfrac{1}{H_{F_{k}}}\left( W_{k+1}^{T}W_{k+1}V_{k} - W_{k+1}^{T}X + 2 \lambda (V_{k}V^{T}_{k}V_{k} - V_{k})\right),\) 
with \(H_{f,W}(V_{k}) > \dfrac{L_{1}(V_{k})}{2}\) , \(H_{f,V}(W_{k+1}) > \dfrac{L_{2}(W_{k+1})}{2}\) , \(H_{F_{k}}= 12 \lambda \Vert V_{k}\Vert _{F}^2 + 12\lambda \alpha _{k}^2 + H_{f,V}(W_{k+1})\)  and \(\alpha _{k}\)  is the positive root of the following third order equation:
\(12 \lambda \alpha ^{3} + \left( 12\lambda \Vert V_{k}\Vert _{F}^2 + H_{f,V}(W_{k+1})\right) \alpha - \Vert \nabla _{V} f(W_{k+1},V_{k}) +\nabla _{V} \psi (W_{k+1},V_{k}) \Vert _{F} = 0.\) 
In our experiments, in RCGD-1 we take \(H_{f,W}(V_{k}) = 0.51 \cdot L_{1}(V_{k})\)  and \(H_{f,V}(W_{k+1}) = 0.51 \cdot L_{2}(W_{k+1})\) , while in RCGD-2 we take \(H_{f,W}(V_{k}) = L_{1}(V_{k})\)  and \(H_{f,V}(W_{k+1}) = L_{2}(W_{k+1})\) . We compare our RCGD algorithm with the algorithm BMM proposed in [37]}. For problem (REF ), BMM is a Bregman gradient descent method having computational cost per iteration comparable to our method. For numerical tests, we consider SalinasA and Indian Pines data sets from [38]}. Each row of matrix \(X\)  is a vectorized image at a given band of the data set. Each image is normalized to \([-1,1]\) . The starting matrix \(W_{0}\)  is generated from a standard normal distribution \(\mathcal {N}(0,1)\)  and the matrix \(V_{0}\)  is generated with orthogonal rows. Moreover, we take \(\lambda = 1000\)  and the dimension \(r\)  is taken as in [38]} (i.e., in SalinasA we take \(r=6\)  and in Indian Pines we choose \(r = 16\) ). We run all the algorithms for 100s. The results are displayed in Figures REF  (SalinasA) and REF  (Indian Pines), where we plot the evolution of function values (left) and the orthogonality error \(O_{\text{error}} = \Vert I - V_{k}V_{k}^{T}\Vert _{F}\)  (right) along time. One can see that in terms of function values RCGD is competitive with the algorithm BMM. However, our algorithm RCGD identifies orthogonality faster than BMM.
<FIGURE><FIGURE>
Conclusions
In this paper we have considered composite problems having the objective function formed as a sum of two terms, one smooth and the other twice differentiable, both possibly nonconvex and nonseparable. We have proposed two algorithms, a random coordinate proximal gradient method and a random coordinate gradient descent method, respectively. For the second algorithm we have designed several adaptive stepsize strategies which guarantee descent. For both algorithms we derived convergence bounds in both convex and nonconvex settings. Preliminary numerical results confirm the efficiency of our algorithms on real applications.
Acknowledgements.
This work has been supported by: ITN-ETN project TraDE-OPT funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 861137; NO Grants 2014-2021, under project ELO-Hyp, contract no. 24/2020.

Appendix
Proof of Lemma  REF
Notice that the sequence \(\left(\Delta _{k}^{\epsilon }\right) _{k\ge 0}\)  defined by
\(\Delta _{k}^{\epsilon } = \left\lbrace \begin{array}{ll} \Delta _{k}\;\text{ if } \; \Delta _{k} \ge \epsilon , \quad \text{satisfies} \quad \Delta _{k}^{\epsilon } \le \epsilon \iff \Delta _{k} \le \epsilon \quad \forall k \ge 0. \\0 \; \text{ otherwise,}\end{array}\right.\vspace*{-5.69046pt}\) 
Therefore, from Markov inequality, we have
\(\mathbb {P}\left[\Delta _{k} > \epsilon \right] = \mathbb {P}\left[ \Delta _{k}^{\epsilon } > \epsilon \right] \le \dfrac{\mathbb {E}[\Delta _{k}^{\epsilon }]}{\epsilon }.\)  Hence, it suffices to show that
\(\theta _{K} \le \epsilon \rho \) ,
where \(\theta _{k}:=\mathbb {E}[\Delta _{k}^{\epsilon }]\) . If (REF ) holds, then
\(\mathbb {E} [\Delta _{k+1}^{\epsilon } | \Delta _{k}^{\epsilon }] \le \Delta _{k}^{\epsilon } - \left( \Delta _{k}^{\epsilon }\right)^{\zeta + 1}, \quad \mathbb {E} [\Delta _{k+1}^{\epsilon } | \Delta _{k}^{\epsilon }] \le \left( 1 - \epsilon ^{\zeta }\right) \Delta _{k}^{\epsilon }.\) 
Taking expectation and using convexity of \(t \rightarrow t^{\zeta + 1}\)  for \(t\ge 0\) , we obtain \(\theta _{k+1} \le \theta _{k} - \theta _{k}^{\zeta +1} \)  and \(\theta _{k+1} \le \left( 1 - \epsilon ^{\zeta }\right) \theta _{k} \) . Using now the inequality (28) of Lemma 9 in [3]}, we get \(k\zeta \le \theta _{k}^{-\zeta } - \theta _{0}^{-\zeta }\) . Therefore, if we let \(k_{1} \ge \dfrac{1}{\zeta }\left(\dfrac{1}{\epsilon ^{\zeta }} - \dfrac{1}{ \Delta _{0}^{\zeta }}\right)\) , we obtain \(\theta _{k_{1}} \le \epsilon \) . Finally, letting, \(k_{2} \ge \dfrac{1}{\epsilon ^{ \zeta }}\log \dfrac{1}{\rho }\) , we have:
\(\theta _{K} \le \theta _{k_{1} + k_{2}} \le \left( 1 - \epsilon ^{\zeta }\right)^{k_{2}} \theta _{k_1} \le \left( (1-\epsilon ^{\zeta })^{\frac{1}{\epsilon ^{ \zeta }}}\right)^{\log \frac{1}{\rho }} \epsilon \le \left( e^{-1} \right)^{\log \frac{1}{\rho }} \epsilon = \epsilon \rho ,\) 
which proves our statement.
