Skip to main content
MathOverflow

Return to Question

Lipschitz constant: M ==> L
Source Link
dohmatob
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Let $\Theta$ be a subset of a metric space. Suppose $(X_\theta)_{\theta \in \Theta}$ is a random process on $\Theta$ which is $M$$L$-Lipschitz and with the property that there exists constants $A, B>0$ such that for every $\epsilon>0$ and $\theta \in \Theta$, it holds that $P(X_\theta \ge \epsilon) \le A\exp(-B\epsilon^2)$.

Question

  • What upper bounds can be obtained on $P(\sup_{\theta \in \Theta} X_\theta \ge \epsilon)$ in terms of the Lipschitz constant $M$$L$, and the covering number of $\Theta$ ?

  • In case the conditions are not sufficient, what can be added in order to obtain any interesting answers ?

Let $\Theta$ be a subset of a metric space. Suppose $(X_\theta)_{\theta \in \Theta}$ is a random process on $\Theta$ which is $M$-Lipschitz and with the property that there exists constants $A, B>0$ such that for every $\epsilon>0$ and $\theta \in \Theta$, it holds that $P(X_\theta \ge \epsilon) \le A\exp(-B\epsilon^2)$.

Question

  • What upper bounds can be obtained on $P(\sup_{\theta \in \Theta} X_\theta \ge \epsilon)$ in terms of the Lipschitz constant $M$, and the covering number of $\Theta$ ?

  • In case the conditions are not sufficient, what can be added in order to obtain any interesting answers ?

Let $\Theta$ be a subset of a metric space. Suppose $(X_\theta)_{\theta \in \Theta}$ is a random process on $\Theta$ which is $L$-Lipschitz and with the property that there exists constants $A, B>0$ such that for every $\epsilon>0$ and $\theta \in \Theta$, it holds that $P(X_\theta \ge \epsilon) \le A\exp(-B\epsilon^2)$.

Question

  • What upper bounds can be obtained on $P(\sup_{\theta \in \Theta} X_\theta \ge \epsilon)$ in terms of the Lipschitz constant $L$, and the covering number of $\Theta$ ?

  • In case the conditions are not sufficient, what can be added in order to obtain any interesting answers ?

added 59 characters in body
Source Link
dohmatob
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Let $\Theta$ be a subset of a metric space. Suppose $(X_\theta)_{\theta \in \Theta}$ is a random process on $\Theta$ which is $M$-Lipschitz and with the property that there exists constants $A, B>0$ such that for every $\epsilon>0$ and $\theta \in \Theta$, it holds that $P(X_\theta \ge \epsilon) \le A\exp(-B\epsilon^2)$.

Question

  • What upper bounds can be obtained on $P(\sup_{\theta \in \Theta} X_\theta \ge \epsilon)$ in terms of the Lipschitz constant $M$, and the covering number of $\Theta$ ?

  • In case the conditions are not sufficient, what can be added in order to obtain any interesting answers ?

Let $\Theta$ be a subset of a metric space. Suppose $(X_\theta)_{\theta \in \Theta}$ is a random process on $\Theta$ with the property that there exists constants $A, B>0$ such that for every $\epsilon>0$ and $\theta \in \Theta$, it holds that $P(X_\theta \ge \epsilon) \le A\exp(-B\epsilon^2)$.

Question

  • What upper bounds can be obtained on $P(\sup_{\theta \in \Theta} X_\theta \ge \epsilon)$ in terms of the covering number of $\Theta$ ?

  • In case the conditions are not sufficient, what can be added in order to obtain any interesting answers ?

Let $\Theta$ be a subset of a metric space. Suppose $(X_\theta)_{\theta \in \Theta}$ is a random process on $\Theta$ which is $M$-Lipschitz and with the property that there exists constants $A, B>0$ such that for every $\epsilon>0$ and $\theta \in \Theta$, it holds that $P(X_\theta \ge \epsilon) \le A\exp(-B\epsilon^2)$.

Question

  • What upper bounds can be obtained on $P(\sup_{\theta \in \Theta} X_\theta \ge \epsilon)$ in terms of the Lipschitz constant $M$, and the covering number of $\Theta$ ?

  • In case the conditions are not sufficient, what can be added in order to obtain any interesting answers ?

Source Link
dohmatob
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Use covering number to get uniform concentration from pointwise concentration

Let $\Theta$ be a subset of a metric space. Suppose $(X_\theta)_{\theta \in \Theta}$ is a random process on $\Theta$ with the property that there exists constants $A, B>0$ such that for every $\epsilon>0$ and $\theta \in \Theta$, it holds that $P(X_\theta \ge \epsilon) \le A\exp(-B\epsilon^2)$.

Question

  • What upper bounds can be obtained on $P(\sup_{\theta \in \Theta} X_\theta \ge \epsilon)$ in terms of the covering number of $\Theta$ ?

  • In case the conditions are not sufficient, what can be added in order to obtain any interesting answers ?