Proof. Clearly, \(f_i(\theta) \geq 0\) and hence \(f(\theta) \geq 0\) for all \(\theta\). Calculating the gradient and hessian for \(f_i(\theta) := \exp(-y_i \langle x_i, \theta \rangle)\), \[\begin{align} \nabla f_i(\theta) &= -\exp(-y_i \langle x_i, \theta \rangle) y_i \, x_i \\ \nabla^2 f_i(\theta) & = \exp(-y_i \langle x_i, \theta \rangle) \, y_i^2 \, x_i \, x_i^T = \exp(-y_i \langle x_i, \theta \rangle) \, x_i \, x_i^T\\ \implies \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} & \leq \exp(-y_i \langle x_i, \theta \rangle) \, \left\|x_i \, x_i^T \right\|_{p \to q} = f_i(\theta) \, \left\|x_i \right\|^{2}_{q}= \left\|u \right\|^{2}_q} \\ \left\|\nabla^2 f(\theta) \right\|_{p \to q} & \leq \frac{1}{n} \,\sum_{i = 1}^{n} \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} \leq f(\theta) \, \max_i \left\|x_i \right\|^{2}_q \end{align}\] Verifying 3 for separable data, \[\begin{align} \left\|\nabla f(\theta) \right\|_q &= \sup_{\left\|u \right\|_p \leq 1} \langle u, \nabla f(\theta) \rangle \\ & = \sup_{\left\|u \right\|_p \leq 1} \left[ \frac{1}{n} \, \left\langle -\sum_{i = 1}^{n} \exp(-y_i \langle x_i, \theta \rangle) y_i \, x_i, u \right \rangle \right] \\ & \geq \left[ \frac{1}{n} \, \left\langle -\sum_{i = 1}^{n} \exp(-y_i \langle x_i, \theta \rangle) y_i \, x_i, u \right \rangle \right]\\ \implies \left\|\nabla f(\theta) \right\|_q & \geq \left[ \frac{1}{n} \, \left\langle \sum_{i = 1}^{n} \exp(-y_i \langle x_i, \theta \rangle) y_i \, x_i, \frac{\theta^*}{\left\|\theta^* \right\|_p} \right \rangle \right] {\left\|\theta^* \right\|_p}} \\ & \geq \min_{j} \frac{y_j \, \langle x_j, \theta^* \rangle}{\left\|\theta^* \right\|_p} \, \left[ \frac{1}{n} \, \sum_{i = 1}^{n} \exp\left(-y_i \, \langle x_i, \theta \rangle \right) \right] \\ \implies \left\|\nabla f(\theta) \right\|_q & \geq \gamma_p \, f(\theta) \end{align}\] ◻

Proof. Clearly, \(f_i(\theta) \geq 0\) and hence \(f(\theta) \geq 0\) for all \(\theta\). Calculating the gradient and hessian for \(f_i(\theta) := \ln(1 + \exp(-y_i \langle x_i, \theta \rangle)\), \[\begin{align} \nabla f_i(\theta) & = \frac{-\exp(-y_i \langle x_i, \theta \rangle)}{1 + \exp(-y_i \langle\, x_i, \theta \rangle)} y_i \, x_i \quad \text{;} \quad \nabla^2 f_i(\theta) = \frac{1}{1 + \exp(-y_i \, \langle x_i, \theta \rangle)} \, \frac{\exp(-y_i \, \langle x_i, \theta \rangle)}{1 + \exp(-y_i \, \langle x_i, \theta \rangle)} \, y_i^2 \, x_i \, x_i^T \\ \end{align}\] Bounding the Hessian, \[\begin{align} \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} & \leq \left\|\frac{1}{1 + \exp(-y_i \, \langle x_i, \theta \rangle)} \, \frac{\exp(-y_i \, \langle x_i, \theta \rangle)}{1 + \exp(-y_i \, \langle x_i, \theta \rangle)} \, y_i^2 \, x_i \, x_i^T \right\|_{p \to q} \\ & = \frac{1}{1 + \exp(-y_i \, \langle x_i, \theta \rangle)} \, \frac{\exp(-y_i \, \langle x_i, \theta \rangle)}{1 + \exp(-y_i \, \langle x_i, \theta \rangle)} \, \left\|x_i \, x_i^T \right\|_{p \to q}\\ & \leq \frac{1}{1 + \exp(-y_i \, \langle x_i, \theta \rangle)} \, \frac{\exp(-y_i \, \langle x_i, \theta \rangle)}{1 + \exp(-y_i \, \langle x_i, \theta \rangle)} \left\|x_i \right\|^{2}_{q}= \left\|u \right\|^{2}_q} \\ & \leq \frac{\exp(-y_i \, \langle x_i, \theta \rangle)}{1 + \exp(-y_i \, \langle x_i, \theta \rangle)} \, \left\|x_i \right\|^{2}_{q} {1 + e^x} \leq 1} \\ & \leq \ln(1 + \exp(-y_i \, \langle x_i, \theta \rangle)) \, \left\|x_i \right\|^{2}_{q} {1+x} \leq \ln(1+x)} \\ \implies \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} & \leq f_i(\theta) \, \left\|x_i \right\|^{2}_{q} \\ \implies \left\|\nabla^2 f(\theta) \right\|_{p \to q} & \leq \frac{1}{n} \,\sum_{i = 1}^{n} \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} \leq f(\theta) \, \max_i \left\|x_i \right\|^{2}_q \end{align}\] Verifying 3 for separable data, \[\begin{align} \left\|\nabla f(\theta) \right\|_q &= \sup_{\left\|u \right\|_p \leq 1} \langle u, \nabla f(\theta) \rangle \\ & = \sup_{\left\|u \right\|_p \leq 1} \left[ \frac{1}{n} \, \left\langle -\sum_{i = 1}^{n} \frac{1}{1 + \exp(y_i \langle x_i, \theta \rangle)} y_i \, x_i, u \right \rangle \right] \\ & \geq \left[ \frac{1}{n} \, \left\langle -\sum_{i = 1}^{n} \frac{1}{1 + \exp(y_i \langle x_i, \theta \rangle)} \, y_i \, x_i, u \right \rangle \right]\\ \implies \left\|\nabla f(\theta) \right\|_q & \geq \left[ \frac{1}{n} \, \left\langle \sum_{i = 1}^{n} \frac{1}{1 + \exp(y_i \langle x_i, \theta \rangle)} y_i \, x_i, \frac{\theta^*}{\left\|\theta^* \right\|_p} \right \rangle \right] {\left\|\theta^* \right\|_p}} \\ & \geq \min_{j} \frac{y_j \, \langle x_j, \theta^* \rangle}{\left\|\theta^* \right\|_p} \, \left[ \frac{1}{n} \, \sum_{i = 1}^{n} \frac{1}{1 + \exp(y_i \langle x_i, \theta \rangle)} \right] \\ \implies \left\|\nabla f(\theta) \right\|_q & \geq \gamma_p \, \left[ \frac{1}{n} \, \sum_{i = 1}^{n} \frac{1}{1 + \exp(y_i \langle x_i, \theta \rangle)} \right] \end{align}\] Case (1): If \(f(\theta) \leq \frac{\ln(2)}{n}\), then, \[\begin{align} \implies \sum_i \ln(1 + \exp(-y_i \langle x_i, \theta \rangle) ) & \leq \ln(2) \implies \ln(1 + \exp(-y_i \langle x_i, \theta \rangle) ) \leq \ln(2)\\ \implies y_i \langle x_i, \theta \rangle \geq 0 \end{align}\] Hence, all examples are classified with a positive margin. In this case, we use the following inequality, \[\begin{align} \frac{1}{1 + \exp(z)} & = \frac{\exp(-z)}{1 + \exp(-z)} \geq \frac{\exp(-z)}{2}\\ & \geq \frac{\ln(1+ \exp(-z))}{2} \end{align}\] Since \(y_i \langle x_i, \theta \rangle > 0\) for all \(i \leq [n]\), \[\begin{align} \frac{1}{1 + \exp(y_i \langle x_i, \theta \rangle)} & \geq \frac{\ln(1 + \exp(-y_i \langle x_i, \theta \rangle))}{2} \\ \implies \left\|\nabla f(\theta) \right\|_q & \geq \frac{\gamma_p}{2} \, \left[ \frac{1}{n} \, \sum_{i = 1}^{n} \ln(1 + \exp(-y_i \langle x_i, \theta \rangle)) \right] = \frac{\gamma_p}{2} \, f(\theta) \end{align}\] Case (2): On the other hand, if \(f(\theta) > \frac{\ln(2)}{n}\) and \(u_i := \exp(-y_i \, \langle x_i \theta \rangle) > 0\), then, \[\begin{align} \sum_{i = 1}^{n} \ln(1 + \exp(- y_i \langle x_i, \theta \rangle)) & > \ln(2) \implies \sum_{i = 1}^{n} u_i > \ln(2)\\ \implies \frac{1}{1 + \exp(y_i \langle x_i, \theta \rangle)} &= \frac{u_i}{1 + u_i} \geq \frac{u_i}{1 + \sum_{j = 1}^{n} u_j}\\ \implies \sum_{i = 1}^{n} \frac{1}{1 + \exp(y_i \langle x_i, \theta \rangle)} &\geq \frac{\sum_{i = 1}^{n} u_i}{1 + \sum_{j = 1}^n u_j} \geq \frac{\ln(2)}{1 + \ln(2)} {1+u} is increasing for u \geq 0} \end{align}\] Using the above lower-bound on the gradient norm, \[\begin{align} \left\|\nabla f(\theta) \right\|_q & \geq \gamma_p \, \left[ \frac{1}{n} \, \sum_{i = 1}^{n} \frac{1}{1 + \exp(y_i \langle x_i, \theta \rangle)} \right] \geq \frac{\gamma_p}{n} \, \frac{\ln(2)}{1 + \ln(2)} \geq \frac{\gamma_p}{3n} \end{align}\] ◻

Proof. Calculating the gradient, \[\begin{align} \nabla f(\theta) &= - \nabla [\langle \pi_\theta, r \rangle ] = - G_\theta \, r \quad \text{where } \quad G_\theta \in \mathbb{R}^{K \times K} = \text{diag}(\pi_\theta) - \pi_\theta \, [\pi_\theta]^T \quad \text{and} \quad G_\theta[i,j] = \frac{\partial \pi_\theta(i)}{\partial \theta_j} \nonumber\\ \implies \nabla f(\theta) &= - \text{diag}(\pi_\theta) \, r + \langle \pi_\theta, r \rangle \, \pi_\theta \implies [\nabla f(\theta)]_j = -\pi_\theta(j) \, [r_j - \langle \pi_\theta, r \rangle ] \label{eq:pg-grad-inter-1} \end{align}\tag{14}\] Calculating the Hessian, \[\begin{align} \frac{\partial^2 f}{\partial \theta_k \,\partial \theta_j} & = \frac{\partial [\nabla f(\theta)]_j}{\partial \theta_k} = -\frac{\partial}{\partial \theta_k} [ \pi_\theta(j) \, (r_j - \langle \pi_\theta, r \rangle )] \\ & = - \left[ G_{j,k} \, [r_j - \langle \pi_\theta, r \rangle] - \pi_\theta(j) \,\left(\pi_\theta(k) \, [r_k - \langle \pi_\theta, r \rangle ] \right) \right] \\ \implies \frac{\partial^2 f}{\partial \theta_k \, \partial \theta_j} & = - G_{j,k} \, [r_j - \langle \pi_\theta, r \rangle] + \pi_\theta(j) \, \pi_\theta(k) \, [r_k - \langle \pi_\theta, r \rangle ] \\ \implies \nabla^2 f(\theta) &= -\underbrace{\text{diag}(r - \langle \pi_\theta, r \rangle \, \mathbf{1})}_{K \times K} \, \underbrace{G_\theta}_{K \times K} + \underbrace{\pi_\theta}_{K \times 1} \, \underbrace{[G_\theta \, r]^T}_{1 \times K} \end{align}\] Define \(w := G_\theta r = \text{diag}(\pi_\theta) \, (r - \langle \pi_\theta, r \rangle \mathbf{1})\), and simplifying the first term, \[\begin{align} \text{diag}(r - \langle \pi_\theta, r \rangle \, \mathbf{1}) \, G_\theta &= \text{diag}(r - \langle \pi_\theta, r \rangle \, \mathbf{1}) \left(\text{diag}(\pi_\theta) - \pi_\theta \, [\pi_\theta]^T\right) \\ & = \text{diag}(\pi_\theta \circ (r - \langle \pi_\theta, r \rangle ) ) - [\pi_\theta \circ (r - \langle \pi_\theta, r \rangle )] [\pi_\theta]^T \\ & = \text{diag}(w) - w [\pi_\theta]^T \end{align}\] Combining the above relations, \[\begin{align} \nabla^2 f(\theta) &= -\text{diag}(w) + w [\pi_\theta]^T + \pi_\theta [w]^T \label{eq:pg-hessian-inter-1} \end{align}\tag{15}\]

Case 1: Consider \(p = q = 2\). In this case, \[\begin{align} \left\|\nabla^2 f(\theta) \right\|_{2 \to 2} & \leq \left\|\text{diag}(w) \right\|_{2 \to 2} + \left\|w [\pi_\theta]^T \right\|_{2 \to 2} + \left\|\pi_\theta [w]^T \right\|_{2 \to 2}\\ & \leq \left\|w \right\|_2 + 2 \, \left\|w \right\|_2 \, \left\|\pi_\theta \right\|_2 \leq 3 \, \left\|w \right\|_2\\ \implies \left\|\nabla^2 f(\theta) \right\|_{2 \to 2} & \leq 3 \, \left\|w \right\|_2 = 3 \, \left\|G_\theta r \right\| = 3 \, \left\|\nabla f(\theta) \right\|_{2} } \end{align}\] Using [6], if \(\left\|\nabla^2 f(\theta) \right\|_{2} \leq 3 \left\|\nabla f(\theta) \right\|_2\) and \(f^* = 0\), \[\begin{align} \left\|\nabla f(\theta) \right\|_2 & \leq 8 \, f(\theta) \end{align}\] Combining the above equations, \[\begin{align} \left\|\nabla^2 f(\theta) \right\|_{2 \to 2} & \leq 24 \, f(\theta) \end{align}\]

Case 2: Consider \(p = \infty, q = 1\). In this case, \[\begin{align} \left\|\nabla^2 f(\theta) \right\|_{\infty \to 1} & \leq \left\|\text{diag}(w) \right\|_{\infty \to 1} + \left\|w [\pi_\theta]^T \right\|_{\infty \to 1} + \left\|\pi_\theta [w]^T \right\|_{\infty \to 1}\\ & \leq \max_{\left\|v \right\|_\infty \leq 1} \left\|\text{diag}(w) \, v \right\| + \left\|w \right\|_{1} \max_{\left\|v \right\|_\infty \leq 1} \langle \pi_\theta, v \rangle + \max_{\left\|v \right\|_\infty \leq 1} \langle w, v \rangle \, \sum_i \pi_\theta(i) \nonumber \\ & \leq 3 \, \left\|w \right\|_{1} = 3 \, \left\|G_\theta \, r \right\|_{1}\right\|_1 = \sum_i \pi_\theta(i) = 1} \\ \implies \left\|\nabla^2 f(\theta) \right\|_{\infty \to 1} & \leq 3 \, \left\|G_\theta \, r \right\|_{1} \label{eq:pg-hessian-inter-2} \end{align}\tag{16}\] Calculating \(\left\|G_\theta \, r \right\|_{1}\), \[\begin{align} \left\|G_\theta \, r \right\|_{1} &= \sum_{a} \pi_\theta(a) \, |r(a) - \langle \pi_\theta, r \rangle | = \sum_{a} \pi_\theta(a) \, |r(a) - r(a^*) + r(a^*) - \langle \pi_\theta, r \rangle | \\ & = \sum_{a} \pi_\theta(a) \, |r(a) - r(a^*) + f(\theta)| \leq f(\theta) + \sum_{a} \pi_\theta(a) |r(a) - r(a^*)|\\ & = f(\theta) + \sum_{a} \pi_\theta(a) [r(a^*) - r(a)]\\ & = f(\theta) + (r(a^*) - \langle \pi_\theta, r \rangle \implies \left\|G_\theta \, r \right\|_{1} &\leq 2 \, f(\theta) \end{align}\] Combining the above inequality with 16 , \[\begin{align} \left\|\nabla^2 f(\theta) \right\|_{\infty \to 1} & \leq 6 \, f(\theta) \end{align}\]

Case 3: Consider \(p = 1, q = \infty\). Since \(\left\|\cdot \right\|_{1,\infty} \leq \left\|\infty,1 \right\|\), using the result for case 2 immediately gives us: \[\begin{align} \left\|\nabla^2 f(\theta) \right\|_{1 \to \infty} & \leq 6 \, f(\theta) \end{align}\]

Verifying 3, for any \(q \geq 1\), \[\begin{align} \left\|\nabla f(\theta) \right\|_q &= \left\|G_\theta \, r \right\|_q \geq \vert \pi_\theta(a^*) \, [r(a^*) - \langle \pi_\theta, r \rangle] \vert = \pi_\theta(a^*) f(\theta) \end{align}\] ◻

Proof. Clearly \(f\) satisfies 1 by construction. Moreover, for \(\theta = [\theta_1 , \theta_2 , \ldots , \theta_m] \in \mathbb{R}^{m \, D}\) where for each \(j \in [m]\), \(\theta_j \in \mathbb{R}^{D}\), \[\begin{align} f(\theta) & = \frac{1}{n} \sum_{i=1}^n g(y_i \, \Phi(\theta, x_i )) \implies \nabla f(\theta) = \frac{1}{n} \sum_{i=1}^n g'(y_i \Phi(\theta, x_i ))\, y_i\nabla \Phi(\theta, x_i ) \nonumber \\ \Phi(\theta,x) & = \sum_{j=1}^m a_j \sigma(\langle \theta_j,x\rangle) \implies \nabla \Phi(\theta,x) = [a_1 \sigma'(\langle \theta_1,x\rangle) x, a_2 \sigma'(\langle \theta_2,x\rangle) x, \ldots, a_m \sigma'(\langle \theta_m,x\rangle) x] \nonumber \\ \implies \|\nabla \Phi(\theta,x)\|_q &\leq \alpha_2 \|a\|_q \|x\|_q\label{eq:phigrad95upperbound} \end{align}\tag{17}\] \(\nabla^2 \Phi(\theta, x)\) is a \(\mathbb{R}^{m D \times m D}\) block-diagonal matrix where block \(j\) is an \(D \times D\) matrix equal to \(a_j \, \sigma''(\langle \theta_j,x\rangle) x x^{T}\). Hence, \[\begin{align} \left\|\nabla^2 \Phi(\theta, x) \right\|_{p \to q} & \leq \sum_{j = 1}^{m} \left\|a_j \, \sigma''(\langle \theta_j,x\rangle) x x^{T} \right\|_{p \to q} \leq \sum_{j = 1}^{m} |a_j| \, M \, \left\|x \right\|^{2}_q = M \, \left\|a \right\|_1 \, \left\|x \right\|^{2}_{q} \label{eq:phihess95upperbound} \end{align}\tag{18}\] Calculating the Hessian of \(f\), \[\begin{align} \nabla^2 f(\theta) &= \frac{1}{n} \, \sum_{i = 1}^{n} \left[ g'(y_i \, \Phi(\theta, x_i )) \, \nabla^2 \Phi(\theta, x_i) + g''(y_i \, \Phi(\theta, x_i )) \, [\nabla \Phi(\theta, x_i)] \, [\nabla \Phi(\theta, x_i)]^{T} \right] \\ \implies \left\|\nabla^2 f(\theta) \right\|_{p \to q} & \leq \frac{1}{n} \, \sum_{i = 1}^{n} \left[ \vert g'(y_i \, \Phi(\theta, x_i )) \vert \left\|\nabla^2 \Phi(\theta, x_i) \right\|_{p \to q} + \vert g''(y_i \, \Phi(\theta, x_i )) \vert \, \left\|[\nabla \Phi(\theta, x_i)] \, [\nabla \Phi(\theta, x_i)]^{T} \right\|_{p \to q} \right]\\ & \leq \frac{1}{n} \, \sum_{i = 1}^{n} g(y_i \, \Phi(\theta, x_i )) \, \left[c_2 \, \left\|\nabla^2 \Phi(\theta, x_i) \right\|_{p \to q} + c'_2 \left\|[\nabla \Phi(\theta, x_i)] \, [\nabla \Phi(\theta, x_i)]^{T} \right\|_{p \to q} \right]\\ & \leq \frac{1}{n} \, \sum_{i = 1}^{n} g(y_i \, \Phi(\theta, x_i )) \, \left[c_2 \, L \, \left\|a \right\|_1 \, \left\|x_i \right\|^{2}_{q} + c'_2 \, \alpha_2^2 \, \|a\|_q^2 \, \left\|x_i \right\|_q^2 \right] \\ & = \left[c_2 \, M \, \left\|a \right\|_1 + c'_2 \, \alpha_2^2 \, \|a\|_q^2 \right] \, \max_i \left\|x_i \right\|^{2}_{q} \, f(\theta) \end{align}\] Hence, \(f\) satisfies 2 with \(H_0=0\) and \(H_1 = \left[c_2 \, M \, \left\|a \right\|_1 + c'_2 \, \alpha_2^2 \, \|a\|_q^2 \right] \, \max_i \left\|x_i \right\|^{2}_{q}\).

Next, using the construction \(v_j = a_j \, w^*\) and \(v = (v_1,v_2,...) = [a_1 \, w^*, a_2 \, w^* , \ldots, a_m \, w^*]\), where \(w^*\) is the max-margin separator that satisfies \(\frac{y_i\langle x_i,w^*\rangle}{\|w^*\|_p}\geq \gamma\), we get that, \[\begin{align} \|\nabla f(\theta) \|_q &=\sup_u \, \frac{\langle -\nabla f(\theta), u\rangle}{\|u\|_p}\\ &= \sup_u\, -\frac{1}{\|u\|_p} \frac{1}{n} \sum_{i=1}^n g'(y_i \Phi(\theta, x_i ))\, y_i\, \langle\nabla \Phi(\theta, x_i ), u \rangle {n} \sum_{i} g'(y_i \Phi(\theta, x_i ))\, y_i\nabla \Phi(\theta, x_i )}\\ &\geq -\frac{1}{\|v\|_p} \frac{1}{n} \sum_{i=1}^n g'(y_i \Phi(\theta, x_i ))\, y_i\, \langle\nabla \Phi(\theta, x_i ), v \rangle \\ &= -\frac{1}{n \|v\|_p} \sum_{i=1}^n g'(y_i \Phi(\theta, x_i )) \, y_i \, \sum_{j=1}^m a_j \, \sigma'(\langle \theta_j,x_i\rangle) \, \langle x_i, v_j \ranglea_j \sigma'(\langle \theta_j,x\rangle) x}\\ &\geq \frac{1}{n \, \left\|v \right\|_p} \sum_{i=1}^n |g'(y_i \Phi(\theta, x_i )) |\, \sum_{j=1}^m a^2_j \, \sigma'(\langle \theta_j, x_i \rangle) \, \langle y_i x_i, w^* \rangle \\ & = \frac{1}{n \|a\|_p} \sum_{i=1}^n |g'(y_i \Phi(\theta, x_i )) |\, \sum_{j=1}^m a^2_j \, \sigma'(\langle \theta_j, x_i \rangle) \, \frac{ \langle y_i x_i, w^* \rangle }{\|w^*\|_p} \\ &\geq \frac{\alpha_1}{n \|a\|_p} \sum_{i=1}^n |g'(y_i \Phi(\theta, x_i )) |\, \underbrace{\sum_{j=1}^m a^2_j }_{\|a\|_2^2} \;\underbrace{ \frac{ \langle y_i x_i, w^* \rangle }{\|w^*\|_p}}_{\geq \gamma}\\ &\geq \frac{\alpha_1 \gamma \|a\|_2^2}{\|a\|_p} \frac{1}{n}\sum_{i=1}^n |g'(y_i \Phi(\theta, x_i ))| = \frac{\alpha_1 \gamma \|a\|_2^2}{\|a\|_p} \frac{1}{n}\sum_{i=1}^n -g'(y_i \Phi(\theta, x_i ))\\ &\geq \frac{\alpha_1 \gamma \|a\|_2^2 c_1}{\|a\|_p} \underbrace{\frac{1}{n}\sum_{i=1}^n g(y_i \Phi(\theta, x_i ))}_{f(\theta)}\end{align}\] Hence, \(f\) satisfies 3 with \(\mu = \frac{\alpha_1 \gamma \|a\|_2^2 c_1}{\|a\|_p}\) ◻

