## 2 Analysis of the Pure Random Orthogonal Search (PROS) Algorithm
### Multi-Dimensional Functions  
In this section, we study the performance of PROS on \(D\)-dimensional functions with domain \(\Omega=[a_{1},b_{1}]\times[a_{2},b_{2}]\times\cdots\times[a_{D},b_{D}]\), where \(D>1\). In particular, we focus on the class of totally separable functions as defined below. For notation simplicity, define \(\mathbf{x}_{-i}\triangleq(x_{1},x_{2},\ldots,x_{i-1},x_{i+1},\ldots,x_{D})\). **Definition 3** (Partially Separable Function). : _A function \(f(\mathbf{x})\) is partially separable with coordinate \(i\) if \(\arg\min\limits_{x_{i}}f(x_{i},\mathbf{x}_{-i})\) is independent of \(\mathbf{x}_{-i}\)._  
An example of partially separable functions with coordinate \(i=1\) is :  
\[f(\mathbf{x})=x_{1}^{2}+\sum_{i=2}^{D-1}(x_{i}-x_{i+1})^{2}.\]  
**Definition 4** (Totally Separable Function). : _A function \(f(\mathbf{x})\) is totally separable if it is partially separable with every of the \(D\) coordinates._  
An example of totally separable functions is:  
\[f(\mathbf{x})=\prod_{i=1}^{D}(x_{i}^{2}+1).\]  
In each iteration, PROS minimizes \(f\) in one of the random coordinate \(i\). As \(f\) is totally separable, each coordinate \(i\) can be minimized independently. The following result shows that PROS converges to the region of global optimum in probability. **Theorem 2**. : _PROS converges in probability to the region of global optimum for all totally separable functions, i.e.,_  
\[\lim_{t\to\infty}P\{\mathbf{x}^{(t)}\in R_{\epsilon}\}=1,\ \ \forall\epsilon>0.\]  
Proof. : Since \(f\) is Lipschitz, given any \(\mathbf{x}_{-i}\), we have  
\[|f(x_{i},\mathbf{x}_{-i})-f(\bar{x}_{i},\mathbf{x}_{-i})|\leq L|x_{i}-\bar{x}_ {i}|.\]  
Therefore, \(f\) can be regarded as a one-dimensional Lipschitz function in \(x_{i}\) with the same constant \(L\). As shown in the previous subsection, there is an interval \(V_{\epsilon_{i}}\) of minimum length \(\frac{\epsilon_{i}}{L}\) such that for all \(x_{i}\in V_{\epsilon_{i}}\),  
\[|f(x_{i},\mathbf{x}_{-i})-f(x_{i}^{*},\mathbf{x}_{-i})|\leq\epsilon_{i}.\]  
Note that \(V_{\epsilon_{i}}\) is independent of \(\mathbf{x}_{-i}\). Under PROS, it is clear that  
\[\lim_{t\to\infty}P\{x_{i}^{(t)}\in V_{\epsilon_{i}}\}=1,\ \ \forall\epsilon_{i}>0.\]  
Since \(f\) is Lipschitz, it is a continuous function. Given any \(\epsilon>0\), there exists sufficiently small positive \(\epsilon_{i}\)'s such that when \(x_{i}^{(t)}\in V_{\epsilon_{i}}\) for all \(i\), we must have \(\mathbf{x}^{(t)}\in R_{\epsilon}\). The statement then follows from  
\[P\{\mathbf{x}^{(t)}\in R_{\epsilon}\}\geq P\{x_{i}^{(t)}\in V_{\epsilon_{i}}, \forall i\}=\prod_{i=1}^{D}P\{x_{i}^{(t)}\in V_{\epsilon_{i}}\}.\]  
The expected convergence time can be obtained for the following subclass of totally separable functions. **Definition 5** (Additively Separable Function). : _A function \(f\) is additively separable if \(f(\mathbf{x})\) can be written in the form of \(f_{1}(x_{1})+f_{2}(x_{2})+\cdots+f_{D}(x_{D})\), where \(\mathbf{x}=(x_{1},x_{2},\ldots,x_{D})\) and \(f_{1},f_{2},\ldots,f_{D}\) are one-dimensional functions._  
An example of additively separable functions is the sum-of-spheres function:  
\[f_{sphere}(\mathbf{x})=\sum_{i=1}^{D}x_{i}^{2}.\]  
For the optimization of \(D\)-dimensional additively separable functions, it is equivalent to optimize \(D\) one-dimensional functions independently, i.e.,  
\[\min_{\mathbf{x}\in\Omega}f(\mathbf{x})=\sum_{i=1}^{D}\min_{x_{i}\in[a_{i},b_{ i}]}f_{i}(x_{i}).\]  
**Theorem 3**. : _The expected convergence time of PROS for D-dimensional additively separable functions is bounded above by_  
\[\mathbb{E}[T]\leq\frac{D^{2}L}{\epsilon}\sum_{i=1}^{D}(b_{i}-a_{i}).\]  
Proof. : A point \(\mathbf{x}=(x_{1},x_{2},\ldots,x_{D})\) belongs to \(R_{\epsilon}\) if  
\[f(\mathbf{x})=\prod_{i=1}^{D}(x_{i}^{2}+1).\]0  
where \(f_{i}^{*}\) is the global minimum of the \(i\)-th one-dimensional function. Then,  
\[f(\mathbf{x})=\prod_{i=1}^{D}(x_{i}^{2}+1).\]1  
is a sufficient condition for \(\mathbf{x}\in R_{\epsilon}\).