A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time

Introduction

Large language models (LLMs) like GPT-1 , BERT , GPT-2 , GPT-3 , ChatGPT , GPT-4 , OPT , Llama , and Llama 2 have demonstrated impressive capabilities in natural language processing (NLP). These models understand and generate complex language, enabling a wide range of applications such as sentiment analysis , language translation , question answering , and text summarization . Despite their high-quality performance, there remains untapped potential in optimizing and training these massive models, making it a challenging endeavor in the present day.

The primary technical foundation supporting the capabilities of LLMs is the attention matrix . The central concept of attention is to learn representations that emphasize the most relevant parts of the input. To be more specific, the attention mechanism compares the query vectors (the output tokens) with the key vectors (the input tokens). The attention weights are then determined based on the similarity of this comparison, indicating the relative importance of each input token. These attention weights are used to compute weighted averages of the value vectors, resulting in the output representation. By leveraging attention, LLMs acquire the ability to focus on the crucial aspects of the input, allowing them to gather pertinent information more efficiently and precisely. This capability enables LLMs to process longer texts effectively and comprehend intricate semantic relationships. Notably, the self-attention mechanism enables LLMs to establish connections between various segments of the input sequence, enhancing their contextual understanding.

We start with defining the general Attention forward layer,

Mathematically, a general optimization with respect to attention computation is defined as:

However, simplifying this problem may lead to a significant decrease in the model performance, which may require extra model training or fine-tuning. This results in deployment obstacles.

In this paper, our focus is on optimizing the attention mechanism. Our goal is to present a complete, un-simplified analysis of the attention problem defined in Definition 1.2, a task that, to the best of our knowledge, has not been done before. We provide a provable guarantee for optimizing the attention function in the case of a single-layer attention network. Our motivation stems from the critical role of the attention optimization problem in the functionality of LLMs, and we firmly believe that our theoretical analysis will significantly influence the development of LLMs.

As , they show that one step forward computation of attention can be done in $o(n^{2})$ time without formulating the $n\times n$ matrix. However, it is still an open problem about how fast we optimize the loss function via the iterative method.

How fast can we optimize the training process of attention matrix (See Definition 1.2)?

In this study, we make progress towards this fundamental question.

To establish the correctness of our algorithm, we conduct a comprehensive analysis of the positive semi-definite (PSD) property and the Lipschitz continuity of the Hessian matrix constructed from the attention matrix. These two properties provide the necessary assurance for employing TensorSRHT and Newton’s method, ensuring both fast computation and convergence, respectively.

Now, we will present our main result as follows.

Moreover, the attention weight can be viewed as the output of a softmax regression model, which is defined as follows:

On the one hand, due to the observation in , the equation in Part 1 of Definition 1.4 can be viewed as one row of the equation in Part 2 of Definition 1.4.

Note that the multiple softmax regression problem is a simplified version of what we study in Definition 1.2. We believe that our work can also support the study of softmax regression.

Relatinship with Support Vector Machines (SVM)

Roadmap

In Section 2, we introduce related research work. In Section 3, we provide an overview of the techniques we will use throughout the rest of the paper. In Section 4, we present the basic notations we use, some mathematical facts, and helpful definitions that support the following proof. In Section 5, we compute the gradients of the helpful functions defined earlier. In Section 6, we define the Hessian for further discussion. In Section 7, we compute the Hessian matrix with respect to $X$. In Section 8, we demonstrate that the Hessian for $X$ is Lipschitz. In Section 9, we show that the Hessian matrix with respect to $X$ is positive semidefinite (PSD). In Section 10, we compute the Hessian matrix with respect to $Y$ and show that it is Lipschitz and positive semidefinite (PSD). In Section 11, we compute the Hessian matrix with respect to both $X$ and $Y$. In Section 12, we demonstrate that the Hessian matrix with respect to both $X$ and $Y$ is Lipschitz. In Section 13, we introduce some tensor sketch techniques to obtain fast approximations of the Hessian. In Section 14, we introduce the Newton step.

Related Work

represents one of the earliest works that employed attention in NLP. They assumed that a fixed-length vector could enhance the performance of the encoder-decoder design by incorporating an attention mechanism. This mechanism allows the decoder to focus on relevant words in the source sentence while generating translations. Consequently, this approach significantly improves the performance of machine translation models compared to those without an attention mechanism. Subsequently, explained two variants of attention: local attention, which considers a subset of source words at a time, and global attention, which attends to all source words.

Attention finds extensive applications across various domains. In image captioning, utilizes attention matrices to align specific parts of an image with words in a caption. In the context of the Transformer model , attention matrices capture differences between words in a sentence. In the realm of graph neural networks, investigates these neural network architectures designed for graph-structured data, computing attention matrices between each node and its neighbors.

On the theoretical side, after the emergence of LLMs, there has been a substantial body of work dedicated to studying attention computation . Notably, recent research by employs Locality Sensitive Hashing (LSH) techniques to approximate attention mechanisms. In particular, introduces $\mathsf{KDEformer}$, an efficient algorithm for approximating dot-product attention. This algorithm provides provable spectral norm bounds and outperforms various pre-trained models. Additionally, current research explores both static and dynamic approaches to calculating attention, as evidenced by the works of and . Furthermore, delves into the regularization of hyperbolic regression problems, which involve functions like $\exp$, $\sinh$, and $\cosh$. Lastly, proposes randomized and deterministic algorithms for reducing the dimensionality of attention matrices in LLMs, achieving high accuracy while significantly reducing feature dimensions.

Additionally, numerous studies have attempted to analyze theoretical attention from the perspectives of optimization and convergence . investigated how transformers acquire knowledge about word co-occurrence patterns. focused on studying regression problems inspired by neural networks that employ exponential activation functions. analyzed why models occasionally prioritize significant words and explained how the attention mechanism evolves during the training process. demonstrated that the presence of a heavy-tailed noise distribution contributes to the bad performance of stochastic gradient descent (SGD) compared to adaptive methods.

Theoretical LLMs

There are numerous amount of works focusing on the theoretical aspects of LLMs. In , the syntactic representations of the attention matrix and the individual word embeddings are presented, together with the mathematical justification of elucidating the geometrical properties of these representations. introduces a structural probe that analyzes, under the linear transformation of a word representation space of a neural network, whether or not syntax trees are embedded.

study the optimization of LLMs. proposes a new algorithm called ZO-BCD. It has favorable overall query complexity and a smaller computational complexity in each iteration. creates a simple scalable second-order optimizer, called Sophia. In different parts of the parameter, Sophia adapts to the curvature. This may be strongly heterogeneous for language modeling tasks. The bound of the running time does not rely on the condition number of the loss.