Proof. For the first part of the proof, note that, \[\begin{align} f_i(\theta) = \text{KL}(y^{(i)} || \pi^{(i)}_\theta) \text{ where \pi^{(i)}_\theta \in \Delta_{K} s.t. } \pi^{(i)}_\theta(c) = \frac{\exp(\langle x^{(i)}, \theta_c \rangle)}{\sum_{k = 1}^{K} \exp(\langle x^{(i)}, \theta_k \rangle)} \,, \end{align}\] where \(\theta_c \in \mathbb{R}^D\) for \(c \in [K]\) and \(\theta = [\theta_1, \theta_2, \ldots, \theta_K]\). Since \(y^{(i)}\) is a one-hot vector, let \(c_{i}\) be the index corresponding to the non-zero entry. Hence, \(y^{(i)}_{c_{i}} = 1\) and for all \(j \neq c_{i}\), \(y^{(i)}_{j} = 0\), and hence, \[\begin{align} f_i(\theta) &= -\ln\left(\pi_\theta^{(i)}(c_{i})\right) \end{align}\] The Hessian can be written as a Kronecker product of a \(K \times K\) matrix which corresponds to the Jacobian of the softmax function, and a \(d \times d\) rank-one matrix formed using the features. Specifically, \[\begin{align} \nabla^2 f_i(\theta) &= \underbrace{G^{(i)}(\theta)}_{K \times K} \,\otimes\, \underbrace{x^{(i)} [x^{(i)}]^{T}}_{d \times d} \text{ where, } G^{(i)}(\theta) := \text{diag}(\pi^i_\theta) - \pi^i_\theta \, [\pi_\theta{^{(i)}}]^T \end{align}\] Using 1 for the fixed \(\theta\), and using \(G^{(i)}\) as a shorthand for \(G^{(i)}(\theta)\), for \(q \in [1,\infty)\), \[\begin{align} \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} & \leq \left(\sum_{k,l} |G^{(i)}_{k,l}|^{q} \right)^{1/q} \, \left(\sum_{k,l} \left(x^{(i)}_{k} \, x^{(i)}_{l}\right)^{q} \right)^{1/q} \\ & = \left(\sum_{k,l} |G^{(i)}_{k,l}|^{q} \right)^{1/q} \, \left\|x^{(i)} \right\|^{2}_{q} \\ & \leq \sum_{k,l} |G^{(i)}_{k,l}| \, \left\|x^{(i)} \right\|^{2}_{q}\leq \left\|\cdot \right\|_1 for all q \geq 1} \end{align}\]

On the other hand, using 1 for \(q = \infty\), \[\begin{align} \left\|\nabla^2 f_i(\theta) \right\|_{1 \to \infty} & \leq \max_{k,l}| G^{(i)}_{k,l} | \, (\max_{k} | x^{(i)}_k |)^{2} \leq \sum_{k,l} |G^{(i)}_{k,l}| \, \left\|x^{(i)} \right\|^{2}_\infty \end{align}\] Hence, in both cases, \[\begin{align} \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} & \leq \sum_{k,l} |G^{(i)}_{k,l}| \, \left\|x^{(i)} \right\|^{2}_q \end{align}\]

Bounding \(\sum_{k,l} |G^{(i)}_{k,l}|\), if \(z := \pi_\theta^{(i)}\), then, \[\begin{align} \sum_{k,l} |G^{(i)}_{k,l}| & = \sum_k z_k \, (1-z_k) - \sum_{l \neq k} z_l \, z_k = 2 \, \sum_k z_k \, (1-z_k)z_l = 1 - z_k} \\ & = 2 \, (1 - \left\|z \right\|_2^2) \leq 2 \, (1 - [z(c_{i})]^2)\leq 1 - [p(c)]^2} \nonumber \\ & \leq 4 \, \left(1 - z(c_{i}) \right)\nonumber \\ & \leq 4 \, \ln\left(\frac{1}{z(c_{i})} \right)\nonumber \\ & = 4 \, \text{KL}(y^{(i)} || \pi_\theta^{(i)})is a one-hot vector and z = \pi_\theta^{(i)}} \\ & = 4 \, f_i(\theta) \end{align}\] Combining the above inequalities, \[\begin{align} \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} & \leq 4 \, \left\|x^{(i)} \right\|^{2}_q \, f_i(\theta) \\ \implies \left\|\nabla^2 f(\theta) \right\|_{p \to q} & \leq \frac{1}{n} \,\sum_{i = 1}^{n} \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} \leq 4 \, \max_i\, \left\|x_i \right\|^{2}_q \, f(\theta) \end{align}\] This proves 2. Note that, for all \(i \in [n]\) and \(j \in [K]\), if \(\theta^* = [\theta_1^*, \theta_2^*, \ldots, \theta^*_K]\) with \(\left\|\theta^* \right\|_p \leq 1\) is the max-margin solution, then, \[\begin{align} \frac{\partial f_i(\theta)}{\partial \theta_{j}} & = \left( \pi_\theta^{(i)}(j) - {\mathcal{I}}\{j = c_{i} \} \right) x^{(i)} \\ \implies -\langle \theta^*, \nabla f_i(\theta) \rangle & = \sum_{j = 1}^{K} \left( {\mathcal{I}}\{j = c_{i} \} - \pi_\theta^{(i)}(j) \right) \langle x^{(i)}, \theta^*_j \rangle = \langle x^{(i)}, \theta^*_{c_{i}} \rangle - \sum_{j = 1}^{K} \pi_\theta^{(i)}(j) \, \langle x^{(i)}, \theta^*_j \rangle \\ & = \sum_{j = 1}^{K} \pi_\theta^{(i)}(j) \left[ \langle x^{(i)}, \theta^*_{c_{i}} - \theta^*_j \rangle \right] = \sum_{j = 1, j \neq c_{i}}^{K} \pi_\theta^{(i)}(j) \left[ \langle x^{(i)}, \theta^*_{c_{i}} - \theta^*_j \rangle \right] \\ & \geq \gamma_p \, \sum_{j = 1, j \neq c_{i}}^{K} \pi_\theta^{(i)}(j)\\ \implies -\langle \theta^*, \nabla f_i(\theta) \rangle & \geq \gamma_p \, \left(1 - \pi_\theta^{(i)}(c_{i}) \right) \\ \implies -\langle \theta^*, \nabla f(\theta) \rangle & \geq \frac{\gamma_p}{n} \, \sum_{i = 1}^{n} \left(1 - \pi_\theta^{(i)}(c_{i}) \right) \\ \intertext{By definition of the dual norm and using the above relation,} \left\|\nabla f(\theta) \right\|_{q} &= \max_{\left\|v \right\|_p \leq 1} \langle v, -\nabla f(\theta) \rangle \geq \frac{\gamma_p}{n} \, \sum_{i = 1}^{n} \left(1 - \pi_\theta^{(i)}(c_{i}) \right) \end{align}\] We will now relate \(\pi_\theta^{(i)}(c_{i})\) to the loss.

Case (i): If \(f(\theta) \leq \frac{\ln(2)}{n}\), then for all \(i \in [n]\), \[\begin{align} f_i(\theta) & \leq \ln(2) \implies \pi_\theta^{(i)}(c_{i}) \geq \frac{1}{2} \implies 1 - \pi_\theta^{(i)}(c_{i}) \geq \frac{-\ln(\pi_\theta^{(i)}(c_{i}))}{2} = \frac{f_i(\theta)}{2} {2},1\right], 1 - u \geq -\frac{\ln(u)}{2}} \\ \implies \left\|\nabla f(\theta) \right\|_{q} & \geq \frac{\gamma_p}{n} \, \sum_{i = 1}^{n} \left(1 - \pi_\theta^{(i)}(c_{i}) \right) \geq \frac{\gamma_p}{2} \, f(\theta) \end{align}\]

Case (ii): If \(f(\theta) > \frac{\ln(2)}{n}\), \[\begin{align} \sum_{i = 1}^{n} f_i(\theta) \geq \ln(2) \implies - \sum_{i = 1}^{n} \ln(\pi_\theta^{(i)}(c_i)) \geq \ln(2) & \implies \pi_\theta^{(1)}(c_1) \times \pi_\theta^{(2)}(c_2) \times \ldots \times \pi_\theta^{(n)}(c_n) \leq \frac{1}{2} \\ \implies 1 - \sum_{i = 1}^{n} [1 - \pi_\theta^{(i)}(c_i)] & \leq \frac{1}{2} \implies \sum_{i = 1}^{n} [1 - \pi_\theta^{(i)}(c_i)] \geq \frac{1}{2} ^{n} p_i \geq 1 - \sum_{i = 1}^{n} [1 - p_i]} \\ \implies \left\|\nabla f(\theta) \right\|_{q} \geq \frac{\gamma_p}{n} \, \sum_{i = 1}^{n} \left(1 - \pi_\theta^{(i)}(c_{i}) \right) & \geq \frac{\gamma_p}{2 \, n} \end{align}\] ◻

Proof. Clearly, \(f_i(\theta) \geq 0\) and hence \(f(\theta) \geq 0\) for all \(\theta\). \(f(\theta)\) is a finite-sum objective. Calculating the gradient and hessian for \(f_i(\theta) = \frac{1}{2} \, \left(\pi_i(\theta) - y_i \right)^2\), \[\begin{align} \nabla f_i(\theta) &= \left(\pi_i(\theta) - y_i \right) \, \frac{1}{1 + \exp(-\langle x_i, \theta \rangle)} \, \frac{\exp(-\langle x_i, \theta \rangle)}{1 + \exp(-\langle x_i, \theta \rangle)} \, x_i = \left(\pi_i(\theta) - y_i \right) \, \pi_i(\theta) \, (1 - \pi_i(\theta)) \, x_i \\ \nabla^2 f_i(\theta) &= [1 - 2 \, \pi_i(\theta)] \, \pi_i(\theta) \, [1 - \pi_i(\theta)] \, [\pi_i(\theta) - y_i] \, x_i \, x_i^T + [\pi_i(\theta)]^2 \, [1 - \pi_i(\theta)]^2 \, x_i \, x_i^T \\ \implies \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} &= \underbrace{\left\vert[1 - 2 \, \pi_i(\theta)] \, \pi_i(\theta) \, [1 - \pi_i(\theta)] \, [\pi_i(\theta) - y_i] + [\pi_i(\theta)]^2 \, [1 - \pi_i(\theta)]^2 \right\vert}_{:= (*)} \, \left\|x_i \right\|^{2}_{q}= \left\|u \right\|^{2}_q} \end{align}\] To bound (*), define \(a_i := \pi_i(\theta) - y_i\) and \(b_i := \pi_i(\theta) \, [1 - \pi_i(\theta)]\), \[\begin{align} (*) &= \left\vert \, [1 - 2 \, \pi_i(\theta)] \, a_i \, b_i + b_i^2 \right\vert \leq \underbrace{|1 - 2 \pi_i(\theta)|}_{\leq 1} \, |a_i| \underbrace{|b_i|}_{\leq \frac{1}{4}} + \underbrace{|b_i|^2}_{\leq \frac{1}{16}} \\ & \leq \frac{|a_i|}{4} + \frac{1}{16} \leq \frac{a_i^2}{8} + \frac{1}{8} + \frac{1}{16} {2}} \\ & = \frac{a_i^2}{8} + \frac{3}{16} \\ (*) & \leq \frac{1}{4} \, \frac{1}{2} \, \left(\pi_i(\theta) - y_i \right)^2 + \frac{3}{16} = \frac{1}{4} \, f_i(\theta) + \frac{3}{16} \\ \implies \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} & \leq \frac{1}{4} \, \left\|x_i \right\|^{2}_{q}f_i(\theta) + \frac{3}{16} \, \left\|x_i \right\|^{2}_{q} \\ \implies \left\|\nabla^2 f(\theta) \right\|_{p \to q} & \leq \frac{1}{n} \,\sum_{i = 1}^{n} \left\|\nabla^2 f_i(\theta) \right\|_{p \to q} \leq \frac{1}{4} \, \frac{\max_i \left\{\left\|x_i \right\|^{2}_{q}\right\}}{n} \, \sum_{i = 1}^{n} f_i(\theta) + \frac{3 \, \max_i \left\{\left\|x_i \right\|^{2}_{q}\right\}}{16}\\ & = \frac{\max_i \left\{\left\|x_i \right\|^{2}_{q}\right\}}{4}f(\theta) + \frac{3 \, \max_i \left\{\left\|x_i \right\|^{2}_{q}\right\}}{16} \end{align}\] 3 follows from [13]. ◻

Proof. For proving the first part, note that, for any matrix \(M\) and vector \(x\), for \(q \in [1, \infty)\), \[\begin{align} \left\|Mx \right\|_q^q &= \sum_{i}\left|\sum_{j}M_{ij} \, x_j\right|^q = \sum_{i} \left|\langle M_{i,:} , x \rangle \right|^q \\ &\leq \sum_{i} \left\|M_{i,:} \right\|^{q}_{q} \, \left\|x \right\|^{q}_p\\ \implies \left\|Mx \right\|_q & \leq \left(\sum_{i} \left\|M_{i,:} \right\|^{q}_{q} \, \left\|x \right\|^{q}_p \right)^{1/q} = \left\|x \right\|_p \, \left(\sum_{i} \left\|M_{i,:} \right\|^{q}_{q} \right)^{1/q} \\ \implies \left\|M \right\|_{p \to q} &= \sup_{x\neq 0}\frac{\left\|Mx \right\|_q}{\left\|x \right\|_p} \leq \left(\sum_{i} \left\|M_{i,:} \right\|^{q}_{q} \right)^{1/q} = \left(\sum_{i,j} |M_{i,j}|^{q} \right)^{1/q} \label{eq:kron-inter-1} \end{align}\tag{20}\] By definition of the Kronecker product and the above inequality, \[\begin{align} \left\|A\otimes B \right\|_{p \to q} & = \left(\sum_{i,j} \sum_{k,l} |A_{i,j}|^{q} \, |B_{k,l}|^{q} \right)^{1/q} \leq \left(\sum_{i,j} |A_{i,j}|^{q} \right)^{1/q} \, \left(\sum_{k,l} |B_{k,l}|^{q} \right)^{1/q} \end{align}\]

For the second part, note that, for any matrix \(M\), if \(q = \infty\), \(p = 1\) and hence, \[\begin{align} \left\|M \right\|_{1\to\infty} &= \sup_{\left\|x \right\|_1\leq 1}\left\|Mx \right\|_\infty = \sup_{\left\|x \right\|_1\leq 1}\max_i\left|\sum_j M_{ij}x_j\right| \\ &= \max_i\sup_{\left\|x \right\|_1\leq 1}\left|\sum_j M_{ij}x_j\right| = \max_i\sup_{\left\|x \right\|_1\leq 1}|\langle M_{i,:},x\rangle| = \max_i \left\|M_{i,:} \right\|_\infty \\ \implies \left\|M \right\|_{1\to\infty} &= \max_i\max_j |M_{ij}| \label{eq:kron-inter-2} \end{align}\tag{21}\] By definition of the Kronecker product and the above inequality, \[\begin{align} \left\|A\otimes B \right\|_{1 \to \infty} & = \max_{i,j} \, \max_{k,l} |A_{ij} B_{k,l}| \leq \max_{i,j }|A_{ij}| \, \max_{k,l} |B_{k,l}| \end{align}\] ◻

