Section 4.5.3 Non-convex Bilevel Optimization

In this section, we discuss the application of the compositional gradient estimation technique to non-convex bilevel optimization defined by

\[\begin{equation}\label{eqn:bi} \begin{aligned} \min_{\mathbf{w}\in\mathbb{R}^d}& f(\mathbf{w}, \mathbf{u}^*(\mathbf{w}))\\ \mathbf{u}^*(\mathbf{w})&=\arg\min_{\mathbf{u}\in\mathbb{R}^{d'}} g(\mathbf{w}, \mathbf{u}), \end{aligned} \end{equation}\]

where \(g\) is twice differentiable and \(\mu_g\)-strongly convex in terms of \(\mathbf{u}\). Let \(F(\mathbf{w}) =f(\mathbf{w}, \mathbf{u}^*(\mathbf{w})).\) The following lemma states the gradient of the objective \(F(\mathbf{w})\).

■

Let us define \[\begin{align*} &\mathcal{M}(\mathbf{w}, \mathbf{u}^*(\mathbf{w}))=\nabla_1 f(\mathbf{w}, \mathbf{u}^*(\mathbf{w})) - \nabla_{21} g(\mathbf{w}, \mathbf{u}^*(\mathbf{w}))^{\top}(\nabla_{22} g(\mathbf{w}, \mathbf{u}^*(\mathbf{w})))^{-1}\nabla_2 f(\mathbf{w}, \mathbf{u}^*(\mathbf{w})). \end{align*}\]

If we can establish the Lipschitz continuity of \(\mathcal{M}(\mathbf{w}, \mathbf{u}^*(\mathbf{w}))\) in terms of the second argument and the Lipschitz continuity of \(\mathbf{u}^*(\mathbf{w})\), then the similar technique can be leveraged. Let \(\mathbf{u}^*(\mathbf{w}_t)\) be tracked by \(\mathbf{u}_t\). It can be updated by SGD: \[\begin{align} \mathbf{u}_{t+1} = \mathbf{u}_t - \gamma_t \nabla_2 g(\mathbf{w}_t, \mathbf{u}_t; \zeta_t). \end{align}\]

With \(\mathbf{u}_t\), the gradient at \(\mathbf{w}_t\) can be estimated by \[\begin{align} \mathcal{M}(\mathbf{w}_t, \mathbf{u}_t)=\nabla_1 f(\mathbf{w}_t, \mathbf{u}_t) +\nabla_{21} g(\mathbf{w}_t, \mathbf{u}_t)^{\top}(\nabla_{22} g(\mathbf{w}_t, \mathbf{u}_t))^{-1}\nabla_2 f(\mathbf{w}_t, \mathbf{u}_t). \end{align}\] However, another challenge is to handle the Hessian inverse \((\nabla_{22} g(\mathbf{w}_t, \mathbf{u}_t)^{-1}\), which itself is a compositional structure. We will discuss three different ways to tackle this challenge. If we have a stochastic estimator of \(\mathcal{M}(\mathbf{w}_t, \mathbf{u}_t)\) denoted by \(\mathbf{v}_{t}\), then we update the model parameter by: \[\begin{align} \mathbf{w}_{t+1} = \mathbf{w}_t - \eta_t \mathbf{v}_{t}. \end{align}\]

4.5.3.1 Approach 1: The MA Estimator

If the lower level problem is low-dimensional such that the inverse of the Hessian matrix can be efficiently computed, we can estimate \(\nabla_{22} g(\mathbf{w}_t, \mathbf{u}_t)\) by a MA estimator: \[\begin{align*} H_{22,t} = S_{\mu_g}[(1-\beta) H_{22,t-1} + \beta \nabla_{22} g(\mathbf{w}_t, \mathbf{u}_t; \zeta_{2,t})]. \end{align*}\] where \(S_{\mu_g}[\cdot]\) is a projection operator that projects a matrix into a matrix whose minimum eigen-value is lower bounded by \(\mu_g\), where \(\mu_g\) is the lower bound of eigen-values of \(\nabla_{22} g(\mathbf{w}, \mathbf{u})\). The projection ensures that \([H_{22,t}]^{-1}\) is Lipschitz continuous with respect to \(H_{22,t}\).

The a vanilla stochastic gradient estimator of \(\mathbf{w}_t\) and its MA estimator are computed by

\[\begin{equation}\label{eqn:bio-hma} \begin{aligned} &\mathbf{z}_{t} = \nabla_1 f(\mathbf{w}_t, \mathbf{u}_t; \xi_{t}) +\nabla_{21} g(\mathbf{w}_t, \mathbf{u}_t; \zeta'_{2,t})^{\top}(H_{22,t})^{-1}\nabla_2 f(\mathbf{w}_t, \mathbf{u}_t; \xi_{t})\\ &\mathbf{v}_{t} =(1-\beta)\mathbf{v}_{t-1} + \beta \mathbf{z}_t. \end{aligned} \end{equation}\]

Convergence Analysis

The proof is largely similar to that of Theorem 4.3. We provide a sketch of proof below. Recall that \[\begin{align*} &\mathcal{M}(\mathbf{w}_t, \mathbf{u}_t)=\nabla_1 f(\mathbf{w}_t, \mathbf{u}_t) +\nabla_{21} g(\mathbf{w}_t, \mathbf{u}_t)^{\top}(\nabla_{22} g(\mathbf{w}_t, \mathbf{u}_t))^{-1}\nabla_2 f(\mathbf{w}_t, \mathbf{u}_t). \end{align*}\] Define: \[\begin{align*} \hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t)=\nabla_1 f(\mathbf{w}_t, \mathbf{u}_t) +\nabla_{21} g(\mathbf{w}_t, \mathbf{u}_t)^{\top} H_{22,t}^{-1}\nabla_2 f(\mathbf{w}_t, \mathbf{u}_t). \end{align*}\]

First, similar to Lemma 4.9, we have the following: \[\begin{align} F(\mathbf{w}_{t+1})& \leq F(\mathbf{w}_t) + \frac{\eta_t}{2} \|\mathbf{v}_t - \nabla F(\mathbf{w}_t)\|_2^2-\frac{\eta_t}{2}\|\nabla F(\mathbf{w}_t)\|_2^2- \frac{1}{4\eta_t} \|\mathbf{w}_{t+1} - \mathbf{w}_t\|_2^2. \end{align}\]

We establish a recursion of the error \(\|\mathbf{v}_t - \nabla F(\mathbf{w}_t)\|_2^2\) similar to Lemma 4.7 by noting that \(\mathbb E_{\xi_t, \zeta'_{2,t}}[\mathbf{z}_t]=\hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t)\) and there exists \(\sigma>0\) such that \(\mathbb E_{\xi_t, \zeta'_{2,t}}[\|\mathbf{z}_t - \hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t)\|_2^2]\leq \sigma^2\). Thus, Lemma 4.7 implies that

\[\begin{align}\label{eqn:bio-v-err} &\mathbb E_{\xi_t, \zeta'_{2,t}}\left[\|\mathbf{v}_{t} - \nabla F(\mathbf{w}_t)\|_2^2\right] \leq (1-\beta_t)\|\mathbf{v}_{t-1} - \nabla F(\mathbf{w}_{t-1})\|_2^2 \\ & \quad + \frac{2L_F^2}{\beta_t}\|\mathbf{w}_{t-1}-\mathbf{w}_t\|_2^2 + 4\beta_t\|\hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t) - \nabla F(\mathbf{w}_t)\|_2^2 + \beta_t^2\sigma^2.\notag \end{align}\]

Then, we bound \(\|\hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t)-\nabla F(\mathbf{w}_t)\|_2^2\) by \[\begin{align*} \|\hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t)-\nabla F(\mathbf{w}_t)\|_2^2&\leq 2\|\hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t) -\mathcal{M}(\mathbf{w}_t, \mathbf{u}_t) \|^2_2\\ & +2\|\mathcal{M}(\mathbf{w}_t, \mathbf{u}_t) - \nabla F(\mathbf{w}_t)\|^2_2\\ & \leq O(\|H_{22,t} - \nabla_{22}g(\mathbf{w}_t, \mathbf{u}_t)\|_2^2) + O(\|\mathbf{u}_t - \mathbf{u}^*(\mathbf{w}_t)\|^2_2). \end{align*}\]

As a result, we have \[\begin{align*} \mathbb E[\|\mathbf{v}_t - &\nabla F(\mathbf{w}_t)\|_2^2] \leq (1-\beta_t)\|\mathbf{v}_{t-1}- \nabla F(\mathbf{w}_{t-1})\|^2 + \frac{2L_F^2}{\beta_t}\|\mathbf{w}_t - \mathbf{w}_{t-1}\|_2^2\\ &+ \beta_t (O(\|H_{22,t} - \nabla_{22}g(\mathbf{w}_t, \mathbf{u}_t)\|_2^2) + O(\|\mathbf{u}_t - \mathbf{u}^*(\mathbf{w}_t)\|^2_2)) + \beta_t^2O(\sigma^2). \end{align*}\] This result is similar to that in Lemma 4.8.

We can further build the error recursion of \(\|H_{22,t} - \nabla_{22}g(\mathbf{w}_t,\mathbf{u}_t)\|_2^2\) similar to Lemma 4.1, and the error recursion of \(\|\mathbf{u}_t - \mathbf{u}^*(\mathbf{w}_t)\|^2_2\) similar to Lemma 4.20. Combining these results, we can establish a complexity of \(O(1/\epsilon^4)\) for finding an \(\epsilon\)-stationary solution of \(F(\cdot)\) in expectation.

4.5.3.2 Approach 2: The Neumann Series (Matrix Taylor Approximation)

If the lower level problem is high-dimensional such that it is prohibited to compute the Hessian, one approach is to leverage the Neuman series: \[\begin{align} A^{-1}= \sum_{i=0}^\infty (I -A)^i, \quad \text{ if }\quad \|A\|\leq 1. \end{align}\] Hence, if \(\|\nabla_{22}g(\mathbf{w}_t, \mathbf{u}_t)\|\leq L_{22}\), we estimate the inverse of \(\frac{1}{L_{22}}\nabla_{22}g(\mathbf{w}_t, \mathbf{u}_t)\), yielding \[\begin{align} \left(\nabla_{22}g(\mathbf{w}_t, \mathbf{u}_t)\right)^{-1}\approx \frac{1}{L_{22}}\sum_{i=0}^{K-1} \left(I - \frac{1}{L_{22}}\nabla_{22}g(\mathbf{w}_t, \mathbf{u}_t)\right)^i. \end{align}\] This can be further estimated by a stochastic route, by sampling \(k\) from \(\{0,\ldots,K- 1\}\) randomly, then estimate the Hessian inverse by \[\begin{align} Q_{22,t} = \left\{\begin{array}{ll}\frac{K}{L_{22}}\prod_{i=1}^{k} \left(I - \frac{1}{L_{22}}\nabla_{22}g(\mathbf{w}_t, \mathbf{u}_t; \zeta_{i})\right)& \text{ if } k\geq 1\\ \frac{K}{L_{22}}I & \text{ if } k=0\end{array}\right.. \end{align}\] This is can be justified by \[\begin{align*} \mathbb{E}[Q_{22,t}] &= \frac{1}{K}\frac{K}{L_{22}}I + \frac{K-1}{K}\mathbb{E}_{k\sim\{1,\ldots, K-1\}}\left[\frac{K}{L_{22}}\prod_{i=1}^{k} \left(I - \frac{1}{L_{22}}\mathbb{E}[\nabla_{22}g(\mathbf{w}_t, \mathbf{u}_t; \zeta_{i})]\right)\right]\\ & = \mathbb{E}_{k}\frac{K}{L_{22}}\left(I - \frac{1}{L_{2}}\nabla_{22}g(\mathbf{w}_t, \mathbf{u}_t)\right)^k = \sum_{k=0}^{K-1}\frac{1}{L_{22}}\left(I -\frac{1}{L_{22}}\nabla_{22}g(\mathbf{w}_t, \mathbf{u}_t)\right)^k. \end{align*}\]

Then the vanilla gradient estimator of \(\mathbf{w}_t\) and its MA estimator are computed by

\[\begin{equation}\label{eqn:bio-neu} \begin{aligned} &\mathbf{z}_{t} = \nabla_1 f(\mathbf{w}_t, \mathbf{u}_t; \zeta_{1,t}) +\nabla_{21} g(\mathbf{w}_t, \mathbf{u}_t; \zeta'_{2,t})^{\top}Q_{22,t}\nabla_2 f(\mathbf{w}_t, \mathbf{u}_t; \zeta_{1,t})\\ &\mathbf{v}_{t} =(1-\beta)\mathbf{v}_{t-1} + \beta \mathbf{z}_t. \end{aligned} \end{equation}\]

Convergence Analysis

We provide a proof sketch below. We can understand that \(\mathbf{z}_t\) is an unbiased stochastic estimator of \[\begin{align*} \hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t)=\nabla_1 f(\mathbf{w}_t, \mathbf{u}_t) +\nabla_{21} g(\mathbf{w}_t, \mathbf{u}_t)^{\top}\mathbb{E}[Q_{22,t}]\nabla_2 f(\mathbf{w}_t, \mathbf{u}_t). \end{align*}\] We decompose the estimation error of \(\mathbf{v}_t\) similarly as in (\(\ref{eqn:bio-v-err}\)) and bound \(\|\hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t) - \nabla F(\mathbf{w}_t)\|_2^2\) by \[\begin{align*} \|\hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t) - \nabla F(\mathbf{w}_t)\|_2^2 &\leq 2\|\mathcal{M}(\mathbf{w}_t, \mathbf{u}_t) -\nabla F(\mathbf{w}_t)\|_2^2 \\ & + 2\|\hat{\mathcal{M}}(\mathbf{w}_t, \mathbf{u}_t) - \mathcal{M}(\mathbf{w}_t,\mathbf{u}_t)\|_2^2 . \end{align*}\] The error recursion of the first term on the right hand side can be similarly bounded as before. To bound the last error, since \[\begin{equation*} \left[\nabla_{22}^2 g(\mathbf{w}, \mathbf{u})\right]^{-1} = \mathbb{E}[Q_{22}] + \frac{1}{L_{22}} \sum_{i=K}^{\infty} \left[I - \frac{1}{L_{22}} \nabla_{22}^2 g(\mathbf{w}, \mathbf{u})\right]^i, \end{equation*}\] we have \[\begin{align*} &\|\mathcal{M}(\mathbf{w}_t, \mathbf{u}_t) - \hat{\mathcal{M}}(\mathbf{w}_t,\mathbf{u}_t)\|_2^2\leq O(\|\left[\nabla_{22}^2 g(\mathbf{w}, \mathbf{u})\right]^{-1} - \mathbb{E}[Q_{22}]\|_2^2),\\ &\left\| \left[\nabla_{22}^2 g(\mathbf{w}, \mathbf{u})\right]^{-1} - \mathbb{E}[Q_{22}] \right\|_2 \le \frac{1}{L_{22}} \sum_{i=K}^{\infty} \left\|I - \frac{1}{L_{22}} \nabla_{22}^2 g(\mathbf{w}, \mathbf{u})\right\|_2^i \le \frac{1}{\mu_g} \left(1 - \frac{\mu_g}{L_{22}}\right)^K. \end{align*}\] As a result, if \(K=O(\frac{L_{22}}{\mu_g}\log(1/(\mu_g\beta_t\sigma^2)))\), then \(\|\mathcal{M}(\mathbf{w}_t, \mathbf{u}_t) - \mathcal{M}'(\mathbf{w}_t,\mathbf{u}_t)\|_2^2\leq O(\beta_t\sigma^2)\). Then similar to the analysis of Approach 1, we can establish a complexity of \(O(1/\epsilon^4)\) for finding an \(\epsilon\)-stationary solution of \(F(\cdot)\) in expectation.

4.5.3.3 Approach 3: The penalty method

An alternative approach to avoid computing the Hessian inverse and Jacobian matrices is to reformulate the problem as a constrained optimization problem: \[\begin{align*} \min_{\mathbf{w},\mathbf{u}} &\quad f(\mathbf{w}, \mathbf{u}) \\ \text{s.t.} &\quad g(\mathbf{w}, \mathbf{u}) \leq \min_{\mathbf{u}} g(\mathbf{w}, \mathbf{u}). \end{align*}\] This constrained problem can be addressed using a penalty method (see Section 6.7): \[\begin{align*} \min_{\mathbf{w},\mathbf{u}} \; f(\mathbf{w}, \mathbf{u}) + \lambda \big( g(\mathbf{w}, \mathbf{u}) - \min_{\mathbf{y}} g(\mathbf{w}, \mathbf{y}) \big)_+, \end{align*}\] where \(\lambda > 0\) is a penalty parameter and \((\cdot)_+\) denotes the positive part. Since \(g(\mathbf{w}, \mathbf{u}) \geq \min_{\mathbf{y}} g(\mathbf{w}, \mathbf{y})\), the formulation simplifies to:

\[\begin{align}\label{eqn:bio-minmax} &\min_{\mathbf{w},\mathbf{u}} \; f(\mathbf{w}, \mathbf{u}) + \lambda \left( g(\mathbf{w}, \mathbf{u}) - \min_{\mathbf{y}} g(\mathbf{w}, \mathbf{y}) \right)\\ &= \min_{\mathbf{w},\mathbf{u}} \max_{\mathbf{y}} f(\mathbf{w}, \mathbf{u}) + \lambda \left( g(\mathbf{w}, \mathbf{u}) - g(\mathbf{w}, \mathbf{y}) \right). \end{align}\]

If both \(f\) and \(g\) are smooth and \(g\) is strongly convex in its second argument, the resulting formulation becomes a non-convex strongly-concave min-max problem, which can be effectively addressed using the SMDA algorithm with the following update for \(t\geq 1\):

\[\begin{equation}\label{eqn:bi-smda} \begin{aligned} &\mathbf{y}_{t+1} = \mathbf{y}_{t} + \gamma_t\lambda\nabla_2 g(\mathbf{w}_t, \mathbf{y}_{t}; \xi_t),\\ &\mathbf{z}_t = \nabla f(\mathbf{w}_t, \mathbf{u}_{t}; \zeta_t) + \lambda \left(\nabla g(\mathbf{w}_t, \mathbf{u}_{t}; \xi_t) - \left[\nabla_1 g(\mathbf{w}_t, \mathbf{y}_{t}; \xi_t)\atop 0\right]\right),\\ &\mathbf{v}_{t} = (1-\beta_t)\mathbf{v}_{t-1} + \beta_t \mathbf{z}_t, \\ &\left[\mathbf{w}_{t+1}\atop \mathbf{u}_{t+1}\right] = \left[\mathbf{w}_t\atop \mathbf{u}_{t}\right] - \eta_t \mathbf{v}_{t}. \end{aligned} \end{equation}\]

Convergence Analysis

The convergence analysis of (\(\ref{eqn:bi-smda}\)) for the min–max problem (\(\ref{eqn:bio-minmax}\)) follows a similar approach to that of Theorem 4.5 for SMDA. However, a remaining challenge lies in converting the convergence result for the min–max formulation into that of the original problem. To address this, we provide the detailed convergence analysis below. We begin by stating the following assumption.

Let us define \(\bar{\mathbf{w}} : = (\mathbf{w}, \mathbf{u})\) and

\[\begin{align} &\bar f(\bar{\mathbf{w}}, \mathbf{y}): = f(\mathbf{w}, \mathbf{u}) + \lambda \left( g(\mathbf{w}, \mathbf{u}) - g(\mathbf{w}, \mathbf{y}) \right),\\ &\bar F(\bar{\mathbf{w}}) : = \max_{\mathbf{y}}\bar f(\bar{\mathbf{w}}, \mathbf{y}). \end{align}\]

Then \[\begin{align*} &\nabla_1\bar f(\bar{\mathbf{w}}, \mathbf{y})=\nabla f(\mathbf{w}, \mathbf{u}) + \lambda \left(\nabla g(\mathbf{w}, \mathbf{u}) - \left[\nabla_1 g(\mathbf{w}, \mathbf{y})\atop 0\right]\right),\\ &\nabla_2\bar f(\bar{\mathbf{w}}, \mathbf{y})= -\lambda \nabla_2 g(\mathbf{w}, \mathbf{y}),\\ &\nabla_1\bar f(\bar{\mathbf{w}}, \mathbf{y};\varepsilon)=\nabla f(\mathbf{w}, \mathbf{u}; \zeta) + \lambda \left(\nabla g(\mathbf{w}, \mathbf{u};\xi) - \left[\nabla_1 g(\mathbf{w}, \mathbf{y}; \xi)\atop 0\right]\right),\\ &\nabla_2\bar f(\bar{\mathbf{w}}, \mathbf{y};\xi)= -\lambda \nabla_2 g(\mathbf{w}, \mathbf{y};\xi). \end{align*}\] where \(\varepsilon=(\zeta, \xi)\). We first show \(\bar f(\bar{\mathbf{w}}, \mathbf{y})\) satisfies the conditions in Assumption 4.8.

■

■

Convergence of the original function

Next, we derive the convergence of the original function in terms of \(\|\nabla F(\mathbf{w})\|_2\). We need the following additional assumption.

Proof.
Let \(\mathbf{u}^* = \mathbf{u}^*(\mathbf{w})\). Then, \[\begin{align*} \nabla_{1} \bar{F}(\mathbf{w}, \mathbf{u}) &= \nabla_{1} f(\mathbf{w}, \mathbf{u}) + \lambda (\nabla_{1} g(\mathbf{w}, \mathbf{u}) - \nabla_{1} g(\mathbf{w}, \mathbf{u}^*)) \\ \nabla_{2} \bar{F}(\mathbf{w}, \mathbf{u}) &= \nabla_{2} f(\mathbf{w}, \mathbf{u}) + \lambda \nabla_{2} g(\mathbf{w}, \mathbf{u}). \end{align*}\] Due to Lemma 4.24, we have

\[\begin{equation} \label{eq:31_new} \begin{split} &\nabla F(\mathbf{w}) - \nabla_{1} \bar{F}(\mathbf{w}, \mathbf{u}) = \nabla_{1} f(\mathbf{w}, \mathbf{u}^*) - \nabla_{1} f(\mathbf{w}, \mathbf{u}) \\ & -\nabla_{12} g(\mathbf{w}, \mathbf{u}^*) \nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} \nabla_{2} f(\mathbf{w}, \mathbf{u}^*) - \lambda (\nabla_{1} g(\mathbf{w}, \mathbf{u}) - \nabla_{1} g(\mathbf{w}, \mathbf{u}^*)). \end{split} \end{equation}\]

We can rearrange terms for \((\nabla_{1} g(\mathbf{w}, \mathbf{u}) - \nabla_{1} g(\mathbf{w}, \mathbf{u}^*))\) as the following:

\[\begin{equation} \label{eq:32_new} \begin{split} \nabla_{1} g(\mathbf{w}, \mathbf{u}) - \nabla_{1} g(\mathbf{w}, \mathbf{u}^*) &= \nabla_{1} g(\mathbf{w}, \mathbf{u}) - \nabla_{1} g(\mathbf{w}, \mathbf{u}^*) - \nabla_{12} g(\mathbf{w}, \mathbf{u}^*)^{\top} (\mathbf{u} - \mathbf{u}^*) \\ & + \nabla_{12} g(\mathbf{w}, \mathbf{u}^*)^{\top} (\mathbf{u} - \mathbf{u}^*). \end{split} \end{equation}\]

To continue, we leverage the following equality: \[\begin{equation*} \begin{split} \mathbf{u} - \mathbf{u}^* =& -\nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} (\nabla_{2} g(\mathbf{w}, \mathbf{u}) - \nabla_{2} g(\mathbf{w}, \mathbf{u}^*) - \nabla_{22} g(\mathbf{w}, \mathbf{u}^*) (\mathbf{u} - \mathbf{u}^*)) \\ & +\nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} (\nabla_{2} g(\mathbf{w}, \mathbf{u}) - \nabla_{2} g(\mathbf{w}, \mathbf{u}^*)). \end{split} \end{equation*}\] By the optimality condition for \(\mathbf{u}^*\), \(\nabla_{2} g(\mathbf{w}, \mathbf{u}^*) = 0\), and \(\nabla_{2} \bar{F}(\mathbf{w}, \mathbf{u})=\nabla_{2} f(\mathbf{w}, \mathbf{u}) + \lambda \nabla_{2} g(\mathbf{w}, \mathbf{u})\), we can express \(\mathbf{u} - \mathbf{u}^*\) as

\[\begin{equation}\label{eq:33_new} \begin{split} \mathbf{u} - \mathbf{u}^* &= -\nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} (\nabla_{2} g(\mathbf{w}, \mathbf{u}) - \nabla_{2} g(\mathbf{w}, \mathbf{u}^*) - \nabla_{22} g(\mathbf{w}, \mathbf{u}^*) (\mathbf{u} - \mathbf{u}^*)) \\ & + \frac{1}{\lambda} \nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} (\nabla_{2} \bar{F}(\mathbf{w}, \mathbf{u}) - \nabla_{2} f(\mathbf{w}, \mathbf{u})). \end{split} \end{equation}\]

