Solving Regularized Exp, Cosh and Sinh Regression Problems

Introduction

State-of-the-art language models like Transformer , BERT , GPT-3 , PaLM , and OPT exhibit greater proficiency in natural language processing when compared to smaller models or traditional techniques. These models have the capacity to understand and generate intricate language, proving beneficial in various applications such as language translation, sentiment analysis, and question answering. LLMs can be customized for multiple purposes without necessitating their reconstruction from scratch. An instance of this is ChatGPT, an OpenAI-developed chat software that employs GPT-3’s full potential. The latest iteration, GPT-4 , has the potential to surpass GPT-3 in its impressive capabilities, including text generation, question answering, and language translation. This development could lead to significant implications in the field of NLP, with new applications potentially emerging in areas such as virtual assistants, chatbots, and automatic content creation. However, even though deep learning has a swift incline in popularity, we hold the belief that there exist discrepancies in our comprehension of the concept of attention and the reasoning behind its effectiveness.

The primary technical foundation behind LLMs is the attention matrix . An attention matrix is a matrix that features rows and columns aligning with individual words or ”tokens” and their relationships within a given text. Its purpose is to measure the critical nature of each token in a sequence in relation to the intended output. The attention matrix is learned during training. These parameters are optimized to maximize the model’s accuracy in predicting the desired output. Through the attention mechanism, each input token is evaluated based on its importance or relevance to the desired output. This is achieved by weighing the token score, which is based on a similarity function comparing the current output state and input states.

More formally, the attention matrix can be expressed by considering two matrices, $Q$ and $K$, containing query and key tokens, respectively. Both $Q$ and $K$ hold values in the $n\times d$ dimensional space. The attention matrix can be denoted by the square matrix $A$ which is of size $n\times n$. This matrix establishes a relationship between the input tokens in the sequence where every entry represents the attention weight or score between a particular input token (query token $Q$) and an output token (key token $K$). It is essential to mention that diagonal entries of this matrix display self-attention scores, signifying the importance of each token with respect to itself. A majority of the methods used for effective computation of attention matrices are divided into two primary categories based on their approach. One approach involves leveraging sparsity, as seen in Reformer , while the other involves utilizing the low-rank attributes of the attention matrices, as observed in Linformer and Performer .

During training, our primary goal is to tackle the issue of multiple attention regression by utilizing the exponential function and its corresponding equation: $\min_{X}\|D^{-1}\exp(AX)-B\|_{2}$, where $D^{-1}$ denotes the normalization factor. However, upon further investigation, it has been brought to our attention that the single regression scenario has not been thoroughly studied. As a result, this study is centered on the situation of single regression.

In our setting, the presence of $D$ is unnecessary due to the fact that $Ax$ is a column vector (but not a matrix). Thus, we have opted to address the optimization problem with regards to $\min_{x}\|\exp(Ax)-b\|_{2}$. It is important to note that our approach is not exclusive to the exponential function, and can also be extended to other hyperbolic functions such as $\cosh$ and $\sinh$.$\cosh(x):=\frac{1}{2}(e^{x}+e^{-x})$ and $\sinh(x):=\frac{1}{2}(e^{x}-e^{-x})$

Let $f$ be any of functions $\exp,\cosh$ and $\sinh$. Let $g$ denote the gradient of function $f$.

Let $x^{*}$ denote the optimal solution of

that $g(x^{*})={\bf 0}_{d}$ and $\|x^{*}\|_{2}\leq R$.

Let $\|A\|\leq R,\|b\|_{2}\leq R$. Let $w_{i}^{2}>0.5b_{i}^{2}+1+l/\sigma_{\min}(A)^{2}$ for all $i\in[n]$.

Let $x_{0}$ denote an initial point such that $M\|x_{0}-x^{*}\|_{2}\leq 0.1l$.

For any accuracy parameter $\epsilon\in(0,0.1)$ and failure probability $\delta\in(0,0.1)$. There is a randomized algorithm (Algorithm 1) that runs $\log(\|x_{0}-x^{*}\|_{2}/\epsilon)$ iterations and spend

holds with probability at least $1-\delta$.

2 Related Work

