Return to Question

Let $\mathcal{X}$ be a measurable space, Fix $m,q \in \mathbb{N}^*$,

and $X = (x_1, \dots, x_m) \sim \mathcal{D}_{\mathcal{X}}^m$.

Consider a finite set of functions $\mathcal{F} = \Big \{ h_1, \dots h_q \Big\}$ that takes the values:$\{-1,1\}$

We are interested in the following set:

$$\mathcal{F}(X) = \Big\{(h_1(x_i), \dots h_q(x_i)), i \in [m]\Big\}$$

such that at least two elements of $\mathcal{F}$ disagree on $X$ (disagree on all samples $x_1, \dots, x_m$): That is :

$$\forall l \in [m], \exists i \neq j \in [q]: h_i(x_l) \neq h_j(x_l)$$

I'm interested in the two following questions :

1- what is a tight upper bound on $|\mathcal{F}(X)|$?

2- what can we say about $\mathbb{E}[|\mathcal{F}(X)|]$?

EDIT:

Previously (before the edit), I represented $\mathcal{F}(X)$ in the matrix form by where each row represents a vector belonging to $\mathcal{F}(X)$,so it can be seen as:

$$ \mathcal{F}(X) = \begin{pmatrix} h_1(x_1) & h_2(x_1)& \cdots & h_q(x_1) \\ h_1(x_2) & h_2(x_2)& \cdots & h_q(x_2) \\ \vdots & \cdots & \cdots & \vdots \\ h_1(x_m) & h_2(x_m) & \cdots & h_q(x_m) \end{pmatrix} $$

Counting elements of $\mathcal{F}(X)$ is equivalent to counting different rows in the matrix representation.