Combining (\(\ref{eq:33_new}\)) and (\(\ref{eq:32_new}\)) and then plugging the result back to (\(\ref{eq:31_new}\)), we have \[\begin{equation*} \begin{split} &\nabla F(\mathbf{w}) - \nabla_{1} \bar{F}(\mathbf{w}, \mathbf{u}) = \nabla_{1} f(\mathbf{w}, \mathbf{u}^*) - \nabla_{1} f(\mathbf{w}, \mathbf{u}) \\ & -\nabla_{12} g(\mathbf{w}, \mathbf{u}^*) \nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} \nabla_{2} f(\mathbf{w}, \mathbf{u}^*) \\ &- \lambda (\nabla_{1} g(\mathbf{w}, \mathbf{u}) - \nabla_{1} g(\mathbf{w}, \mathbf{u}^*) - \nabla_{12} g(\mathbf{w}, \mathbf{u}^*)^{\top} (\mathbf{u} - \mathbf{u}^*))\\ & +\lambda \nabla_{12} g(\mathbf{w}, \mathbf{u}^*)^{\top} \nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} (\nabla_{2} g(\mathbf{w}, \mathbf{u}) - \nabla_{2} g(\mathbf{w}, \mathbf{u}^*) - \nabla_{22} g(\mathbf{w}, \mathbf{u}^*) (\mathbf{u} - \mathbf{u}^*)) \\ & - \nabla_{12} g(\mathbf{w}, \mathbf{u}^*)^{\top} \nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} (\nabla_{2} \bar{F}(\mathbf{w}, \mathbf{u}) - \nabla_{2} f(\mathbf{w}, \mathbf{u})). \end{split} \end{equation*}\]