Proof. For convenience, we define \(\lambda = \sqrt{H_1}\) and \(c = \frac{H_0}{H_1}\). Define the function \[\phi(t) := (g(0) + c) \, \cosh(\lambda t) + \frac{g'(0)}{\lambda} \, \sinh(\lambda t) - c,\] where \(\sinh(x) := \frac{\exp(x) - \exp(-x)}{2}\) and \(\cosh(x) = \frac{\exp(x) + \exp(-x)}{2}\) are hyperbolic sine and cosine functions. We can verify the following relations: \(\phi(0) = g(0)\), and \[\begin{align} \phi'(t) &= \frac{(g(0) + c) \, \lambda}{2} \, (\exp(\lambda \, t) - \exp(-\lambda \, t)) + \frac{g'(0)}{2} \, (\exp(\lambda t) + \exp(-\lambda t)) \implies \phi'(0) = g'(0) \\ \phi''(t) &= \frac{(g(0) + c) \, \lambda^2}{2} \, (\exp(\lambda \, t) + \exp(-\lambda \, t)) + \frac{g'(0) \, \lambda}{2} \, (\exp(\lambda t) - \exp(-\lambda t)) \implies \phi''(t) = \lambda^2 \, (\phi(t) + c) = H_0 + H_1 \, \phi(t) \end{align}\] Hence, \(\phi(t)\) satisfies a similar condition as \(g\), but with an equality. We now show that \(\phi(t)\) upper-bounds \(g(t)\). For this define \[\Delta(t) = \phi(t) - g(t)\] and verify that (i) \(\Delta''(t) \geq \lambda^2 \, \Delta(t)\), (ii) \(\Delta'(0) = 0\) and (iii) \(\Delta(0) = 0\). We define \(H(t)\) and calculate its derivative: \[\begin{align} H(t) := \exp(-\lambda \, t) \left[ \Delta'(t) + \lambda \, \Delta(t) \right] \quad \text{;} \quad H'(t) = \exp(-\lambda t) \left[ \Delta''(t) - \lambda^2 \Delta(t) \right] \geq 0 \end{align}\] Hence, \(H(t)\) is a non-decreasing function, and hence for all \(t \geq 0\), \(H(t) \geq H(0) = 0\). Hence, for all \(t \geq 0\), \[\begin{align} & H(t) = \exp(-\lambda \, t) \left[ \Delta'(t) + \lambda \, \Delta(t) \right] \geq 0 \implies \exp(2 \lambda(t) ) \, H(t) = \exp(\lambda \, t) \left[ \Delta'(t) + \lambda \, \Delta(t) \right] \geq 0 \\ \implies & \frac{\partial \exp(\lambda t) \, \Delta(t)}{\partial t} \geq 0 \end{align}\] Hence, \(h(t) := \exp(\lambda t) \, \Delta(t)\) is a non-decreasing function, and hence, for all \(t \geq 0\), \(h(t) \geq h(0) = 0\). This implies that \(\Delta(t) \geq 0\) for all \(t \geq 0\).
Hence, for \(t \geq 0\), \(\phi(t) \geq g(t)\). By defining \(\tilde{H}(t) := \exp(\lambda \, t) \left[ \Delta'(t) - \lambda \, \Delta(t) \right]\) and following an analogous argument, we prove that for all \(t \leq 0\), \(\phi(t) \geq g(t)\). \[\begin{align} \tilde{H}(t) := \exp(\lambda \, t) \left[ \Delta'(t) - \lambda \, \Delta(t) \right] \quad \text{;} \quad \tilde{H}'(t) = \exp(\lambda t) \left[ \Delta''(t) - \lambda^2 \Delta(t) \right] \geq 0 \end{align}\] Hence, \(\tilde{H}(t)\) is a non-decreasing function, and hence for all \(t \leq 0\), \(\tilde{H}(t) \leq \tilde{H}(0) = 0\). Hence, for all \(t \leq 0\), \[\begin{align} & \tilde{H}(t) = \exp(\lambda \, t) \left[ \Delta'(t) - \lambda \, \Delta(t) \right] \leq 0 \implies \exp(-2 \lambda(t) ) \, \tilde{H}(t) = \exp(-\lambda \, t) \left[ \Delta'(t) - \lambda \, \Delta(t) \right] \leq 0 \\ \implies & \frac{\partial \exp(-\lambda t) \, \Delta(t)}{\partial t} \leq 0 \end{align}\] Hence, \(\tilde{h}(t) := \exp(-\lambda t) \, \Delta(t)\) is a non-increasing function, and hence, for all \(t \leq 0\), \(\tilde{h}(t) \geq \tilde{h}(0) = 0\). This implies that \(\Delta(t) \geq 0\) for all \(t \leq 0\).
Hence, for all \(t \in \mathbb{R}\), \(\phi(t) \geq g(t) \geq 0 \implies \min_{t \in \mathbb{R}} \phi(t) \geq 0\). Therefore, \(\phi''(t)\geq 0\) for all \(t\) and \(\phi(t)\) is convex.
Therefore, we can minimize \(\phi(t)\) by setting \(\phi'(t) = 0\): \[\phi'(t) = (g(0)+c)\lambda \sinh(\lambda t) + g'(0) \cosh(\lambda t) = 0 \iff \tanh(\lambda t^*) = -\frac{g'(0)}{(g(0)+c)\lambda }\] so since \(\cosh(\tanh^{-1}(x))=\frac{1}{\sqrt{1-x^2}}\) then \[\min_{t\in R}\phi(t) = \left((g(0)+c) - \frac{g'(0)^2}{\lambda^2(g(0)+c)}\right) \cosh(\lambda t^*) - c = \frac{1}{\lambda}\sqrt{(g(0)+c)^2\lambda^2 - g'(0)^2} - c.\] Therefore \[\begin{align} (g(0) + c)^2 - \frac{g'(0)^2}{\lambda^2} \geq c^2 } \\ \implies & g'(0) \leq \lambda \, [\sqrt{2 c g(0) + g(0)^2}] = \sqrt{2 H_0 \, g(0) + H_1 \, g(0)^2} \end{align}\] ◻

Proof. If \(H_1 = 0\), then using the standard descent lemma and the non-negativity of \(f\) gives us that, for all \(\theta\), \[\begin{align} \left\|\nabla f(\theta) \right\|^{2}_{q} & \leq 2 H_0 \, f(\theta) \end{align}\]

For the case where \(H_1 > 0\), we define \(g(t) := f(\theta + t u)\) s.t. \(\left\|u \right\|_p \leq 1\). From assumption 1, we know that \(g(t) \geq 0\) for all \(t\). Furthermore, \[\begin{align} g'(t) & = \langle \nabla f(\theta + t \, u), u \rangle \\ g''(t) &= u^T \, \nabla^2 f(\theta + t \, u) \, u \leq \left\|u \right\|_{p} \, \left\|\nabla^2 f(\theta + t \, u) \, u \right\|_{q}\\ & = \left\|u \right\|^{2}_p \, \left\|\nabla^2 f(\theta + t \, u) \right\|_{p \to q}\\ & \leq \left\|u \right\|^{2}_p \, (H_0 + H_1 \, f(\theta + t \, u)) } \\ \implies g''(t) & \leq H_0 + H_1 \, g(t)}\\ \end{align}\] Using 2 for \(H_0 \geq 0\) and \(H_1 > 0\), we get that, \(g(t) \geq 0\) and \(g''(t) \leq H_0 + H_1 \, g(t)\), then, \(g'(0) \leq \sqrt{2 H_0 \, g(0) + H_1 \, g(0)^2}\). Hence, \[\begin{align} \langle \nabla f(\theta), u \rangle & \leq \sqrt{2 H_0 \, f(\theta) + H_1 \, [f(\theta)]^2} \implies \max_{\left\|u \right\|_p \leq 1} \langle \nabla f(\theta), u \rangle \leq \sqrt{2 H_0 \, f(\theta) + H_1 \, [f(\theta)]^2} \\ \implies \left\|\nabla f(\theta) \right\|_{q} & \leq \sqrt{2 H_0 \, f(\theta) + H_1 \, [f(\theta)]^2} \end{align}\] ◻

Proof. Define \(g(\theta) := \ln(f(\theta))\), and note that \(\left\|\nabla g(\theta) \right\|_q = \frac{\left\|\nabla f(\theta) \right\|_{q}}{f(\theta)} \leq \sqrt{H_1}\), as a consequence of assumption 2 and Lemma 3. Hence, \(g\) is \(\sqrt{H_1}\)-Lipschitz. Hence, for all \(y, x\) \[\begin{align} g(y) - g(x) \leq \sqrt{H_1} \, \left\|y - x \right\|_{p} \implies \ln\left(\frac{f(y)}{f(x)}\right) \leq \sqrt{H_1} \, \left\|y - x \right\|_p \implies f(y) \leq f(x) \, \exp\left( \sqrt{H_1} \, \left\|y - x \right\|_p \right). \end{align}\] ◻

Proof. Define \(\tilde{f}(\theta):= f(\theta) + \frac{H_0}{H_1}\). We will show that if \(f\) satisfies assumption 2 with \(H_0 > 0, H_1 > 0\), then \(\tilde{f}\) satisfies assumption 2 with \(H_0 = 0, H_1 > 0\). For all \(\theta\), \[\begin{align} \left\|\nabla^2 \tilde{f}(\theta) \right\|_{p \to q} &= \left\|\nabla^2 f(\theta) \right\|_{p \to q} \leq H_0 + H_1 \, f(\theta)for f} \\ & = H_0 + H_1 \, \left( \tilde{f}(\theta) - \frac{H_0}{H_1} \right) = H_0 + H_1 \, \tilde{f}(\theta) - H_0 = H_1 \, \tilde{f}(\theta) (\theta) = f(\theta) + \frac{H_0}{H_1}} \\ \implies \left\|\nabla^2 \tilde{f}(\theta) \right\|_{p \to q} & \leq H_1 \tilde{f}(\theta) \end{align}\] Hence, \(\tilde{f}(\theta)\) satisfies assumption 2 with \(H_0 = 0\). Using 4 for \(\tilde{f}\), \[\begin{align} \tilde{f}(y) & \leq \tilde{f}(x) \exp\left(\sqrt{H_1} \left\|y - x \right\|_p \right) \\ \implies f(y) + \frac{H_0}{H_1} & \leq \left(f(x) + \frac{H_0}{H_1}\right) \exp\left(\sqrt{H_1} \left\|y - x \right\|_p \right) \\ \implies f(y) & \leq \left(f(x) + \frac{H_0}{H_1}\right) \exp\left(\sqrt{H_1} \left\|y - x \right\|_p \right) - \frac{H_0}{H_1} \end{align}\] ◻

Proof. By the fundamental theorem of calculus, \[\begin{align} \nabla f(y) - \nabla f(x) & = \int_{t = 0}^{1} \nabla^2 f((1-t) \, x + t \, y) \, (y - x) \, dt \\ \implies \left\|\nabla f(y) - \nabla f(x) \right\|_q & = \left\|\int_{t = 0}^{1} \nabla^2 f((1-t) \, x + t \, y) \, (y - x) \, dt \right\|_q \\ & \leq \int_{t = 0}^{1} \, \left\|\nabla^2 f((1-t) \, x + t \, y) \, (y - x) \right\|_{q} dt\\ & \leq \int_{t = 0}^{1} \, \left\|\nabla^2 f((1-t) \, x + t \, y) \right\|_{p \to q} \, \left\|y - x \right\|_p \, dt\\ & \leq \left\|y - x \right\|_p \, \left[\int_{t = 0}^{1} \, H_0 + H_1 \, f((1-t) \, x + t \, y) \, dt \right] }\\ & = \left\|y - x \right\|_p \, \left[H_0 + H_1 \, \int_{t = 0}^{1} \, f((1-t) \, x + t \, y) \, dt \right] \\ & \leq \left\|y - x \right\|_p \, \left[ H_1 \, \int_{t = 0}^{1} \, \left(f(x) + \frac{H_0}{H_1} \right)\, \exp(\sqrt{H_1} \, t \, \left\|y - x \right\|) \, dt \right]with \theta = ty + (1-t)x and \theta' = x} \\ & = \left\|y - x \right\|_p \, \left[H_1 \left(f(x) + \frac{H_0}{H_1} \right) \, \int_{t = 0}^{1} \, \exp(\sqrt{H_1} \, t \, \left\|y - x \right\|) \, dt \right] \\ & \leq \left\|y - x \right\|_p \, \left[H_1 \left(f(x) + \frac{H_0}{H_1} \right) \, \int_{t = 0}^{1} \, \exp(t) \, dt \right] {\sqrt{H_1}}} \\ & = \left[H_1 \left(f(x) + \frac{H_0}{H_1} \right) \, (e-1) \right]\, \left\|y - x \right\|_p \\ & \leq [H_0 + H_1 f(x)] \, e \, \left\|y - x \right\|_p \end{align}\] ◻

Proof. Define \(u(t) = (1-t) x + t y\) and \(g(t) = f(u(t))\). Use Taylor’s theorem for \(g\), \[\begin{align} g(b) = g(a) + (b - a) \, g'(a) + \int_{t = a}^{b} (b - t) \, g''(t) \, dt \\ \implies g(1) = g(0) + g'(0) + \int_{t = 0}^{1} (1 - t) \, g''(t) \, dt \end{align}\] We know that, \[\begin{align} g'(t) &= \frac{\partial f(u(t))}{\partial t} = \langle \nabla f(u(t)), y - x \rangle \quad \text{;} \quad g''(t) = \frac{\partial^2 f(u(t))}{\partial t^2} = (y - x)^T \nabla^2 f(u(t)) (y - x) \end{align}\] Combining the above relations, and using that \(g(1) = f(y)\), \(g(0) = f(x)\), \(g'(0) = \langle \nabla f(x), y - x \rangle\). \[\begin{align} f(y) &= f(x) + \langle \nabla f(x), y - x \rangle + (y-x)^T \left[\int_{t = 0}^{1} (1-t) \, \nabla^2 f(t \, y + (1-t) \, x) \, dt \right]\, (y-x) \\ \intertext{Simplifying the last term,} & (y-x)^T \left[\int_{t = 0}^{1} (1-t) \, \nabla^2 f(t \, y + (1-t) \, x) \, dt \right]\, (y-x) \\ &\leq \left\|y - x \right\|_p \, \left\|\left[\int_{t = 0}^{1} (1-t) \, \nabla^2 f(t \, y + (1-t) \, x) \, dt \right]\, (y-x) \right\|_{q}\\ & \leq \left\|y - x \right\|_p \, \left[\int_{t = 0}^{1} (1-t) \, \left\|\nabla^2 f(t \, y + (1-t) \, x) \, (y-x) \right\|_{q} \, dt \right]\\ & \leq \left\|y - x \right\|^{2}_p \, \int_{t = 0}^{1} (1-t) \, \left\|\nabla^2 f(t \, y + (1-t) \, x) \right\|_{p \to q} \, dt\\ & \leq \left\|y - x \right\|^{2}_p \, \int_{t = 0}^{1} (1-t) \, [H_0 + H_1 \, f(t \, y + (1-t) \, x)] \, dt } \\ & \leq \left\|y - x \right\|^{2}_p \, \int_{t = 0}^{1} (1-t) \, \left(H_0 + H_1 \, \left[ \left(f(x) + \frac{H_0}{H_1} \right) \exp(\sqrt{H_1} \, t \, \left\|y - x \right\|_p) - \frac{H_0}{H_1} \right] \right)\, dtwith \theta = ty + (1-t)x and \theta' = x} \\ & = \left\|y - x \right\|^{2}_p \, \int_{t = 0}^{1} (1-t) \, \left((H_0 + H_1 \, f(x)) \, \exp(\sqrt{H_1} \, t \, \left\|y - x \right\|_p) \right)\, dt \\ & = \left\|y - x \right\|^{2}_p \, (H_0 + H_1 \, f(x))\, \int_{t = 0}^{1} (1-t) \, \left( \, \exp(\sqrt{H_1} \, t \, \left\|y - x \right\|_p) \right)\, dt \\ & \leq \left\|y - x \right\|^{2}_p \, (H_0 + H_1 \, f(x))\, \int_{t = 0}^{1} (1-t) \, \left( \, \exp( t ) \right)\, dt {\sqrt{H_1}}} \\ & \leq \left\|y - x \right\|^{2}_p \, (H_0 + H_1 \, f(x))\, \left[\int_{t = 0}^{1} \exp(t) \, dt - \int_{t = 0}^{1} t \, \exp(t) \, dt \right] \\ & \leq \left\|y - x \right\|^{2}_p \, (H_0 + H_1 \, f(x))\, (e-2) \\ & \leq \left\|y - x \right\|^{2}_p \, (H_0 + H_1 \, f(x))\\ \end{align}\] Putting everything together, \[\begin{align} f(y) &\leq f(x) + \langle \nabla f(x), y - x \rangle + \left(H_0 + H_1 \, f(x) \right) \, \left\|y - x \right\|^{2}_p \end{align}\] ◻

Proof. \[\begin{align} \nabla^2 \ln(f(\theta)) &= \frac{\nabla^2 f(\theta)}{f(\theta)} - \frac{[\nabla f(\theta)] \, [\nabla f(\theta)]^{T}}{[f(\theta)]^2} \\ \implies \left\|\nabla^2 \ln(f(\theta)) \right\|_{p \to q} & \leq \left\|\frac{\nabla^2 f(\theta)}{f(\theta)} \right\|_{p \to q} + \left\|\frac{[\nabla f(\theta)] \, [\nabla f(\theta)]^{T}}{[f(\theta)]^2} \right\|_{p \to q}\\ & \leq H_1 + \frac{1}{[f(\theta)]^2} \, \left\|[\nabla f(\theta)] \, [\nabla f(\theta)]^{T} \right\|_{p \to q} } \\ & \leq H_1 + \frac{\left\|\nabla f(\theta) \right\|^{2}_q}{[f(\theta)]^2}= \left\|x \right\|^{2}_{q}} \\ \implies \left\|\nabla^2 \ln(f(\theta)) \right\|_{p \to q} & \leq 2 \, H_1with H_0 = 0} \end{align}\] By the fundamental theorem of calculus, \[\begin{align} \nabla \ln(f(y)) - \nabla \ln(f(x)) & = \int_{t = 0}^{1} \nabla^2 \ln(f(t \, y + (1-t) x)) (y-x) \, dt \\ \implies \left\|\nabla \ln(f(y)) - \nabla \ln(f(x)) \right\|_{q} & \leq \int_{t = 0}^{1} \left\|\nabla^2 \ln(f(t \, y + (1-t) x)) (y-x) \right\|_{q} \, dt\\ & \leq \int_{t = 0}^{1} \, \left\|\nabla^2 \ln(f(t \, y + (1-t) x)) \right\|_{p \to q} \, \left\|y-x \right\|_p \, dt\\ & \leq 2 \, H_1 \, \left\|y - x \right\|_p\\ \implies \left\|\frac{\nabla f(y)}{f(y)} - \frac{\nabla f(x)}{f(x)} \right\|_q & \leq 2 \, H_1 \, \left\|y - x \right\|_p \end{align}\] ◻

Proof. Define \(\tilde{f}(\theta):= f(\theta) + \frac{H_0}{H_1}\). We will show that if \(f\) satisfies assumption 2 with \(H_0 > 0, H_1 > 0\), then \(\tilde{f}\) satisfies assumption 2 with \(H_0 = 0, H_1 > 0\). For all \(\theta\), \[\begin{align} \left\|\nabla^2 \tilde{f}(\theta) \right\|_{p \to q} &= \left\|\nabla^2 f(\theta) \right\|_{p \to q} \leq H_0 + H_1 \, f(\theta)for f} \\ & = H_0 + H_1 \, \left( \tilde{f}(\theta) - \frac{H_0}{H_1} \right) = H_0 + H_1 \, \tilde{f}(\theta) - H_0 = H_1 \, \tilde{f}(\theta) (\theta) = f(\theta) + \frac{H_0}{H_1}} \\ \implies \left\|\nabla^2 \tilde{f}(\theta) \right\|_{p \to q} & \leq H_1 \tilde{f}(\theta) \end{align}\] Hence, \(\tilde{f}(\theta)\) satisfies assumption 2 with \(H_0 = 0\). Using 8 for \(\tilde{f}\) and noting that \(\nabla \tilde{f}(\theta) = f(\theta)\), then, for all \(x, y\), \[\begin{align} \left\|\frac{\nabla \tilde{f}(y)}{\tilde{f}(y)} - \frac{\nabla \tilde{f}(x)}{\tilde{f}(x)} \right\|_q \leq 2 \, H_1 \, \left\|y - x \right\|_p \\ \implies \left\|\frac{\nabla f(y)}{f(y) + \frac{H_0}{H_1}} - \frac{\nabla f(x)}{f(x) + \frac{H_0}{H_1}} \right\|_q \leq 2 \, H_1 \, \left\|y - x \right\|_p \end{align}\] ◻

Proof. Define the function \(h(\theta) := \ln(\left\|\nabla f(\theta) \right\|_q + c)\). We will first prove that \(h(\theta)\) is \(\frac{H_1}{\mu}\)-Lipschitz w.r.t the \(\ell_{p}\) norm. Since \(\left\|\cdot \right\|_q\) can be non-smooth, consider a Clarke subgradient computed using Lemma 12 \[\partial h(\theta) = \frac{\nabla^2 f(\theta) \partial \|z\|_q}{\|z\|_q+c}, \qquad z = \nabla f(\theta).\] \[\begin{align} \intertext{Then, for g = \nabla^2 f(\theta) s where s \in \partial(\left\|\cdot \right\|_q)(\nabla f(\theta)) is a subgradient of \left\|\cdot \right\|_{q} evaluated at \nabla f(\theta).} \left\|v \right\|_{q} &= \frac{\left\|[\nabla^2 f(\theta)] \, s \right\|_q}{\left\|\nabla f(\theta) \right\|_q + c} \leq \frac{\left\|\nabla^2 f(\theta) \right\|_{p \to q} \, \left\|s \right\|_{p}}{\left\|\nabla f(\theta) \right\|_q + c}\\ \implies \left\|v \right\|_{q} & \leq \frac{\left\|\nabla^2 f(\theta) \right\|_{p \to q}}{\left\|\nabla f(\theta) \right\|_q + c}\\ \end{align}\] Using assumption 2 to simplify the numerator, and noting that lower-bounding the denominator, \[\begin{align} \forall v \in \partial{h}(\theta), \quad \left\|v \right\|_q & \leq \frac{H_0 + H_1 \, f(\theta)}{c} \end{align}\] By Lebourg’s mean value theorem ([42], Thm. 2.4), since \(h\) is Lipschitz in an open set containing \(y\) and \(x\), then there exists a point \(u = tx+(1-t)y\), for some \(t\in[0,1]\) such that \[h(y)-h(x)\in \langle g,y-x\rangle, \qquad g\in \partial h(u).\] Therefore, \[\begin{align} h(y) - h(x) &\leq \max_{t\in[0,1]} \langle g,y-x\rangle \quad {where} \quad g \in \partial h(t \, x + (1-t) \, y) \\ & \leq \left\|y - x \right\|_p \, \max_{t\in[0,1]}\,\|g\|_q\\ & \leq \frac{\left\|y - x \right\|_p}{c} \, \max_{t\in[0,1]} \, (H_0 + H_1 \, f(t \, x + (1-t) \, y)),\\ & \leq \frac{\left\|y - x \right\|_p}{c} \,\max_{t\in[0,1]} \left[H_0 + H_1 \, \left( \left(f(x) + \frac{H_0}{H_1} \right) \, \exp\left(\sqrt{H_1} \, t \, \left\|y - x \right\|_p \right) - \frac{H_0}{H_1}\right) \right] } \\ & = \frac{\left\|y - x \right\|_p}{c} \,\max_{t\in[0,1]} (H_0 + H_1 \, f(x)) \, \exp\left(\sqrt{H_1} \, t \, \left\|y - x \right\|_p \right) \\ & \leq\, \frac{\left\|y - x \right\|_p}{c} \, \max_{t\in[0,1]} \, (H_0 + H_1 \, f(x)) \, \exp\left(t \right) {\sqrt{H_1}}} \\ & \leq\, \frac{\left\|y - x \right\|_p}{c} \, \, (H_0 + H_1 \, f(x)) \,e \end{align}\] \[\begin{align} \implies & \ln(\left\|\nabla f(y) \right\|_q + c) - \ln(\left\|\nabla f(x) \right\|_q + c) \leq (H_0 + H_1 \, f(x)) \, e \, \frac{\left\|y - x \right\|_p}{c} \\ \implies & \left\|\nabla f(y) \right\|_q + c \leq \left(\left\|\nabla f(x) \right\|_q + c \right) \, \exp\left((H_0 + H_1 \, f(x)) \, e \, \frac{\left\|y - x \right\|_p}{c} \right) \end{align}\] This proves the first part of the lemma. For the second part, using assumption 2 to simplify the numerator of the above relation, \[\begin{align} \left\|\nabla^2 f(\theta) \right\|_{p \to q} & \leq H_0 + H_1 \, f(\theta) = [H_0 + H_1 \, f^*] + H_1 \, [f(\theta) - f^*] \\ & \leq [H_0 + H_1 \, f^*] + \frac{H_1}{\mu} \, \left\|\nabla f(\theta) \right\|_{q}with \zeta = 1 and \mu} \\ & = \frac{H_1}{\mu} \, \left[ \left\|\nabla f(\theta) \right\|_{q} + \frac{\mu \, [H_0 + H_1 \, f^*]}{H_1} \right] = \frac{H_1}{\mu} \, \left[\left\|\nabla f(\theta) \right\|_{q} + c \right]\\ \implies \forall v \in \partial{h}(\theta), \quad \left\|v \right\|_q & \leq \frac{H_1}{\mu} \end{align}\] Again, using the mean value theorem \[\begin{align} h(y) - h(x) &\leq \max_{t\in[0,1]} \langle g, y - x \rangle \quad {where} \quad g \in \partial h(t \, x + (1-t) \, y) \\ & \leq \left\|y - x \right\|_p \, \max_{t\in[0,1]} \left\|g \right\|_q\\ & \leq \left\|y - x \right\|_p \, \frac{H_1}{\mu}\\ \implies h(y) - h(x) & \leq \frac{H_1}{\mu} \, \left\|y - x \right\|_p \\ \implies \left\|\nabla f(y) \right\|_q + c & \leq \left(\left\|\nabla f(x) \right\|_q + c \right) \, \exp \left(\frac{H_1}{\mu} \left\|y - x \right\|_{p} \right) \,, \end{align}\] ◻

Proof. By definition, since \(f(\theta) \geq f^*\), \(h\) satisfies 1 and \(h^* = 0\). Since \(f\) is \((H_0, H_1)\) \(\textsf{NS}\), \[\begin{align} \left\|\nabla^2 f(\theta) \right\| & \leq H_0 + H_1 \, f(\theta) \\ \implies \left\|\nabla^2 h(\theta) \right\| & = \left\|\nabla^2 f(\theta) \right\| \leq H_0 + H_1 \, f(\theta) \\ & = \underbrace{H_0 + H_1 \, f^*}_{:= L'_0} + \underbrace{H_1}_{:= L'_1} \, [f(\theta) - f^*] \\ \implies \left\|\nabla^2 h(\theta) \right\| & \leq L'_0 + L'_1 \, h(\theta) \end{align}\] ◻

Proof. The first statement is given exactly in [42]. Both are the result of the following statement, which is follows from the standard definition of lim sup:

Consider \(A(t) \to a\) and \(\limsup_{t\to 0} B(t) = \mathcal{B}\) where \(a\) is a point and \(\mathcal{B}\) is a closed set. Then if \(a\in \mathbb{R}\) or \(\mathcal{B}\subset \mathbb{R}\), then \[\limsup_{t\to 0} A(t)\cdot B(t) \subset a\cdot \mathcal{B} = \{ab : b\in \mathcal{B}\}.\]