Let $\mathcal{X} \subseteq \mathbb{R}^n$ be a measurable space, Fix $m,q \in \mathbb{N}^*$, (the $m$ $x_i$'s are i.i.d and follow distribution $\mathcal{D}$)

and $X = (x_1, \dots, x_m) \sim \mathcal{D}_{\mathcal{X}}^m$.

Consider a finite set of functions $\mathcal{F} = \Big \{ h_1, \dots h_q \Big\}$ that takes the values:$\{-1,1\}$

We are interested in the following set:

$$\mathcal{F}(X) = \Big\{(h_1(x_i), \dots h_q(x_i)), i \in [m]\Big\}$$

such that at least two elements of $\mathcal{F}$ disagree on $X$ (disagree on all samples $x_1, \dots, x_m$): That is :

$$\forall l \in [m], \exists i \neq j \in [q]: h_i(x_l) \neq h_j(x_l)$$

I'm interested in the two following questions :

1- what is a tight upper bound on $|\mathcal{F}(X)|$?

2- what can we say about $\mathbb{E}[|\mathcal{F}(X)|]$?

EDIT:

Previously (before the edit), I represented $\mathcal{F}(X)$ in the matrix form by where each row represents a vector belonging to $\mathcal{F}(X)$,so it can be seen as:

$$ \mathcal{F}(X) = \begin{pmatrix} h_1(x_1) & h_2(x_1)& \cdots & h_q(x_1) \\ h_1(x_2) & h_2(x_2)& \cdots & h_q(x_2) \\ \vdots & \cdots & \cdots & \vdots \\ h_1(x_m) & h_2(x_m) & \cdots & h_q(x_m) \end{pmatrix} $$

Counting elements of $\mathcal{F}(X)$ is equivalent to counting different rows in the matrix representation.

Let $\mathcal{X}$ be a measurable space, Fix $m,q \in \mathbb{N}^*$,

and $X = (x_1, \dots, x_m) \sim \mathcal{D}_{\mathcal{X}}^m$.

Consider a finite set of functions $\mathcal{F} = \{h_1, \dots h_q\}$ that takes the values:$\{-1,1\}$

We are interested in the following set:

$$\mathcal{F}(X) = \Big\{h_1(x_i), \dots h_q(x_i), i \in [m]\Big\}$$

such that at least two elements of $\mathcal{F}$ disagree on $X$ (disagree on all samples $x_1, \dots, x_m$): That is :

$$\forall l \in [m], \exists i \neq j \in [q]: h_i(x_l) \neq h_j(x_l)$$

I'm interested in the two following questions :

1- what is a tight upper bound on $|\mathcal{F}(X)|$?

2- what can we say about $\mathbb{E}[|\mathcal{F}(X)|]$?

EDIT:

Previously (before the edit), I represented $\mathcal{F}(X)$ in the matrix form by where each row represent a vector belonging to $\mathcal{F}(X)$,so it can be seen as:

$$ \mathcal{F}(X) = \begin{pmatrix} h_1(x_1) & h_2(x_1)& \cdots & h_q(x_1) \\ h_1(x_2) & h_2(x_2)& \cdots & h_q(x_2) \\ \vdots & \cdots & \cdots & \vdots \\ h_1(x_m) & h_2(x_m) & \cdots & h_q(x_m) \end{pmatrix} $$

Counting elements of $\mathcal{F}(X)$ is equivalent to counting different rows in the matrix representation.

Let $\mathcal{X}$ be a measurable space, Fix $m,q \in \mathbb{N}^*$,

and $X = (x_1, \dots, x_m) \sim \mathcal{D}_{\mathcal{X}}^m$.

Consider a finite set of functions $\mathcal{F} = \Big \{ h_1, \dots h_q \Big\}$ that takes the values:$\{-1,1\}$

We are interested in the following set:

$$\mathcal{F}(X) = \Big\{(h_1(x_i), \dots h_q(x_i)), i \in [m]\Big\}$$

such that at least two elements of $\mathcal{F}$ disagree on $X$ (disagree on all samples $x_1, \dots, x_m$): That is :

$$\forall l \in [m], \exists i \neq j \in [q]: h_i(x_l) \neq h_j(x_l)$$

I'm interested in the two following questions :

1- what is a tight upper bound on $|\mathcal{F}(X)|$?

2- what can we say about $\mathbb{E}[|\mathcal{F}(X)|]$?

EDIT:

Previously (before the edit), I represented $\mathcal{F}(X)$ in the matrix form by where each row represents a vector belonging to $\mathcal{F}(X)$,so it can be seen as:

$$ \mathcal{F}(X) = \begin{pmatrix} h_1(x_1) & h_2(x_1)& \cdots & h_q(x_1) \\ h_1(x_2) & h_2(x_2)& \cdots & h_q(x_2) \\ \vdots & \cdots & \cdots & \vdots \\ h_1(x_m) & h_2(x_m) & \cdots & h_q(x_m) \end{pmatrix} $$

Counting elements of $\mathcal{F}(X)$ is equivalent to counting different rows in the matrix representation.

Let $\mathcal{X}$ be a measurable space, Fix $m,q \in \mathbb{N}^*$,

and $X = (x_1, \dots, x_m) \sim \mathcal{D}_{\mathcal{X}}^m$.

Consider a finite set of functions $\mathcal{F} = \{f_1, \dots f_q\}$ that takes the values:$\{-1,1\}$

We are interested in the following set:

$$\mathcal{F}(X) = \Big\{f_1(x_i), \dots f_q(x_i), i \in [m]\Big\}$$

such that at least two elements of $\mathcal{F}$ disagree on $X$ (disagree on all samples $x_1, \dots, x_m$): That is :

$$\forall l \in [m], \exists i \neq j \in [q]: h_i(x_l) \neq h_j(x_l)$$

I'm interested in the two following questions :

1- what is a tight upper bound on $|\mathcal{F}(X)|$?

2- what can we say about $\mathbb{E}[|\mathcal{F}(X)|]$?

EDIT:

Previously (before the edit), I represented $\mathcal{F}(X)$ in the matrix form by where each row represent a vector belonging to $\mathcal{F}(X)$,so it can be seen as:

$$ \mathcal{F}(X) = \begin{pmatrix} h_1(x_1) & h_2(x_1)& \cdots & h_q(x_1) \\ h_1(x_2) & h_2(x_2)& \cdots & h_q(x_2) \\ \vdots & \cdots & \cdots & \vdots \\ h_1(x_m) & h_2(x_m) & \cdots & h_q(x_m) \end{pmatrix} $$

Counting elements of $\mathcal{F}(X)$ is equivalent to counting different rows in the matrix representation.

Let $\mathcal{X}$ be a measurable space, Fix $m,q \in \mathbb{N}^*$,

and $X = (x_1, \dots, x_m) \sim \mathcal{D}_{\mathcal{X}}^m$.

Consider a finite set of functions $\mathcal{F} = \{h_1, \dots h_q\}$ that takes the values:$\{-1,1\}$

We are interested in the following set:

$$\mathcal{F}(X) = \Big\{h_1(x_i), \dots h_q(x_i), i \in [m]\Big\}$$

such that at least two elements of $\mathcal{F}$ disagree on $X$ (disagree on all samples $x_1, \dots, x_m$): That is :

$$\forall l \in [m], \exists i \neq j \in [q]: h_i(x_l) \neq h_j(x_l)$$

I'm interested in the two following questions :

1- what is a tight upper bound on $|\mathcal{F}(X)|$?

2- what can we say about $\mathbb{E}[|\mathcal{F}(X)|]$?

EDIT:

Previously (before the edit), I represented $\mathcal{F}(X)$ in the matrix form by where each row represent a vector belonging to $\mathcal{F}(X)$,so it can be seen as:

$$ \mathcal{F}(X) = \begin{pmatrix} h_1(x_1) & h_2(x_1)& \cdots & h_q(x_1) \\ h_1(x_2) & h_2(x_2)& \cdots & h_q(x_2) \\ \vdots & \cdots & \cdots & \vdots \\ h_1(x_m) & h_2(x_m) & \cdots & h_q(x_m) \end{pmatrix} $$

Counting elements of $\mathcal{F}(X)$ is equivalent to counting different rows in the matrix representation.