Other theoretical LLM papers study the knowledge and skills of LLMs. analyzes distinct “skill” neurons, which are regarded as robust indicators of downstream tasks when employing the process of soft prompt-tuning, as discussed in , for language models. find a positive relationship between the activation of these neurons and the expression of their corresponding facts, through analyzing BERT. Simultaneously, employs a fully unsupervised approach to extract latent knowledge from a language model’s internal activations. In addition, and show that in the feed-forward layers of pre-trained models, language models localize knowledge. explores the feasibility of selecting a specific subset of layers for modification and determining the optimal location for integrating a classifier. demonstrate that large trained transformers exhibit sparsity in their feedforward activations. Zero-th order algorithm for training LLM has been analyzed .

LLMs Application and Evaluation

Recently, there has been much interest in developing LLM-based systems for conversational AI and task-oriented dialogue, like Google’s Meena chatbot , Microsoft 365 Copilot , Adobe firefly, Adobe Photoshop, GPT series , and BERT .

Moreover, LLM evaluation is also a popular research area. Within the field of NLP, LLMs are evaluated based on natural language understanding , reasoning , natural language generation , and multilingual tasks . Robustness , ethics , biases , and trustworthiness are also important aspects. More specifically, the abilities of LLMs in social science , mathematics , science , engineering , and medical applications are evaluated.

Sketching

Sketching is a powerful tool that is used to accelerate the performance of machine learning algorithms and optimization processes. The fundamental concept of sketching is to partition a large input matrix into a significantly smaller sketching matrix but still preserve the main characteristics of the original matrix. Therefore, the algorithms may work with the smaller matrix instead of the huge original, which leads to a substantial reduction in processing time. Many previous works have studied sketching, proposed sketching algorithms, and supported these algorithms with robust theoretical guarantees. For example, the Johnson-Lindenstrauss lemma is proposed by : it shows that under a certain high-dimensional space, projecting points to a lower-dimensional subspace may preserve the pairwise distances between these points. This mathematical property becomes the foundation of the development of faster algorithms for tasks such as nearest neighbor search. In addition, as explained in , the Fast Johnson-Lindenstrauss Transform (FJLT) introduces a specific family of structured random projections that can be applied to a matrix in input sparsity time.

More recently, sketching has been applied to many numerical linear algebra tasks, such as linear regression , dynamic kernel estimation , submodular maximization , matrix sensing , gradient-based algorithm , clustering , convex programming , online optimization problems , training neural networks , reinforcement learning , tensor decomposition , relational database , low-rank approximation , distributed problems , weighted low rank approximation , CP decomposition , regression inspired by softmax , matrix sensing , and Kronecker product regression .

Second-order Method

Second-order method have been used for solving many convex optimization and non-convex optimization problems, such as linear programming , empirical risk minimization , support vector machines , cutting plan method , semi-definite programming , hyperbolic programming/polynomials , streaming algorithm , federated learning .

Convergence and Deep Neural Network Optimization

Many works focus on analyzing optimization, convergence guarantees, and training improvement. shows that stochastic gradient descent optimizes over-parameterized neural networks on structured data, while demonstrates that gradient descent optimizes over-parameterized neural networks. In , a convergence theory for over-parameterized deep neural networks via gradient descent is developed. analyzes the convergence rate of training recurrent neural networks. provides a fine-grained analysis of optimization and generalization for over-parameterized two-layer neural networks. studies exact computation with an infinitely wide neural network. proposes a Gram-Gauss-Newton method for optimizing over-parameterized neural networks. improves the analysis of the global convergence of stochastic gradient descent when training deep neural networks, requiring a milder over-parameterization compared to prior research. Other research, such as , focuses on optimization and generalization, while emphasize the convergence rate and stability. Works like concentrate on specialized optimization algorithms and techniques for training neural networks, and concentrate on leveraging neural network structure.

Algorithmic Regularization

There is a significant body of research exploring the latent bias inherent in gradient descent when applied to separable classification tasks. This research typically employs logistic or exponentially-tailed loss functions to maximize margins, as demonstrated in previous studies . These novel findings have also been applied to non-separable data through the utilization of gradient-based techniques . Analysis of implicit bias in regression problems and associated loss functions is carried out using methods such as mirror descent and stochastic gradient descent . These findings extend to the implicit bias of adaptive and momentum-based optimization methods .

Technique Overview

In this section, we will introduce the primary technique employed in this paper. The notations used in this section are presented in Preliminary (Section 4).

In the fast approximation and convergence guarantee of the training process for the attention matrix, the positive semi-definite property is a key focus in Section 6. In comparison to single/multiple softmax regression, both the weights $X$ and $Y$ (refer to Definition 1.2) need to be considered. Therefore, our Hessian matrix discussed in Section 6 has the following format

To establish the positive semi-definite property, we will examine the properties of the matrix above individually.

Positive Semi-Definite For Hessian Hx,xH_{x,x}, Hy,yH_{y,y}

The positive semi-definite of the Hessian, denoted as ${H_{x,x},H_{y,y}}$, constitutes a crucial initial step in the proof outlined in Lemma 6.1. These Hessian are discussed in detail in Section 9 and Section 10.

Leveraging Lemma 10.1 and Lemma 9.1, we can establish the following results if the regularization weight sufficiently large (see Section 9 in details), then

Spectral upper bound for Hx,yH_{x,y}, Hy,xH_{y,x}

To establish the spectral upper bound of $H_{x,y}$, we can decompose $H_{x,y}$ into $\{{G_{i}}\}_{i=1}^{4}$ as described in Lemma 12.10. Building upon the results from Lemma 12.10, we obtain: $\max_{i\in[n]}\|G_{i}\|\leq R^{2}$. The spectral upper bound for $H_{x,y}$ is then established in Lemma 12.8 as follows: $\|H(x,y)\|\leq nd\cdot 10R^{2}$.

Given this upper bound, our final focus in the proof of the positive semi-definite property (PSD) will be as follows.

PSD for Hessian HH

The Hessian matrix $H$ can be regarded as a combination of four matrices. The norm of the diagonal elements ($H_{x,x}$ in Section 9 and $H_{y,y}$ in Section 10) can be guaranteed to have a higher lower bound than $H_{x,y}$ and $H_{y,x}$ which are discussed in Section 11. Consequently, based on the positive semi-definite property of the diagonal matrix, the computation of the off-diagonal part of the matrix does not affect the positivity of the entire matrix, thereby establishing a positive semi-definite. With $a_{1}$, $a_{2}$, $a_{3}$ as the bound of the matrix above respectively in Lemma 6.1, we have the following result

Given the relationship of $\{a_{i}\}_{i=1}^{3}$ as discussed above, the positive semi-definite property of the Hessian matrix is established.