If \(h(x)\) is smooth at \(x\), then \[\partial h(x) = \{\nabla h(x)\} = \begin{cases} \{f'(g(x))\cdot \nabla g(x)\}, & g:\mathbb{R}^n\to\mathbb{R}\\ \{J(x)^T \nabla f(g(x))\}, & g:\mathbb{R}^p\to \mathbb{R}^n \end{cases}\]

If \(h(x)\) is not smooth at \(x\), then in the first case, \[\limsup_{z\to x} \nabla h(z) = \limsup_{z\to x} f'(g(z))\cdot \nabla g(z) \subseteq f'(g(x)) \cdot \partial g(x).\] Since subdifferentials are closed and convex, then \[\partial h(x) = \mathrm{co\,cl}\limsup_{z\to x} \nabla h(z) = f'(g(x)) \cdot \partial g(x).\]

By similar logic, in the second case, for \(w = g(z)\), \(u = g(x)\) \[\limsup_{z\to x} \nabla h(z) = \limsup_{z\to x} J(z)^T\nabla f(w) \subset J(x)^T \limsup_{w\to u} \nabla f(w) = J(x)^T\partial f(u)\] which are also closed and convex sets. So, \[\partial h(x) = \{J(x)^Ty : y\in\partial f(u),\,u=g(x)\}.\] ◻

Proof. •For \((p,q) = (\infty,1)\), for \(d\) s.t. \(\left\|d \right\|_\infty \leq 1\), \[\begin{align} \langle \nabla_t, d \rangle \leq \left\|\nabla_t \right\|_1 \, \left\|d \right\|_\infty \leq \left\|\nabla_t \right\|_1 \end{align}\] For \(d^* = \text{sign}(\nabla_t)\) where \(\text{sign}(0) = 0\), \(\left\|d^* \right\|_\infty = 1\) and \[\begin{align} \langle \nabla_t, d^* \rangle &= \sum_{i \in [D], \nabla_{t,i} \neq 0} \nabla_{t,i} \, d^*_i + \sum_{i \in [D], \nabla_{t,i} = 0} \nabla_{t,i} \, d^*_i = \sum_{i \in [D], \nabla_{t,i} \neq 0} \nabla_{t,i} \, \text{sign}(\nabla_{t,i}) = \sum_{i \in [D], \nabla_{t,i} \neq 0} |\nabla_{t,i}| = \left\|\nabla_t \right\|_1 \end{align}\] Hence, \(d^*\) attains the upper-bound, and is therefore optimal. Hence, the \(\texttt{NSD}\) update simplifies to \(\theta_{t+1}= \theta_t- {\eta_t}\, \text{sign}(\nabla_{t})\).

•For \((p,q) = (2,2)\), for \(d\) s.t. \(\left\|d \right\|_2 \leq 1\), \[\begin{align} \langle \nabla_t, d \rangle \leq \left\|\nabla_t \right\|_2 \, \left\|d \right\|_2 \leq \left\|\nabla_t \right\|_2 \end{align}\] For \(d^* := \frac{\nabla_t}{\left\|\nabla_t \right\|_2}\), \(\left\|d^* \right\|_2 = 1\), and \(\langle \nabla_t, d^* \rangle = \left\|\nabla_t \right\|_2\). Hence, \(d^*\) attains the upper-bound, and is therefore optimal. Hence, the \(\texttt{NSD}\) update simplifies to \(\theta_{t+1}= \theta_t- {\eta_t}\, \frac{\nabla_t}{\left\|\nabla_t \right\|_2}\)

•For \((p,q) = (1,\infty)\), for \(d\) s.t. \(\left\|d \right\|_1 \leq 1\), \[\begin{align} \langle \nabla_t, d \rangle \leq \left\|\nabla_t \right\|_\infty \, \left\|d \right\|_1 \leq \left\|\nabla_t \right\|_\infty \end{align}\] Pick a coordinate \(i_t \in \mathop{\mathrm{arg\,max}}_{i \in [D]}|\nabla_{t,i}|\) and define \(d^* = \text{sign}(\nabla_{t,i_t}) \, e_{i_t}\). For \(d^*\), \(\left\|d^* \right\|_{1} = 1\) and \[\begin{align} \langle \nabla_t, d^* \rangle & = \sum_i \nabla_{t,i} \, d^*_i = \nabla_{t,i_t} \, d^*_{i_t} = \nabla_{t,i_t} \, \text{sign}(\nabla_{t,i_t}) = |\nabla_{t, i_t}| = \max_{i \in [D]} |\nabla_{t, i}| = \left\|\nabla_t \right\|_\infty \end{align}\] Hence, \(d^*\) attains the upper-bound, and is therefore optimal. Hence, the \(\texttt{NSD}\) update simplifies to \(\theta_{t+1}= \theta_t- {\eta_t}\, \text{sign}(\nabla_{t,i_t}) \, e_{i_t}\), where, \(i_t \in \mathop{\mathrm{arg\,max}}_{i \in [D]}|\nabla_{t,i}|\). ◻

Proof. Using 15 for \(\eta \leq \frac{1}{\sqrt{H_1}}\), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla f(\theta_t) \right\|_{q} +\left(H_0 + H_1 \, f(\theta_t) \right) \, \eta^2 \nonumber \\ & \leq f(\theta_t) - \eta \, \mu \, [f(\theta_t)]^{\tau} +\left(H_0 + H_1 \, f(\theta_t) \right) \, \eta^2with f^* = 0 and \mu(\theta) = \mu} \\ \implies f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \mu \, [f(\theta_t)]^{\tau} +\left(H_0 + H_1 \, f(\theta_t) \right) \, \eta^2 \label{eq:sd-2pl-inter-1} \end{align}\tag{22}\] Define \(T_0\) to be the first iteration s.t. \(f(\theta_{T_0}) < \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\).

Phase 1: We first analyze 22 for \(t < T_0\) where \(f(\theta_t) \geq \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\). Simplifying 22 in this case, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \mu \, [f(\theta_t)]^{\tau} + 2 \, H_1 \, f(\theta_t) \, \eta^2 \end{align}\] We will now use an inductive proof and prove that for all \(t \leq T_0\), \(f(\theta_t) \leq f(\theta_1)\).

Base Case: For \(t = 1\), this is true by definition.

Inductive Hypothesis: Assume for iteration \(t < T_0\), \(f(\theta_t) \leq f(\theta_1)\).

Induction: We will prove that \(f(\theta_{t+1}) \leq f(\theta_1)\). For this, note that \(f(\theta_t) \leq f(\theta_1)\) by the inductive hypothesis and \(1 - \tau \geq 0\). Hence, the above inequality can simplified as: \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \mu \, \frac{f(\theta_t)}{[f(\theta_1)]^{1 - \tau}} + 2 H_1 \, f(\theta_t) \, \eta^2 \end{align}\] Using 13 with \(A = \frac{\mu}{[f(\theta_1)]^{1 - \tau}}\), \(B = 2 H_1\), \(\bar{\eta}_1 = \frac{1}{\sqrt{H_1}}\) and \(\delta = \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\), we get that with \(\eta = \min\left\{\bar{\eta}_1, \frac{\mu}{4 \, H_1 \, [f(\theta_1)]^{1 - \tau}} \right\}\), \(f(\theta_{t+1}) \leq f(\theta_t)\). This completes the induction. Moreover, \(f(\theta_{T_0}) \leq \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\) after \[T_0 \geq O \left(\frac{[f(\theta_1)]^{1 - \tau}}{\mu \, \eta} \ln\left(\frac{f(\theta_1)}{\delta}\right) \right) = O \left(\ln\left(\min\left\{\frac{1}{\epsilon}, \frac{H_1}{H_0} \right\} \right) \right)\, \text{iterations.}\] Hence, if \(\epsilon \geq \frac{H_0}{H_1}\), \(\texttt{NSD}\) with a constant step-size requires \(O(\ln(1/\epsilon))\) iterations to guarantee convergence to an \(\epsilon\) sub-optimality.

Phase 2: Consider iteration \(t > T_0\) such that \(f(\theta_t) < \frac{H_0}{H_1}\). Simplifying 22 in this case, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \mu \, [f(\theta_t)]^{\tau} + 2 H_0 \, \eta^2 \end{align}\] Using 14 with \(A = \mu\), \(B = 2 \, H_0\), \(r = \tau\), \(\bar{\eta}_1 = \frac{1}{\sqrt{H_1}}\) and \(\delta = \epsilon\), we get that with \(\eta = \min\left\{\frac{1}{\sqrt{H_1}}, \frac{\mu \, \epsilon^{\tau}}{4 H_0}\right\}\), \(f(\theta_{t+1}) \leq f(\theta_t) \leq f(\theta_{T_0}) \leq \frac{H_0}{H_1}\) for all \(t \geq T_0\).

Furthermore, if \(\tau = 1\), \(f(\theta_{T_\epsilon + T_0}) \leq \epsilon\) after \[T_\epsilon \geq \frac{2}{\mu \, \eta} \ln\left(\frac{f(\theta_1)}{\delta}\right)= O \left( \frac{1}{\epsilon} \right) \text{iterations}.\] Else, if \(\tau < 1\), \(f(\theta_{T_\epsilon + T_0}) \leq \epsilon\) after \[T_\epsilon \geq \frac{2 \, [f(\theta_{T_0})]^{1 - \tau}}{\mu \, \eta \, (1 - \tau)} = O \left( \frac{1}{\epsilon^{\tau}} \right) \text{iterations}.\] Hence, for \(T := T + T_\epsilon\), \(f(\theta_{T+1}) \leq \epsilon\) after, \[O \left( \frac{1}{\epsilon^{\tau}} + \ln \left( \frac{H_1}{H_0} \right) \right) \, \text{iterations.}\] ◻

Proof. From [prop:bandits], we know that the multi-armed bandit problem satisfies 2 with \(H_0 = 0\) and 3 with \(\tau = 1\) and \(f^* = 0\), though with a non-uniform \(\mu(\theta)\). In order to use [thm:nsd-pl], we need to lower-bound \(\mu(\theta) = \pi_\theta(a^*)\) by a constant \(\mu\). For this, we use a uniform initialization which guarantees that \(\pi_{\theta_1}(a^*) = \frac{1}{K}\).

We then use [14] which implies that if \(f(\theta_{t+1}) \leq f(\theta_t)\), \(\pi_{\theta_{t+1}}(a^*) \geq \pi_{\theta_t}(a^*)\). For \(\texttt{NSD}\) on a function with a fixed \(\mu\), [thm:nsd-pl] guarantees descent for all \(t\) in both phases. Consequently, we can inductively conclude that for all \(t\), \(\pi_{\theta_{t+1}}(a^*) \geq \pi_{\theta_t}(a^*) \geq \pi_{\theta_1}(a^*) \geq \mu := \frac{1}{K}\).

Hence, [thm:nsd-pl] immediately recovers a linear convergence rate with \(\mu = \frac{1}{K}\). ◻

Proof. Since we are considering logistic regression on linearly separable data, \(f^* = 0\) and \(H_0 = 0\). We will use a similar proof as that for [thm:nsd-pl]. In particular, using 15 for \(\eta \leq \bar{\eta}_0 := \frac{1}{\sqrt{H_1}}\), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla f(\theta_t) \right\|_{q} + H_1 \, f(\theta_t) \, \eta^2 \label{eq:sd-logreg-inter-1} \end{align}\tag{23}\] We will use an inductive argument and prove that for all \(t \geq 0\), \(f(\theta_t) \leq f(\theta_1)\).

Base Case: For \(t = 1\), this is true by definition.

Inductive Hypothesis: Assume for iteration \(t > 0\), \(f(\theta_t) \leq f(\theta_1)\).

Induction: We will prove that \(f(\theta_{t+1}) \leq f(\theta_1)\). To complete the induction, we will consider two phases. For this, define \(T_0\) to be the first iteration s.t. \(f(\theta_{T_0}) < \max\left\{\epsilon, \frac{\ln(2)}{n}\right\}\).

Phase 1: For all \(t < T_0\), \(f(\theta_t) > \frac{\ln(2)}{n}\) and we use part (2) of [prop:logistic] to conclude that \(\left\|\nabla_t \right\|_q \geq \frac{\gamma_p}{3n}\). Simplifying 23 , \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla f(\theta_t) \right\|_{q} + H_1 \, f(\theta_1) \, \eta^2\\ & \leq f(\theta_t) - \frac{\eta \, \gamma_p}{4n} + H_1 \, f(\theta_1) \, \, \eta^2 {3n} \geq \frac{\gamma_p}{4n} } \\ & \leq f(\theta_t) - \frac{\eta \, \gamma_p}{8n} _1 := \frac{\gamma_p}{8 \, H_1 \, f(\theta_1) \, n}} \\ \intertext{Since f(\theta_{t+1}) \leq f(\theta_t) \leq f(\theta_1), this completes the induction for Phase 1. By recursing for T_0-1 iterations,} \implies f(\theta_{T_0}) & \leq f(\theta_1) - \frac{\eta \, \gamma_p}{8n} \, (T_0-1) = \ln(2) - \frac{\eta \, \gamma_p}{8n} \, (T_0-1) \end{align}\] Hence, by using that \(\eta \leq \min\{\bar{\eta}_0, \bar{\eta}_1\}\), \[T_0 \geq O \left(\frac{n \, \ln(2)}{\eta \, \gamma_p} \right) = O \left( \left(\frac{n}{\gamma_p}\right)^2 \, H_1 \right) \text{iterations}\] guarantee that \(f(\theta_{T_0}) \leq \frac{\ln(2)}{n}\).

Phase 2: After \(T_0\) iterations, \(f(\theta_{T_0}) \leq \frac{\ln(2)}{n} < f(\theta_1)\). We will now prove that for \(t > T_0\), \(f(\theta_t) \leq f(\theta_{T_0}) < f(\theta_1)\), thus completing the induction in Phase 2. We will again do this proof via induction.

Base Case: For \(t = T_0\), this is true by definition.

Inductive Hypothesis: Assume for iteration \(t > T_0\), \(f(\theta_t) \leq f(\theta_{T_0})\).

Induction: We will prove that \(f(\theta_{t+1}) \leq f(\theta_{T_0})\). Since \(f(\theta_t) \leq f(\theta_{T_0}) < f(\theta_1)\) by the inductive hypothesis, combining the above relation with 23 , \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla_t \right\|_q + H_1 \, f(\theta_t) \,\eta^2 \\ & \leq f(\theta_t) - \frac{\eta \, \gamma_p}{2} f(\theta_t) + H_1 \, f(\theta_t) \, \eta^2 } \\ & \leq f(\theta_t) - \frac{\eta \, \gamma_p}{4} f(\theta_t) _2 := \frac{\gamma_p}{4 \, H_1} } \\ \intertext{Since f(\theta_{t+1}) < f(\theta_t) < f(\theta_{T_0}), this completes the induction. Furthermore, by recursing for T iterations} \implies f(\theta_{T_0 + T}) & \leq f(\theta_{T_0}) \, \exp\left(-\frac{\eta \, \gamma_p}{4} \, T \right) \leq \frac{\ln(2)}{n} \, \, \exp\left(-\frac{\eta \, \gamma_p}{4} \, T \right) \end{align}\] Hence, by using a step-size \(\eta \leq \min\{\bar{\eta}_0, \bar{\eta}_2\}\), \[T \geq O \left( \frac{1}{\eta \, \gamma_p} \, \ln\left(\frac{\ln(2)}{n \, \epsilon} \right) \right) = O \left( \frac{H_1}{\gamma_p^2} \, \ln\left(\frac{1}{n \epsilon}\right) \right)\] iterations suffice to guarantee that \(f(\theta_{T + T_0}) \leq \epsilon\). Hence, attaining an \(\epsilon\) sub-optimality for logistic regression requires, \[T_{\text{final}} = O \left( \frac{H_1}{\gamma_p^2} \, \ln\left(\frac{1}{n \epsilon}\right) \right) + O \left( \left(\frac{n}{\gamma_p}\right)^2 \, H_1 \right) = O\left(\frac{H_1}{\gamma_p^2} \, \left[n^2 + \ln\left(\frac{1}{n \epsilon}\right)\right]\right) \text{iterations.}\] ◻

Proof. We first prove for a fixed \(\eta > \sqrt{8 \epsilon}\), we can find an initialization \(\theta_1\) such that the \(\texttt{NSD}\) iterates oscillate around \(\theta^* = 0\) and that \(f(\theta_t) > \epsilon\) for all \(t \geq 1\).

For this, consider the \(\texttt{NSD}\) update at \(t = 1\) with \(\theta_1 = \frac{\eta}{2}\). In this case, \[\begin{align} d_1 &= \mathop{\mathrm{arg\,max}}_{|d| \leq 1} d \, f'(\theta_1) = \mathop{\mathrm{arg\,max}}_{|d| \leq 1} d \, \theta_1 = 1 \implies \theta_2 = \theta_1 - \eta \, d_1 = \frac{\eta}{2} - \eta = -\frac{\eta}{2} \end{align}\] Similarly, for \(t = 2\), \(d_2 = -1 \implies \theta_3 = \frac{\eta}{2}\). Hence, the iterates oscillate between \(\eta/2\) and \(-\eta/2\). For all \(t \geq 1\), \(f(\theta_t) = \frac{\theta_t^2}{2} = \frac{\eta^2}{8} > \epsilon\).

Hence, ensuring \(\epsilon\) convergence from any initialization requires \(\eta \leq \sqrt{8 \epsilon}\). In this case, choose the initialization \(\theta_1 = 1\) and define \(T_\text{sign} := \inf_{t \geq 1} \theta_t< 0\). Using the \(\texttt{NSD}\) update, for all \(t < T_\text{sign}\), \(\theta_t> 0\) and, \[\begin{align} \theta_{t+1}& = \theta_t- \eta \implies \theta_{T_\text{sign}} = 1 - \eta \, (T_\text{sign} - 1) \implies T_\text{sign} > 1 + \frac{1}{\eta} \geq 1 + \frac{1}{\sqrt{8 \epsilon}} \end{align}\]

Case 1: If \(T_\epsilon \geq T_{\rm sign}\), then \(T_\epsilon \geq T_{\rm sign} > 1+\frac{1}{\eta} \geq 1+\frac{1}{\sqrt{8\epsilon}}\), which gives the desired lower bound.

Case 2: If \(T_\epsilon < T_{\rm sign}\), then for all \(t < T_\epsilon < T_\text{sign}\), \(f(\theta_t) = \frac{(1 - \eta \, (t-1))^2}{2}\). By definition of \(T_\epsilon\), \[\begin{align} \frac{(1 - \eta \, (T_\epsilon-1))^2}{2} \leq \epsilon \implies T_\epsilon \geq 1 + \frac{1 - \sqrt{2 \epsilon}}{\eta} \geq 1 + \frac{1 - \sqrt{2 \epsilon}}{\sqrt{8 \epsilon}} \end{align}\] Hence, the hitting time \(T_\epsilon = \Omega\left(\frac{1}{\sqrt{\epsilon}}\right)\). ◻

Proof. Setting \(\eta \leq \frac{A}{2 \, B}\), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \frac{A \, \eta}{2} \, f(\theta_t) \implies f(\theta_{t+1}) \leq f(\theta_t)\left(1-\frac{A\eta}{2}\right)\\ \implies f(\theta_{T+1}) & \leq f(\theta_1) \, \exp\left(-T \, \frac{A \, \eta}{2} \right) \end{align}\] Hence, in order to guarantee that \(f(\theta_{T+1}) \leq \delta\), it is sufficient to set, \[\begin{align} T & \geq \frac{2}{A \, \eta} \, \ln \left( \frac{f(\theta_1)}{\delta} \right) = \frac{2 \, \max\left\{\frac{1}{\bar{\eta}_1}, \frac{2 \, B}{A}\right\}}{A} \, \ln \left( \frac{f(\theta_1)}{\delta} \right) = O\left(\ln\left(\frac{1}{\delta} \right)\right) \end{align}\] ◻

Proof. For the desired sub-optimality \(\delta\), setting \(\eta = \min\left\{\bar{\eta}_1, \frac{A \, \delta^{r}}{2B} \right\}\), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, A \, [f(\theta_t)]^r + \frac{A \, \eta}{2} \, \delta^r \end{align}\] Let \(T_\delta\) be the first iteration s.t. \(f(\theta_t) \leq \delta\). Hence, for all \(t < T_\delta\), \(f(\theta_t) \geq \delta \implies [f(\theta_t)]^{r} \geq \delta^r\). Hence, for \(t < T_\delta\), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \frac{A \, \eta}{2} \, [f(\theta_t)]^r \implies f(\theta_{t+1}) \leq f(\theta_t)\left(1-\frac{A\eta}{2}\right) \label{eq:lemma-p2-sd-inter-1} \end{align}\tag{24}\] Case 1: If \(r = 1\), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) \left[1 - \frac{A \eta}{2} \right] \\ \implies f(\theta_{T_\delta}) & \leq f(\theta_1) \, \exp\left(-(T_\delta-1) \, \frac{A \eta}{2}\right) \end{align}\] For \(f(\theta_{T_\delta}) \leq \delta\), it is sufficient to set \(T_\delta\) s.t., \[\begin{align} T_\delta \geq \frac{2}{A \eta} \, \ln\left(\frac{f(\theta_1)}{\delta}\right) + 1 = \frac{2 \, \max\left\{\frac{1}{\bar{\eta}_1}, \frac{2 \, B}{A \delta}\right\}}{A} \, \ln\left(\frac{f(\theta_1)}{\delta}\right) + 1 = O\left(\frac{1}{\delta} \, \ln\left(\frac{1}{\delta} \right)\right) \end{align}\]

Case 2: If \(r < 1\), continuing from 24 , note that \(g(x) = x^{1-r}\) is concave in \(x\) if \(r < 1\). Furthermore, \(g'(x) = (1-r) \, x^{-r}\). Using concavity, for any \(y, x\), \[\begin{align} g(y) & \leq g(x) + g'(x) (y - x) \implies y^{1 - r} \leq x^{1 - r} + (1-r) \, x^{-r} \, (y - x) \\ \implies [f(\theta_{t+1})]^{1 - r} & \leq [f(\theta_t)]^{1-r} + (1-r) \, [f(\theta_t)]^{-r} \, (f(\theta_{t+1}) - f(\theta_t)) \\ & \leq [f(\theta_t)]^{1-r} - (1-r) \, [f(\theta_t)]^{-r} \, \frac{A \, \eta}{2} \, [f(\theta_t)]^r } \\ & = [f(\theta_t)]^{1-r} - (1-r) \, \frac{A \, \eta}{2} \\ \implies [f(\theta_{T_\delta})]^{1 - r} & \leq [f(\theta_1)]^{1-r} - (1-r) \, \frac{A \, \eta}{2} \, (T_\delta -1) \end{align}\] For \(f(\theta_{T_\delta}) \leq \delta\), it is sufficient to set \(T_\delta\) s.t., \[\begin{align} [f(\theta_1)]^{1-r} - (1-r) \, \frac{A \, \eta}{2} \, (T_\delta -1) & \leq \delta^{1-r} \\ \end{align}\] Hence, it is sufficient to set \(T_\delta\) s.t. \[\begin{align} T_{\delta} & \geq \frac{2 \, [f(\theta_1)]^{1-r}}{A \, \eta \, (1-r)} + 1 = \frac{2 \, [f(\theta_1)]^{1-r} \, \max\left\{\frac{1}{\bar{\eta}_1}, \frac{2 \, B}{A \delta^r}\right\}}{A (1-r)} + 1 = O \left( \frac{1}{\delta^r} \right) \end{align}\]

Case 3: If \(r > 1\), continuing from 24 , note that \(g(x) = x^{1-r}\) is convex in \(x\) if \(r > 1\). Furthermore, \(g'(x) = (1-r) \, x^{-r}\). Using convexity, for any \(y, x\), \[\begin{align} g(y) & \geq g(x) + g'(x) (y - x) \implies y^{1 - r} \geq x^{1 - r} + (1-r) \, x^{-r} \, (y - x) \\ \implies [f(\theta_{t+1})]^{1 - r} & \geq [f(\theta_t)]^{1-r} + (1-r) \, [f(\theta_t)]^{-r} \, (f(\theta_{t+1}) - f(\theta_t)) \\ & \geq [f(\theta_t)]^{1-r} - (1-r) \, [f(\theta_t)]^{-r} \, \frac{A \, \eta}{2} \, [f(\theta_t)]^r } \\ & = [f(\theta_t)]^{1-r} - (1-r) \, \frac{A \, \eta}{2} \\ \implies [f(\theta_{T_\delta})]^{1 - r} & \geq [f(\theta_1)]^{1-r} - (1-r) \, \frac{A \, \eta}{2} \, (T_\delta -1) = [f(\theta_1)]^{1-r} + (r-1) \, \frac{A \, \eta}{2} \, (T_\delta-1)\\ \implies [f(\theta_{T_\delta})]^{r - 1} & \leq \frac{1}{ [f(\theta_1)]^{1-r} + (r-1) \, \frac{A \, \eta}{2} \, (T_\delta-1)} \end{align}\] For \(f(\theta_{T_\delta}) \leq \delta\), it is sufficient to set \(T_\delta\) s.t., \[\begin{align} \frac{1}{ [f(\theta_1)]^{1-r} + (r-1) \, \frac{A \, \eta}{2} \, (T_\delta-1)} \leq \delta^{r-1} \implies [f(\theta_1)]^{1-r} + (r-1) \, \frac{A \, \eta}{2} \, (T_\delta-1) & \geq \delta^{1-r} \\ \end{align}\] Hence, it is sufficient to set \(T_\delta\) s.t. \[\begin{align} T_{\delta} & \geq \frac{2\, \delta^{1-r}}{A \, \eta \, (r-1) \, } + 1 = \frac{2 \, \max\left\{\frac{1}{\bar{\eta}_1}, \frac{2 \, B}{A \delta^r}\right\}\, \delta^{1-r}}{A (r-1) } + 1 = O \left( \frac{1}{\delta^{2 \, r - 1}} \right) \end{align}\] ◻

