I am reading this paper related to an algorithm for nonsmooth optimization problems. After many simplifications, I was able to formalize the method as follows: let $\Bbb B $ denote the unit ball in $\Bbb R^n$ and consider a set $D\subseteq \Bbb B.$ We have an operator $T: \Bbb R^n \times D \to \Bbb R^n,$ and the probability space $(\Bbb B, \mathcal{B}|_{\Bbb B}, \mu),$ where

  • $\mathcal{B}|_{\Bbb B}$ denotes the Borel sigma algebra in $\Bbb R^n$ restricted to the unit ball

  • $\mu$ is the Lebesgue measure restricted to $\Bbb B$ scaled so that it is a probability measure, i.e, for $B\in \mathcal{B}|_{\Bbb B},$ $$\mu(B):=\frac{\mu'(B)}{\mu'(\Bbb B)},$$ and $\mu'$ is the Lebesgue measure in $\Bbb R^n.$ Furthermore, we have that $\mu(D)=\mu (\Bbb B).$

The algorithm is then as follows:

  • Step 0: Take $x^0\in \Bbb R^n,\; k=0.$

  • Step 1: Sample $u^k$ from $\Bbb B$ according to the probability space described. If $u^k \notin D:$ Stop, return $x^k.$ Else, go to Step 2

  • Step 2: Take $x^{k+1}:= T(x^k, u^k),\; k=k+1.$ Go to Step 1.

The main result of the paper states that:

  • With probability one, the method above never stops and every accumulation point of the generated sequence belongs to a set $S$ (of stationary points).

I am not able to formalize this statement in order to attempt a proof by myself due to the following questions:

  1. According to such statement, the set

$$A:= \{\{x^k\}: \{x^k\} \textrm{ is generated by the method(that does not stop) and every accumulation point belongs to } S\}$$ is an event in some probability space $(X,\mathcal{A},\nu)$ with $\nu(A)=1.$

Who is $(X,\mathcal{A},\nu)$? In the paper, this is not explained because it seems not to be needed.

  1. If you don't need the definition of $(X,\mathcal{A},\nu),$ is there a branch of probability theory that is devoted to the study of these types of statements? To my little knowledge, this seems to be related to stochastic processes or random walks.

Thanks to all in advance.



It appears that by $\mu(D)=\mu(B)$ you meant $\mu(D)=\mu(\Bbb B)$; otherwise, this condition would not make sense.

It also appears that the sentence "Sample $u^k$ from $\Bbb B$ according to the probability space described", which you quoted, means that $u^0,u^1,\dots$ are independent. More generally, we may assume that the joint distributions, say $\mu_k$, of the finite sequences $(u^0,\dots,u^k)$ on the corresponding product sigma-algebras $\F^{\otimes (k+1)}$ (where $\F:=\mathcal{B}|_{\Bbb B}$) are defined consistently for all $k=0,1,\dots$, in the sense that for each such $k$ the push-forward measure $\mu_{k+1}\pi_{k+1,k}^{-1}$ of the probability measure $\mu_{k+1}$ under the projection $\pi_{k+1,k}$ from $\Bbb B^{k+2}$ onto $\Bbb B^{k+1}$ coincides with $\mu_k$. (If the $u_j$'s are independent, then $\mu_k$ is the product measure $\mu^{\otimes (k+1)}$.) Let $\F^{\otimes\infty}$ be the smallest sigma-algebra over $\Bbb B^\infty$ containing the set of all cylindrical sets, that is, of all sets of the form $\pi_{\infty,k}^{-1}(E)$, where $k=0,1,\dots$, $E\in\F^{\otimes (k+1)}$, and $\pi_{\infty,k}$ is the projection from $\Bbb B^\infty$ onto $\Bbb B^{k+1}$.

Then, by the Kolmogorov extension theorem, there is a unique probability measure $\mu_\infty$ on $\F^{\otimes\infty}$ such that for all $k=0,1,\dots$ and all $E\in\F^{\otimes (k+1)}$ we have $\mu_\infty(\pi_{\infty,k}^{-1}(E))=\mu_k(E)$. So, for your probability space $(X,\mathcal{A},\nu)$ you can take $(\Bbb B^\infty,\F^{\otimes\infty},\mu_\infty)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.