Lipschitz property for Hessian

The Lipschitz property of the Hessian is determined by the upper bound and Lipschitz property of the basic functions that constitute the Hessian matrix $H$. Since $H$ has three parts $H_{x,x}$, $H_{x,y}$ and $H_{y,y}$. In Section 10, due to $H(y)$ is independent of $y$, the Lipschitz property can be easily established. For details of others, we refer the readers to read Section 12.

To compute the Lipschitz continuity of $H_{x,x}$, we will begin by providing a brief explanation. In our proof, we first establish upper bounds for the functions $u(x)$, $c(x)$, and $f(x)$ in Lemma 8.4, which together form the matrix $H_{x,x}$ (as detailed in Section 4.3). Importantly, we ensure that these basic functions possess the Lipschitz property in Lemma 8.5. Using the foundational components mentioned above, we can decompose $H_{x,x}$ into four distinct parts denoted as $\{G_{k}\}_{k=1}^{4}$. We will leverage the Lipschitz property of the basic functions above and a method introduced below, The following task is extensively involved in the Lipschitz proof (for each $G_{k}$), we want to bound

where assume that $\beta_{0}(x)=1$ and $\beta_{t+1}(x)=1$ for convenient. We will then proceed to establish the Lipschitz continuity of $H_{x,x}$

2 Algorithm

Gradient Computation

We can compute the gradient in Section 5 as follows:

Straightforward Hessian Computation

TensorSRHT Fast Approximation for Hessian

Overall Time

Preliminary

In Section 4.1, we present the basic mathematical properties of vectors, norms and matrices. In section 4.2, we provide a definition of $L(X,Y)$. In Section 4.3, we define a series of helpful functions with respect to $X$. In section 4.4, we define a series of helpful functions with respect to $Y$. In Section 4.5, we define a series of helpful functions with respect to both $X$ and $Y$. In Section 4.6, we define the regularization function. In Section 4.7, we introduce facts related to fast matrix multiplication.

Now we define the basic notations we use in this paper.

1 Basic Facts

In this section, we will introduce the basic mathematical facts.

$\langle u\circ v,w\rangle=\langle u\circ w,v\rangle$

$\langle u\circ v,w\rangle=\langle u\circ v\circ w,{\bf 1}_{n}\rangle=u^{\top}\diag(v)w$

$\langle u\circ v\circ w\circ z,{\bf 1}_{n}\rangle=u^{\top}\diag(v\circ w)z$

$u\circ v=v\circ u=\diag(u)\cdot v=\diag(v)\cdot u$

$u^{\top}(v\circ w)=v^{\top}(u\circ w)=w^{\top}(u\circ v)=u^{\top}\diag(v)w=v^{\top}\diag(u)w=w^{\top}\diag(u)v$

$\diag(u)\cdot\diag(v)\cdot{\bf 1}_{n}=\diag(u)v$

$a\langle w,v\rangle+b\langle u,v\rangle=\langle aw+bu,v\rangle=\langle v,aw+bu\rangle=a\langle v,w\rangle+b\langle v,u\rangle$.

$\|x\circ y\|_{2}\leq\|x\|_{\infty}\cdot\|y\|_{2}$

$\|x\|_{\infty}\leq\|x\|_{2}\leq\sqrt{n}\|x\|_{\infty}$

$\|\exp(x)\|_{\infty}\leq\exp(\|x\|_{2})$

$\|\alpha x\|_{2}\leq|\alpha|\cdot\|x\|_{2}$

For any $\|x\|_{2},\|y\|_{2}\leq R$, we have $\|\exp(x)-\exp(y)\|_{2}\leq\exp(R)\cdot\|x-y\|_{2}$

If $X\preceq\alpha\cdot Y$, then $\|X\|\leq\alpha\cdot\|Y\|$

Part 1. $uu^{\top}\preceq\|u\|_{2}^{2}\cdot I_{n}$

Part 2. $\diag(u)\preceq\|u\|_{2}\cdot I_{n}$

Part 3. $\diag(u\circ u)\preceq\|u\|_{2}^{2}\cdot I_{n}$

Part 4. $uv^{\top}+vu^{\top}\preceq uu^{\top}+vv^{\top}$

Part 5. $uv^{\top}+vu^{\top}\succeq-(uu^{\top}+vv^{\top})$

Part 6. $(v\circ u)(v\circ u)^{\top}\preceq\|v\|^{2}_{\infty}uu^{\top}$

Part 7. $\diag(u\circ v)\preceq\|u\|_{2}\|v\|_{2}\cdot I_{n}$

2 General Definitions

In this section, we introduce some general definitions.

We use $i$ to denote indices in $[d^{2}]$ range, and $j$ to denote indices in $[n^{2}]$ range.

We use $i_{0},i_{1},i_{2}$ to denote indices in $[d]$, and $j_{0},j_{1},j_{2}$ to denote indices in $[n]$.

Our final goal is to study the loss function, defined as:

Further, for each $j_{0}\in[n],i_{0}\in[d]$, we define $L(X,Y)_{j_{0},i_{0}}$ as follows:

3 Helpful Definitions With Respect to XX

4 A Helpful Definition With Respect to YY

5 Helpful Definitions With Respect to Both XX and YY

Furthermore, we define $c(x,:)_{j_{0},i_{0}}$ as follows

Similarly, we also define $c(:,y)_{j_{0},i_{0}}$ as follows

6 Regularization

In this section, we define the regularization loss we use.

Note that $\|WA_{3}y\|_{F}^{2}=\sum_{i_{0}=1}^{d}\|WA_{3}y_{i_{0}}\|_{2}^{2}$.

7 Fast Matrix Multiplication

The following fact can be found in Lemma 3.6 of , also see .

Gradient

In Section 5.1, we show the gradient with respect to variables $x$. In Section 5.2, we prove the gradient with respect to variables $y$. In Section 5.3, we compute running time of $c,f,h$. In Section 5.4, we reformulate the gradient with respect to $X$ to compute time complexity. In Section 5.5, we reformulate the gradient with respect to $Y$ to compute time complexity.

In this section, we compute the gradient for $x$. Most of the following gradient computations can be found in .

Then, for each $i\in[d^{2}]$, for each $j_{0}\in[n]$, we have

Part 9 (for hessian diagonal term, this can be obtained by using Part 4 as a black-box)

Part 10 (for hessian off-diagonal term, this can be obtained by using Part 4 as a black-box)

Proof of Part 1. See Part 4 of Proof of Lemma 5.18 in (Page 14).

Proof of Part 2. See Part 5 of Proof of Lemma 5.18 in (Page 14).

Proof of Part 3. See Part 9 of Proof of Lemma 5.18 in (page 15).

