Skip to main content
added 26 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}$, which depends continuously-differentiably on $x$, such that $G(x) = \nabla g(x)$ for all $x \in \mathbb R^m$. Further ssume that:

  • $G$ looks thesame every where. $G(x)$, $-G(x)$, and $G(x')$ are equal in distribution for all $x,x' \in \mathbb R^m$. In particular, this implies $G$ is centered., i.e $E[G(x)] = 0$.
  • Moment bounds. There exists $\alpha,\beta,\gamma > 0$ such that for all $x \in \mathbb R^m$,
    • $ E[\|G(x)\|^2] \le \alpha$,
    • $E[\|G(x)\|^4] \le \beta$ (note that this automatically implies the correlation bound $E[\|G(x)\|^2\|G(x')\|^2] \le \beta^2$),
    • $\gamma_1 \le Var[\|G(x)\|^2] \le \gamma_2$.

Fix $x_0 \in \mathbb R^m$, set $g_0:=\mbox{sign}(g(x_0))$, and consider the differential equation

$$ \begin{split} \dot{x}(t) &= -G(x(t)), \;t \in \mathbb R\\ x(0) &= x_0. \end{split} \tag{1} $$$$ \begin{split} \dot{x}(t) &= -g_0G(x(t)), \;t \in \mathbb R\\ x(0) &= x_0. \end{split} \tag{1} $$ For each $t \ge 0$, define $r_t := \|x(t)-x_0\|$ and $c_t := \int_0^t \|G(x(s))\|^2ds$

Goal. My ultimate goal to prove that there is a time $t^\star \ge 0$ (which is deterministic, but may depend on dimension parameter $m \to \infty$) such w.p $1-o(1)$, $g(x(t^\star))<0$$g_0g(x(t^\star))<0$ (i.e $g(x(t))$ flips sign from $t=0$ to $t=t^\star$) and $r_{t^\star}$ is as small as possible.

I figured out I could use concentration of measure techniques. This is because, for all $t \ge 0$, $g(x(t)) = g(x_0) - \int_0^t \|G(x(s))\|^2ds$.

Question. How to go about large and small deviation inequalities for $r_t$ and $c_t$ as a function of time $t$ ? More specically, I'd like to how (anti-)concentration inequalities for both $r_t$ and $c_t$.

Softer question. I don't know under what topic such problems fall "concentration of random fields" ?, "oncentration of gradient flows" ?, etc. High-level help and references on this point, would already be very useful.

Observations

Some parts of my problem can be crudely solved. For example, if $u > 0$, then for all time $0 < t < u/\alpha$ we have

$$ P(c_t > u) \le \frac{E[\int_0^t \|G(x(s))\|^2 ds]}{u} = \frac{\int_0^t E[\|G(x(s))\|^2] ds}{u} \le \frac{t\alpha}{u} $$

Similarly, a concentration bound for $r_t$ can be obtained using Hoelder's inequality combined with Markov like so

$$ \begin{split} P(r_t > r) &= P\left(\|\int_0^t G(x(s))ds\|^2 > r^2\right) \le \ldots \le t^2 P\left(\int_0^t \|G(x(s))\|^2ds > r^2\right)\\ & \le \frac{t^2\alpha}{r^2}, \end{split} $$ valid for all $r > 0$ and time $0 < t < r/\sqrt{\alpha}$.

Completely worked-out example

Consider a static random field given by $G(x) = \nabla g(x)$ with $g(x) := w^Tx$, where $w \sim N(0,(1/m)I_m)$ and $a:=\mbox{sign}(w^Tx_0)$. Then integrating (1) gives $x(t) = x_0 - atw$$x(t) = x_0 - g_0tw$. Thus, $r_t = t\|w\|$ and $c_t = t\|w\|^2$, and there is no shortage of anti-/concentration inequalities in this case. We can take $t^\star = \|x_0\|^2/m \cdot e_m$ for any deterministic $e_m \to \infty$ and get the following w.p $1-o(1)$

  • $r_{t^\star} = \mathcal O(t^\star)$.
  • $c_{t^\star} = \Theta(t^\star)$.
  • $g(x(t^\star)) < 0$$g_0g(x(t^\star)) < 0$.

Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}$, which depends continuously-differentiably on $x$, such that $G(x) = \nabla g(x)$ for all $x \in \mathbb R^m$. Further ssume that:

  • $G$ looks thesame every where. $G(x)$, $-G(x)$, and $G(x')$ are equal in distribution for all $x,x' \in \mathbb R^m$. In particular, this implies $G$ is centered., i.e $E[G(x)] = 0$.
  • Moment bounds. There exists $\alpha,\beta,\gamma > 0$ such that for all $x \in \mathbb R^m$,
    • $ E[\|G(x)\|^2] \le \alpha$,
    • $E[\|G(x)\|^4] \le \beta$ (note that this automatically implies the correlation bound $E[\|G(x)\|^2\|G(x')\|^2] \le \beta^2$),
    • $\gamma_1 \le Var[\|G(x)\|^2] \le \gamma_2$.

Fix $x_0 \in \mathbb R^m$ and consider the differential equation

$$ \begin{split} \dot{x}(t) &= -G(x(t)), \;t \in \mathbb R\\ x(0) &= x_0. \end{split} \tag{1} $$ For each $t \ge 0$, define $r_t := \|x(t)-x_0\|$ and $c_t := \int_0^t \|G(x(s))\|^2ds$

Goal. My ultimate goal to prove that there is a time $t^\star \ge 0$ (which is deterministic, but may depend on dimension parameter $m \to \infty$) such w.p $1-o(1)$, $g(x(t^\star))<0$ and $r_{t^\star}$ is as small as possible.

I figured out I could use concentration of measure techniques. This is because, for all $t \ge 0$, $g(x(t)) = g(x_0) - \int_0^t \|G(x(s))\|^2ds$.

Question. How to go about large and small deviation inequalities for $r_t$ and $c_t$ as a function of time $t$ ? More specically, I'd like to how (anti-)concentration inequalities for both $r_t$ and $c_t$.

Softer question. I don't know under what topic such problems fall "concentration of random fields" ?, "oncentration of gradient flows" ?, etc. High-level help and references on this point, would already be very useful.

Observations

Some parts of my problem can be crudely solved. For example, if $u > 0$, then for all time $0 < t < u/\alpha$ we have

$$ P(c_t > u) \le \frac{E[\int_0^t \|G(x(s))\|^2 ds]}{u} = \frac{\int_0^t E[\|G(x(s))\|^2] ds}{u} \le \frac{t\alpha}{u} $$

Similarly, a concentration bound for $r_t$ can be obtained using Hoelder's inequality combined with Markov like so

$$ \begin{split} P(r_t > r) &= P\left(\|\int_0^t G(x(s))ds\|^2 > r^2\right) \le \ldots \le t^2 P\left(\int_0^t \|G(x(s))\|^2ds > r^2\right)\\ & \le \frac{t^2\alpha}{r^2}, \end{split} $$ valid for all $r > 0$ and time $0 < t < r/\sqrt{\alpha}$.

Completely worked-out example

Consider a static random field given by $G(x) = \nabla g(x)$ with $g(x) := w^Tx$, where $w \sim N(0,(1/m)I_m)$ and $a:=\mbox{sign}(w^Tx_0)$. Then integrating (1) gives $x(t) = x_0 - atw$. Thus, $r_t = t\|w\|$ and $c_t = t\|w\|^2$, and there is no shortage of anti-/concentration inequalities in this case. We can take $t^\star = \|x_0\|^2/m \cdot e_m$ for any deterministic $e_m \to \infty$ and get the following w.p $1-o(1)$

  • $r_{t^\star} = \mathcal O(t^\star)$.
  • $c_{t^\star} = \Theta(t^\star)$.
  • $g(x(t^\star)) < 0$.

Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}$, which depends continuously-differentiably on $x$, such that $G(x) = \nabla g(x)$ for all $x \in \mathbb R^m$. Further ssume that:

  • $G$ looks thesame every where. $G(x)$, $-G(x)$, and $G(x')$ are equal in distribution for all $x,x' \in \mathbb R^m$. In particular, this implies $G$ is centered., i.e $E[G(x)] = 0$.
  • Moment bounds. There exists $\alpha,\beta,\gamma > 0$ such that for all $x \in \mathbb R^m$,
    • $ E[\|G(x)\|^2] \le \alpha$,
    • $E[\|G(x)\|^4] \le \beta$ (note that this automatically implies the correlation bound $E[\|G(x)\|^2\|G(x')\|^2] \le \beta^2$),
    • $\gamma_1 \le Var[\|G(x)\|^2] \le \gamma_2$.

Fix $x_0 \in \mathbb R^m$, set $g_0:=\mbox{sign}(g(x_0))$, and consider the differential equation

$$ \begin{split} \dot{x}(t) &= -g_0G(x(t)), \;t \in \mathbb R\\ x(0) &= x_0. \end{split} \tag{1} $$ For each $t \ge 0$, define $r_t := \|x(t)-x_0\|$ and $c_t := \int_0^t \|G(x(s))\|^2ds$

Goal. My ultimate goal to prove that there is a time $t^\star \ge 0$ (which is deterministic, but may depend on dimension parameter $m \to \infty$) such w.p $1-o(1)$, $g_0g(x(t^\star))<0$ (i.e $g(x(t))$ flips sign from $t=0$ to $t=t^\star$) and $r_{t^\star}$ is as small as possible.

I figured out I could use concentration of measure techniques. This is because, for all $t \ge 0$, $g(x(t)) = g(x_0) - \int_0^t \|G(x(s))\|^2ds$.

Question. How to go about large and small deviation inequalities for $r_t$ and $c_t$ as a function of time $t$ ? More specically, I'd like to how (anti-)concentration inequalities for both $r_t$ and $c_t$.

Softer question. I don't know under what topic such problems fall "concentration of random fields" ?, "oncentration of gradient flows" ?, etc. High-level help and references on this point, would already be very useful.

Observations

Some parts of my problem can be crudely solved. For example, if $u > 0$, then for all time $0 < t < u/\alpha$ we have

$$ P(c_t > u) \le \frac{E[\int_0^t \|G(x(s))\|^2 ds]}{u} = \frac{\int_0^t E[\|G(x(s))\|^2] ds}{u} \le \frac{t\alpha}{u} $$

Similarly, a concentration bound for $r_t$ can be obtained using Hoelder's inequality combined with Markov like so

$$ \begin{split} P(r_t > r) &= P\left(\|\int_0^t G(x(s))ds\|^2 > r^2\right) \le \ldots \le t^2 P\left(\int_0^t \|G(x(s))\|^2ds > r^2\right)\\ & \le \frac{t^2\alpha}{r^2}, \end{split} $$ valid for all $r > 0$ and time $0 < t < r/\sqrt{\alpha}$.

Completely worked-out example

Consider a static random field given by $G(x) = \nabla g(x)$ with $g(x) := w^Tx$, where $w \sim N(0,(1/m)I_m)$. Then integrating (1) gives $x(t) = x_0 - g_0tw$. Thus, $r_t = t\|w\|$ and $c_t = t\|w\|^2$, and there is no shortage of anti-/concentration inequalities in this case. We can take $t^\star = \|x_0\|^2/m \cdot e_m$ for any deterministic $e_m \to \infty$ and get the following w.p $1-o(1)$

  • $r_{t^\star} = \mathcal O(t^\star)$.
  • $c_{t^\star} = \Theta(t^\star)$.
  • $g_0g(x(t^\star)) < 0$.
added 26 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}$, which depends continuously-differentiably on $x$, such that $G(x) = \nabla g(x)$ for all $x \in \mathbb R^m$. Further ssume that:

  • $G$ looks thesame every where. $G(x)$, $-G(x)$, and $G(x')$ are equal in distribution for all $x,x' \in \mathbb R^m$. In particular, this implies $G$ is centered., i.e $E[G(x)] = 0$.
  • Moment bounds. There exists $\alpha,\beta,\gamma > 0$ such that for all $x \in \mathbb R^m$,
    • $ E[\|G(x)\|^2] \le \alpha$,
    • $E[\|G(x)\|^4] \le \beta$ (note that this automatically implies the correlation bound $E[\|G(x)\|^2\|G(x')\|^2] \le \beta^2$),
    • $\gamma_1 \le Var[\|G(x)\|^2] \le \gamma_2$.

Fix $x_0 \in \mathbb R^m$ and consider the differential equation

$$ \begin{split} \dot{x}(t) &= -G(x(t)), \;t \in \mathbb R\\ x(0) &= x_0. \end{split} \tag{1} $$ For each $t \ge 0$, define $r_t := \|x(t)-x_0\|$ and $c_t := \int_0^t \|G(x(s)\|^2ds$$c_t := \int_0^t \|G(x(s))\|^2ds$

Goal. My ultimate goal to prove that there is a time $t^\star \ge 0$ (which is deterministic, but may depend on dimension parameter $m \to \infty$) such thatw.p $\|x(t^\star)-x_0\|$ and$1-o(1)$, $g(x(t^\star))<0$ with probabilityand $1-o(1)$$r_{t^\star}$ is as small as possible.

I figured out I could use concentration of measure techniques. This is because, for all $t \ge 0$, $g(x(t)) = g(x_0) - \int_0^t \|G(x(s))\|^2ds$.

Question. How to go about large and small deviation inequalities for $r_t$ and $c_t$ as a function of time $t$ ? More specically, I'd like to how (anti-)concentration inequalities for both $r_t$ and $c_t$.

Softer question. I don't know under what topic such problems fall "concentration of random fields" ?, "oncentration of gradient flows" ?, etc. High-level help and references on this point, would already be very useful.

Observations

Some parts of my problem can be crudely solved. For example, if $u > 0$, then for all time $0 < t < u/\alpha$ we have

$$ P(c_t > u) \le \frac{E[\int_0^t \|G(x(s))\|^2 ds]}{u} = \frac{\int_0^t E[\|G(x(s))\|^2] ds}{u} \le \frac{t\alpha}{u} $$

Similarly, a concentration bound for $r_t$ can be obtained using Hoelder's inequality combined with Markov like so

$$ \begin{split} P(r_t > r) &= P\left(\|\int_0^t G(x(s))ds\|^2 > r^2\right) \le \ldots \le t^2 P\left(\int_0^t \|G(x(s))\|^2ds > r^2\right)\\ & \le \frac{t^2\alpha}{r^2}, \end{split} $$ valid for all $r > 0$ and time $0 < t < r/\sqrt{\alpha}$.

Completely worked-out example

Consider a static random field given by $G(x) = \nabla g(x)$ with $g(x) := w^Tx$, where $w \sim N(0,(1/m)I_m)$ and $a:=\mbox{sign}(w^Tx_0)$. Then integrating (1) gives $x(t) = x_0 - atw$. Thus, $r_t = t\|w\|$ and $c_t = t\|w\|^2$, and there is no shortage of anti-/concentration inequalities in this case. We can take $t^\star = \|x_0\|^2/m \cdot e_m$ for any deterministic $e_m \to \infty$ and get the following w.p $1-o(1)$

  • $r_{t^\star} = \mathcal O(t^\star)$.
  • $c_{t^\star} = \Theta(t^\star)$.
  • $g(x(t^\star)) < 0$.

Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}$, which depends continuously-differentiably on $x$, such that $G(x) = \nabla g(x)$ for all $x \in \mathbb R^m$. Further ssume that:

  • $G$ looks thesame every where. $G(x)$, $-G(x)$, and $G(x')$ are equal in distribution for all $x,x' \in \mathbb R^m$. In particular, this implies $G$ is centered., i.e $E[G(x)] = 0$.
  • Moment bounds. There exists $\alpha,\beta,\gamma > 0$ such that for all $x \in \mathbb R^m$,
    • $ E[\|G(x)\|^2] \le \alpha$,
    • $E[\|G(x)\|^4] \le \beta$ (note that this automatically implies the correlation bound $E[\|G(x)\|^2\|G(x')\|^2] \le \beta^2$),
    • $\gamma_1 \le Var[\|G(x)\|^2] \le \gamma_2$.

Fix $x_0 \in \mathbb R^m$ and consider the differential equation

$$ \begin{split} \dot{x}(t) &= -G(x(t)), \;t \in \mathbb R\\ x(0) &= x_0. \end{split} \tag{1} $$ For each $t \ge 0$, define $r_t := \|x(t)-x_0\|$ and $c_t := \int_0^t \|G(x(s)\|^2ds$

Goal. My ultimate goal to prove that there is a time $t^\star \ge 0$ (which may depend on dimension parameter $m \to \infty$) such that $\|x(t^\star)-x_0\|$ and $g(x(t^\star))<0$ with probability $1-o(1)$.

I figured out I could use concentration of measure techniques. This is because, for all $t \ge 0$, $g(x(t)) = g(x_0) - \int_0^t \|G(x(s))\|^2ds$.

Question. How to go about large and small deviation inequalities for $r_t$ and $c_t$ as a function of time $t$ ? More specically, I'd like to how (anti-)concentration inequalities for both $r_t$ and $c_t$.

Softer question. I don't know under what topic such problems fall "concentration of random fields" ?, "oncentration of gradient flows" ?, etc. High-level help and references on this point, would already be very useful.

Observations

Some parts of my problem can be crudely solved. For example, if $u > 0$, then for all time $0 < t < u/\alpha$ we have

$$ P(c_t > u) \le \frac{E[\int_0^t \|G(x(s))\|^2 ds]}{u} = \frac{\int_0^t E[\|G(x(s))\|^2] ds}{u} \le \frac{t\alpha}{u} $$

Similarly, a concentration bound for $r_t$ can be obtained using Hoelder's inequality combined with Markov like so

$$ \begin{split} P(r_t > r) &= P\left(\|\int_0^t G(x(s))ds\|^2 > r^2\right) \le \ldots \le t^2 P\left(\int_0^t \|G(x(s))\|^2ds > r^2\right)\\ & \le \frac{t^2\alpha}{r^2}, \end{split} $$ valid for all $r > 0$ and time $0 < t < r/\sqrt{\alpha}$.

Completely worked-out example

Consider a static random field given by $G(x) = \nabla g(x)$ with $g(x) := w^Tx$, where $w \sim N(0,(1/m)I_m)$ and $a:=\mbox{sign}(w^Tx_0)$. Then integrating (1) gives $x(t) = x_0 - atw$. Thus, $r_t = t\|w\|$ and $c_t = t\|w\|^2$, and there is no shortage of anti-/concentration inequalities in this case. We can take $t^\star = \|x_0\|^2/m \cdot e_m$ for any $e_m \to \infty$ and get the following w.p $1-o(1)$

  • $r_{t^\star} = \mathcal O(t^\star)$.
  • $c_{t^\star} = \Theta(t^\star)$.
  • $g(x(t^\star)) < 0$.

Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}$, which depends continuously-differentiably on $x$, such that $G(x) = \nabla g(x)$ for all $x \in \mathbb R^m$. Further ssume that:

  • $G$ looks thesame every where. $G(x)$, $-G(x)$, and $G(x')$ are equal in distribution for all $x,x' \in \mathbb R^m$. In particular, this implies $G$ is centered., i.e $E[G(x)] = 0$.
  • Moment bounds. There exists $\alpha,\beta,\gamma > 0$ such that for all $x \in \mathbb R^m$,
    • $ E[\|G(x)\|^2] \le \alpha$,
    • $E[\|G(x)\|^4] \le \beta$ (note that this automatically implies the correlation bound $E[\|G(x)\|^2\|G(x')\|^2] \le \beta^2$),
    • $\gamma_1 \le Var[\|G(x)\|^2] \le \gamma_2$.

Fix $x_0 \in \mathbb R^m$ and consider the differential equation

$$ \begin{split} \dot{x}(t) &= -G(x(t)), \;t \in \mathbb R\\ x(0) &= x_0. \end{split} \tag{1} $$ For each $t \ge 0$, define $r_t := \|x(t)-x_0\|$ and $c_t := \int_0^t \|G(x(s))\|^2ds$

Goal. My ultimate goal to prove that there is a time $t^\star \ge 0$ (which is deterministic, but may depend on dimension parameter $m \to \infty$) such w.p $1-o(1)$, $g(x(t^\star))<0$ and $r_{t^\star}$ is as small as possible.

I figured out I could use concentration of measure techniques. This is because, for all $t \ge 0$, $g(x(t)) = g(x_0) - \int_0^t \|G(x(s))\|^2ds$.

Question. How to go about large and small deviation inequalities for $r_t$ and $c_t$ as a function of time $t$ ? More specically, I'd like to how (anti-)concentration inequalities for both $r_t$ and $c_t$.

Softer question. I don't know under what topic such problems fall "concentration of random fields" ?, "oncentration of gradient flows" ?, etc. High-level help and references on this point, would already be very useful.

Observations

Some parts of my problem can be crudely solved. For example, if $u > 0$, then for all time $0 < t < u/\alpha$ we have

$$ P(c_t > u) \le \frac{E[\int_0^t \|G(x(s))\|^2 ds]}{u} = \frac{\int_0^t E[\|G(x(s))\|^2] ds}{u} \le \frac{t\alpha}{u} $$

Similarly, a concentration bound for $r_t$ can be obtained using Hoelder's inequality combined with Markov like so

$$ \begin{split} P(r_t > r) &= P\left(\|\int_0^t G(x(s))ds\|^2 > r^2\right) \le \ldots \le t^2 P\left(\int_0^t \|G(x(s))\|^2ds > r^2\right)\\ & \le \frac{t^2\alpha}{r^2}, \end{split} $$ valid for all $r > 0$ and time $0 < t < r/\sqrt{\alpha}$.

Completely worked-out example

Consider a static random field given by $G(x) = \nabla g(x)$ with $g(x) := w^Tx$, where $w \sim N(0,(1/m)I_m)$ and $a:=\mbox{sign}(w^Tx_0)$. Then integrating (1) gives $x(t) = x_0 - atw$. Thus, $r_t = t\|w\|$ and $c_t = t\|w\|^2$, and there is no shortage of anti-/concentration inequalities in this case. We can take $t^\star = \|x_0\|^2/m \cdot e_m$ for any deterministic $e_m \to \infty$ and get the following w.p $1-o(1)$

  • $r_{t^\star} = \mathcal O(t^\star)$.
  • $c_{t^\star} = \Theta(t^\star)$.
  • $g(x(t^\star)) < 0$.
edited body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}$, which depends continuously-differentiably on $x$, such that $G(x) = \nabla G(x)$$G(x) = \nabla g(x)$ for all $x \in \mathbb R^m$. AssumeFurther ssume that:

  • $G$ looks thesame every where. $G(x)$, $-G(x)$, and $G(x')$ are equal in distribution for all $x,x' \in \mathbb R^m$. In particular, this implies $G$ is centered., i.e $E[G(x)] = 0$.
  • Moment bounds. There exists $\alpha,\beta,\gamma > 0$ such that for all $x \in \mathbb R^m$,
    • $ E[\|G(x)\|^2] \le \alpha$,
    • $E[\|G(x)\|^4] \le \beta$ (note that this automatically implies the correlation bound $E[\|G(x)\|^2\|G(x')\|^2] \le \beta^2$),
    • $\gamma_1 \le Var[\|G(x)\|^2] \le \gamma_2$.

Fix $x_0 \in \mathbb R^m$ and consider the differential equation

$$ \begin{split} \dot{x}(t) &= -G(x(t)), \;t \in \mathbb R\\ x(0) &= x_0. \end{split} \tag{1} $$ For each $t \ge 0$, define $r_t := \|x(t)-x_0\|$ and $c_t := \int_0^t \|G(x(s)\|^2ds$

Goal. My ultimate goal to prove that there is a time $t^\star \ge 0$ (which may depend on dimension parameter $m \to \infty$) such that $\|x(t^\star)-x_0\|$ and $g(x(t^\star))<0$ with probability $1-o(1)$.

I figured out I could use concentration of measure techniques. This is because, for all $t \ge 0$, $g(x(t)) = g(x_0) - \int_0^t \|G(x(s))\|^2ds$.

Question. How to go about large and small deviation inequalities for $r_t$ and $c_t$ as a function of time $t$ ? More specically, I'd like to how (anti-)concentration inequalities for both $r_t$ and $c_t$.

Softer question. I don't know under what topic such problems fall "concentration of random fields" ?, "oncentration of gradient flows" ?, etc. High-level help and references on this point, would already be very useful.

Observations

Some parts of my problem can be crudely solved. For example, if $u > 0$, then for all time $0 < t < u/\alpha$ we have

$$ P(c_t > u) \le \frac{E[\int_0^t \|G(x(s))\|^2 ds]}{u} = \frac{\int_0^t E[\|G(x(s))\|^2] ds}{u} \le \frac{t\alpha}{u} $$

Similarly, a concentration bound for $r_t$ can be obtained using Hoelder's inequality combined with Markov like so

$$ \begin{split} P(r_t > r) &= P\left(\|\int_0^t G(x(s))ds\|^2 > r^2\right) \le \ldots \le t^2 P\left(\int_0^t \|G(x(s))\|^2ds > r^2\right)\\ & \le \frac{t^2\alpha}{r^2}, \end{split} $$ valid for all $r > 0$ and time $0 < t < r/\sqrt{\alpha}$.

Completely worked-out example

Consider a static random field given by $G(x) = \nabla g(x)$ with $g(x) := w^Tx$, where $w \sim N(0,(1/m)I_m)$ and $a:=\mbox{sign}(w^Tx_0)$. Then integrating (1) gives $x(t) = x_0 - atw$. Thus, $r_t = t\|w\|$ and $c_t = t\|w\|^2$, and there is no shortage of anti-/concentration inequalities in this case. We can take $t^\star = \|x_0\|^2/m \cdot e_m$ for any $e_m \to \infty$ and get the following w.p $1-o(1)$

  • $r_{t^\star} = \mathcal O(t^\star)$.
  • $c_{t^\star} = \Theta(t^\star)$.
  • $g(x(t^\star)) < 0$.

Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}$, which depends continuously-differentiably on $x$, such that $G(x) = \nabla G(x)$ for all $x \in \mathbb R^m$. Assume that

  • $G$ looks thesame every where. $G(x)$, $-G(x)$, and $G(x')$ are equal in distribution for all $x,x' \in \mathbb R^m$. In particular, this implies $G$ is centered., i.e $E[G(x)] = 0$.
  • Moment bounds. There exists $\alpha,\beta,\gamma > 0$ such that for all $x \in \mathbb R^m$,
    • $ E[\|G(x)\|^2] \le \alpha$,
    • $E[\|G(x)\|^4] \le \beta$ (note that this automatically implies the correlation bound $E[\|G(x)\|^2\|G(x')\|^2] \le \beta^2$),
    • $\gamma_1 \le Var[\|G(x)\|^2] \le \gamma_2$.

Fix $x_0 \in \mathbb R^m$ and consider the differential equation

$$ \begin{split} \dot{x}(t) &= -G(x(t)), \;t \in \mathbb R\\ x(0) &= x_0. \end{split} \tag{1} $$ For each $t \ge 0$, define $r_t := \|x(t)-x_0\|$ and $c_t := \int_0^t \|G(x(s)\|^2ds$

Goal. My ultimate goal to prove that there is a time $t^\star \ge 0$ (which may depend on dimension parameter $m \to \infty$) such that $\|x(t^\star)-x_0\|$ and $g(x(t^\star))<0$ with probability $1-o(1)$.

I figured out I could use concentration of measure techniques. This is because, for all $t \ge 0$, $g(x(t)) = g(x_0) - \int_0^t \|G(x(s))\|^2ds$.

Question. How to go about large and small deviation inequalities for $r_t$ and $c_t$ as a function of time $t$ ? More specically, I'd like to how (anti-)concentration inequalities for both $r_t$ and $c_t$.

Softer question. I don't know under what topic such problems fall "concentration of random fields" ?, "oncentration of gradient flows" ?, etc. High-level help and references on this point, would already be very useful.

Observations

Some parts of my problem can be crudely solved. For example, if $u > 0$, then for all time $0 < t < u/\alpha$ we have

$$ P(c_t > u) \le \frac{E[\int_0^t \|G(x(s))\|^2 ds]}{u} = \frac{\int_0^t E[\|G(x(s))\|^2] ds}{u} \le \frac{t\alpha}{u} $$

Similarly, a concentration bound for $r_t$ can be obtained using Hoelder's inequality combined with Markov like so

$$ \begin{split} P(r_t > r) &= P\left(\|\int_0^t G(x(s))ds\|^2 > r^2\right) \le \ldots \le t^2 P\left(\int_0^t \|G(x(s))\|^2ds > r^2\right)\\ & \le \frac{t^2\alpha}{r^2}, \end{split} $$ valid for all $r > 0$ and time $0 < t < r/\sqrt{\alpha}$.

Completely worked-out example

Consider a static random field given by $G(x) = \nabla g(x)$ with $g(x) := w^Tx$, where $w \sim N(0,(1/m)I_m)$ and $a:=\mbox{sign}(w^Tx_0)$. Then integrating (1) gives $x(t) = x_0 - atw$. Thus, $r_t = t\|w\|$ and $c_t = t\|w\|^2$, and there is no shortage of anti-/concentration inequalities in this case. We can take $t^\star = \|x_0\|^2/m \cdot e_m$ for any $e_m \to \infty$ and get the following w.p $1-o(1)$

  • $r_{t^\star} = \mathcal O(t^\star)$.
  • $c_{t^\star} = \Theta(t^\star)$.
  • $g(x(t^\star)) < 0$.

Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}$, which depends continuously-differentiably on $x$, such that $G(x) = \nabla g(x)$ for all $x \in \mathbb R^m$. Further ssume that:

  • $G$ looks thesame every where. $G(x)$, $-G(x)$, and $G(x')$ are equal in distribution for all $x,x' \in \mathbb R^m$. In particular, this implies $G$ is centered., i.e $E[G(x)] = 0$.
  • Moment bounds. There exists $\alpha,\beta,\gamma > 0$ such that for all $x \in \mathbb R^m$,
    • $ E[\|G(x)\|^2] \le \alpha$,
    • $E[\|G(x)\|^4] \le \beta$ (note that this automatically implies the correlation bound $E[\|G(x)\|^2\|G(x')\|^2] \le \beta^2$),
    • $\gamma_1 \le Var[\|G(x)\|^2] \le \gamma_2$.

Fix $x_0 \in \mathbb R^m$ and consider the differential equation

$$ \begin{split} \dot{x}(t) &= -G(x(t)), \;t \in \mathbb R\\ x(0) &= x_0. \end{split} \tag{1} $$ For each $t \ge 0$, define $r_t := \|x(t)-x_0\|$ and $c_t := \int_0^t \|G(x(s)\|^2ds$

Goal. My ultimate goal to prove that there is a time $t^\star \ge 0$ (which may depend on dimension parameter $m \to \infty$) such that $\|x(t^\star)-x_0\|$ and $g(x(t^\star))<0$ with probability $1-o(1)$.

I figured out I could use concentration of measure techniques. This is because, for all $t \ge 0$, $g(x(t)) = g(x_0) - \int_0^t \|G(x(s))\|^2ds$.

Question. How to go about large and small deviation inequalities for $r_t$ and $c_t$ as a function of time $t$ ? More specically, I'd like to how (anti-)concentration inequalities for both $r_t$ and $c_t$.

Softer question. I don't know under what topic such problems fall "concentration of random fields" ?, "oncentration of gradient flows" ?, etc. High-level help and references on this point, would already be very useful.

Observations

Some parts of my problem can be crudely solved. For example, if $u > 0$, then for all time $0 < t < u/\alpha$ we have

$$ P(c_t > u) \le \frac{E[\int_0^t \|G(x(s))\|^2 ds]}{u} = \frac{\int_0^t E[\|G(x(s))\|^2] ds}{u} \le \frac{t\alpha}{u} $$

Similarly, a concentration bound for $r_t$ can be obtained using Hoelder's inequality combined with Markov like so

$$ \begin{split} P(r_t > r) &= P\left(\|\int_0^t G(x(s))ds\|^2 > r^2\right) \le \ldots \le t^2 P\left(\int_0^t \|G(x(s))\|^2ds > r^2\right)\\ & \le \frac{t^2\alpha}{r^2}, \end{split} $$ valid for all $r > 0$ and time $0 < t < r/\sqrt{\alpha}$.

Completely worked-out example

Consider a static random field given by $G(x) = \nabla g(x)$ with $g(x) := w^Tx$, where $w \sim N(0,(1/m)I_m)$ and $a:=\mbox{sign}(w^Tx_0)$. Then integrating (1) gives $x(t) = x_0 - atw$. Thus, $r_t = t\|w\|$ and $c_t = t\|w\|^2$, and there is no shortage of anti-/concentration inequalities in this case. We can take $t^\star = \|x_0\|^2/m \cdot e_m$ for any $e_m \to \infty$ and get the following w.p $1-o(1)$

  • $r_{t^\star} = \mathcal O(t^\star)$.
  • $c_{t^\star} = \Theta(t^\star)$.
  • $g(x(t^\star)) < 0$.
deleted 27 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76
Loading
deleted 27 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76
Loading
deleted 27 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76
Loading
added 164 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76
Loading
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76
Loading