Input sparsity is a term used to describe datasets that have a majority of elements that are either zero or negligible. Utilizing algorithms optimized for sparse input data enables faster processing times than those utilized in dense data algorithms. This is because these algorithms can solely focus on non-zero elements, thereby minimizing computational and memory usage. Sparse algorithms’ time complexity depends only on the number of non-zero elements rather than the number of total elements. Input sparsity algorithms are highly applicable within fields such as solving John Ellipsoid , discrepancy minimization , low-rank approximation , subspace embeddings , column subset selection and least squares regression .

Algorithmic Regularization

The standard exponential regression is non-convex. We study the regularization version of the exponential regression problem which is a convex problem. In the context of deep learning, the non-convexity of the objective function necessitates the use of regularization techniques. Due to the possibility of the objective function generating multiple global minima that are widely scattered and vary significantly in their generalization capabilities, this becomes essential. Algorithmic regularization can be observed in various machine learning applications such as binary classification , matrix factorization , convolutional neural networks , generative adversarial networks , contrastive learning and mixture of experts . There are numerous factors that can induce algorithmic regularization. introduce how learning rate and batch size help regularize the training process. explains that while a small initial learning rate may result in prompt training and better performance initially, a larger learning rate tends to yield improved generalization shortly after the annealing of the learning rate. The regularizer’s role in the GAN model is expounded in . In addition, has conducted a theoretical analysis of the regularization generated by momentum. Furthermore, the employment of an adaptive step-size optimizer, such as Adam optimizer, can also function as a form of regularization during the training process . Batch normalization is analyzed in a theoretical capacity in , which delves into its impact on regularization. A separate study conducted by explains how introducing dropout into the training process can prevent overfitting. In , they apply TensorSketch to the Kronecker product of multiple matrices efficiently without explicitly computing the tensor product and also apply the regularization to solve the Kronecker product regression.

Attention Theory

The topic of attention’s expressivity has been a focus of early theoretical works. In the case of self-attention blocks, interpret self-attention as a system of self-interacting particles and theoretically explain the attention. explain it from inductive biases and variable creation perspective. The role of attention in Transformers was studied by . In terms of optimization, examined the impact of adaptive approaches on attention models, while analyzed the dynamics of single-head attention to approximate Seq2Seq architecture’s learning process. For most LLMs, it generally suffices to conduct attention computations in an approximate manner during the inference process, provided that there are adequate assurances of accuracy. Research conducted by various sources such as has underscored this perspective. Due to that motivation, study the computation of the attention matrix from the hardness perspective and purpose faster algorithms.

Newton Method and Hessian Computation

Computing the Hessian or approximately computing the Hessian is a standard task in convex optimization. Many of the previous have work on this direction and use that improve several optimization problems such as linear programming , empirical risk minimization , cutting plane method , semi-definite programming , sum of squares , training over-parameterized neural network .

Roadmap.

We organize the following paper as follows. In Section 2 we provide some tools for basic algebra and the analysis of a regularization term $L_{\operatorname{reg}}$. In Section 3 we provide detailed analysis of the loss function based on $\exp(x)$ (denoted as $L_{\exp}$) and the loss function with a regularization term $L_{\exp,\operatorname{reg}}$. In Section 4 we provide detailed analysis of $L_{\cosh}$ and $L_{\cosh,\operatorname{reg}}$. In Section 5 we provide detailed analysis of $L_{\sinh}$ and $L_{\sinh,\operatorname{reg}}$. In Section 6 we provide an approximate version of newton method which use for solving convex optimization problem which is more efficient under certain assumptions.

Preliminary

In this section, we provide preliminaries to be used in our paper. In Section 2.1 we introduce notations we use. In Section 2.2 we provide some facts about approximate computations and exact computations. In Section 2.3, we provide some trivial facts regarding gradient and hessian. In Section 2.4, we computed the gradient and hessian of a regularization term $L_{\operatorname{reg}}$.

For a matrix $A$, we use $\sigma_{\max}(A)$ to denote the largest singular value of $A$. We use $\sigma_{\min}(A)$ to denote the smallest singular value of $A$.

We use ${\bf 1}_{n}$ to denote a length-$n$ vector where all the entries are ones.

We say $A\succeq B$ if $x^{\top}Ax\geq x^{\top}Bx$ for all vector $x$.

We define $\cosh(x)=\frac{1}{2}(\exp(x)+\exp(-x))$ and $\sinh(x)=\frac{1}{2}(\exp(x)-\exp(-x))$.