Proof of Part 4. See Part 14 of Proof of Lemma 5.18 in (page 15).

Proof of Part 6. Noted that by Definition 4.13, we have

where the first step is due to Eq. (4), the second step is because of chain rule of derivative, the last step comes from Part 5.

where the first step is due to Fact 4.5, the second step comes from Fact 4.5, the third step is because of Part 4, the fourth step is owing to simple algebra, the fifth step follows from Fact 4.1, and the last step comes from Fact 4.1.

where the first step comes from Fact 4.5, the second step is because of Fact 4.5, the third step follows from Part 4, the fourth step is due to simple algebra, the fifth step is owing to Fact 4.1, and the last step comes from Fact 4.1.

where the first step is due to Fact 4.5, the second step comes from Part 4, and the last step is because of Fact 4.1.

where the first step comes from Fact 4.5, the second step is owing to Part 4, and the last step is due to Fact 4.1. ∎

2 Gradient With Respect to yy

In this section, we compute the gradient with respect to $y$.

Let $h(y_{i_{0}}):=\underbrace{A_{3}}_{n\times d}\underbrace{y_{i_{0}}}_{d\times 1}.$

Let $h(y_{i_{0}})=h(y)_{i_{0}}$ for convenient

where the first step is due to $i_{1}\neq i_{2}$.

where the first step comes from Fact 4.5, the second step is due to the result of Part 1.

where the first step is becaues of Fact 4.5, the second step comes from the result of Part 2.

where the first step is due to the Definition 4.13, the second step comes from the chain rule of derivative, and the last step is owing to Part 5.

where the first step is because of the Definition 4.13, the second step is due to the chain rule of derivative, and the last step comes from Part 6. ∎

3 Computation of c,f,hc,f,h

In this section, we explain how to compute $c(x,y),f(x),h(y)$.

4 Reformulating Gradient (xx) in Matrix View

In this section, we reformulate the gradient $x$ in the matrix’s view.

We first compute $(\diag(f(x)_{j_{0}})-f(x)_{j_{0}}f(x)_{j_{0}}^{\top})h(y)_{i_{0}}$, this can be done in $O(n)$ time.

Then we can compute the rest, it takes $O(nd^{2})$ time.

where the first step is based on Definition 4.7, the second step is because of Part 1, the third step is due to Eq. (8), the fourth step follows from Eq. (9), and the last step due to tensor-trick.

5 Reformulating Gradient (yy) in Matrix View

In this section, we reformulate the gradient $y$ in the matrix’s view.

Let $\widetilde{q}(x,y)_{i_{0}}=\sum_{j_{0}=1}^{n}f(x)_{j_{0}}c(x,y)_{j_{0},i_{0}}$

where the first step comes from the assumption from the Lemma statement and the second step is based on Fact 4.1.

where the first step is due to the assumption from the Lemma statement, the second step is because of Fact 4.1, and the last step comes from the definition of $\widetilde{q}(x,y)_{i_{0}}$ (see from the Lemma statement).

where the first step comes from tensor trick based on Part 2.

Hessian

In this section, we provide more details related to Hessian.

We can view $H_{y,y}=\begin{bmatrix}H_{y,y,1,1}&0&0&\cdots&0\\ 0&H_{y,y,2,2}&0&\cdots&0\\ 0&0&H_{y,y,3,3}&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&H_{y,y,d,d}\end{bmatrix}$

Let $\alpha_{1}\geq\alpha_{3}>0$, $\alpha_{2}\geq\alpha_{3}>0$

where the first step is based on the expansion of $H$, the second step is due to $H_{x,x}\succeq\alpha_{1}I_{d^{2}},H_{y,y}\succeq\alpha_{2}I_{d^{2}}$, the third step comes from Fact 4.2 and Fact 4.3 , the fourth step is because of $\|H_{x,y}\|\leq\alpha_{3},\|H_{y,x}\|\leq\alpha_{3}$, the fifth step is owing to $2\|u\|_{2}\|v\|_{2}\leq\|u\|_{2}^{2}+\|v\|_{2}^{2}$, and the last step is based on the simple algebra.

Hessian for XX

In Section 7.1, we compute the Hessian matrix with respect to $x$. In Section 7.2, we present a helpful lemma to simplify the Hessian. In Section 7.3, we define $B(x)$, representing the Hessian.

Now, we start to compute the Hessian matrix with respect to $x$.

Let $\gamma(x)_{j_{0}}:=\langle f(x)_{j_{0}},v\rangle$ (We define this notation for easy of writing proofs.)

Then we have for each $i\in[d^{2}]$, $l\in[d^{2}]$

Part 2. $i\neq l$ Hessian off-diagonal term

where the first step is based on the product rule of derivative, the second step comes from Part 4, Part 7, and Part 9 of Lemma 5.1, and the last step is due to simple algebra.

where the first step comes from Part 6 of Lemma 5.1 and the second step is due to Part 5 of Lemma 5.1.

Combining the above two equations, we complete the proof.

where the first step is owing to the product rule of derivative, the second step is based on Part 4, Part 8, and Part 10 of Lemma 5.1, and the last step comes from simple algebra.

Combining the above two equations, we complete the proof. ∎

2 A Helpful Lemma

In this section, we present a helpful Lemma.

where the first step follows from Fact 4.1.

where the first step follows from Fact 4.1, the second step follows from Fact 4.1, and the last step follows from the simple algebra.

where the first step follows from Fact 4.1, and the last step follows from Fact 4.1.

where the first step follows from Fact 4.1. ∎

3 Defining B⁡(x)B(x)

In this section, we formally define $B(x)$.

Let $\gamma_{j_{0}}(x)=\langle f(x)_{j_{0}},v\rangle$

$B_{\diag}^{1}:=(1-\gamma_{j_{0}}(x))\cdot c(x,:)_{j_{0},i_{0}}\cdot\diag(f(x)_{j_{0}}\circ v)$

$B_{\rank}^{1}:=-(2\gamma_{j_{0}}(x)+c(x,:)_{j_{0},i_{0}})\cdot((f(x)_{j_{0}}\circ v)f(x)_{j_{0}}^{\top}+f(x)_{j_{0}}(f(x)_{j_{0}}\circ v)^{\top})$

$B_{\rank}^{2}:=(2\gamma_{j_{0}}(x)c(x,:)_{j_{0},i_{0}}+\gamma_{j_{0}}(x)^{2})\cdot f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$

$B_{\rank}^{3}:=(f(x)_{j_{0}}\circ v)\cdot(f(x)_{j_{0}}\circ v)^{\top}$

Let $B(x)$ be defined as Definition 7.3, then we have

The proof follows by combining Lemma 7.1 and Lemma 7.2. ∎

Lipschitz Property of Hx,xH_{x,x}