As a result, we have \[\begin{equation*} \begin{split} &\nabla F(\mathbf{w}) - \nabla_{1} \bar{F}(\mathbf{w}, \mathbf{u})+ \nabla_{12} g(\mathbf{w}, \mathbf{u}^*)^{\top} \nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} \nabla_{2} \bar{F}(\mathbf{w}, \mathbf{u}) \\ & = \nabla_{1} f(\mathbf{w}, \mathbf{u}^*) - \nabla_{1} f(\mathbf{w}, \mathbf{u}) \\ & -\nabla_{12} g(\mathbf{w}, \mathbf{u}^*) \nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} (\nabla_{2} f(\mathbf{w}, \mathbf{u}^*) - \nabla_{2} f(\mathbf{w}, \mathbf{u})) \\ &- \lambda (\nabla_{1} g(\mathbf{w}, \mathbf{u}) - \nabla_{1} g(\mathbf{w}, \mathbf{u}^*) - \nabla_{12} g(\mathbf{w}, \mathbf{u}^*)^{\top} (\mathbf{u} - \mathbf{u}^*))\\ & +\lambda \nabla_{12} g(\mathbf{w}, \mathbf{u}^*)^{\top} \nabla_{22} g(\mathbf{w}, \mathbf{u}^*)^{-1} (\nabla_{2} g(\mathbf{w}, \mathbf{u}) - \nabla_{2} g(\mathbf{w}, \mathbf{u}^*) - \nabla_{22} g(\mathbf{w}, \mathbf{u}^*) (\mathbf{u} - \mathbf{u}^*)) . \end{split} \end{equation*}\]

■

Next, we bound \(\|\mathbf{u}^*_\lambda(\mathbf{w}) - \mathbf{u}^*(\mathbf{w})\|_2\).

■

■

← Go Back