Proof. If \(\left\|\theta_{t+1}- \theta_t \right\|_p \leq \frac{1}{\sqrt{H_1}}\), using 7 and denoting \(\nabla_t := \nabla f(\theta_t)\) for convenience, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla f(\theta_t), d_t \rangle + \left(H_0 + H_1 \, f(\theta_t) \right) \, \eta^2 \, \left\|d_t \right\|^{2}_{p} \\ & \leq f(\theta_t) - \eta \, \langle \nabla f(\theta_t), d_t \rangle + \left(H_0 + H_1 \, f(\theta_t) \right) \, \eta^2\\ \implies f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla f(\theta_t) \right\|_{q} +\left(H_0 + H_1 \, f(\theta_t) \right) \, \eta^2\langle z, u \rangle} \end{align}\] ◻

Proof. Using 16 for \(\eta \leq \frac{\sqrt{1-\beta}}{\sqrt{H_1}}\), \(\left\|d_t \right\|_\infty \leq \frac{1}{\sqrt{1 - \beta}}\) and, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla_t, d_t \rangle + \left(H_0 + H_1 \, f(\theta_t) \right) \, \frac{\eta^2}{1 - \beta} \label{eq:rms-2pl-inter-1} \end{align}\tag{25}\] Using 17 to simplify the second term on the RHS of 25 , \[\begin{align} \langle \nabla_t, d_t \rangle &= \sum_i [\nabla_t]_i \, [d_t]_i = \sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}} \geq \left\|\nabla_t \right\|_1 \, \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1} \tag{26} \intertext{Combining the above inequalities,} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \,\left\|\nabla_t \right\|_1 \, \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1} + \left(H_0 + H_1 \, f(\theta_t) \right) \, \frac{\eta^2}{1 - \beta} \tag{27} \end{align}\]

Phase 1: Define \(T_0\) to be the first iteration s.t. \(f(\theta_{T_0}) < \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\), and analyze the above inequality for \(t < T_0\) where \(f(\theta_t) \geq \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\). Using 27 in this case, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla_t \right\|_1 \, \underbrace{\frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1}}_{(*)} + 2 \, H_1 \, f(\theta_t) \, \frac{\eta^2}{1 - \beta} \label{eq:rms-2pl-p1-1} \end{align}\tag{28}\] We will now use an inductive proof and prove that for all \(t \leq T_0\), \(f(\theta_t) \leq f(\theta_1)\).

Base Case: For \(t = 1\), this is true by definition.

Inductive Hypothesis: Assume for iteration \(t < T_0\), \(f(\theta_t) \leq f(\theta_1)\).

Induction: We will prove that \(f(\theta_{t+1}) \leq f(\theta_1)\). First, for \(\eta \leq \frac{\mu \, \sqrt{1 - \beta}}{ e} \, \left(\frac{H_0}{H_1}\right)^\tau \, \frac{1}{H_0 + H_1 \, f(\theta_1)} \, \ln(\frac{1}{\beta^{1/4}})\) and all \(t\), \[\|\theta_{t+1}-\theta_{t}\|_\infty = |\eta_t|\,\underbrace{\max_i |\frac{g_{t,i}}{\sqrt{v_{t,i}}}|}_{\leq \frac{1}{\sqrt{1-\beta}}}\leq \underbrace{ \mu \,\left(\frac{H_0}{H_1}\right)^\tau}_{c} \, \frac{1}{e(H_0 + H_1 \, f(\theta_1))} \,\underbrace{ \ln(\frac{1}{\beta^{1/4}})}_{a}.\] Since \(f(\theta_t) \leq f(\theta_1)\) by the inductive hypothesis, we can use 18 and obtain that,

\[\begin{align} (*) = \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1} \geq \underbrace{\frac{1 - \beta^{1/4}}{\sqrt{1 - \beta}}}_{:= C} \, \frac{1}{1 + \left( \frac{H_0}{H_1 \, f(\theta_t)} \right)^{\tau} } = \frac{C}{1 + \left( \frac{H_0}{H_1 \, f(\theta_t)} \right)^{\tau} } \label{eq:rms-2pl-induction-1} \end{align}\tag{29}\] Combining 28 and 29 and noting that in Phase (1), \(\frac{H_0}{H_1 \, f(\theta_t)} \leq 1 \implies (*) \geq \frac{C}{2}\), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla_t \right\|_1 \, \frac{C}{2} + 2 \, H_1 \, f(\theta_t) \, \frac{\eta^2}{1 - \beta} \\ & \leq f(\theta_t) - \eta \, [f(\theta_t)]^\tau \, \frac{C \, \mu}{2} + 2 \, H_1 \, f(\theta_t) \, \frac{\eta^2}{1 - \beta}with f^* = 0 and \mu(\theta) = \mu} \\ & \leq f(\theta_t) - \eta \, \frac{f(\theta_t)}{[f(\theta_1)]^{1-\tau}} \, \frac{C \, \mu}{2} + 2 \, H_1 \, f(\theta_t) \, \frac{\eta^2}{1 - \beta} \end{align}\] Using 13 with \(A = \frac{C}{2} \, \frac{\mu}{[f(\theta_1)]^{1 - \tau}}\), \(B = \frac{2 H_1}{1 - \beta}\), \(\bar{\eta}_1 = \min\left\{\frac{\sqrt{1-\beta}}{\sqrt{H_1}}, \frac{\mu \, \sqrt{1 - \beta}}{2 e} \, \left(\frac{H_0}{H_1}\right)^\tau \, \frac{1}{H_0 + H_1 \, f(\theta_1)} \, \ln(\frac{1}{\beta^{1/4})}\right\}\) and \(\delta = \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\), we get that with \(\eta = \min\left\{\bar{\eta}_1, \frac{C \, \mu \, (1 - \beta)}{8 \, H_1 \, [f(\theta_1)]^{1 - \tau}} \right\}\), \(f(\theta_{t+1}) \leq f(\theta_t)\). This completes the induction. Moreover, \(f(\theta_{T_0}) \leq \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\) after \[T_0 \geq O \left(\frac{[f(\theta_1)]^{1 - \tau}}{C \, \mu \, \eta} \ln\left(\frac{f(\theta_1)}{\delta}\right) \right) = O \left(\ln\left(\min\left\{\frac{1}{\epsilon}, \frac{H_1}{H_0} \right\} \right) \right)\, \text{iterations.}\] Hence, if \(\epsilon \geq \frac{H_0}{H_1}\), \(\texttt{RMSProp}\) with a constant step-size requires \(O(\ln(1/\epsilon))\) iterations to guarantee convergence to an \(\epsilon\) sub-optimality.

Phase 2: Consider iteration \(t > T_0\) such that \(f(\theta_t) < \frac{H_0}{H_1}\). Simplifying 27 in this case, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla_t \right\|_1 \, \underbrace{\frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1}}_{(*)} + 2 \, H_0 \, \frac{\eta^2}{1 - \beta} \label{eq:rms-2pl-p1-2} \end{align}\tag{30}\] We will now use an inductive proof and prove that for all \(t \geq T_0\), \(f(\theta_t) \leq f(\theta_{T_0}) \leq \frac{H_0}{H_1}\).

Base Case: For \(t = T_0\), this is true by definition.

Induction: We will prove that \(f(\theta_{t+1}) \leq f(\theta_{T_0})\). Since \(f(\theta_t) \leq f(\theta_{T_0}) \leq \frac{H_0}{H_1} \leq f(\theta_1)\) by the inductive hypothesis, and ensuring that \(\eta \leq \frac{\mu \, \sqrt{1 - \beta}}{2 e} \, \left(\frac{H_0}{H_1}\right)^{\tau} \, \frac{1}{H_0 + H_1 \, f(\theta_1)} \, \ln(\frac{1}{\beta^{1/4}})\), we can use 18 and obtain that, \[\begin{align} (*) = \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1} \geq \underbrace{\frac{1 - \beta^{1/4}}{\sqrt{1 - \beta}}}_{:= C} \, \frac{1}{1 + \left( \frac{H_0}{H_1 \, f(\theta_t)} \right)^{\tau} } = \frac{C}{1 + \left( \frac{H_0}{H_1 \, f(\theta_t)} \right)^{\tau} } \label{eq:rms-2pl-induction-2} \end{align}\tag{31}\] Combining 30 and 31 and noting that, \(\frac{H_0}{H_1 \, f(\theta_t)} \geq 1 \implies (*) \geq \frac{C}{2 \, \left( \frac{H_0}{H_1 \, f(\theta_t)} \right)^{\tau}}\), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla_t \right\|_1 \, \frac{C}{2} \, \left(\frac{H_1}{H_0}\right)^\tau \, [f(\theta)]^\tau + 2 \, H_0 \, \frac{\eta^2}{1 - \beta} \\ & \leq f(\theta_t) - \eta \, \frac{C \, \mu}{2} \, \left( \frac{H_1}{H_0} \right)^\tau \, [f(\theta_t)]^{2 \, \tau} + 2 \, H_0 \, \frac{\eta^2}{1 - \beta}with f^* = 0 and \mu(\theta) = \mu} \end{align}\] Using 14 with \(A = \frac{C \, \mu}{2} \, \left( \frac{H_1}{H_0} \right)^\tau\), \(B = \frac{2 \, H_0}{1- \beta}\), \(\bar{\eta}_1 = \min\left\{\frac{\sqrt{1-\beta}}{\sqrt{H_1}}, \frac{\mu \, \sqrt{1 - \beta}}{2 e} \, \left( \frac{H_1}{H_0} \right)^\tau \, \frac{1}{H_0 + H_1 \, f(\theta_1)} \, \ln(\frac{1}{\beta^{1/4}})\right\}\), \(r = 2\tau\), \(\delta = \epsilon\), we get that with \(\eta = \min\left\{\bar{\eta}_1, \frac{C \, \, \mu \, (1-\beta) \epsilon^{2\tau}}{8 \, H_0} \, \left( \frac{H_1}{H_0} \right)^\tau \right\}\), \(f(\theta_{t+1}) \leq f(\theta_t) \leq f(\theta_{T_0}) \leq \frac{H_0}{H_1}\) for all \(t \geq T_0\). This completes the induction.

Furthermore, for \(\tau = \frac{1}{2}\), \(f(\theta_{T_\epsilon + T_0}) \leq \epsilon\) after \[T_\epsilon \geq O \left( \frac{1}{C \, \mu \, \eta} \, \sqrt{\frac{H_0}{H_1} }\ln\left(\frac{f(\theta_1)}{\delta}\right) \right) = \tilde{O} \left( \frac{1}{\epsilon} \right) \text{iterations}.\] Else, for \(\tau < \frac{1}{2}\), \(f(\theta_{T_\epsilon + T_0}) \leq \epsilon\) after \[T_\epsilon \geq O \left(\frac{[f(\theta_{T_0})]^{1 - 2 \, \tau}}{C \, \mu \, \eta \, (1 - 2 \, \tau)} \, \left( \frac{H_0}{H_1} \right)^\tau \right) = O \left( \frac{1}{\epsilon^{2 \, \tau}} \right) \text{iterations}.\] Else, for \(\tau > \frac{1}{2}\), \(f(\theta_{T_\epsilon + T_0}) \leq \epsilon\) after \[T_\epsilon \geq O \left(\frac{1}{C \, \mu \, \eta \, (2 \, \tau - 1) \, \epsilon^{2 \tau - 1}} \, \left( \frac{H_0}{H_1} \right)^\tau \right) = O \left( \frac{1}{\epsilon^{4 \tau - 1}} \right) \text{iterations}.\] Hence, for \(T := T + T_\epsilon\), \(f(\theta_{T+1}) \leq \epsilon\) after, \[O \left( \frac{1}{\epsilon^{2 \tau}} + \ln \left( \frac{H_1}{H_0} \right) \right) \, \text{iterations, if \tau \leq \frac{1}{2} ;}\] \[O \left( \frac{1}{\epsilon^{4 \tau - 1}} + \ln \left( \frac{H_1}{H_0} \right) \right) \, \text{iterations, if \tau > \frac{1}{2}}\] ◻

Proof. If \(\left\|\theta_{t+1}- \theta_t \right\|_\infty \leq \frac{1}{\sqrt{H_1}}\), using 7 with \(p = \infty\) and \(q = 1\), and denoting \(\nabla_t := \nabla f(\theta_t)\) for convenience, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla_t, d_t \rangle + \left(H_0 + H_1 \, f(\theta_t) \right) \, \eta^2 \, \left\|d_t \right\|^{2}_\infty \end{align}\] Simplifying the third term on the RHS, \[\begin{align} \left\|d_t \right\|_\infty = \max_{i} \frac{g_{t,i}}{\sqrt{v}_{t,i}} \leq \frac{1}{\sqrt{1 - \beta}}\geq (1-\beta) \, g^2_{t,i}} \end{align}\] Ensuring that \(\eta \leq \frac{\sqrt{1-\beta}}{\sqrt{H_1}}\) guarantees that \(\left\|\theta_{t+1}- \theta_t \right\|_\infty \leq \frac{1}{\sqrt{H_1}}\). Combining the above inequalities, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla_t, d_t \rangle + \left(H_0 + H_1 \, f(\theta_t) \right) \, \frac{\eta^2}{1 - \beta} \end{align}\] ◻

Proof. \[\begin{align} \left\|\nabla_t \right\|_1 &= \sum_i |g_{t,i}| = \sum_i \frac{|g_{t,i}|}{v^{1/4}_{t,i}} \, v^{1/4}_{t,i} \leq \sqrt{\sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}} } \, \sqrt{\sum_i \sqrt{v}_{t,i}}\nonumber \\ \implies \left\|\nabla_t \right\|^{2}_1 & \leq \left(\sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}}\right) \, \left(\sum_i \sqrt{v}_{t,i}\right) \implies \left(\sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}}\right) \geq \frac{\left\|\nabla_t \right\|^{2}_1}{\underbrace{\sum_i \sqrt{v}_{t,i} }_{:= u_t} } \label{eq:rms-1pl-secondterm-2} \end{align}\tag{32}\] Simplifying \(u_t\), \[\begin{align} u_t = \sum_i \sqrt{v}_{t,i} & = \sum_i \sqrt{\beta \, v_{t-1,i} + (1-\beta) \, g^2_{t,i}} \leq \sum_i \sqrt{\beta} \, \sqrt{v}_{t-1,i} + \sqrt{1-\beta} \, |g_{t,i}|\leq \sqrt{a} + \sqrt{b}} \nonumber \\ & = \sqrt{\beta} \, \sum_{i} \sqrt{v}_{t-1,i} + \sqrt{1-\beta} \, \left\|\nabla_t \right\|_1 = \sqrt{\beta} \, u_{t-1} + \sqrt{1 - \beta} \, \left\|\nabla_t \right\|_1 \\ \intertext{Recursing from j = 0 to t-1, and using that v_{0,i} = 0,} \implies u_t &\leq \sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1 \label{eq:rms-1pl-urecursion} \\ \implies \left(\sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}}\right) & \geq \left\|\nabla_t \right\|_1 \, \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1}} \end{align}\tag{33}\]  ◻

Proof. Using part (1) of 10 with \(p = \infty\), \(q = 1\) and \(y = \theta_{t-1}\), \(x = \theta_t\), \(c > 0\), \[\begin{align} \left\|\nabla_{t-1} \right\|_1 + c & \leq (\left\|\nabla_{t} \right\|_1 + c) \, \exp\left((H_0 + H_1 \, f(\theta_t)) \, e \, \frac{\left\|\theta_{t-1} - \theta_t \right\|_\infty}{c} \right) \\ & \leq (\left\|\nabla_{t} \right\|_1 + c) \, \exp\left((H_0 + H_1 \, f(\theta_1)) \, e \, \frac{\left\|\theta_{t-1} - \theta_t \right\|_\infty}{c} \right)\\ & \leq (\left\|\nabla_{t} \right\|_1 + c) \, \exp(a)\\ \implies \left\|\nabla_{t-j} \right\|_1 & \leq (\left\|\nabla_{t} \right\|_1 + c) \, \exp(a \, j) \end{align}\] Using the above relation to lower-bound \(\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1\), first note that, \[\begin{align} \sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1 & \leq \sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^j \, (\left\|\nabla_{t} \right\|_1 + c) \, \exp(a \, j) \\ & \leq \frac{\sqrt{1 - \beta} \; (\left\|\nabla_{t} \right\|_1 + c)}{1 - \sqrt{\beta} \, \exp(a)}\, \exp(a) < 1} \\ \implies \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1} & \geq \frac{\left\|\nabla_t \right\|_1}{\left\|\nabla_t \right\|_1 + c} \, \frac{1 - \sqrt{\beta} \, \exp(a)}{\sqrt{1 - \beta}} \end{align}\] Furthermore, if \(f\) satisfies 3 with \(f^* = 0\) and \(\mu(\theta) = \mu\), then, \[\begin{align} \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1} & \geq \frac{1 - \sqrt{\beta} \, \exp(a)}{\sqrt{1 - \beta}} \, \frac{1}{1 + \frac{c}{\mu \, [f(\theta_t)]^{\tau}}}with f^* = 0 and \mu(\theta) = \mu} \\ \implies \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1} & \geq \frac{1 - \sqrt{\beta} \, \exp(a)}{\sqrt{1 - \beta}} \, \frac{1}{1 + \left(\frac{H_0}{H_1} \, \frac{1}{f(\theta_t)}\right)^{\tau}} {H_1}\right)^{\tau}} \end{align}\] ◻

Proof. Using 19 for \(\eta \leq \frac{1}{C_3 \, \sqrt{H_1}}\) and \(\beta_1 \leq \beta_2\) where \(C_3 := \sqrt{\frac{1 - \beta_1}{1 - \beta_2}}\), and, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla_t, d_t \rangle + \left(H_0 + H_1 \, f(\theta_t) \right) \, \eta^2 \, C^2_3 \label{eq:adam-2pl-inter-1} \end{align}\tag{34}\] Simplifying the second term on the RHS of 34 , first note that, \[\begin{align} \langle \nabla_t, d_t \rangle &= \sum_i [\nabla_t]_i \, [d_t]_i = \sum_i \frac{g_{t,i} \, m_{t,i}}{\sqrt{v}_{t,i}} = \sum_i \frac{g_{t,i} \, (m_{t,i} - g_{t,i})}{\sqrt{v}_{t,i}} + \frac{g^2_{t,i}}{\sqrt{v}_{t,i}} \nonumber \\ & \geq -\sum_i \frac{|g_{t,i}| \, |m_{t,i} - g_{t,i}|}{\sqrt{v}_{t,i}} + \sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}} \nonumber \\ \implies - \langle \nabla_t, d_t \rangle & \leq \underbrace{\sum_i \frac{|g_{t,i}| \, |m_{t,i} - g_{t,i}|}{\sqrt{v}_{t,i}}}_{:= \text{Term (i)}} - \underbrace{\sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}}}_{:= \text{Term (ii)}} \label{eq:adam-2pl-secondterm-1} \end{align}\tag{35}\] Bounding Term (i) using 20 and using a constant step-size \(\eta \leq \frac{1}{C_3 \, \sqrt{H_1}} \, \ln(1/\sqrt{\beta_1})\), we get that, \[\begin{align} \text{Term (i)} & \leq \frac{\beta_1\,e \, C_3 \, \sum_{s = 1}^{t-1} (\sqrt{\beta_1})^{t-1-s} \, \eta_{s}}{\sqrt{1 - \beta_2}} \, (H_0 + H_1 \, f(\theta_t)) \\ & \leq \eta \, \underbrace{\frac{\beta_1\,e \, C_3 \, }{\sqrt{1 - \beta_2} \, (1 - \sqrt{\beta_1})}}_{:= C_1} (H_0 + H_1 \, f(\theta_t))\\ \implies \text{Term (i)} & \leq \, \eta \, C_1 \, (H_0 + H_1 \, f(\theta_t)) \label{eq:adam-2pl-secondterm-p1} \end{align}\tag{36}\] Similar to the proof of [thm:rms-pl], we use 17 to bound Term (ii), \[\begin{align} \text{Term (ii)} & \geq \left\|\nabla_t \right\|_1 \, \underbrace{\frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta_2} \, \sum_{j = 0}^{t-1} (\sqrt{\beta_2})^{j} \, \left\|\nabla_{t-j} \right\|_1}}_{(*)} \label{eq:adam-1pl-secondterm} \end{align}\tag{37}\]

Phase 1: Define \(T_0\) to be the first iteration s.t. \(f(\theta_{T_0}) < \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\), and analyze 34 for \(t < T_0\) where \(f(\theta_t) \geq \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\). Using 36 37 and simplifying 34 in this case, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla_t \right\|_1 \, \underbrace{\frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta_2} \, \sum_{j = 0}^{t-1} (\sqrt{\beta_2})^{j} \, \left\|\nabla_{t-j} \right\|_1}}_{(*)} + 2 \, H_1 \, f(\theta_t) \, \eta^2 \, (C_1+ C^2_3) \label{eq:adam-2pl-p1-1} \end{align}\tag{38}\] We will now use an inductive proof and prove that for all \(t \leq T_0\), \(f(\theta_t) \leq f(\theta_1)\).

Base Case: For \(t = 1\), this is true by definition.

Inductive Hypothesis: Assume for iteration \(t < T_0\), \(f(\theta_t) \leq f(\theta_1)\).

Induction: We will prove that \(f(\theta_{t+1}) \leq f(\theta_1)\). Since \(f(\theta_t) \leq f(\theta_1)\) by the inductive hypothesis, and \(\eta \leq \frac{\mu }{2 e C_3} \, \left(\frac{H_0}{H_1}\right)^\tau \, \frac{1}{H_0 + H_1 \, f(\theta_1)} \, \ln(\frac{1}{\beta_2^{1/4}})\) so \[\|\theta_{t+1}-\theta_{t}\|_\infty \leq \eta \, C_3 \leq \underbrace{\mu \, \left(\frac{H_0}{H_1}\right)^\tau}_{c} \,\frac{1}{e}\, \frac{1}{H_0 + H_1 \, f(\theta_1)} \, \underbrace{\ln(\frac{1}{\beta_2^{1/4}})}_{a},\] we can use 18 and obtain that,