In Section 8.1, we present the main results of the Lipschitz property of $H_{x,x}$. In Section 8.2, we summarize the results from following steps 1-9. In Section 8.3, we compute the upper bound of basic functions for the following proof. In Section 8.4, we compute the Lipschitz Property of basic functions for the following proof. In Section 8.5, we analyze the first step of Lipschitz function $c(x,:)_{j_{0},i_{0}}\cdot\diag(f(x)_{j_{0}}\circ v)$. In Section 8.6, we analyze the second step of Lipschitz function $-\gamma_{j_{0}}(x)\cdot c(x,:)_{j_{0},i_{0}}\cdot\diag(f(x)_{j_{0}}\circ v)$. In Section 8.7, we analyze the third step of Lipschitz function $-2\gamma_{j_{0}}(x)\cdot(f(x)_{j_{0}}\circ v)f(x)_{j_{0}}^{\top}$. In Section 8.8, we analyze the fourth step of Lipschitz function $-c(x,:)_{j_{0},i_{0}}\cdot(f(x)_{j_{0}}\circ v)f(x)_{j_{0}}^{\top}$. In Section 8.9, we analyze the fifth step of Lipschitz function $-2\gamma_{j_{0}}(x)\cdot f(x)_{j_{0}}(f(x)_{j_{0}}\circ v)^{\top}$. In Section 8.10, we analyze the sixth step of Lipschitz function $-c(x,:)_{j_{0},i_{0}})\cdot f(x)_{j_{0}}(f(x)_{j_{0}}\circ v)^{\top}$. In Section 8.11, we analyze the seventh step of Lipschitz function $2\gamma_{j_{0}}(x)c(x,:)_{j_{0},i_{0}}\cdot f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$. In Section 8.12, we analyze the eighth step of Lipschitz function $\gamma_{j_{0}}(x)^{2}\cdot f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$. In Section 8.13, we analyze the nineth step of Lipschitz function $(f(x)_{j_{0}}\circ v)\cdot(f(x)_{j_{0}}\circ v)^{\top}$.

In this section, we present the main result of the Lipschitz property.

Let $H=\sum_{j_{0}=1}^{n}\sum_{i_{0}=1}^{d}H_{j_{0},i_{0}}$ (because $L=\sum_{j_{0}=1}^{n}\sum_{i_{0}=1}^{d}L_{j_{0},i_{0}}$)

$\|A_{1}\|,\|A_{2}\|,\|A_{3}\|\leq R$, $\|\A_{j_{0}}\|\leq R$, $\|x\|_{2}\leq R$,$|b_{j_{0},i_{0}}|\leq R$, $\|v\|_{2}\leq R^{2}$

Part 1. For each $j_{0}\in[n]$, $i_{0}\in[d]$

where the first step follows from definition of $H_{j_{0},i_{0}}(x)$, the second step follows from Lemma 8.2, and last step follows from simple algebra.

where the first step follows from triangle inequality and $H=\sum_{j_{0}=1}^{n}\sum_{i_{0}=1}^{d}H_{j_{0},i_{0}}$, and the second step follows from Part 1. ∎

2 Summary of Nine Steps

In this section, we provide a summary of the nine-step calculation of Lipschitz for different matrix functions.

$G_{1}(x)=c(x,:)_{j_{0},i_{0}}\cdot\diag(f(x)_{j_{0}}\circ v)$

$G_{2}(x)=-\gamma_{j_{0}}(x)\cdot c(x,:)_{j_{0},i_{0}}\cdot\diag(f(x)_{j_{0}}\circ v)$

$G_{3}(x)=-2\gamma_{j_{0}}(x)\cdot(f(x)_{j_{0}}\circ v)f(x)_{j_{0}}^{\top}$

$G_{4}(x)=-c(x,:)_{j_{0},i_{0}}\cdot(f(x)_{j_{0}}\circ v)f(x)_{j_{0}}^{\top}$

$G_{5}(x)=-2\gamma_{j_{0}}(x)\cdot f(x)_{j_{0}}(f(x)_{j_{0}}\circ v)^{\top}$ (The proof of this is identical to $G_{3}$)

$G_{6}(x)=-c(x,:)_{j_{0},i_{0}}\cdot f(x)_{j_{0}}(f(x)_{j_{0}}\circ v)^{\top}$ (The proof of this is identical to $G_{4}$)

$G_{7}(x)=2\gamma_{j_{0}}(x)c(x,:)_{j_{0},i_{0}}\cdot f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$

$G_{8}(x)=\gamma_{j_{0}}(x)^{2}\cdot f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$

$G_{9}(x)=(f(x)_{j_{0}}\circ v)\cdot(f(x)_{j_{0}}\circ v)^{\top}$

The proof follows from Lemma 8.7, Lemma 8.8, Lemma 8.9, Lemma 8.10, Lemma 8.11, Lemma 8.12, Lemma 8.13, Lemma 8.14, and Lemma 8.15. ∎

3 A Core Tool: Upper Bound for Several Basic Functions

In this section, we analyze the upper bound of several basic functions.

Provided that the subsequent requirements are satisfied

Let $\beta$ be the greatest lower bound of $\langle u(x)_{j_{0}},{\bf 1}_{n}\rangle$

Let $\beta$ be the greatest lower bound of $\langle u(x)_{j_{0}},{\bf 1}_{n}\rangle$

Part 1. $\|u(x)_{j_{0}}\|_{2}\leq\sqrt{n}\cdot\exp(R^{2})$

Part 2. $|\alpha(x)_{j_{0}}|\leq n\exp(R^{2})$

Part 3. $|\alpha(x)_{j_{0}}|^{-1}\leq\exp(R^{2})$

Part 6. $|c(x,:)_{j_{0},i_{0}}|\leq 2R^{2}$

where the first step follows from Definition 4.8, the second step is based on Fact 4.2, the third step follows from Fact 4.2, and the fourth step is because of $\|\A_{j_{0}}\|\leq R$ and $\|x\|_{2}\leq R$ (see from the Lemma statement).

where the first step is due to Definition 4.9, the second is based on Fact 4.2, the third step follows from Part 1. and the forth step follows from simple algebra.

where the first step is because of Definition 4.9, the second step follows from the definition of $\beta$ and the third step is due to Lemma 8.3.

where the first step follows from Fact 4.2, the second step is due to Definition 4.10

where the first step is based on Definition 4.12, the second step is because of the definition of $\gamma_{j_{0}}(x)$, the third step follows from triangle inequality, the fourth step is based on Part 6 and $|b_{j_{0},i_{0}}|\leq R$ (see from the Lemma statement), and the last step follows from $R\geq 1$. ∎

4 A Core Tool: Lipschitz Property for Several Basic Functions

