Is the Power of Deep Learning over Linear Models Inherently Distribution Dependent?

For an input distribution $D$ on $\mathcal X$, target $h^*\in\{\pm1\}^{\mathcal X}$, and predictor $\widehat h$, write

$$L_{D,h^*}(\widehat h) :=\Pr_{x\sim D}[\widehat h(x)h^*(x)<0].$$

1. SGD learning versus dimension complexity. Is there a constant $C$ such that the following holds? Let $\mathcal X=\{\pm1\}^n$, $\mathcal H\subseteq\{\pm1\}^{\mathcal X}$, and $\epsilon<1/4$. Suppose there is a fully connected ReLU network with $S$ parameters, a step size $\eta$, and $T$ SGD steps such that, for every input distribution $D$ and every $h^*\in\mathcal H$, standard Gaussian initialization and SGD sampling produce $\widehat h$ with

$$\mathbb E[L_{D,h^*}(\widehat h)]\leq\epsilon.$$

Must

$$\operatorname{dc}(\mathcal H)\leq C,TS$$

hold?

1. SQ learning versus dimension complexity. A tolerance-$\tau$ SQ oracle, on a query $q:\mathcal X\times\{\pm1\}\to[-1,1]$, returns a value within $\tau$ of $\mathbb E_{x\sim D}[q(x,h^*(x))]$. Is there a constant $C$ such that for every domain $\mathcal X$, every class $\mathcal H\subseteq\{\pm1\}^{\mathcal X}$, and every $\epsilon<1/4$, if an $(m,\tau)$-SQ algorithm returns $\widehat h$ satisfying

$$\mathbb E[L_{D,h^*}(\widehat h)]\leq\epsilon$$

for every $D$ and every $h^*\in\mathcal H$, then

$$\operatorname{dc}(\mathcal H)\leq C\frac{m}{\tau^2}?$$

Even a polynomial upper bound, $\operatorname{dc}(\mathcal H)=\operatorname{poly}(S,T)$ or $\operatorname{poly}(m,1/\tau)$, would be of interest, as would a counterexample ruling such a bound out. Other variants may allow dependence on $n=\log|\mathcal X|$ or replace deterministic dimension complexity by the probabilistic variants described in the source.