\[\begin{align} (*) = \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta_2} \, \sum_{j = 0}^{t-1} (\sqrt{\beta_2})^{j} \, \left\|\nabla_{t-j} \right\|_1} \geq \underbrace{\frac{1 - \beta_2^{1/4}}{\sqrt{1 - \beta_2}}}_{:= C_2} \, \frac{1}{1 + \left( \frac{H_0}{H_1 \, f(\theta_t)} \right)^{\tau} } = \frac{C_2}{1 + \left( \frac{H_0}{H_1 \, f(\theta_t)} \right)^{\tau} } \label{eq:adam-2pl-induction-1} \end{align}\tag{39}\] Combining 38 and 39 and noting that in Phase (1), \(\frac{H_0}{H_1 \, f(\theta_t)} \leq 1 \implies (*) \geq \frac{C_2}{2}\), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla_t \right\|_1 \, \frac{C_2}{2} + 2 \, H_1 \, f(\theta_t) \, \eta^2 \, (C_1+ C^2_3) \\ & \leq f(\theta_t) - \eta \, [f(\theta_t)]^\tau \, \frac{C_2 \, \mu}{2} + 2 \, H_1 \, f(\theta_t) \, \eta^2 \, (C_1+ C^2_3)with f^* = 0 and \mu(\theta) = \mu} \\ & \leq f(\theta_t) - \eta \, \frac{f(\theta_t)}{[f(\theta_1)]^{1-\tau}} \, \frac{C_2 \, \mu}{2}+ 2 \, H_1 \, f(\theta_t) \, \eta^2 \, (C_1+ C^2_3) \end{align}\]

Using 13 with \(A = \frac{C_2}{2} \, \frac{\mu}{[f(\theta_1)]^{1 - \tau}}\), \(B = 2 \, H_1(C_1+ C^2_3)\), \(\bar{\eta}_1 = \min\left\{\frac{1}{C_3 \, \sqrt{H_1}}, \frac{1}{C_3 \, \sqrt{H_1}} \, \ln(1/\sqrt{\beta_1}), \frac{\mu }{2 e C_3} \, \left(\frac{H_0}{H_1}\right)^\tau \, \frac{1}{H_0 + H_1 \, f(\theta_1)} \, \ln(\frac{1}{\beta_2^{1/4})} \right\}\), \(\delta = \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\), we get that with \(\eta = \min\left\{\bar{\eta}_1, \frac{C_2 \, \mu}{8 \, (C_1+ C^2_3) \, H_1 \, [f(\theta_1)]^{1 - \tau}} \right\}\), \(f(\theta_{t+1}) \leq f(\theta_t)\). This completes the induction. Moreover, \(f(\theta_{T_0}) \leq \max\left\{\epsilon, \frac{H_0}{H_1} \right\}\) after \[T_0 \geq O \left(\frac{ [f(\theta_1)]^{1 - \tau}}{C_2 \, \mu \, \eta} \right) = O \left(\ln\left(\min\left\{\frac{1}{\epsilon}, \frac{H_1}{H_0} \right\} \right) \right)\, \text{iterations.}\] Hence, if \(\epsilon \geq \frac{H_0}{H_1}\), \(\texttt{Adam}\) with a constant step-size requires \(O(\ln(1/\epsilon))\) iterations to guarantee convergence to an \(\epsilon\) sub-optimality.

Phase 2: Consider iteration \(t > T_0\) such that \(f(\theta_t) < \frac{H_0}{H_1}\). Simplifying 34 in this case, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla_t \right\|_1 \, \underbrace{\frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta_2} \, \sum_{j = 0}^{t-1} (\sqrt{\beta_2})^{j} \, \left\|\nabla_{t-j} \right\|_1}}_{(*)} + 2 \, H_0 \, \eta^2 (C_1+ C^2_3) \label{eq:adam-2pl-p1-2} \end{align}\tag{40}\] We will now use an inductive proof and prove that for all \(t \geq T_0\), \(f(\theta_t) \leq f(\theta_{T_0}) \leq \frac{H_0}{H_1} \leq f(\theta_1)\).

Base Case: For \(t = T_0\), this is true by definition.

Induction: We will prove that \(f(\theta_{t+1}) \leq f(\theta_{T_0})\). Since \(f(\theta_t) \leq f(\theta_{T_0}) \leq \frac{H_0}{H_1} \leq f(\theta_1)\) by the inductive hypothesis, and ensuring that \(\eta \leq \frac{\mu }{2C_3 e} \, \left(\frac{H_0}{H_1}\right)^{\tau} \, \frac{1}{H_0 + H_1 \, f(\theta_1)} \, \ln(\frac{1}{\beta^{1/4}})\), we can use 18 and obtain that,

\[\begin{align} (*) = \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1} \geq \underbrace{\frac{1 - \beta^{1/4}}{\sqrt{1 - \beta}}}_{:= C_2} \, \frac{1}{1 + \left( \frac{H_0}{H_1 \, f(\theta_t)} \right)^{\tau} } = \frac{C_2}{1 + \left( \frac{H_0}{H_1 \, f(\theta_t)} \right)^{\tau} } \label{eq:adam-2pl-induction-2} \end{align}\tag{41}\] Combining 40 and 41 and noting that, \(\frac{H_0}{H_1 \, f(\theta_t)} \geq 1 \implies (*) \geq \frac{C_2}{2 \, \left( \frac{H_0}{H_1 \, f(\theta_t)} \right)^{\tau}}\), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla_t \right\|_1 \, \frac{C_2}{2} \, \left(\frac{H_1}{H_0}\right)^\tau \, [f(\theta)]^\tau + 2 \, H_0 \, \eta^2(C_1+ C^2_3) \\ & \leq f(\theta_t) - \eta \, \frac{C_2 \, \mu}{2} \, \left( \frac{H_1}{H_0} \right)^\tau \, [f(\theta_t)]^{2 \, \tau}+ 2 \, H_0 \, \eta^2 \, (C_1+ C^2_3) with f^* = 0 and \mu(\theta) = \mu} \end{align}\]

Using 14 with \(A = \frac{C_2 \, \mu}{2} \, \left( \frac{H_1}{H_0} \right)^\tau\), \(B = 2 \, H_0\, (C_1+ C^2_3)\),
\(\bar{\eta}_1 = \min\left\{\frac{1}{C_3 \, \sqrt{H_1}}, \frac{1}{C_3 \, \sqrt{H_1}} \, \ln(1/\sqrt{\beta_1}), \frac{\mu }{2 e C_3} \, \left(\frac{H_0}{H_1}\right)^\tau \, \frac{1}{H_0 + H_1 \, f(\theta_1)} \, \ln(\frac{1}{\beta_2^{1/4}}) \right\}\), \(r = 2\tau\), \(\delta = \epsilon\), we get that with
\(\eta = \min\left\{\bar{\eta}_1, \frac{C_2 \, \mu \, \epsilon^{2\tau}}{8 \, H_0 \, (C_1+ C^2_3)} \, \left( \frac{H_1}{H_0} \right)^\tau \right\}\), \(f(\theta_{t+1}) \leq f(\theta_t) \leq f(\theta_{T_0}) \leq \frac{H_0}{H_1}\) for all \(t \geq T_0\). This completes the induction.

Furthermore, for \(\tau = \frac{1}{2}\), \(f(\theta_{T_\epsilon + T_0}) \leq \epsilon\) after \[T_\epsilon \geq O\left(\frac{1}{C_2 \, \mu \, \eta} \, \sqrt{\frac{H_0}{H_1} } \ln\left(\frac{f_{T_0}}{2}\right)\right) = \tilde{O} \left( \frac{1}{\epsilon} \right) \text{iterations}.\] Else, for \(\tau < \frac{1}{2}\), \(f(\theta_{T_\epsilon + T_0}) \leq \epsilon\) after \[T_\epsilon \geq O \left( \frac{[f(\theta_{T_0})]^{1 - 2 \, \tau}}{C_2 \, \mu \, \eta \, (1 - 2 \, \tau)} \, \left( \frac{H_0}{H_1} \right)^\tau \right) = O \left( \frac{1}{\epsilon^{2 \, \tau}} \right) \text{iterations}.\] Else, for \(\tau > \frac{1}{2}\), \(f(\theta_{T_\epsilon + T_0}) \leq \epsilon\) after \[T_\epsilon \geq O \left(\frac{1}{C_2 \, \mu \, \eta \, (2 \, \tau - 1) \, \epsilon^{ 2 \tau - 1}} \, \left( \frac{H_0}{H_1} \right)^\tau \right) = O \left( \frac{1}{\epsilon^{4 \tau - 1}} \right) \text{iterations}.\] Hence, for \(T := T + T_\epsilon\), \(f(\theta_{T+1}) \leq \epsilon\) after, \[O \left( \frac{1}{\epsilon^{2 \tau}} + \ln \left( \frac{H_1}{H_0} \right) \right) \, \text{iterations, if \tau \leq \frac{1}{2} ;}\] \[O \left( \frac{1}{\epsilon^{4 \tau - 1}} + \ln \left( \frac{H_1}{H_0} \right) \right) \, \text{iterations, if \tau > \frac{1}{2}}\] ◻

Proof. Since we are considering logistic regression on linearly separable data, \(f^* = 0\) and \(H_0 = 0\). We will use a similar proof as that for [thm:adam-pl]. In particular, using 19 for \(\eta \leq \bar{\eta}_0 := \frac{1}{C_3 \, \sqrt{H_1}}\) and \(\beta_1 \leq \beta_2\) where \(C_3 := \sqrt{\frac{1 - \beta_1}{1 - \beta_2}}\), and, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla_t, d_t \rangle + \left(H_1 \, f(\theta_t) \right) \, \eta^2 \, C_3 \label{eq:adam-logreg-inter-1} \end{align}\tag{42}\] Simplifying the second term on the RHS of 42 , first note that, \[\begin{align} \langle \nabla_t, d_t \rangle &= \sum_i [\nabla_t]_i \, [d_t]_i = \sum_i \frac{g_{t,i} \, m_{t,i}}{\sqrt{v}_{t,i}} = \sum_i \frac{g_{t,i} \, (m_{t,i} - g_{t,i})}{\sqrt{v}_{t,i}} + \frac{g^2_{t,i}}{\sqrt{v}_{t,i}} \nonumber \\ & \geq -\sum_i \frac{|g_{t,i}| \, |m_{t,i} - g_{t,i}|}{\sqrt{v}_{t,i}} + \sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}} \nonumber \\ \implies - \langle \nabla_t, d_t \rangle & \leq \underbrace{\sum_i \frac{|g_{t,i}| \, |m_{t,i} - g_{t,i}|}{\sqrt{v}_{t,i}}}_{:= \text{Term (i)}} - \underbrace{\sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}}}_{:= \text{Term (ii)}} \label{eq:adam-logreg-secondterm-1} \end{align}\tag{43}\] Bounding Term (i) using 20 and using a constant step-size equal to \(\eta\), we get that, \[\begin{align} \text{Term (i)} & \leq \frac{\beta_1\,e \, C_3 \, \sum_{s = 1}^{t-1} (\sqrt{\beta_1})^{t-1-s} \, \eta_{s}}{\sqrt{1 - \beta_2}} \, ( H_1 \, f(\theta_t)) \\ & \leq \eta \, \underbrace{\frac{\beta_1\,e \, C_3 \, }{\sqrt{1 - \beta_2} \, (1 - \sqrt{\beta_1})}}_{:= C_1} ( H_1 \, f(\theta_t))\\ \implies \text{Term (i)} & \leq \, \eta C_1 \, (H_1 \, f(\theta_t)) \label{eq:adam-logreg-secondterm-2} \end{align}\tag{44}\] Similar to the proof of [thm:rms-pl], we use 17 to bound Term (ii), \[\begin{align} \text{Term (ii)} & \geq \left\|\nabla_t \right\|_1 \, \underbrace{\frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta_2} \, \sum_{j = 0}^{t-1} (\sqrt{\beta_2})^{j} \, \left\|\nabla_{t-j} \right\|_1}}_{(*)} \label{eq:adam-logreg-secondterm-3} \end{align}\tag{45}\]

We will use 18 to bound (*). For this, we need to ensure that (i) the value of \(\eta\) ensures that \(\left\|\theta_{t+1}- \theta_t \right\|_\infty = \eta \, \left\|d_t \right\|_{\infty} = \eta \, C_3 < \underbrace{\frac{\gamma_1}{3 n \, e}}_{c/e} \, \frac{1}{H_1 \, f(\theta_1)} \, \underbrace{\ln(1/\beta_2^{1/4})}_{a}\). Setting \[\eta \leq \bar{\eta}_1 := \frac{\gamma_1 }{4 \, n \, e \, C_3} \, \frac{1}{H_1 \, f(\theta_1)} \, \ln(1/ \beta_2^{1/4})\] ensures that this condition is satisfied. Furthermore, we need to ensure that (ii) \(f(\theta_t) \leq f(\theta_1)\). For this, we will use an inductive argument and prove that for all \(t \geq 1\), \(f(\theta_t) \leq f(\theta_1)\).

Base Case: For \(t = 1\), this is true by definition.

Inductive Hypothesis: Assume for iteration \(t > 1\), \(f(\theta_t) \leq f(\theta_1)\).

Induction: We will prove that \(f(\theta_{t+1}) \leq f(\theta_1)\). Since \(f(\theta_t) \leq f(\theta_1)\) by the inductive hypothesis, and \(\eta \leq \bar{\eta}_1\), we can use 18 and obtain that, \[\begin{align} (*) = \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta_2})^{j} \, \left\|\nabla_{t-j} \right\|_1} & \geq \frac{\left\|\nabla_t \right\|_1}{\left\|\nabla_t \right\|_1 + c} \, \frac{1 - \sqrt{\beta_2} \, \exp(a)}{\sqrt{1 - \beta_2}} \label{eq:adam-logreg-precond} \end{align}\tag{46}\] To complete the induction, we will consider two phases. For this, define \(T_0\) to be the first iteration s.t. \(f(\theta_{T_0}) < \max\left\{\epsilon, \frac{\ln(2)}{n}\right\}\).

Phase 1: For all \(t < T_0\), \(f(\theta_t) > \frac{\ln(2)}{n}\) and we use part (2) of [prop:logistic] to conclude that \(\left\|\nabla_t \right\|_1 \geq \frac{\gamma_1}{3n}\). Using this relation with 46 and using that \(c = \frac{\gamma_1}{3n}\), \(\alpha = \ln(\frac{1}{\beta_2^{1/4}})\) \[\begin{align} (*) \geq \frac{1}{2} \, \underbrace{\frac{1 - \beta_2^{1/4}}{\sqrt{1- \beta_2}}}_{C_4} _1 and since \beta_2 < 1} \end{align}\] Combining the above relation with 42 44 , \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \frac{\eta \,C_4\, \left\|\nabla_t \right\|_1}{2} + H_1 \, f(\theta_t) \, \eta^2(C_1+C^2_3) \\ & \leq f(\theta_t) - \frac{\eta \,C_4\, \left\|\nabla_t \right\|_1}{2} + H_1 \, f(\theta_1) \, \eta^2(C_1+C^2_3)\\ & \leq f(\theta_t) - \frac{\eta\,C_4 \, \gamma_1}{6n} + H_1 \, f(\theta_1) \, \eta^2(C_1+C^2_3) {3n}} \\ & \leq f(\theta_t) - \frac{\eta \,C_4\, \gamma_1}{12n} _2 := \frac{ \gamma_1\,C_4}{12 \, H_1 \, f(\theta_1) \, n \, (C_1+C^2_3)}} \\ \intertext{Since f(\theta_{t+1}) \leq f(\theta_t) \leq f(\theta_1), this completes the induction for Phase 1. By recursing for T_0-1 iterations,} \implies f(\theta_{T_0}) & \leq f(\theta_1) - \frac{\eta\,C_4 \, \gamma_1}{12n} \, (T_0-1) = \ln(2) - \frac{\eta\,C_4 \, \gamma_1}{12n} \, (T_0-1) \end{align}\] Hence, by using that \(\eta \leq \min\{\bar{\eta}_0, \bar{\eta}_1 , \bar{\eta}_2\}\), \[\begin{align} T_0 & \geq O \left(\frac{n}{\eta \,C_4\, \gamma_1} \right) = O \left( \left(\frac{n}{\gamma_1}\right)^2 \right) \end{align}\] iterations guarantee that \(f(\theta_{T_0}) \leq \frac{\ln(2)}{n}\).

Phase 2: After \(T_0\) iterations, \(f(\theta_{T_0}) \leq \frac{\ln(2)}{n} < f(\theta_1)\). We will now prove that for \(t > T_0\), \(f(\theta_t) \leq f(\theta_{T_0}) < f(\theta_1)\), thus completing the induction in Phase 2. We will again do this proof via induction.

Base Case: For \(t = T_0\), this is true by definition.

Inductive Hypothesis: Assume for iteration \(t > T_0\), \(f(\theta_t) \leq f(\theta_{T_0})\).

Induction: We will prove that \(f(\theta_{t+1}) \leq f(\theta_{T_0)}\). Since \(f(\theta_t) \leq f(\theta_{T_0}) < f(\theta_1)\) by the inductive hypothesis, we can again use an appropriate step-size \[\eta \leq \bar{\eta}_3 := \frac{\gamma_1}{2e \, C_3 \, H_1}\ln\left(\frac{1}{\beta_2^{1/4}}\right)\,,\] which then guarantees \[\|\theta_{t+1} - \theta_t\|_p \leq \eta\, C_3 \leq \frac{\gamma_1 }{2e H_1 }\ln\left(\frac{1}{\beta_2^{1/4}}\right) = \frac{ca}{eH_1f(\theta)}, \qquad c = \frac{\gamma_1 \, f(\theta_1)}{2}, \, a = \ln\left(\frac{1}{\beta_2^{1/4}}\right)\] and 46 to bound (*) as follows: \[\begin{align} (*) = \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta_2} \, \sum_{j = 0}^{t-1} (\sqrt{\beta_2})^{j} \, \left\|\nabla_{t-j} \right\|_1} & \geq \frac{\left\|\nabla_t \right\|_1}{\left\|\nabla_t \right\|_1 + c} \, \frac{1 - \sqrt{\beta_2} \, \exp(a)}{\sqrt{1 - \beta_2}} \\ \intertext{Using part (1) of~\ref{prop:logistic} to conclude that \left\|\nabla_t \right\|_1 \geq \frac{\gamma_p}{2} \, f(\theta_t), using the induction hypothesis to further bound f(\theta_t) by f(\theta_1) and using that c = \frac{\gamma_1 \, f(\theta_1)}{2},} (*) & \geq \frac{1}{2} \, \underbrace{\frac{1 - \beta_2^{1/4}}{\sqrt{1 - \beta_2}}}_{=:C_4} _3} \end{align}\] Combining the above relation with 42 44 , \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \frac{\eta \,C_4\, \left\|\nabla_t \right\|_1}{2} + H_1 \, f(\theta_t) \, \eta^2\, (C_1+ C^2_3) \\ & \leq f(\theta_t) - \frac{\eta \, C_4\,\gamma_1}{4} f(\theta_t) + H_1 \, f(\theta_t) \, \eta^2\, (C_1+ C^2_3)} \\ & \leq f(\theta_t) - \frac{\eta \, C_4\,\gamma_1}{8} f(\theta_t) _4 := \frac{\gamma_1 \,}{8 \, H_1 \, (C_1+C^2_3)} } \\ \intertext{Since f(\theta_{t+1}) < f(\theta_t) < f(\theta_{T_0}), this completes the induction. Furthermore, by recursing for T iterations} \implies f(\theta_{T_0 + T}) & \leq f(\theta_{T_0}) \, \exp\left(-\frac{\eta \, C_4\,\gamma_1}{8} \, T \right) \leq \frac{\ln(2)}{n} \, \, \exp\left(-\frac{\eta \,C_4\, \gamma_1}{8} \, T \right) \end{align}\] Hence, by using a step-size \(\eta \leq \min\{\bar{\eta}_0, \bar{\eta}_3, \bar{\eta}_4\}\), \[T \geq O \left( \frac{1}{\eta \,C_4\, \gamma_1} \, \ln\left(\frac{\ln(2)}{n \, \epsilon} \right) \right) = O \left( \frac{1}{\gamma_1^2} \, \ln\left(\frac{1}{n \epsilon}\right) \right)\] iterations suffice to guarantee that \(f(\theta_{T + T_0}) \leq \epsilon\). Hence, attaining an \(\epsilon\) sub-optimality for logistic regression requires, \[\begin{align} T_{\text{final}} &= O \left( \frac{1}{\gamma_1^2} \, \ln\left(\frac{1}{n \epsilon}\right) \right) + O \left( \left(\frac{n}{\gamma_1}\right)^2 \right) \\ &= O\left( \frac{1}{\gamma_1^2} \, \left[n^2 + \ln\left(\frac{1}{n \epsilon}\right)\right]\right) \text{iterations}. \end{align}\] ◻

Proof. If \(\left\|\theta_{t+1}- \theta_t \right\|_\infty \leq \frac{1}{\sqrt{H_1}}\), using 7 with \(p = \infty\) and \(q = 1\), and denoting \(\nabla_t := \nabla f(\theta_t)\) for convenience, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla_t, d_t \rangle + \left(H_0 + H_1 \, f(\theta_t) \right) \, \eta^2 \, \left\|d_t \right\|^{2}_\infty \end{align}\] Simplifying the third term on the RHS, \(\left\|d_t \right\|_\infty = \max_{i} \frac{m_{t,i}}{\sqrt{v}_{t,i}}\), and \[\begin{align} m_{t,i} & = (1-\beta_1) \, \sum_{s = 1}^{t} \beta_1^{t-s} g_{s,i} \\ \implies m^2_{t,i} & \leq \left(1-\beta_1\right)^2 \, \left(\sum_{s = 1}^{t} \beta_1^{t-s}\right) \left(\sum_{s = 1}^{t} \beta_1^{t-s} g^2_{s,i} \right)\\ & \leq \left(1-\beta_1\right) \, \sum_{s = 1}^{t} \beta_1^{t-s} g^2_{s,i}\\ & \leq \frac{1 - \beta_1}{1 - \beta_2} \, \left[\left(1-\beta_2\right) \, \sum_{s = 1}^{t} \beta_2^{t-s} g^2_{s,i} \right]\\ &= \frac{1 - \beta_1}{1 - \beta_2} \, v_{t,i} } \\ \implies \frac{m^2_{t,i}}{v_{t,i}} & \leq \frac{1 - \beta_1}{1 - \beta_2} \implies \frac{m_{t,i}}{\sqrt{v}_{t,i}} \leq B := \sqrt{\frac{1 - \beta_1}{1 - \beta_2} } \\ \implies \left\|\theta_{t+1}- \theta_t \right\|_\infty & \leq \eta \, \left\|d_t \right\|_\infty \leq \eta \, B \label{eq:adam-1pl-thirdterm} \end{align}\tag{47}\] Ensuring that \(\eta \leq \frac{1}{B \, \sqrt{H_1}}\) guarantees that \(\left\|\theta_{t+1}- \theta_t \right\|_\infty \leq \frac{1}{\sqrt{H_1}}\). Combining the above inequalities, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla_t, d_t \rangle + \left(H_0 + H_1 \, f(\theta_t) \right) \, \eta^2 \, B^2 \end{align}\] ◻