For any function $f$, we use $\widetilde{O}(f)$ to denote $f\cdot\operatorname{poly}(\log f)$.

2 Basic Algebras

We state some facts which can give exact computation.

$\exp(x)=\sum_{i=0}^{\infty}\frac{1}{i!}x^{i}$

$\cosh(x)=\sum_{i=0}^{\infty}\frac{1}{(2i)!}x^{2i}$

$\sinh(x)=\sum_{i=0}^{\infty}\frac{1}{(2i+1)!}x^{2i+1}$

We state some facts which can give a reasonable approximate computation.

Part 1. For any $x$ satisfy that $|x|\leq 0.1$, we have $|\exp(x)-1|\leq 2|x|$

Part 2. For any $x$ satisfy that $|x|\leq 0.1$, we have $|\cosh(x)-1|\leq x^{2}$

Part 3. For any $x$ satisfy that $|x|\leq 0.1$, we have $|\sinh(x)|\leq 2|x|$

Part 4. For any $x,y$ satisfy that $|x-y|\leq 0.1$, we have $|\exp(x)-\exp(y)|\leq\exp(x)\cdot 2|x-y|$

Part 5. For any $x,y$ satisfy that $|x-y|\leq 0.1$, we have $|\cosh(x)-\cosh(y)|\leq\cosh(x)\cdot 2|x-y|$

Part 6. For any $x,y$ satisfy that $|x-y|\leq 0.1$, we have $|\sinh(x)-\sinh(y)|\leq\cosh(x)\cdot 2|x-y|$

Most of the proofs are standard, we only provide proofs for some of them.

where the first step follows from the definition of $\cosh$, the second step follows from triangle inequality, the third step follows from simple algebra, the fourth step follows from the fact that $|\exp(x)-1|\leq 2x$ for all $x\in[0,0.1]$ and the last step follows from the definition of $\cosh$.

where the first step follows from the definition of $\sinh$, the second step follows from triangle inequality, the third step follows from simple algebra, the fourth step follows from the fact that $|\exp(x)-1|\leq 2x$ for all $x\in[0,0.1]$ and the last step follows from the definition of $\cosh$. ∎

$a\circ b=b\circ a=\operatorname{diag}(a)\cdot b=\operatorname{diag}(b)\cdot a=\operatorname{diag}(a)\cdot\operatorname{diag}(b)\cdot{\bf 1}_{n}$

$a^{\top}(b\circ c)=a^{\top}\operatorname{diag}(b)c$

$a^{\top}(b\circ c)=b^{\top}(a\circ c)=c^{\top}(a\circ b)$

$a^{\top}\operatorname{diag}(b)c=b^{\top}\operatorname{diag}(a)c=a^{\top}\operatorname{diag}(c)b$

$\operatorname{diag}(a\circ b)=\operatorname{diag}(a)\operatorname{diag}(b)$

$\operatorname{diag}(a)+\operatorname{diag}(b)=\operatorname{diag}(a+b)$

Part 1. $\|a\circ b\|_{2}\leq\|a\|_{\infty}\cdot\|b\|_{2}$

Part 2. $\|a\|_{\infty}\leq\|a\|_{2}\leq\sqrt{n}\cdot\|a\|_{\infty}$

Part 3. $\|\exp(a)\|_{\infty}\leq\exp(\|a\|_{2})$

Part 4. $\|\cosh(a)\|_{\infty}\leq\cosh(\|a\|_{2})\leq\exp(\|a\|_{2})$

Part 5. $\|\sinh(a)\|_{\infty}\leq\sinh(\|a\|_{2})\leq\cosh(\|a\|_{2})\leq\exp(\|a\|_{2})$

Part 6. $\cosh(a)\circ\cosh(a)-\sinh(a)\circ\sinh(a)={\bf 1}_{n}$

Part 7. For any $\|a-b\|_{\infty}\leq 0.01$, we have $\|\exp(a)-\exp(b)\|_{2}\leq\|\exp(a)\|_{2}\cdot 2\|a-b\|_{\infty}$

Part 8. For any $\|a-b\|_{\infty}\leq 0.01$, we have $\|\cosh(a)-\cosh(b)\|_{2}\leq\|\cosh(a)\|_{2}\cdot 2\|a-b\|_{\infty}$

Part 9. For any $\|a-b\|_{\infty}\leq 0.01$, we have $\|\sinh(a)-\sinh(b)\|_{2}\leq\|\cosh(a)\|_{2}\cdot 2\|a-b\|_{\infty}$

