• 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.

  • $\begingroup$ 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! $\endgroup$
    – Aryeh
    May 4 at 19:40
  • 1
    $\begingroup$ Indeed. Update: I've droped everything else except $n$ and $r$. $\endgroup$
    – dohmatob
    May 4 at 19:55


Your Answer

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