Proof. \[\begin{align} \sum_i \frac{|g_{t,i}| \, |m_{t,i} - g_{t,i}|}{\sqrt{v}_{t,i}} &\leq \frac{1}{\sqrt{1 - \beta_2}} \, \sum_i |m_{t,i} - g_{t,i}|\geq (1 - \beta_2) \, g^2_{t,i}} \\ & \leq \frac{\left\|m_t - g_t \right\|_1}{\sqrt{1 - \beta_2}} \label{eq:adam-1pl-mom-recursion-1} \end{align}\tag{48}\] In order to bound \(\left\|m_t - g_t \right\|_1\), note that for all \(i \in [D]\), \[\begin{align} |m_{t,i} - g_{t,i}| &= |\beta_1 \, m_{t-1,i} + (1-\beta_1) \, g_{t,i} - g_{t,i}| = \beta_1 \, |m_{t-1,i} - g_{t,i}| \\ & \leq \beta_1 \, |m_{t-1,i} - g_{t-1,i}| + \beta_1 \, |g_{t-1,i} - g_{t,i}|\\ \implies \sum_i |m_{t,i} - g_{t,i}| & \leq \beta_1 \, \sum_i |m_{t-1,i} - g_{t-1,i}| + \beta_1 \, \sum_i |g_{t-1,i} - g_{t,i}| \nonumber \\ \implies \left\|m_t - g_t \right\|_1 & \leq \beta_1 \left\|m_{t-1} - \nabla_{t-1} \right\|_1 + \beta_1 \left\|\nabla_t - \nabla_{t-1} \right\|_1 \nonumber \\ \intertext{Simplifying the second term on the RHS using~\ref{lemma:grad-lip-gen} with p = \infty, q = 1, y = \theta_{t-1} and x = \theta_t. Ensuring that \eta_{t-1} \leq \frac{1}{B \, \sqrt{H_1}} guarantees that \left\|\theta_t- \theta_{t+1} \right\|_\infty \leq \frac{1}{\sqrt{H_1}}. Hence,} \implies\left\|m_t - g_t \right\|_1& \leq \beta_1 \, \left\|m_{t-1} - \nabla_{t-1} \right\|_1 + \beta_1 \, (H_0 + H_1 \, f(\theta_t)) \, e \, \left\|\theta_t- \theta_{t-1} \right\|_{\infty} \nonumber \\ & \leq \beta_1 \, \left\|m_{t-1} - \nabla_{t-1} \right\|_{1} + \beta_1 \, \underbrace{(H_0 + H_1 \, f(\theta_t))}_{:= \bar{L}_t} \, e \, \eta_{t-1} \, B } \\ \implies \frac{\left\|m_t - g_t \right\|_1}{\bar{L}_t} & \leq \beta_1 \, \frac{\left\|m_{t-1} - \nabla_{t-1} \right\|_{1}}{\bar{L}_t} + \beta_1 \,e \, \eta_{t-1} \, B \label{eq:adam-1pl-mom-recursion-2} \end{align}\tag{49}\] We now write \(\bar{L}_t\) in terms of \(\bar{L}_{t-1}\). In particular, using 5 with \(p = \infty\), \(q = 1\) and \(y = \theta_{t-1}\), \(x = \theta_t\), \[\begin{align} \bar{L}_t = H_0 + H_1 \, f(\theta_t) & \geq H_0 + H_1 \left[ \left(f(\theta_{t-1}) + \frac{H_0}{H_1} \right) \exp\left(-\sqrt{H_1} \, \left\|\theta_t- \theta_{t-1} \right\|_{\infty} \right) - \frac{H_0}{H_1} \right] \nonumber\\ & = \left(H_0 + H_1 \, f(\theta_{t-1}) \right) \, \exp\left(-\sqrt{H_1} \, \left\|\theta_t- \theta_{t-1} \right\|_{\infty} \right) \nonumber \\ &= \bar{L}_{t-1} \, \exp\left(-\sqrt{H_1} \, \left\|\theta_t- \theta_{t-1} \right\|_{\infty} \right) \nonumber\\ \implies \frac{1}{\bar{L}_t} & \leq \frac{1}{\bar{L}_{t-1}} \, \exp\left(\sqrt{H_1} \, \left\|\theta_t- \theta_{t-1} \right\|_{\infty} \right) \leq \frac{1}{\bar{L}_{t-1}} \, \frac{1}{\sqrt{\beta_1}}and since \eta_{t-1} \leq \frac{1}{B \, \sqrt{H_1}} \, \ln(1/\sqrt{\beta_1}} \end{align}\] Combining the above inequality with 49 , \[\begin{align} \frac{\left\|m_t - g_t \right\|_1}{\bar{L}_t} & \leq \sqrt{\beta_1} \, \frac{\left\|m_{t-1} - \nabla_{t-1} \right\|_{1}}{\bar{L}_{t-1}} + \beta_1\,e \, \eta_{t-1} \, B \\ & \leq \beta_1\,e \, B \, \sum_{s = 1}^{t-1} (\sqrt{\beta_1})^{t-1-s} \, \eta_{s}= g_{1,i}} \\ \implies \left\|m_t - g_t \right\|_1 & \leq (H_0 + H_1 \, f(\theta_t)) \, \beta_1\,e \, B \, \sum_{s = 1}^{t-1} (\sqrt{\beta_1})^{t-1-s} \, \eta_{s} \label{eq:adam-1pl-mom-recursion-final} \end{align}\tag{50}\] Combining the above inequality with 48 , \[\begin{align} \sum_i \frac{|g_{t,i}| \, |m_{t,i} - g_{t,i}|}{\sqrt{v}_{t,i}} & \leq (H_0 + H_1 \, f(\theta_t)) \, \underbrace{\frac{\beta_1\,e \, B \, \sum_{s = 1}^{t-1} (\sqrt{\beta_1})^{t-1-s} \, \eta_{s}}{\sqrt{1 - \beta_2}}}_{:= C_1} = C_1 \, (H_0 + H_1 \, f(\theta_t)) \end{align}\] ◻

Proof. Note that \(\nabla f(\theta) = \frac{-1}{1 + \exp(\theta)} < 0\) for all finite \(\theta\). We define \(\nabla_t := \nabla f(\theta_t)\). Since \(\beta \in [0,1)\), for all \(t\), \[\begin{align} m_t & = (1-\beta) \, \sum_{s = 1}^{t} \beta^{t-s} \, \nabla_s \implies m_t < 0 \tag{51} \\ \implies \theta_{t+1}& = \theta_t- {\eta_t}\, m_t = \theta_t+ {\eta_t}| m_t | \leq \theta_t+ \eta_1 \, |m_t|is non-increasing} \\ \implies \theta_{t+1}& = \theta_t+ \eta_1 \, |m_t| \tag{52} \end{align}\] Hence, \(\theta_{t+1}> \theta_t\) for all \(t\). Since \(\theta_1 = 0\), \(\theta_t \geq 0\) for all \(t \geq 1\) and consequently, \(|\nabla_t| \leq 1\). Using this relation to uniformly bound the magnitude of \(m_t\), \[\begin{align} |m_t| & = |(1-\beta) \, \sum_{s = 1}^{t} \beta^{t-s} \, \nabla f(\theta_s)| \leq (1-\beta) \, \sum_{s = 1}^{t} \beta^{t-s} \, |\nabla_s|\\ \implies |m_t| & \leq 1 \label{eq:mt-magnitude} \end{align}\tag{53}\] We will now relate \(|m_t|\) to \(|\nabla_t|\). For this note that the logistic loss satisfies 1, 2 with \(H_0 = 0\) and \(H_1 = 1\), and 3 with \(\zeta = 1\), \(f^* = 0\) and \(\mu = 1\). Using Part 2 of 10 and noting that \(c :=\frac{\mu(H_0+H_1 f^*)}{H_1} = 0\), we get that, \[\begin{align} |\nabla_{t-1}| &\leq |\nabla_t| \, \exp \left( | \theta_{t} - \theta_{t-1}| \right) = |\nabla_t| \, \exp \left( \eta_{t-1} \, |m_{t-1}| \right) \leq |\nabla_t| \, \exp \left( \eta_1 \, |m_{t-1}| \right)is non-increasing} \\ \implies |\nabla_{t-1}| &\leq |\nabla_t| \, \exp(\eta_1) \implies |\nabla_{t-j}| \leq |\nabla_t| \, \exp(\eta_1 \, j) } \end{align}\] Using the above inequality to bound \(|m_t|\) in terms of \(|\nabla_t|\), \[\begin{align} |m_t| & \leq (1-\beta) \, \sum_{j = 0}^{t} \beta^j \, |\nabla_{t-j}|\\ & \leq (1-\beta) \, |\nabla_{t}| \sum_{j = 0}^{t} \beta^j \, \exp(\eta_1 \, j) \nonumber \\ & \leq \frac{1-\beta}{1 - \beta \, \exp(\eta_1)} \, |\nabla_{t}| {\beta}\right)} \\ \implies |m_t| & \leq \frac{1-\beta}{1 - \beta \, \exp(\eta_1)} \, |\nabla_t| \label{eq:mt-nablat} \end{align}\tag{54}\] Using 54 with 52 , \[\begin{align} \theta_{t+1}&= \theta_t+ \eta_1 \, |m_t| \leq \theta_t+ \underbrace{\frac{\eta_1 \, (1-\beta)}{1 - \beta \, \exp(\eta_1)}}_{:= C} \, |\nabla_t| = \theta_t+ \frac{C}{1 + \exp(\theta_t)} \end{align}\] In order to complete the proof we will use the following inequalities to bound \(\frac{1}{1 + \exp(\theta)}\). \[\begin{align} \forall \theta \text{,} \quad & \frac{1}{1 + \exp(\theta)} < \frac{1}{\exp(\theta)} = \exp(-\theta) \quad \text{;} \quad \forall \theta \geq 0 \,, \, \frac{1}{1 + \exp(\theta)} = \frac{\exp(-\theta)}{1 + \exp(-\theta)} > \frac{\exp(-\theta)}{2} \label{eq:grad-bounds} \end{align}\tag{55}\] Using the above bounds, since \(C> 0\), \[\begin{align} \theta_{t+1}- \theta_t& \leq C\, \exp(-\theta_t) \nonumber \\ \implies \exp(\theta_{t+1}) - \exp(\theta_t) &= \exp(\theta_t) [ \exp(\theta_{t+1}- \theta_t) - 1] \leq \exp(\theta_t) \, [ \exp(C\, \exp(-\theta_t)) - 1] \nonumber\\ \intertext{For x \in (0, 1] and c > 0, \exp(cx) - 1 \leq (\exp(c)) \, c \, x. Since \theta_t\geq 0, using this inequality with x = \exp(-\theta_t) \leq 1 and c = C > 0,} \exp(\theta_{t+1}) - \exp(\theta_t) & \leq \exp(\theta_t) \, \left[ C\, (\exp(C)) \, \exp(-\theta_t) \right] = C \, \exp(C) \nonumber \\ \intertext{Summing up from t = 1 to T and telescoping, } \exp(\theta_{T+1}) - \exp(\theta_1) & \leq C \, \exp(C) \, T \implies \exp(\theta_{T+1}) \leq 1 + C \, \exp(C) \, T\\ \implies \exp(-\theta_{T+1}) & \geq \frac{1}{1 + C\, \exp(C) \, T} \label{eq:adagrd-inter} \end{align}\tag{56}\] For all \(x \in [0,1]\), \(\ln(1+x) > \frac{x}{2}\). Since \(\theta_{T+1} \geq 0\), \(\exp(-\theta_{T+1}) \leq 1\), using this inequality with \(x = \exp(-\theta_{T+1})\), \[\begin{align} f(\theta_{T+1}) &= \ln(1 + \exp(-\theta_{T+1})) \geq \frac{\exp(-\theta_{T+1})}{2} \geq \frac{1}{2 \, (1 + C \, \exp(C) \, T)} \end{align}\] Since \(C\) is a constant independent of \(T\), the convergence rate is lower-bounded by \(\Omega(1/T)\). ◻

Proof. Using 25 for \(\eta \leq \bar{\eta}_0 := \frac{1}{C_3 \, L_1}\) and \(\beta_1 \leq \beta_2\) where \(C_3 := \sqrt{\frac{1 - \beta_1}{1 - \beta_2}}\), and, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla_t, d_t \rangle + \left(L_0 + L_1 \, \left\|\nabla f(\theta_t) \right\|_1 \right) \, \eta^2 \, C^2_3 \label{eq:adam-2pl-inter-1-gnus} \end{align}\tag{57}\] Simplifying the second term on the RHS of 57 , first note that, \[\begin{align} \langle \nabla_t, d_t \rangle &= \sum_i [\nabla_t]_i \, [d_t]_i = \sum_i \frac{g_{t,i} \, m_{t,i}}{\sqrt{v}_{t,i}} = \sum_i \frac{g_{t,i} \, (m_{t,i} - g_{t,i})}{\sqrt{v}_{t,i}} + \frac{g^2_{t,i}}{\sqrt{v}_{t,i}} \nonumber \\ & \geq -\sum_i \frac{|g_{t,i}| \, |m_{t,i} - g_{t,i}|}{\sqrt{v}_{t,i}} + \sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}} \nonumber \\ \implies - \langle \nabla_t, d_t \rangle & \leq \underbrace{\sum_i \frac{|g_{t,i}| \, |m_{t,i} - g_{t,i}|}{\sqrt{v}_{t,i}}}_{:= \text{Term (i)}} - \underbrace{\sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}}}_{:= \text{Term (ii)}} \label{eq:adam-2pl-secondterm-1-gnus} \end{align}\tag{58}\] Bounding Term (i) using 26 and using a constant step-size equal to \(\eta\), we get that, \[\begin{align} \text{Term (i)} & \leq \frac{\beta_1\,e \, C_3 \, \sum_{s = 1}^{t-1} (\sqrt{\beta_1})^{t-1-s} \, \eta_{s}}{\sqrt{1 - \beta_2}} \, (L_0 + L_1 \, \left\|\nabla f(\theta_t) \right\|_1 ) \\ & \leq \eta \, \underbrace{\frac{\beta_1\,e \, C_3 \, }{\sqrt{1 - \beta_2} \, (1 - \sqrt{\beta_1})}}_{:= C_1} (L_0 + L_1 \, \left\|\nabla f(\theta_t) \right\|_1 )\\ \implies \text{Term (i)} & \leq \, \eta C_1 \, (L_0 + L_1 \, \left\|\nabla f(\theta_t) \right\|_1 ) \label{eq:adam-2pl-secondterm-p1-gnus} \end{align}\tag{59}\] We use 17 to bound \(\text{Term (ii)} = \sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}}\), with \(u_t := \sqrt{1 - \beta_2} \, \sum_{j = 0}^{t-1} (\sqrt{\beta_2})^{j} \, \left\|\nabla_{t-j} \right\|_1\), \[\begin{align} \sum_i \frac{g^2_{t,i}}{\sqrt{v}_{t,i}} & \geq \left\|\nabla_t \right\|_1 \, \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta_2} \, \sum_{j = 0}^{t-1} (\sqrt{\beta_2})^{j} \, \left\|\nabla_{t-j} \right\|_1} = \frac{\left\|\nabla_t \right\|^{2}_1}{u_t} \label{eq:adam-1pl-secondterm-gnus} \end{align}\tag{60}\] Combining 57 with the bounds on Term (i) and Term (ii), \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \frac{\left\|\nabla_t \right\|^{2}_1}{u_t} + \left(L_0 + L_1 \, \left\|\nabla f(\theta_t) \right\|_1 \right) \, \eta^2 \, (C^2_3 + C_1) \label{eq:adam-2pl-inter-2-gnus} \end{align}\tag{61}\]

Case (1): For \(\epsilon \geq \frac{L_0}{L_1}\): To bound \(u_t\), we use 22, with \(a = \ln(1/ \beta_2^{1/4})\), while \(\sqrt{\beta_2} \exp( \ln(1/\beta_2^{1/4})) =\beta_2^{1/4}\leq 1\) and setting \(\eta \leq \bar{\eta}_1 := \frac{1}{2 \, C_3 \, L_1}\ln(1/\beta_2^{1/4})\) \[\begin{align} u_t & \leq \frac{\sqrt{1 - \beta_2} \; (\left\|\nabla_{t} \right\|_1 + \frac{L_0}{L_1})}{1 - \sqrt{\beta_2} \, \exp(a)} \end{align}\] Combining the above inequality with 61 and \(C_2 := \frac{1-\beta_2^{1/4}}{ \sqrt{1 - \beta_2}}\), we have \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, C_2 \, \frac{\left\|\nabla_t \right\|^2_1}{\left\|\nabla_t \right\|_1 + \frac{L_0}{L_1}} + \left(L_0 + L_1 \, \left\|\nabla_t \right\|_1 \right) \, \eta^2 \,(C_1+ C^2_3) \label{eq:adam-2pl-inter-2half-gnus} \end{align}\tag{62}\] Define \(T\) to be the first iteration s.t. \(\left\|\nabla f(\theta_{T}) \right\|_1 < \epsilon, \frac{L_0}{L_1}\), and analyze the above inequality for \(t < T\) where \(\left\|\nabla f(\theta_t) \right\|_1 \geq \epsilon \geq \frac{L_0}{L_1}\). Setting \(\eta \leq \bar{\eta}_2 := \frac{C_2}{8\, L_1\,(C_1+C_3^2)}\) and simplifying 61 in this case, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \frac{\eta \, C_2}{2} \, \left\|\nabla_t \right\|_1 + \left(2 L_1 \, \left\|\nabla_t \right\|_1 \right) \, \eta^2 \,(C_1+ C^2_3) \nonumber \\ & \leq f(\theta_t) - \frac{\eta \, C_2}{4} \, \left\|\nabla_t \right\|_1 _2} \nonumber \\ \implies & \frac{\eta \, C_2}{4} \, \left\|\nabla_t \right\|_1 \leq f(\theta_t) - f(\theta_{t+1}) \label{eq:adam-2pl-inter-3-gnus} \end{align}\tag{63}\] Note that from the above we have \(f(\theta_{t+1}) \leq f(\theta_t)\) for all \(t \leq T\) which indicates \(f(\theta_{T}) \leq f(\theta_1)\). Recursing for \(T\) iterations, we have \[\begin{align} \frac{\eta \, C_2}{4}\, T \, \left\|\nabla_{T} \right\| &\leq \frac{\eta \, C_2}{4} \, \sum_{t=1}^{T} \left\|\nabla_t \right\|_1\right\| \leq \frac{L_0}{L_1} and \left\|\nabla_{t} \right\| \geq \frac{L_0}{L_1} \, \forall t < T}\\ &\leq f(\theta_1)- f(\theta_{T + 1}) \\ & \leq f(\theta_1) \\ \implies \left\|\nabla_{T} \right\| & \leq \frac{4 \, f(\theta_1)}{\eta \, C_2 \, T} \end{align}\] Hence when \(T \geq \frac{4 \, f(\theta_1) }{\eta \, C_2\, \max \{\epsilon, \frac{L_0}{L_1}\}} = O(\frac{1}{\epsilon})\), then \(\left\|\nabla_{T} \right\|_1 \leq \epsilon\), where \(\eta = \min \left\{\bar{\eta}_0, \bar{\eta}_1, \bar{\eta}_2 \right\}\).

Case (2): For \(\epsilon < \frac{L_0}{L_1}\): Starting from 61 and summing from \(t = 1\) to \(T\), \[\begin{align} f(\theta_{T+1}) & \leq f(\theta_1) - \eta \, \underbrace{\sum_{t = 1}^{T} \frac{\left\|\nabla_t \right\|^{2}_1}{u_t}}_{:= (*)} + L_0 \, \eta^2 \, (C^2_3 + C_1) \, T + L_1 \, \eta^2 \, (C^2_3 + C_1) \, \sum_{t = 1}^{T} \left\|\nabla_t \right\|_1 \end{align}\] In order to simplify (*), note that by Cauchy Schwarz, \[\begin{align} \sum_{t = 1}^T \left\|\nabla_t \right\| &= \sum_{t = 1}^T \frac{\left\|\nabla_t \right\|}{\sqrt{u_t}} \, \sqrt{u_t} \leq \sqrt{\sum_{t = 1}^{T} \, \frac{\left\|\nabla_t \right\|^{2}}{u_t}} \, \sqrt{\sum_{t = 1}^{T} u_t} \implies (*) \geq \frac{\left(\sum_{t = 1}^T \left\|\nabla_t \right\|\right)^2}{\sum_{t = 1}^{T} u_t} \end{align}\] Simplifying \(\sum_{t = 1}^{T} u_t\), \[\begin{align} \sum_{t = 1}^{T} u_t & = \sqrt{1 - \beta_2} \, \sum_{t = 1}^{T} \left[ \sum_{j = 0}^{t-1} (\sqrt{\beta_2})^{j} \, \left\|\nabla_{t-j} \right\|_1 \right] = \sqrt{1 - \beta_2} \, \sum_{t = 1}^{T} \left[ \sum_{s = 1}^{t} (\sqrt{\beta_2})^{t-s} \left\|\nabla_{s} \right\|_1 \right] \\ & = \sqrt{1 - \beta_2} \, \sum_{s = 1}^{T} \left\|\nabla_{s} \right\|_1 \, \sum_{t = s}^{T} (\sqrt{\beta_2})^{t-s} = \sqrt{1 - \beta_2} \, \sum_{s = 1}^{T} \left\|\nabla_{s} \right\|_1 \, \sum_{j = 0}^{T-s} (\sqrt{\beta_2})^{j} ^{T} \, \sum_{s = 1}^{t} = \sum_{s = 1}^{T} \, \sum_{t = s}^{T}} \\ \implies \sum_{t = 1}^{T} u_t & \leq \frac{\sqrt{1 - \beta_2}}{1 - \sqrt{\beta_2}} \sum_{t = 1}^{T} \left\|\nabla_{t} \right\|_1 \end{align}\] Combining the above inequalities, we can conclude that \((*) \geq \frac{1 - \sqrt{\beta_2}}{\sqrt{1 - \beta_2}} \, \sum_{t = 1}^{T} \left\|\nabla_t \right\|_1\), and therefore, if \(C_4 := \frac{1 - \sqrt{\beta_2}}{\sqrt{1 - \beta_2}}\), then, \[\begin{align} f(\theta_{T+1}) & \leq f(\theta_1) - \eta \, \frac{C_4}{2} \, \sum_{t = 1}^{T} \left\|\nabla_t \right\|_1 + L_0 \, \eta^2 \, (C^2_3 + C_1) \, T _1 := \frac{C_4}{2 L_1 \, (C^2_3 + C_1)}} \\ \implies \sum_{t = 1}^{T} \left\|\nabla_t \right\|_1 & \leq \frac{2 \, f(\theta_1)}{C_4 \, \eta} + \frac{2 \, L_0 \, \eta \, (C^2_3 + C_1) \, T}{C_4} \\ \implies \min_{t \leq T} \left\|\nabla_t \right\|_1 & \leq \frac{\sum_{t = 1}^{T} \left\|\nabla_t \right\|_1}{T} \leq \frac{2 \, f(\theta_1)}{C_4 \, \eta \, T} + \frac{2 \, L_0 \, \eta \, (C^2_3 + C_1)}{C_4} \\ \intertext{Setting \eta = \min\{\bar{\eta}_0, \bar{\eta}_1, \, \frac{ C_4}{4\, L_0\,(C_3^2 + C_1)} \, \epsilon \},} \min_{t \leq T} \left\|\nabla_t \right\|_1 & \leq \frac{2 \, f(\theta_1)}{C_4 \, \eta \, T} + \frac{\epsilon}{2} \intertext{Setting T \geq \frac{4 f(\theta_1)}{C_4 \, \eta \, \epsilon} = O\left(\frac{1}{\epsilon^2}\right)) is sufficient to ensure that,} \min_{t \leq T} \left\|\nabla_t \right\|_1 & \leq \epsilon \end{align}\] ◻