In this section, we analyze the Lipschitz property of several basic functions.

Let $\beta$ be the greatest lower bound of $\langle u(x)_{j_{0}},{\bf 1}_{n}\rangle$

Part 1. $\|u(x)_{j_{0}}-u(\widetilde{x})_{j_{0}}\|_{2}\leq\sqrt{n}\exp(2R^{2})\cdot\|x-\widetilde{x}\|_{2}$

Part 2. $|\alpha(x)^{-1}-\alpha^{-1}(\widetilde{x})|\leq n\exp(4R^{2})\cdot\|x-\widetilde{x}\|_{2}$

Part 3. $\|f(x)_{j_{0}}-f(\widetilde{x})_{j_{0}}\|_{2}\leq n^{1.5}R\exp(6R^{2})\cdot\|x-\widetilde{x}\|_{2}$

Part 4. $|\gamma(x)_{j_{0}}-\gamma(\widetilde{x})_{j_{0}}|\leq n^{1.5}\exp(7R^{2})\cdot\|x-\widetilde{x}\|_{2}$

Part 5. $|c(x,:)_{j_{0},i_{0}}-c(\widetilde{x},:)_{j_{0},i_{0}}|\leq n^{1.5}\exp(7R^{2})\cdot\|x-\widetilde{x}\|_{2}$

where the first step is due to Definition 4.8, the second step is because of Fact 4.2, the third step is based on Fact 4.2, the fourth step follows from Fact 4.3 , fifth step is due to $\|\A_{j_{0}}\|\leq R$.

where the first step is due to simple algebra, the second step is due to $\beta\geq\langle u(x)_{j_{0}},{\bf 1}_{n}\rangle$, the third step follows from Definition of $\alpha(x)$ (see Definition 4.9), the fourth step is based on Fact 4.1 and Fact 4.2, the fifth step is because of Part 1, and the sixth step follows from $R>4$ and $\beta^{-1}\leq\exp(R^{2})$.

where the first step is due to Definition 4.10, the second step is based on triangle inequality, the third step follows from Fact 4.2, the fourth follows from combination of Part 1, Part 2 and Lemma 8.4.

where the first step is based on the definition of $\gamma_{j_{0}}(x)$, the second is because of Fact 4.1, the third step is due to Cauchy–Schwarz inequality, and the last step follows from Part 3, $\|v\|\leq R^{2}$ and $R\geq 4$.

where the first step follows from Definition 4.12, the second step is based on the definition of $\gamma_{j_{0}}(x)$ and the last step follows from Part 4. ∎

In this section, we introduce our calculation of Lipschitz for $c(x,:)_{j_{0},i_{0}}\cdot\diag(f(x)_{j_{0}}\circ v)$.

Let $G_{1}(x)=c(x,:)_{j_{0},i_{0}}\cdot\diag(f(x)_{j_{0}}\circ v)$

$\|A_{1}\|,\|A_{2}\|,\|A_{3}\|\leq R$, $\|\A_{j_{0}}\|\leq R$, $\|x\|_{2}\leq R$,$|b_{j_{0},i_{0}}|\leq R$, $\|v\|_{2}\leq R^{2}$

where the first step is based on definition $G_{1,1}$, the second step is due to Fact 4.3, the third step follows from Lemma 8.4, and the fourth step is because of Lemma 8.5.

where the first step is because of definition of $G_{1,2}$, the second step is due to Fact 4.3, the third step follows from Lemma 8.4, and the fourth step is because of Lemma 8.5.

Combining the above two equations, we complete the proof. ∎

In this section, we introduce our calculation of Lipschitz for $-\gamma_{j_{0}}(x)\cdot c(x,:)_{j_{0},i_{0}}\cdot\diag(f(x)_{j_{0}}\circ v)$.

Let $G_{2}(x)=-\gamma_{j_{0}}(x)\cdot c(x,:)_{j_{0},i_{0}}\cdot\diag(f(x)_{j_{0}}\circ v)$

where the first step is because of definition of $G_{2,1}$, the second step is due to Fact 4.3, the third step follows from Lemma 8.4, and the fourth step is because of Lemma 8.5.

where the first step is because of definition of $G_{2,2}$, the second step is due to Fact 4.3, the third step follows from Lemma 8.4, and the fourth step is because of Lemma 8.5.

where the first step is because of definition of $G_{2,3}$, the second step is due to Fact 4.3, the third step follows from Lemma 8.4 and Lemma 8.5.

Combining all the above equations finish the proof. ∎

In this section, we introduce our calculation of Lipschitz for $-2\gamma_{j_{0}}(x)\cdot(f(x)_{j_{0}}\circ v)f(x)_{j_{0}}^{\top}$.

Let $G_{3}(x)=-2\gamma_{j_{0}}(x)\cdot(f(x)_{j_{0}}\circ v)f(x)_{j_{0}}^{\top}$.

Let $R_{0}$ be defined in Definition 8.6.

$\|A_{1}\|,\|A_{2}\|,\|A_{3}\|\leq R$, $\|\A_{j_{0}}\|\leq R$, $\|x\|_{2}\leq R$,$|b_{j_{0},i_{0}}|\leq R$, $\|v\|_{2}\leq R^{2}$

where the first step is based on Fact 4.3 and the second step is due to Lemma 8.4 and Lemma 8.5.

In this section, we introduce our calculation of Lipschitz for $-c(x,:)_{j_{0},i_{0}}\cdot(f(x)_{j_{0}}\circ v)f(x)_{j_{0}}^{\top}$.

$\|A_{1}\|,\|A_{2}\|,\|A_{3}\|\leq R$, $\|\A_{j_{0}}\|\leq R$, $\|x\|_{2}\leq R$,$|b_{j_{0},i_{0}}|\leq R$, $\|v\|_{2}\leq R^{2}$

Let $G_{4}(x)=-c(x,:)_{j_{0},i_{0}}\cdot(f(x)_{j_{0}}\circ v)f(x)_{j_{0}}^{\top}$

In this section, we introduce our calculation of Lipschitz for $-2\gamma_{j_{0}}(x)\cdot f(x)_{j_{0}}(f(x)_{j_{0}}\circ v)^{\top}$.

$\|A_{1}\|,\|A_{2}\|,\|A_{3}\|\leq R$, $\|\A_{j_{0}}\|\leq R$, $\|x\|_{2}\leq R$,$|b_{j_{0},i_{0}}|\leq R$, $\|v\|_{2}\leq R^{2}$

Let $G_{5}(x)=-2\gamma_{j_{0}}(x)\cdot f(x)_{j_{0}}(f(x)_{j_{0}}\circ v)^{\top}$

This proof is similar to the proof of Lemma 8.9, so we omit it here. ∎

