<ul>
<li><p>Fix <span class="math-container">$d=1$</span>, <span class="math-container">$r \in (0,\infty)$</span> and a neigborhood <span class="math-container">$\Omega$</span> of <span class="math-container">$0$</span> in <span class="math-container">$\mathbb R^d$</span> and let and let <span class="math-container">$W^{1,\infty}(r)$</span> be the Sobolev ball continuously differentiable functions <span class="math-container">$f:\mathbb R^d \to \mathbb R$</span> such that <span class="math-container">$\|f\|_{W^{1,\infty}} := \max(\|f\|_{L^\infty(\Omega)}, \|Df\|_{L^\infty(\Omega)}) \le r$</span>.</p>
</li>
<li><p>Fix <span class="math-container">$\alpha,\beta\in(0,1)$</span> and let <span class="math-container">$f_{\pm 1} \in W^{1,\infty}(r)$</span> be smooth <em>probability density functions</em> in the sense that: (1) <span class="math-container">$f_{\pm 1} \ge 0$</span>; (2) <span class="math-container">$\int_{\mathbb R^d}f_y(x)\,dx = 1$</span> for <span class="math-container">$y=\pm 1$</span>; (3) <span class="math-container">$\int_{\mathbb R^d}\|x\|^\alpha f_y(x)\,dx \le \beta$</span> for all <span class="math-container">$y \in \{\pm 1\}$</span>.</p>
</li>
<li><p>Let <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> be randow variables on <span class="math-container">$\mathbb R^d$</span> and <span class="math-container">$\{\pm 1\}$</span> respectively such that <span class="math-container">$\mathbb P(Y=\pm 1) = 1/2$</span> and conditioned on <span class="math-container">$Y=y$</span> the distirbution of <span class="math-container">$X$</span> has denstity <span class="math-container">$f_y$</span>. Given <span class="math-container">$(w,b) \in \mathbb R^{d+1}$</span>, let <span class="math-container">$C_{w,b}:\mathbb R^{d} \to \{\pm 1\}$</span> be defined by <span class="math-container">$C_{w,b}(x) = sign(x^\top w - b)$</span>, with the convention <span class="math-container">$sign(0) = 1$</span>.</p>
</li>
<li><p>Fix <span class="math-container">$\gamma\ge 0$</span>, and define the following risk functional
<span class="math-container">$$
R_\gamma(C) := \mathbb P(YC(X) \le \gamma).
$$</span></p>
</li>
</ul>
<p>Note that when <span class="math-container">$\gamma=0$</span>, <span class="math-container">$R_\gamma$</span> correspond to usual misclassification error. The parameter <span class="math-container">$\gamma$</span> can be thought of as a margin parameter.</p>
<ul>
<li>Finally, let <span class="math-container">$D_n := \{(X_1,Y_1),\ldots,(X_n,Y_n)\}$</span> be a dataset of <span class="math-container">$n$</span> iid copies of <span class="math-container">$(X,Y)$</span> and define <span class="math-container">$s\in [0,1]$</span> by
<span class="math-container">$$
s := \inf_{\hat C_n}\sup_{f_{\pm 1}} \mathbb E_{D_n}\,[R_\gamma(\hat C_n)]
$$</span>
where the infimum is taken over all algorithms which produce a linear classifier <span class="math-container">$\hat{C}_n$</span> after observing the dataset <span class="math-container">$D_n$</span>.</li>
</ul>
<blockquote>
<p><strong>Question.</strong> <em>What is a good lower-bound for <span class="math-container">$s$</span> as a function of <span class="math-container">$n$</span> and <span class="math-container">$r$</span>, valid for large <span class="math-container">$n$</span> (ignoring constant factors, log n factors, etc.) ?</em></p>
</blockquote>
<p>More generally, how to go about solving such problems ? I'm new to mini-max theory.</p>

CC BY-SA 4.0
2022-05-04T19:40:15.133Z
You're asking for a minimax lower bound in terms of $5$ parameters -- a rather tall order! How about holding all but one or two fixed (presumably, the most interesting/important ones -- but perhaps also just "feasible")?

In other words: Ask the *simplest* question that you don't have an answer for!
Aryeh
CC BY-SA 4.0
2022-05-04T19:55:40.833Z
Indeed. Update: I've droped everything else except $n$ and $r$.
dohmatob
<reference-request><machine-learning><pr.probability><lg.learning><st.statistics>
Minimax computation for classification problems with smooth densities functions
dohmatob
# Minimax computation for classification problems with smooth densities functions

(Asked by: username_0 on 2022-05-04)

* Fix $d=1$, $r \in (0,\infty)$ and a neigborhood $\Omega$ of $0$ in $\mathbb R^d$ and let and let $W^{1,\infty}(r)$ be the Sobolev ball continuously differentiable functions $f:\mathbb R^d \to \mathbb R$ such that $\|f\|\_{W^{1,\infty}} := \max(\|f\|\_{L^\infty(\Omega)}, \|Df\|\_{L^\infty(\Omega)}) \le r$.
* Fix $\alpha,\beta\in(0,1)$ and let $f\_{\pm 1} \in W^{1,\infty}(r)$ be smooth *probability density functions* in the sense that: (1) $f\_{\pm 1} \ge 0$; (2) $\int\_{\mathbb R^d}f\_y(x)\,dx = 1$ for $y=\pm 1$; (3) $\int\_{\mathbb R^d}\|x\|^\alpha f\_y(x)\,dx \le \beta$ for all $y \in \{\pm 1\}$.
* Let $X$ and $Y$ be randow variables on $\mathbb R^d$ and $\{\pm 1\}$ respectively such that $\mathbb P(Y=\pm 1) = 1/2$ and conditioned on $Y=y$ the distirbution of $X$ has denstity $f\_y$. Given $(w,b) \in \mathbb R^{d+1}$, let $C\_{w,b}:\mathbb R^{d} \to \{\pm 1\}$ be defined by $C\_{w,b}(x) = sign(x^\top w - b)$, with the convention $sign(0) = 1$.
* Fix $\gamma\ge 0$, and define the following risk functional
  $$
  R\_\gamma(C) := \mathbb P(YC(X) \le \gamma).
  $$

Note that when $\gamma=0$, $R\_\gamma$ correspond to usual misclassification error. The parameter $\gamma$ can be thought of as a margin parameter.

* Finally, let $D\_n := \{(X\_1,Y\_1),\ldots,(X\_n,Y\_n)\}$ be a dataset of $n$ iid copies of $(X,Y)$ and define $s\in [0,1]$ by
  $$
  s := \inf\_{\hat C\_n}\sup\_{f\_{\pm 1}} \mathbb E\_{D\_n}\,[R\_\gamma(\hat C\_n)]
  $$
  where the infimum is taken over all algorithms which produce a linear classifier $\hat{C}\_n$ after observing the dataset $D\_n$.

> **Question.** *What is a good lower-bound for $s$ as a function of $n$ and $r$, valid for large $n$ (ignoring constant factors, log n factors, etc.) ?*

More generally, how to go about solving such problems ? I'm new to mini-max theory.

**Tags:** reference-request, machine-learning, pr.probability, lg.learning, st.statistics
> **Comments:**
> **username_1**: You're asking for a minimax lower bound in terms of $5$ parameters -- a rather tall order! How about holding all but one or two fixed (presumably, the most interesting/important ones -- but perhaps also just "feasible")?  In other words: Ask the *simplest* question that you don't have an answer for!  
> **username_0**: Indeed. Update: I've droped everything else except $n$ and $r$.  

---

## 0 answers