Most of the proofs are standard, we only provide proofs for some of them.

where the first step follows from Part 5 in Fact 2.2 and the last step follows from the definition of norm. By summing up the square of both sides, we have

where the first step follows from Part 6 in Fact 2.2 and the last step follows from the definition of norm. By summing up the square of both sides, we have

If $A\preceq\alpha\cdot B$, then $\|A\|\leq\alpha\cdot\|B\|$

$-\epsilon A\preceq B-A\preceq\epsilon A$

$-\epsilon\preceq A^{-1/2}(B-A)A^{-1/2}\preceq\epsilon$

$(1+\epsilon)^{-1}B\preceq A\preceq(1-\epsilon)^{-1}A$

$(1-2\epsilon)B\preceq A\preceq(1+2\epsilon)B$

$\|B^{-1/2}(B-A)B^{-1/2}\|\leq 2\epsilon$

3 Standard Gradient and Hessian Computation

The equation takes derivative of the vector $x$ by each entry $x_{i}$ of itself and trivially gets the result of $A_{*,i}$.

where the first step is an expansion of the Hessian, the second step follows from the differential chain rule, and the last step is due to the constant entries of the matrix $A_{*,i}$.

4 Regularization term

where the first step follows from chain rule.

where the first step follows from the expansion of Hessian, the second step follows from by applying the arguments in Part 1, the third step follows from simple algebra. ∎

where the first step follows from simple algebra, the second step follows from the definition of $\|x\|_{2}$, the third step follows from simple algebra, the fourth step follows from the definition of $\|x\|_{2}$, the fifth step follows from definition of $\sigma_{\min}(A)$ , the last step follows from simple algebra . ∎

Exponential Regression

In this section, we provide detailed analysis of $L_{\exp}$. In Section 3.1 we define the loss function $L_{\exp}$ based on $\exp(x)$. In Section 3.2 we compute the gradient of $L_{\exp}$ by detail. In Section 3.3 we compute the hessian of $L_{\exp}$ by detail. In Section 3.4, we summarize the result of Section 3.2 and Section 3.3 and aquire the gradient $\nabla L_{\exp}$ and hessian $\nabla^{2}L_{\exp}$ for $L_{\exp}$. In Section 3.5 we define $L_{\exp,\operatorname{reg}}$ by adding the regularization term $L_{\operatorname{reg}}$ in Section 2.4 to $L_{\exp}$ and compute the gradient $\nabla L_{\exp,\operatorname{reg}}$ and hessian $\nabla^{2}L_{\exp,\operatorname{reg}}$ of $L_{\exp,\operatorname{reg}}$. In Section 3.6 we proved that $\nabla^{2}L_{\exp,\operatorname{reg}}\succ 0$ and thus showed that $L_{\exp,\operatorname{reg}}$ is convex. In Section 3.7 we provide the upper bound for $\|\nabla^{2}L_{\exp,\operatorname{reg}}(x)-\nabla^{2}L_{\exp,\operatorname{reg}}(y)\|$ and thus proved $\nabla^{2}L_{\exp,\operatorname{reg}}$ is lipschitz.

2 Gradient

where the first and second step follow from the differential chain rule.

where the first step follows from the property of the gradient, the second step follows from simple algebra, and the last step directly follows from Lemma 2.7.

By substitute $x_{i}$ into $t$ of Part 3, we get

where this step follows from the result of Part 4 directly. ∎

3 Hessian

where the first step is an expansion of the Hessian, the second step follows from the differential chain rule, the third step extracts the matrix $A_{*,i}$ with constant entries out of the derivative, and the last step also follows from the chain rule.

where the first step is an expansion of the Hessian, the second step follows from Part 3 of Lemma 3.2, the third step follows from Part 3 of Lemma 3.2.

where the first step is an expansion of the Hessian, the second step follows from Part 4 of Lemma 3.2, the third step follows from differential chain rule and Part 1 of Lemma 3.2, the last step follows from Fact 2.3.

where the first step is an expansion of the Hessian, the second step follows from Part 4 of Lemma 3.2, the third step follows from differential chain rule and Part 1 of Lemma 3.2, the last step follows from Fact 2.3.

4 Gradient and Hessian of the Loss function for Exp Function