In this section, we introduce our calculation of Lipschitz for $-c(x,:)_{j_{0},i_{0}}\cdot f(x)_{j_{0}}(f(x)_{j_{0}}\circ v)^{\top}$.

$\|A_{1}\|,\|A_{2}\|,\|A_{3}\|\leq R$, $\|\A_{j_{0}}\|\leq R$, $\|x\|_{2}\leq R$,$|b_{j_{0},i_{0}}|\leq R$, $\|v\|_{2}\leq R^{2}$

Let $G_{6}(x)=-c(x,:)_{j_{0},i_{0}}\cdot f(x)_{j_{0}}(f(x)_{j_{0}}\circ v)^{\top}$

This proof is similar to the proof of Lemma 8.10, so we omit it here. ∎

In this section, we introduce our calculation of Lipschitz for $2\gamma_{j_{0}}(x)c(x,:)_{j_{0},i_{0}}\cdot f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$.

$\|A_{1}\|,\|A_{2}\|,\|A_{3}\|\leq R$, $\|\A_{j_{0}}\|\leq R$, $\|x\|_{2}\leq R$,$|b_{j_{0},i_{0}}|\leq R$, $\|v\|_{2}\leq R^{2}$

Let $G_{7}(x)=2\gamma_{j_{0}}(x)c(x,:)_{j_{0},i_{0}}\cdot f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$

where the first step is due to the definition of $G_{7,1}$, the second step is because of Fact 4.3, the third step is based on Part 4 of Lemma 8.5 and Fact 4.3, and the last step comes from Part 4 and Part 6 of Lemma 8.4.

In this section, we introduce our calculation of Lipschitz for $\gamma_{j_{0}}(x)^{2}\cdot f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$.

$\|A_{1}\|,\|A_{2}\|,\|A_{3}\|\leq R$, $\|\A_{j_{0}}\|\leq R$, $\|x\|_{2}\leq R$,$|b_{j_{0},i_{0}}|\leq R$, $\|v\|_{2}\leq R^{2}$

Let $G_{8,1}=\gamma_{j_{0}}(x)^{2}\cdot f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$

In this section, we introduce our calculation of Lipschitz for $(f(x)_{j_{0}}\circ v)\cdot(f(x)_{j_{0}}\circ v)^{\top}$.

$\|A_{1}\|,\|A_{2}\|,\|A_{3}\|\leq R$, $\|\A_{j_{0}}\|\leq R$, $\|x\|_{2}\leq R$,$|b_{j_{0},i_{0}}|\leq R$, $\|v\|_{2}\leq R^{2}$

Let $G_{9}(x)=(f(x)_{j_{0}}\circ v)\cdot(f(x)_{j_{0}}\circ v)^{\top}$

Hessian for XX Is PSD

In Section 9.1, we present the main result of PSD bound for Hessian. In Section 9.2, we show the PSD bound for $B(x)$. In this section, our focus will be on establishing the PSD bound for $H_{x,x}$. Throughout this section, we will use the symbol $H$ to represent $H_{x,x}$ for the sake of simplicity.

In this section, we introduce the main result of the PSD bound for Hessian.

Let $\max_{j_{0}\in[n]}\|\A_{j_{0}}\|\leq R$

Let $\sigma_{\min}$ be the smallest singular value. We define $\sigma_{\min}(\A_{\min}):=\min_{j_{0}\in[n]}\sigma_{\min}(\A_{j_{0}})$.

Let $H=\sum_{j_{0}=1}^{n}\sum_{i_{0}=1}^{d}H_{j_{0},i_{0}}$

Let $H_{\reg}=\sum_{j_{0}=1}^{n}\sum_{i_{0}=1}^{d}H_{\reg,j_{0},i_{0}}$

Let $C_{0}:=30R^{8}$ (be a local parameter in this lemma)

Let $l>0$ (denote the strongly convex parameter for hessian)

Part 1. For each $j_{0}\in[n]$, for each $i_{0}\in[d]$

Part 2. For each $j_{0}\in[n]$, for each $i_{0}\in[d]$

Part 3. For each $j_{0}\in[n]$, $i_{0}\in[d]$, if $\min_{j_{1}\in[n]}w_{j_{1},j_{1}}\geq\frac{l}{\sigma_{\min}(\A_{j_{0}})^{2}}+C_{0}$, then we have

Part 4. For each $j_{0}\in[n]$, $i_{0}\in[d]$, if $\min_{j_{1}\in[n]}w_{j_{1},j_{1}}\geq\frac{l}{\sigma_{\min}(\A_{j_{0}})^{2}}+100\cdot C_{0}$, then we have

Part 5. For each $j_{0}\in[n]$, $i_{0}\in[d]$, if $\min_{j_{1}\in[n]}w_{j_{1},j_{1}}\geq\frac{l}{nd\sigma_{\min}(\A_{\min})^{2}}+C_{0}$, then we have

Part 6. For each $j_{0}\in[n]$, $i_{0}\in[d]$, if $\min_{j_{1}\in[n]}w_{j_{1},j_{1}}\geq\frac{l}{nd\sigma_{\min}(\A_{\min})^{2}}+100\cdot C_{0}$, then we have

where the first step follows from the $H_{j_{0},i_{0}}=\A_{j_{0}}^{\top}B_{j_{0},i_{0}}(x)\A_{j_{0}}$, the second step follows from Fact 4.3, the third step follows from $\max_{j_{0}\in[n]}\|\A_{j_{0}}\|\leq R$, and the last step follow from Part 1.

Proof of Part 5 and Part 6. It is because we can write $H$ as summation of $nd$ terms $H_{j_{0},i_{0}}$ for all $j_{0}\in[d]$, $i_{0}\in[d]$. ∎

2 PSD Bound

In this section, we analyze the PSD bound for each of the $B_{\rank}$ and $B_{\diag}$.

$B_{\diag}^{1}:=(1-\gamma_{j_{0}}(x))\cdot c(x,:)_{j_{0},i_{0}}\cdot\diag(f(x)_{j_{0}}\circ v)$

$B_{\rank}^{1}:=-(2\gamma_{j_{0}}(x)+c(x,:)_{j_{0},i_{0}})\cdot((f(x)_{j_{0}}\circ v)f(x)_{j_{0}}^{\top}+f(x)_{j_{0}}(f(x)_{j_{0}}\circ v)^{\top})$

$B_{\rank}^{2}:=(2\gamma_{j_{0}}(x)c(x,:)_{j_{0},i_{0}}+\gamma_{j_{0}}(x)^{2})\cdot f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$

$B_{\rank}^{3}:=(f(x)_{j_{0}}\circ v)\cdot(f(x)_{j_{0}}\circ v)^{\top}$

