# Minimax computation for classification problems with smooth densities functions

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

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