Part 1. We run Lemma 3.2 and Fact 2.3 directly.

Part 2. It follows from Part 3 and 4 of Lemma 3.3. ∎

5 Loss Function with a Regularization Term

Let $L_{\exp,\operatorname{reg}}$ be defined as Definition 3.5, then we have

Proof of Part 1. We run Lemma 3.4 and Lemma 2.8 directly.

Proof of Part 2. We run Lemma 3.4 and Lemma 2.8 directly.

6 Hessian is Positive Definite

$w_{i}^{2}>0.5b_{i}^{2}+l/\sigma_{\min}(A)^{2}$ for all $i\in[n]$

where the first step follows from simple algebra, the second step follows from replacing $\exp(Ax)$ with $z=\exp(Ax)$, the third step follows from $w_{i}^{2}>0.5b_{i}^{2}+l/\sigma_{\min}(A)^{2}$, the fourth step follows from simple algebra, the fifth step follows from $x^{2}\geq 0,\forall x$.

Since we know $D_{i,i}>l/\sigma_{\min}(A)^{2}$ for all $i\in[n]$ and Lemma 2.9, we have

Thus, Hessian is positive definite forever and thus the function is convex.

7 Hessian is Lipschitz

where the first step follows from $H(x)=\nabla^{2}L$ and simple algebra, the second step follows from Fact 2.5, the third step follows from simple algebra, the fourth step follows from simple algebra, the last step follows from Fact 2.4.

For the second term in Eq. (3.7), we have

where the first step follows from Fact 2.4 , the second step follows from Fact 2.4, the third step follows from $\|Ax\|_{2}\leq R^{2},\|Ay\|_{2}\leq R^{2}$, the fourth step follows from $\|b\|_{\infty}\leq\|b\|_{2}\leq R$, the last step follows from $R\geq 2$.

where the first step follows from $\|A(y-x)\|_{\infty}<0.01$ and Fact 2.4, the second step follows from Fact 2.4, the third step follows from Fact 2.4 , the fourth step follows from Fact 2.4, the fifth step follows from Fact 2.5 and $\|Ax\|_{2}\leq R^{2}$, the last step follows from $\|A\|\leq R$.

where the first step follows from by applying Eq. (2), Eq. (3.7), and Eq. (3.7), the second step follows from simple algebra, the third step follows from $R\geq 2$, the last step follows from simple algebra.

Cosh Regression

In this section, we provide detailed analysis of $L_{\cosh}$. In Section 4.1 we define the loss function $L_{\cosh}$ based on $\cosh(x)$. In Section 4.2 we compute the gradient of $L_{\cosh}$ by detail. In Section 4.3 we compute the hessian of $L_{\cosh}$ by detail. In Section 4.4, we summarize the result of Section 4.2 and Section 4.3 and aquire the gradient $\nabla L_{\cosh}$ and hessian $\nabla^{2}L_{\cosh}$ for $L_{\cosh}$. In Section 4.5 we define $L_{\cosh,\operatorname{reg}}$ by adding the regularization term $L_{\operatorname{reg}}$ in Section 2.4 to $L_{\cosh}$ and compute the gradient $\nabla L_{\cosh,\operatorname{reg}}$ and hessian $\nabla^{2}L_{\cosh,\operatorname{reg}}$ of $L_{\cosh,\operatorname{reg}}$. In Section 4.6 we proved that $\nabla^{2}L_{\cosh,\operatorname{reg}}\succ 0$ and thus showed that $L_{\cosh,\operatorname{reg}}$ is convex. In Section 4.7 we provide the upper bound for $\|\nabla^{2}L_{\cosh,\operatorname{reg}}(x)-\nabla^{2}L_{\cosh,\operatorname{reg}}(y)\|$ and thus proved $\nabla^{2}L_{\cosh,\operatorname{reg}}$ is lipschitz.

2 Gradient

where the first and second step follow from the differential chain rule.

where the first step follows from the property of the gradient, the second step follows from simple algebra, and the last step directly follows from Lemma 2.7.

By substitute $x_{i}$ into $t$ of Part 3, we get

where the first step follows from the result of Part 2, the second step follows from the result of Lemma 2.7, the last step follows from Fact 2.3.

this follows from the result of Part 4 directly. ∎

3 Hessian