where the first step follows from the definition of $B_{\diag}^{1}$, the second step follows from Fact 4.4, and the last step follows from Lemma 8.4, $|\gamma(x)_{j_{0}}|\leq R^{2},~|c(x,:)_{j_{0},i_{0}}|\leq 2R^{2}$, and $\|v\|_{2}\leq R^{2}$.

where the first step follows from the definition of $B_{\rank}^{1}$, the second step follows from Fact 4.4, the third step follows from $|\gamma(x)_{j_{0}}|\leq R^{2},~|c(x,:)_{j_{0},i_{0}}|\leq 2R^{2}$ and Fact 4.4, the fourth step follows from Fact 4.1, and last step follows from Lemma 8.4 and $\|v\|_{2}\leq R^{2}$.

where the first step follows from definition of $B_{\rank}^{2}$, the second step follows from Fact 4.4, and the last step follows from $|\gamma(x)_{j_{0}}|\leq R^{2},~|c(x,:)_{j_{0},i_{0}}|\leq 2R^{2}$ and Lemma 8.4.

where the first step follows from definition of $B_{\rank}^{3}$, the second step follows from Fact 4.4, the third step follows from Fact 4.1, and the last step follows from $\|v\|_{2}\leq R^{2}$ and Lemma 8.4.

Hessian for YY

In Section 10.1, we present the hessian property with respect to $Y$. In Section 10.2, we compute the Hessian matrix with respect to $Y$ for one $j_{0},i_{0}$.

In this section, we analyze the Hessian properties.

Let $B(x)=\sum_{j_{0}=1}^{n}B_{j_{0}}(x)$

Part 3. If $\min_{j_{1}\in[n]}w_{j_{1},j_{1}}^{2}\geq\frac{l}{\sigma_{\min}(A_{3})^{2}}$

Part 4. If $\min_{j_{1}\in[n]}w_{j_{1},j_{1}}^{2}\geq\frac{l}{\sigma_{\min}(A_{3})^{2}}+100n$

Part 5. Lipschitz, Due to $H(y)$ is independent of $y$, then

For hessian closed-form, we can obtain them from Lemma 10.2.

The proofs are straightforward, so we omit the details here. ∎

2 Hessian for One j0,i0j_{0},i_{0}

In this section, we analyze the Hessian for the matrix $Y$ with one $j_{0},i_{0}$.

We define a temporary notation here $v:=f(x)_{j_{0}}$ (for simplicity we drop the index $j_{0}$ in the statement. Note that $v$ could have different meaning in other sections.)

Let $f(x)_{j_{0}}$ be defined as Definition 4.10.

Let $c(x,:)_{j_{0},i_{0}}$ be defined as Definition 4.12.

Let $h(y)_{i_{0}}$ be defined as Definition 4.11.

Let $L_{j_{0},i_{0}}$ be defined as Definition 4.10.

Part 1. For $i_{1}=i_{2}$, the diagonal case

Part 2. For $i_{1}\neq i_{2}$, the off-diagonal case

where the first step follows from simple algebra, the second step follows from Lemma 5.2, the third step follows from Lemma 5.2, and the last step follows from Fact 4.1.

where the first step follows from simple algebra, the second step follows from Lemma 5.2, the third step follows from Lemma 5.2, and the last step follows from Fact 4.1.

It follows by combining above two parts directly. ∎

Hessian for XX and YY

In Section 11.1, we compute the Hessian matrix with respect to both $X$ and $Y$. In Section 11.2, we present several helpful lemmas for the following proof. In Section 11.2, we create $B(x)$ for the further analysis.

In this section, we compute the Hessian matrix for $X$ and $Y$.

Let $f(x)_{j_{0}}$ be defined as Definition 4.10.

Let $c(x,y)_{j_{0},i_{0}}$ be defined as Definition 4.12.

Let $h(y)_{i_{0}}$ be defined as Definition 4.11.

Let $L_{j_{0},i_{0}}$ be defined as Definition 4.7.

where the first step is due to Part 6 of Lemma 5.1, the second step comes from the product rule of derivative, the third step is based on Lemma 10.2, and the last step follows from simple algebra.

2 A Helpful Lemma

In this section, we provide a helpful Lemma.

Let $f(x)_{j_{0}}$ be defined in Definition 4.10.

Let $c(x,y)_{j_{0},i_{0}}$ be defined as Definition 4.12.

Let $h(y)_{i_{0}}$ be defined as Definition 4.11.

Let $L_{j_{0},i_{0}}$ be defined as Definition 4.7.

where the first step follows from Fact 4.1, and the second step follows from Fact 4.1.

where the first step follows from Fact 4.1.

where the first, second, and last step follows from Fact 4.1.

where the first step follows from Fact 4.1.

3 Creating B⁡(x,y)B(x,y)

In this section, we give a formal definition of $B(x,y)$.

$B_{\rank}^{1}(x,y)=(f(x)_{j_{0}}\circ h(y)_{i_{0}})f(x)_{j_{0}}^{\top}$

$B_{\rank}^{2}(x,y)=-\langle f(x)_{j_{0}},h(y)_{i_{0}}\rangle f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$

$B_{\diag}^{1}(x,y)=-c(x,y)_{j_{0},i_{0}}\diag(f(x)_{j_{0}})$

$B_{\rank}^{3}(x,y)=c(x,y)_{j_{0},i_{0}}f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$

Let $B(x,y)$ be defined as Definition 11.3.

where the first step follows from combining Lemma 11.1 and Lemma 11.2.

where the first step follows from combining Lemma 11.1 and Lemma 11.2.

Lipschitz for Hessian of x,yx,y

In Section 12.1, we present the main results of the Lipschitz property of $H_{x,y}$. In Section 12.2, we summarize the results from the following steps 1-4. In Section 12.3, we compute the upper bound of basic functions for the following proof. In Section 12.4, we compute the Lipschitz Property of basic functions for the following proof. In Section 12.5, we analyze the first step of Lipschitz function $(f(x)_{j_{0}}\circ h(y)_{i_{0}})f(x)_{j_{0}}^{\top}$. In Section 12.6, we analyze the second step of Lipschitz function $-\langle f(x)_{j_{0}},h(y)_{i_{0}}\rangle f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$. In Section 12.7, we analyze the third step of Lipschitz function $-c(x,y)_{j_{0},i_{0}}\diag(f(x)_{j_{0}})$. In Section 12.8, we analyze the fourth step of Lipschitz function $c(x,y)_{j_{0},i_{0}}f(x)_{j_{0}}f(x)_{j_{0}}^{\top}$. In Section 12.9, we compute the PSD upper bound for the Hessian matrix. In Section 12.10, we summarize PSD upper bound of $G(x,y)$.