I have a function $F$ which is defined as follows: $$ F(x) = \sum_{i=1}^N f(z_i^T x) $$ where ${z_i}$ are known $m \times 1$ vectors, $x$ is an $m \times 1$ vector, and for $t\in \mathbb{R}$, $f(t) = \frac{1}{1+e^{-t/\sigma}}$ with a known $\sigma$ (a sigmoid function).

For a local or global maximum of $F(x)$, I would like to characterize the basin of attraction---the set of all starting points from which a gradient ascent algorithm converges to the local maximum.

I know that the gradient of $F$ is: $$ \nabla F = \frac{1}{\sigma} \sum_i \frac{e^{-z_i^Tx/\sigma}}{(1+e^{-z_i^Tx/\sigma})^2}z_i^T $$ and the Hessian can also be easily derived.

How can I use the gradient and Hessian to come up with a simple condition for the basin of attraction of $x^*$, e.g., if $\|x-x^*\|^2<g$ for some $g$, then $x$ is in the basin of attraction of $x^*$?

  • $\begingroup$ Minor observation: If there is a vector $y \in \mathbb{R}^N$ such that $z_i^Ty>0$ for all $i\in\{1, ..., N\}$, then there is no global max and $\lim_{\theta \rightarrow\infty} F(\theta y) = \sup_{x \in \mathbb{R}^N} F(x) = N$. $\endgroup$
    – Michael
    Sep 16 '15 at 21:28
  • $\begingroup$ It seems you can get a condition from the second-order Taylor theorem in multiple variables, of the form $F(y) = F(x^*) + \frac{1}{2}(y-x)^T \nabla^2 f(z) (y-z)$ for some vector $z$ that lies on the line between $y$ and $x^*$, and where $x^*$ is a local max. If all eigenvalues of $\nabla^2 f(z)$ are negative, you are in business and the smallest magnitude eigenvalue helps give a bound that might be useful. $\endgroup$
    – Michael
    Sep 16 '15 at 21:42

Your Answer

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

Browse other questions tagged or ask your own question.