where the first step is an expansion of the Hessian, the second step follows from the differential chain rule, the third step extracts the matrix $A_{*,i}$ with constant entries out of the derivative, and the last step also follows from the chain rule.

where the first step is an expansion of the Hessian, the second and third steps follow from the differential chain rule.

Here in the proof, for simplicity, we let use $\cosh^{2}(Ax)=\cosh(Ax)\circ\cosh(Ax)$.

where the first step is an expansion of the Hessian, the second step follows from Part 4 of Lemma 4.2, the third step follows from the product rule of calculus, the fourth step follows from Fact 2.3, the last step follows from Fact 2.3.

where the first step is an expansion of the Hessian, the second step follows from Part 4 of Lemma 4.2, the third step follows from the product rule of calculus, the fourth step follows from Fact 2.3, the last step follows from Fact 2.3.

4 Gradient and Hessian of the Loss function for Cosh Function

Part 1. We run Lemma 4.2 and Fact 2.3 directly.

Part 2. It follows from Part 5 of Lemma 4.3. ∎

5 Loss Function with a Regularization Term

Let $L$ be defined as Definition 4.5, then we have

Proof of Part 1. We run Lemma 3.4 and Lemma 2.8 directly.

Proof of Part 2. We run Lemma 3.4 and Lemma 2.8 directly.

6 Hessian is Positive Definite

If $w_{i}^{2}>0.5b_{i}^{2}+l/\sigma_{\min}(A)^{2}+1$ for all $i\in[n]$, then

where the first step follows from simple algebra, the second step follows from replacing $\cosh(Ax)$ with $z=\cosh(Ax)$ and $\sinh^{2}()=\cosh^{2}()-1$ (Fact 2.1), the third step follows from $w_{i}^{2}>0.5b_{i}^{2}+l/\sigma_{\min}(A)^{2}+1$, the fourth step follows from simple algebra, the fifth step follows from $x^{2}\geq 0,\forall x$.

Since we know $D_{i,i}>0$ for all $i\in[n]$ and Lemma 2.9, we have

Thus, Hessian is positive definite forever and thus the function is convex. ∎

7 Hessian is Lipschitz

where the first step follows from $H(x)=\nabla^{2}L$ and simple algebra, the second step follows from Fact 2.5, the third step follows from simple algebra, the fourth step follows from simple algebra, the last step follows from Fact 2.4.

For the second term in Eq. (4.7), we have

where the first step follows from Fact 2.4 , the second step follows from Fact 2.4 , the third step follows from $\|Ax\|_{2}\leq R^{2}$, $\|Ay\|_{2}\leq R^{2}$, the fourth step follows from $\|b\|_{\infty}\leq R$ and the last step follows from $R\geq 2$.

where the first step follows from $\|A(y-x)\|_{\infty}<0.01$ and Fact 2.4, the second step follows from Fact 2.4, the third step follows from Fact 2.4, the fourth step follows from $\|Ax\|_{2}\leq R^{2}$, the fifth step follows from Fact 2.5, the last step follows from $\|A\|\leq R$.

where the first step follows from by applying Eq. (6), Eq. (4.7), and Eq. (4.7), the second step follows from simple algebra, the third step follows from $R\geq 2$, the last step follows from simple algebra.

Sinh Regression

In this section, we provide detailed analysis of $L_{\sinh}$. In Section 5.1 we define the loss function $L_{\sinh}$ based on $\sinh(x)$. In Section 5.2 we compute the gradient of $L_{\sinh}$ by detail. In Section 5.3 we compute the hessian of $L_{\sinh}$ by detail. In Section 5.4, we summarize the result of Section 5.2 and Section 5.3 and aquire the gradient $\nabla L_{\sinh}$ and hessian $\nabla^{2}L_{\sinh}$ for $L_{\sinh}$. In Section 5.5 we define $L_{\sinh,\operatorname{reg}}$ by adding the regularization term $L_{\operatorname{reg}}$ in Section 2.4 to $L_{\sinh}$ and compute the gradient $\nabla L_{\sinh,\operatorname{reg}}$ and hessian $\nabla^{2}L_{\sinh,\operatorname{reg}}$ of $L_{\sinh,\operatorname{reg}}$. In Section 5.6 we proved that $\nabla^{2}L_{\sinh,\operatorname{reg}}\succ 0$ and thus showed that $L_{\sinh,\operatorname{reg}}$ is convex. In Section 5.7 we provide the upper bound for $\|\nabla^{2}L_{\sinh,\operatorname{reg}}(x)-\nabla^{2}L_{\sinh,\operatorname{reg}}(y)\|$ and thus proved $\nabla^{2}L_{\sinh,\operatorname{reg}}$ is lipschitz.