Proof. Define the function \(h(\theta) := \ln(\left\|\nabla f(\theta) \right\|_q + \frac{L_0}{L_1})\). We will first prove that \(h(\theta)\) is \(L_1\)-Lipschitz w.r.t the \(\ell_{p}\) norm. Since \(\left\|\cdot \right\|_q\) can be non-smooth, consider a Clarke subgradient computed using Lemma 12 \[\partial h(\theta) = \frac{\nabla^2 f(\theta) \partial \|z\|_q}{\|z\|_q+\frac{L_0}{L_1}}, \qquad z = \nabla f(\theta).\] \[\begin{align} \intertext{Then, for g = \nabla^2 f(\theta) s where s \in \partial(\left\|\cdot \right\|_q)(\nabla f(\theta)) is a subgradient of \left\|\cdot \right\|_{q} evaluated at \nabla f(\theta), we write the norm of v\in \partial h(\theta) as} \left\|v \right\|_{q} &= \frac{\left\|[\nabla^2 f(\theta)] \, s \right\|_q}{\left\|\nabla f(\theta) \right\|_q + \frac{L_0}{L_1}} \leq \frac{\left\|\nabla^2 f(\theta) \right\|_{p \to q} \, \left\|s \right\|_{p}}{\left\|\nabla f(\theta) \right\|_q + \frac{L_0}{L_1}}\\ \implies \left\|v \right\|_{q} & \leq \frac{\left\|\nabla^2 f(\theta) \right\|_{p \to q}}{\left\|\nabla f(\theta) \right\|_q + \frac{L_0}{L_1}}\\ \end{align}\] Using 4 to simplify the numerator, and noting that lower-bounding the denominator, \[\begin{align} \forall v \in \partial{h}(\theta), \quad \left\|v \right\|_q & \leq \frac{L_0 + L_1 \, \left\|\nabla f(\theta) \right\|_q}{\left\|\nabla f(\theta) \right\|_q+\frac{L_0}{L_1}} \leq L_1 \end{align}\] By Lebourg’s mean value theorem ([42], Thm. 2.4), since \(h\) is Lipschitz in an open set containing \(y\) and \(x\), then there exists a point \(u = tx+(1-t)y\), for some \(t\in[0,1]\) such that \[\exists g\in \partial h(u), \qquad h(y)-h(x)=\langle g,y-x\rangle.\] Therefore, \[\begin{align} h(y) - h(x) &\leq \max_{t\in[0,1]} \langle g,y-x\rangle \quad {where} \quad g \in \partial h(t \, x + (1-t) \, y) \\ & \leq \left\|y - x \right\|_p \, \max_{t\in[0,1]}\,\|g\|_q\\ & \leq L_1 \, \left\|y - x \right\|_p\\ \end{align}\] \[\begin{align} \implies \ln(\left\|\nabla f(y) \right\|_q + \frac{L_0}{L_1}) - \ln(\left\|\nabla f(x) \right\|_q + \frac{L_0}{L_1}) & \leq L_1 \, \left\|y - x \right\|_p \\ \implies \left\|\nabla f(y) \right\|_q +\frac{L_0}{L_1} & \leq \left(\left\|\nabla f(x) \right\|_q + \frac{L_0}{L_1} \right) \, \exp\left(L_1 \left\|y - x \right\|_p\right) \end{align}\] ◻

Proof. Using part (1) of 21 with \(p = \infty\), \(q = 1\) and \(y = \theta_{t-1}\), \(x = \theta_t\), \(c > 0\), \[\begin{align} \left\|\nabla_{t-1} \right\|_1 + \frac{L_0}{L_1} & \leq (\left\|\nabla_{t} \right\|_1 + \frac{L_0}{L_1}) \, \exp\left(L_1 \, \left\|\theta_{t-1} - \theta_t \right\|_\infty \right) \\ & \leq (\left\|\nabla_{t} \right\|_1 + \frac{L_0}{L_1}) \, \exp(a)\\ \implies \left\|\nabla_{t-j} \right\|_1 & \leq (\left\|\nabla_{t} \right\|_1 + \frac{L_0}{L_1}) \, \exp(a \, j) \end{align}\] Using the above relation to lower-bound \(\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1\), first note that, \[\begin{align} \sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1 & \leq \sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^j \, (\left\|\nabla_{t} \right\|_1 + \frac{L_0}{L_1}) \, \exp(a \, j) \\ & \leq \frac{\sqrt{1 - \beta} \; (\left\|\nabla_{t} \right\|_1 + \frac{L_0}{L_1})}{1 - \sqrt{\beta} \, \exp(a)}\, \exp(a) < 1} \\ \implies \frac{\left\|\nabla_t \right\|_1}{\sqrt{1 - \beta} \, \sum_{j = 0}^{t-1} (\sqrt{\beta})^{j} \, \left\|\nabla_{t-j} \right\|_1} & \geq \frac{\left\|\nabla_t \right\|_1}{\left\|\nabla_t \right\|_1 + \frac{L_0}{L_1}} \, \frac{1 - \sqrt{\beta} \, \exp(a)}{\sqrt{1 - \beta}} \end{align}\] ◻

Proof. By the fundamental theorem of calculus, \[\begin{align} \nabla f(y) - \nabla f(x) & = \int_{t = 0}^{1} \nabla^2 f((1-t) \, x + t \, y) \, (y - x) \, dt \\ \implies \left\|\nabla f(y) - \nabla f(x) \right\|_q & = \left\|\int_{t = 0}^{1} \nabla^2 f((1-t) \, x + t \, y) \, (y - x) \, dt \right\|_q \\ & \leq \int_{t = 0}^{1} \, \left\|\nabla^2 f((1-t) \, x + t \, y) \, (y - x) \right\|_{q} dt\\ & \leq \int_{t = 0}^{1} \, \left\|\nabla^2 f((1-t) \, x + t \, y) \right\|_{p \to q} \, \left\|y - x \right\|_p \, dt\\ & \leq \left\|y - x \right\|_p \, \left[\int_{t = 0}^{1} \, L_0 + L_1 \, \left\|\nabla f((1-t) \, x + t \, y) \right\|_q \, dt \right] }\\ & = \left\|y - x \right\|_p \, \left[L_0 + L_1 \, \int_{t = 0}^{1} \, \left\|\nabla f((1-t) \, x + t \, y) \right\|_q \, dt \right] \\ & \leq \left\|y - x \right\|_p \, \left[ L_1 \, \int_{t = 0}^{1} \, \left(\left\|\nabla f(x) \right\|_q + \frac{L_0}{L_1}\right)\, \exp(L_1 \, t \, \left\|y - x \right\|) \, dt \right]with \theta = ty + (1-t)x and \theta' = x} \\ & = \left\|y - x \right\|_p \, \left[L_1 \left(\left\|\nabla f(x) \right\|_q + \frac{L_0}{L_1} \right) \, \int_{t = 0}^{1} \, \exp(L_1 \, t \, \left\|y - x \right\|) \, dt \right] \\ & \leq \left\|y - x \right\|_p \, \left[L_1 \left(\left\|\nabla f(x) \right\|_q + \frac{L_0}{L_1} \right) \, \int_{t = 0}^{1} \, \exp(t) \, dt \right] {L_1}} \\ & = \left[L_1 \left(\left\|\nabla f(x) \right\|_q + \frac{L_0}{L_1} \right) \, (e-1) \right]\, \left\|y - x \right\|_p \\ & \leq [L_0 + L_1 \, \left\|\nabla f(x) \right\|_q] \, e \, \left\|y - x \right\|_p \end{align}\] ◻

Proof. Define \(u(t) = (1-t) x + t y\) and \(g(t) = f(u(t))\). Use Taylor’s theorem for \(g\), \[\begin{align} g(b) = g(a) + (b - a) \, g'(a) + \int_{t = a}^{b} (b - t) \, g''(t) \, dt \\ \implies g(1) = g(0) + g'(0) + \int_{t = 0}^{1} (1 - t) \, g''(t) \, dt \end{align}\] We know that, \[\begin{align} g'(t) &= \frac{\partial f(u(t))}{\partial t} = \langle \nabla f(u(t)), y - x \rangle \quad \text{;} \quad g''(t) = \frac{\partial^2 f(u(t))}{\partial t^2} = (y - x)^T \nabla^2 f(u(t)) (y - x) \end{align}\] Combining the above relations, and using that \(g(1) = f(y)\), \(g(0) = f(x)\), \(g'(0) = \langle \nabla f(x), y - x \rangle\). \[\begin{align} f(y) &= f(x) + \langle \nabla f(x), y - x \rangle + (y-x)^T \left[\int_{t = 0}^{1} (1-t) \, \nabla^2 f(t \, y + (1-t) \, x) \, dt \right]\, (y-x) \\ \intertext{Simplifying the last term,} & (y-x)^T \left[\int_{t = 0}^{1} (1-t) \, \nabla^2 f(t \, y + (1-t) \, x) \, dt \right]\, (y-x) \\ &\leq \left\|y - x \right\|_p \, \left\|\left[\int_{t = 0}^{1} (1-t) \, \nabla^2 f(t \, y + (1-t) \, x) \, dt \right]\, (y-x) \right\|_{q}\\ & \leq \left\|y - x \right\|_p \, \left[\int_{t = 0}^{1} (1-t) \, \left\|\nabla^2 f(t \, y + (1-t) \, x) \, (y-x) \right\|_{q} \, dt \right]\\ & \leq \left\|y - x \right\|^{2}_p \, \int_{t = 0}^{1} (1-t) \, \left\|\nabla^2 f(t \, y + (1-t) \, x) \right\|_{p \to q} \, dt\\ & \leq \left\|y - x \right\|^{2}_p \, \int_{t = 0}^{1} (1-t) \, [L_0 + L_1 \, \left\|\nabla f(t \, y + (1-t) \, x) \right\|_q] \, dt } \\ & = \left\|y - x \right\|^{2}_p \, \int_{t = 0}^{1} (1-t) \, L_1 \, \left [\frac{L_0}{L_1} + \, \left\|\nabla f(t \, y + (1-t) \, x) \right\|_q\right] \, dt\\ & \leq \left\|y - x \right\|^{2}_p \, \int_{t = 0}^{1} (1-t) \, L_1 \, \left[ \left(\left\|\nabla f(x) \right\|_q + \frac{L_0}{L_1} \right) \exp(L_1 \, t \, \left\|y - x \right\|_p) \right] \, dtwith \theta = ty + (1-t)x and \theta' = x} \\ & = \left\|y - x \right\|^{2}_p \, \int_{t = 0}^{1} (1-t) \, \left((L_0 + L_1 \, \left\|\nabla f(x) \right\|_q) \, \exp(L_1 \, t \, \left\|y - x \right\|_p) \right)\, dt \\ & = \left\|y - x \right\|^{2}_p \, (L_0 + L_1 \, \left\|\nabla f(x) \right\|_q)\, \int_{t = 0}^{1} (1-t) \, \left( \, \exp(L_1 \, t \, \left\|y - x \right\|_p) \right)\, dt \\ & \leq \left\|y - x \right\|^{2}_p \, (L_0 + L_1 \, \left\|\nabla f(x) \right\|_q)\, \int_{t = 0}^{1} (1-t) \, \left( \, \exp( t ) \right)\, dt {\sqrt{L_1}}} \\ & \leq \left\|y - x \right\|^{2}_p \, (L_0 + L_1 \, \left\|\nabla f(x) \right\|_q)\, \left[\int_{t = 0}^{1} \exp(t) \, dt - \int_{t = 0}^{1} t \, \exp(t) \, dt \right] \\ & \leq \left\|y - x \right\|^{2}_p \, (L_0 + L_1 \, \left\|\nabla f(x) \right\|_q)\, (e-2) \\ & \leq \left\|y - x \right\|^{2}_p \, (L_0 + L_1 \, \left\|\nabla f(x) \right\|_q)\\ \end{align}\] Putting everything together, \[\begin{align} f(y) &\leq f(x) + \langle \nabla f(x), y - x \rangle + \left(L_0 + L_1 \, \left\|\nabla f(x) \right\|_q \right) \, \left\|y - x \right\|^{2}_p \end{align}\] ◻

Proof. If \(\left\|\theta_{t+1}- \theta_t \right\|_\infty \leq \frac{1}{L_1}\), using 24 with \(p = \infty\) and \(q = 1\), and denoting \(\nabla_t := \nabla f(\theta_t)\) for convenience, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla_t, d_t \rangle + \left(L_0 + L_1 \, \left\|\nabla f(\theta_t) \right\|_1 \right) \, \eta^2 \, \left\|d_t \right\|^{2}_\infty \end{align}\] Simplifying the third term on the RHS, \(\left\|d_t \right\|_\infty = \max_{i} \frac{m_{t,i}}{\sqrt{v}_{t,i}}\). \[\begin{align} m_{t,i} & = (1-\beta_1) \, \sum_{s = 1}^{t} \beta_1^{t-s} g_{s,i} \\ \implies m^2_{t,i} & \leq \left(1-\beta_1\right)^2 \, \left(\sum_{s = 1}^{t} \beta_1^{t-s}\right) \left(\sum_{s = 1}^{t} \beta_1^{t-s} g^2_{s,i} \right)\\ & \leq \left(1-\beta_1\right) \, \sum_{s = 1}^{t} \beta_1^{t-s} g^2_{s,i}\\ & \leq \frac{1 - \beta_1}{1 - \beta_2} \, \left[\left(1-\beta_2\right) \, \sum_{s = 1}^{t} \beta_2^{t-s} g^2_{s,i} \right]\\ &= \frac{1 - \beta_1}{1 - \beta_2} \, v_{t,i} } \\ \implies \frac{m^2_{t,i}}{v_{t,i}} & \leq \frac{1 - \beta_1}{1 - \beta_2} \implies \frac{m_{t,i}}{\sqrt{v}_{t,i}} \leq B := \sqrt{\frac{1 - \beta_1}{1 - \beta_2} } \\ \implies \left\|\theta_{t+1}- \theta_t \right\|_\infty \leq \eta \, \left\|d_t \right\|_\infty \leq \eta \, B \label{eq:adam-1pl-thirdterm-gnus} \end{align}\tag{64}\] Ensuring that \(\eta \leq \frac{1}{B \, L_1}\) guarantees that \(\left\|\theta_{t+1}- \theta_t \right\|_\infty \leq \frac{1}{L_1}\). Combining the above inequalities, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \langle \nabla_t, d_t \rangle + \left(L_0 + L_1 \, \left\|\nabla f(\theta_t) \right\|_1 \right) \, \eta^2 \, B^2 \end{align}\] ◻

Proof. \[\begin{align} \sum_i \frac{|g_{t,i}| \, |m_{t,i} - g_{t,i}|}{\sqrt{v}_{t,i}} &\leq \frac{1}{\sqrt{1 - \beta_2}} \, \sum_i |m_{t,i} - g_{t,i}|\geq (1 - \beta_2) \, g^2_{t,i}} \\ & \leq \frac{\left\|m_t - g_t \right\|_1}{\sqrt{1 - \beta_2}} \label{eq:adam-1pl-mom-recursion-1-gnus} \end{align}\tag{65}\] In order to bound \(\left\|m_t - g_t \right\|_1\), note that, \[\begin{align} |m_{t,i} - g_{t,i}| &= |\beta_1 \, m_{t-1,i} + (1-\beta_1) \, g_{t,i} - g_{t,i}| = \beta_1 \, |m_{t-1,i} - g_{t,i}| \\ & \leq \beta_1 \, |m_{t-1,i} - g_{t-1,i}| + \beta_1 \, |g_{t-1,i} - g_{t,i}| \nonumber \\ \implies \sum_i |m_{t,i} - g_{t,i}| & \leq \beta_1 \, \sum_i |m_{t-1,i} - g_{t-1,i}| + \beta_1 \, \sum_i |g_{t-1,i} - g_{t,i}| \nonumber \\ \implies \left\|m_t - g_t \right\|_1 & \leq \beta_1 \left\|m_{t-1} - \nabla_{t-1} \right\|_1 + \beta_1 \left\|\nabla_t - \nabla_{t-1} \right\|_1 \nonumber \\ \intertext{Using~\ref{lemma:grad-lip-gnus} with p = \infty, q = 1, y = \theta_{t-1} and x = \theta_t while ensuring that \eta_{t-1} \leq \frac{1}{B \, L_1} guarantees that \left\|\theta_t- \theta_{t+1} \right\|_\infty \leq \frac{1}{L_1}} & \leq \beta_1 \, \left\|m_{t-1} - \nabla_{t-1} \right\|_1 + \beta_1 \, (L_0 + L_1 \, \left\|\nabla f(\theta_t) \right\|_1) \, e \, \left\|\theta_t- \theta_{t-1} \right\|_{\infty} \nonumber \\ & \leq \beta_1 \, \left\|m_{t-1} - \nabla_{t-1} \right\|_{1} + \beta_1 \, \underbrace{(L_0 + L_1 \, \left\|\nabla f(\theta_t) \right\|_1)}_{:= \bar{L}_t} \, e \, \eta_{t-1} \, B \nonumber \\ \implies \frac{\left\|m_t - g_t \right\|_1}{\bar{L_t}} & \leq \beta_1 \, \frac{\left\|m_{t-1} - \nabla_{t-1} \right\|_{1}}{\bar{L}_t} +\beta_1\, e \, \eta_{t-1} \, B \label{eq:adam-1pl-mom-recursion-2-gnus} \end{align}\tag{66}\] We now write \(\bar{L}_t\) in terms of \(\bar{L}_{t-1}\). In particular, using 21 with \(p = \infty\), \(q = 1\) and \(y = \theta_{t-1}\), \(x = \theta_t\), \[\begin{align} \bar{L}_t = L_0 + L_1 \, \left\|\nabla f(\theta_t) \right\|_1 & \geq \left(L_0 + L_1 \, \left\|\nabla f(\theta_{t-1}) \right\|_1 \right) \, \exp\left(-L_1 \, \left\|\theta_t- \theta_{t-1} \right\|_{\infty} \right)\nonumber\\ & = \bar{L}_{t-1} \, \exp\left(-L_1 \, \left\|\theta_t- \theta_{t-1} \right\|_{\infty} \right) \nonumber\\ \frac{1}{\bar{L}_t} & \leq \frac{1}{\bar{L}_{t-1}} \, \exp\left(L_1 \, \left\|\theta_t- \theta_{t-1} \right\|_{\infty} \right) \leq \frac{1}{\bar{L}_{t-1}} \, \frac{1}{\sqrt{\beta_1}}and ensuring that \eta_{t-1} \leq \frac{1}{B \, L_1} \, \ln(1/\sqrt{\beta_1}} \end{align}\] Combining the above inequality with 66 , \[\begin{align} \frac{\left\|m_t - g_t \right\|_1}{\bar{L_t}} & \leq \sqrt{\beta_1} \, \frac{\left\|m_{t-1} - \nabla_{t-1} \right\|_{1}}{\bar{L}_{t-1}} + \beta_1\,e \, \eta_{t-1} \, B \\ & \leq \beta_1\,e \, B \, \sum_{s = 1}^{t-1} (\sqrt{\beta_1})^{t-1-s} \, \eta_{s}= g_{1,i}} \\ \implies \left\|m_t - g_t \right\|_1 & \leq (L_0 + L_1 \, \left\|f(\theta_t) \right\|_1) \,\beta_1\, e \, B \, \sum_{s = 1}^{t-1} (\sqrt{\beta_1})^{t-1-s} \, \eta_{s} \label{eq:adam-1pl-mom-recursion-final-gnus} \end{align}\tag{67}\] Combining the above inequality with 65 , \[\begin{align} \sum_i \frac{|g_{t,i}| \, |m_{t,i} - g_{t,i}|}{\sqrt{v}_{t,i}} & \leq (L_0 + L_1 \, \left\|f(\theta_t) \right\|_1) \, \underbrace{\frac{\beta_1\,e \, B \, \sum_{s = 1}^{t-1} (\sqrt{\beta_1})^{t-1-s} \, \eta_{s}}{\sqrt{1 - \beta_2}}}_{:= C} = C \, (L_0 + L_1 \, \left\|f(\theta_t) \right\|_1) \end{align}\] ◻

Proof. We will show that any \(\eta \leq \frac{1 - c}{H_0 + H_1 \, f(\theta_t)}\) will satisfy the Armijo condition, and hence the back-tracking Armijo line-search will return a step-size larger than \(\min \left\{ \eta_{\max},\frac{1 - c}{H_0 + H_1 \, f(\theta_t)} \right\}\).

First, note that for \(\eta \leq \frac{1}{H_0 + H_1 \, f(\theta_t)}\), \[\begin{align} \eta \, \left\|\nabla_t \right\|_{q} & \leq \frac{\left\|\nabla_t \right\|_{q}}{H_0 + H_1 \, f(\theta_t)} \leq \frac{\sqrt{2 H_0 \, f(\theta_t) + H_1 \, [f(\theta_t)]^2}}{H_0 + H_1 \, f(\theta_t)} } \\ & \leq \frac{1}{\sqrt{H_1}} \, \frac{\sqrt{2 H_0 \, H_1 \, f(\theta_t) + H_1^2 \, [f(\theta_t)]^2 + H_0^2}}{H_0 + H_1 \, f(\theta_t)}\\ \implies \eta \, \left\|\nabla_t \right\|_{q} & \leq \frac{1}{\sqrt{H_1}} \end{align}\] Hence, for any \(\eta \leq \frac{1-c}{H_0 + H_1 \, f(\theta_t)} < \frac{1}{H_0 + H_1 \, f(\theta_t)}\), the condition required for 7 is satisfied for \(y = \theta_{t+1}\), \(x = \theta_t\). Using 7, \[\begin{align} f(\theta_{t+1}) & \leq f(\theta_t) - \eta \, \left\|\nabla_t \right\|_{q} \, \langle \nabla_t, d_t \rangle + \eta^2 \, (H_0 + H_1 \, f(\theta_t)) \, \left\|\nabla_t \right\|^{2}_{q}\\ & =f(\theta_t) - \eta \, \left\|\nabla_t \right\|^{2}_{q} + \eta^2 \, (H_0 + H_1 \, f(\theta_t)) \, \left\|\nabla_t \right\|^{2}_{q}\\ & \leq f(\theta_t) - c \, \eta \, \left\|\nabla_t \right\|^{2}_{q} \end{align}\] Hence, the Armijo condition is satisfied for any \(\eta \leq \frac{1-c}{H_0 + H_1 \, f(\theta_t)}\). Since the back-tracking line-search returns the largest step-size (smaller than \(\eta_{\max}\)) that satisfies the Armijo condition, the returned step-size \({\eta_t}\geq \max\left\{\eta_{\max}, \frac{1-c}{H_0 + H_1 \, f(\theta_t)}\right\}\). ◻