Update History

1. [2023.12.02] Problem 2 (4): correction: $\sum_{t=1}^T \max_{\mathbf{x} \in \mathcal{X}}\|{\color{red}\nabla} c_t(\mathbf{x})\|_2^2 \leq C_T$.

2. [2023.12.02] Problem 3 (4): First prove that:

   $\langle F_t(\mathbf{z}_t^\star), \mathbf{z}_t^\star - \mathbf{z}\rangle \leq \frac{1}{2\eta}\left(\|\mathbf{z} - {\color{red}\hat{\mathbf{z}}_{t-1}}\|_2^2 - \|\mathbf{z} - {\color{red}\hat{\mathbf{z}}_t}\|_2^2 + 2D \|\mathbf{z}_t^\star - \hat{\mathbf{z}}_t\|_2\right)$

3. [2023.12.03] Problem 1 (2): Correct definition:

   $\|A\|_{\infty, 1} \triangleq \max_{{\color{red}\mathbf{x} \in \mathbb{R}^d, \mathbf{x}\neq \boldsymbol{0}}} \|A\mathbf{x}\|_{\infty}/\|{\color{red}\mathbf{x}}\|_1$

4. [2023.12.04] Problem 4 (1): correction: $\sum_{t=1}^T\left\langle\boldsymbol{p}_t, \widehat{\ell}_t\right\rangle-\sum_{t=1}^T\left\langle\boldsymbol{p}, \widehat{\ell}_t\right\rangle {\color{red}\leq} \underbrace{\frac{\psi(\boldsymbol{p})-\psi\left(\boldsymbol{p}_1\right)}{\eta}}_{\text {range term }}+\underbrace{\sum_{t=1}^T\left(F_t\left(\boldsymbol{p}_t\right)-F_{t+1}\left(\boldsymbol{p}_{t+1}\right)+\left\langle\boldsymbol{p}_t, \widehat{\ell}_t\right\rangle\right)}_{\text {stability term }}$

5. [2023.12.05] Problem 3 (3) correction & typos: $\mathbf{v}_t^{(k)} = \Pi_{\mathcal{Z}}\left[\mathbf{z}_t - {\color{red}\eta}{} F(\mathbf{v}_t^{(k-1)})\right], \quad \|{\color{red}\mathbf{v}_t^{(K)}}-\mathbf{z}_{t+1}\|$

6. [2023.12.08] Problem 1: we assume the property of $A$ throughout the problem.

7. [2023.12.14] Problem 4: $\sum_{t=1}^T\left\langle\boldsymbol{p}_t-\boldsymbol{p}_{t+1}, \widehat{\ell}_t\right\rangle-\frac{1}{\eta} \mathcal{D}_\psi\left(\boldsymbol{p}_{t+1}, \boldsymbol{p}_t\right) \leq \frac{\eta}{2} \sum_{t=1}^T\left\|\widehat{\ell}_t\right\|_{\nabla^{-2} \psi\left(\boldsymbol{p}_t\right)}^{\color{red} 2}$

8. [2023.12.14] Problem 4: In the Hint: $\boldsymbol{q}_t=\arg \max _{\boldsymbol{q} \in \mathbb{R}_{+}^K} {\color{red}\left(\boldsymbol{p}_t-\boldsymbol{q}\right)^{\top} \widehat{\boldsymbol{\ell}}_t-\frac{1}{\eta} \mathcal{D}_\psi\left(\boldsymbol{q}, \boldsymbol{p}_t\right)}$

9. [2023.12.14] Problem 4: Assume ${\color{red}\widehat{\ell}_1, \ldots, \widehat{\ell}_T \in \mathbb{R}_{+}^K}$