2 Gradient

where the first and second step follow from the differential chain rule.

where the first step follows from the property of the gradient, the second step follows from the differential chain rule, and the last step directly follows from Lemma 2.7.

By substitute $x_{i}$ into $t$ of Part 3, we get

where the first step follows from the result of Part 2 and the second step follows from the result of Lemma 2.7, the last step follows from Fact 2.3.

where this step follows from the result of Part 4 directly. ∎

3 Hessian

where the first step is an expansion of the Hessian, the second step follows from the differential chain rule, the third step extracts the matrix $A_{*,i}$ with constant entries out of the derivative, and the last step also follows from the chain rule.

where the first step is an expansion of the Hessian, the second and third steps follow from the differential chain rule.

where the first step is an expansion of the Hessian, the second step follows from Part 4 of Lemma 5.2, the third step follows from the product rule of calculus, the fourth step follows from Fact 2.3, the last step follows from Fact 2.3.

where the first step is an expansion of the Hessian, the second step follows from Part 4 of Lemma 5.2, the third step follows from the product rule of calculus, the fourth step follows from Fact 2.3, the last step follows from Fact 2.3.

4 Gradient and Hessian of the Loss function for Sinh Function

Part 1. We run Lemma 5.2 and Fact 2.3 directly.

Part 2. It follows from Part 5 of Lemma 5.3. ∎

5 Loss Function with a Regularization Term

Let $L$ be defined as Definition 5.5, then we have

Proof of Part 1. We run Lemma 3.4 and Lemma 2.8 directly.

Proof of Part 2. We run Lemma 3.4 and Lemma 2.8 directly. ∎

6 Hessian is Positive Definite

Let $l>0$ denote a parameter. If $w_{i}^{2}>0.5b_{i}^{2}+l/\sigma_{\min}(A)^{2}-1$ for all $i\in[n]$, then

where the first step follows from simple algebra, the second step follows from replacing $\sinh(Ax)$ with $z=\sinh(Ax)$ and $\cosh^{2}()=\sinh^{2}()+1$ (Fact 2.1), the third step follows from $w_{i}^{2}>0.5b_{i}^{2}+1/\sigma_{\min}(A)^{2}-1$, the fourth step follows from simple algebra, the fifth step follows from $x^{2}\geq 0,\forall x$.

Since we know $D_{i,i}>l$ for all $i\in[n]$ and Lemma 2.9, we have

Thus, Hessian is positive definite forever and thus the function is convex. ∎

7 Hessian is Lipschitz

where the first step follows from $H(x)=\nabla^{2}L$ and simple algebra, the second step follows from Fact 2.5, the third step follows from simple algebra, the fourth step follows from simple algebra, the last step follows from Fact 2.4.

For the second term in Eq. (5.7), we have

where the first step follows from Fact 2.4 , the second step follows from Fact 2.4, the third step follows from Fact 2.4, the fourth step follows from $\|Ax\|_{2}\leq R^{2},\|Ay\|_{2}\leq R^{2}$, the fifth step follows from $\|b\|_{\infty}\leq R$, the last step follows from $R\geq 2$.

where the first step follows from $\|A(y-x)\|_{\infty}<0.01$ and Fact 2.4, the second step follows from Fact 2.4, the third step follows from Fact 2.4, the fourth step follows from $\|Ax\|_{2}\leq R^{2}$, the fifth step follows from Fact 2.5, the last step follows from $\|A\|\leq R$.

where the first step follows from by applying Eq. (10), Eq. (5.7), and Eq. (5.7), the second step follows from simple algebra, the third step follows from $R\geq 2$, the last step follows from simple algebra.

Newton Method

In this section, we provide an approximate version of the Newton method for solving convex optimization problems and provide a detailed analysis of such a method. In Section 6.1 we define some assumptions under which we can tackle the optimization problem efficiently. In Section 6.2 we state a simple lemma which is useful in Section 6.5. In Section 6.3 we provide an approximation variant for the update step of the newton method for convex optimization. In Section 6.4 we provide the upper bound of $\|H(x_{k})\|$. In Section 6.5 we provide the upper bound for $\|r_{k+1}\|$ and thus showed that our approximate update step is effective in solving the optimization problem. In Section 6.6 we provide a lemma that showed our update step is effective. In Section 6.7, we prove our main result.

Let us study the local convergence of the Newton method. Consider the problem

$\nabla^{2}f(x^{*})\succeq l\cdot I_{d}$.

Hessian is $M$-Lipschitz. Let $M>0$ denote a parameter that

Good Initialization Point. Let $r_{0}:=\|x_{0}-x_{*}\|_{2}$ such that

We define gradient and Hessian as follows

2 Connection between Gradient and Hessian

3 Approximation of Hessian and Update Rule

In many optimization applications, computing $\nabla^{2}f(x_{k})$ or $(\nabla^{2}f(x_{k}))^{-1}$ is quite expensive. Therefore, a natural motivation is to approximately formulate its Hessian or inverse of Hessian.

For any $H(x_{k})$, we define $\widetilde{H}(x_{k})$ to satisfy the following condition

To efficiently compute $\widetilde{H}(x_{k})$, we use a standard tool from the literature

4 Property of Hessian

Let $f$ be function that Hessian is $M$-Lipschitz (see Definition 6.1)

Suppose the optimal solution $x^{*}$ satisfy that $\|H(x_{*})\|\geq l$ (see Definition 6.1)

where the first step follows from Fact 2.5, the second step follows from $f$ is a $M$-bounded function, the third step follows from $\|H(x_{k})\|\geq l$. ∎

5 One Step Shrinking Lemma

Function $f$ follows from Definition 6.1.

where the first step follows from Definition 6.7, the second step follows from $g(x^{*})={\bf 0}_{d}$, the third step follows from Lemma 6.4, the forth step follows from $H^{-1}H=I$, the fifth step follows from simple algebra, the sixth step follows from simple algebra, the last step follows from rewrite the equation using $G_{k}$ below :

where the first step follows from the definition of $G_{k}$, the second step follows from simple algebra, the third step follows from simple algebra, the last step follows from Fact 2.5.

where the first step follows from Eq. (6.5) and by definition of $r_{k}$, the second step follows form $\|ab\|\leq\|a\|\|b\|,\forall a,b$, the third step follows from $r_{k}=\|x_{k}-x^{*}\|$, the last step follows from Eq. (6.5), Eq. (6.5), and Eq. (6.5).

6 Induction

$r_{i}\leq 0.4r_{i-1}$, for all $i\in[k]$

$M\cdot r_{i}\leq 0.1l$, for all $i\in[k]$

where the first step follows from Lemma 6.9.

7 Main Result

Let $f$ be any of functions $\exp,\cosh$ and $\sinh$.

Let $x^{*}$ denote the optimal solution of

that $g(x^{*})={\bf 0}_{d}$ and $\|x^{*}\|_{2}\leq R$.

Let $w_{i}^{2}\geq 0.5b_{i}^{2}+l$ for all $i\in[n]$. (If $f=\exp$, see Lemma 3.7)

Let $w_{i}^{2}\geq 0.5b_{i}^{2}+l/\sigma_{\min}(A)^{2}+1$ for all $i\in[n]$. (If $f=\cosh$, see Lemma 4.7)

Let $w_{i}^{2}\geq 0.5b_{i}^{2}+l/\sigma_{\min}(A)^{2}-1$ for all $i\in[n]$. (If $f=\sinh$, see Lemma 5.7)

Let $x_{0}$ denote an initial point such that $M\|x_{0}-x^{*}\|_{2}\leq 0.1l$.

For any accuracy parameter $\epsilon\in(0,0.1)$ and failure probability $\delta\in(0,0.1)$. There is a randomized algorithm (Algorithm 1) that runs $\log(\|x_{0}-x^{*}\|_{2}/\epsilon)$ iterations and spend

holds with probability at least $1-\delta$.

It follows from combining Lemma 3.7, Lemma 6.10, Lemma 6.6, and Lemma 6.9.

By choice of $T$, we get the desired bound. The failure probability is following from union bound over $T$ iterations.

It follows from combining Lemma 4.7, Lemma 6.10, Lemma 6.6, and Lemma 6.9.

It follows from combining Lemma 5.7, Lemma 6.10, Lemma 6.6, and Lemma 6.9.

References