- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This works analyzes the empirical Rademacher complexities of predictor with a representation maps. They study the effects of learning both representation, and predictors using the same dataset. Their results cover family of representations, and apply to practical deep ReLU networks. Finally, they provide few experiments that corroborate with their theory.
Critical strengths
S1) Studying the effects of same sample representation selection is very relevant problem in deep learning, this work provide rigorous theory on empirical Rademacher complexity that is very essential for generalization theory.
S2) The paper is well organized, and I had no problem following through it.
Critical weaknesses
W1) The paper lacks population Rademacher bounds that are needed to provide final generalization bounds for considered learning problem.
Questions for authors
Q1) Can the authors provide insights whether computing population Rademacher bounds is feasible at-least under certain data distributions?
Q2) Could the authors clarify whether selection cost about picking features on the same data is a generally observed phenomenon or is it specific to Brownian heads? Please support your response with few references.
3 comments
Response to pJNx (2/2): distribution-level bounds and non-Brownian selection
Your Q1: population Rademacher complexity under distributions. For a measurable deterministic representation, define . If and is fixed independently of the i.i.d. sample, the fixed-head bound and Jensen's inequality give $ \mathbb E_S\widehat{\mathcal R}_S(\mathcal F_{z,B}^{(q)}) \leq\frac B{\sqrt n}\mathbb E_S\sqrt{\widehat M_{q,S}(z)} \leq B\sqrt{\frac{M_q}{n}}. $ Thus no Gaussian-input assumption is needed; the stated finite activation moment suffices. For , the class vanishes almost surely on the input distribution and the complexity is zero. For a representation learned independently of the target sample, the same calculation holds conditionally when its conditional activation moment is finite. This is a separately scoped consequence. Averaging a bound for an arbitrary sample-generated family does not by itself supply the population-risk guarantee discussed in Part 1.
Your Q2: is selection cost specific to Brownian heads? No. It is a general union-class phenomenon: $ \mathbb E_\varepsilon\sup_z g_z(\varepsilon) \geq\sup_z\mathbb E_\varepsilon g_z(\varepsilon), $ where is the Rademacher support function of the prediction class for representation . Strict inequality is possible without Brownian heads. On a two-point sample, consider bounded-norm linear-head evaluation classes $ \mathcal A=\{a(1,1):|a|\leq1\},\qquad \mathcal B=\{a(1,-1):|a|\leq1\}. $ Each has empirical Rademacher complexity , because . Their union has complexity 1: the maximum of the two absolute sign sums is 2 for every sign pair. Its selection excess is therefore . This is an explicit non-Brownian example, not a replacement for the paper's model or a claim that every family has positive excess.
What is Brownian-specific is the quantitative link to activation mass, the feature-distance identity, and the layer-cake/Gaussian-projection structure enabling threshold bounds. The new centered-Gram and Gram-root results distinguish variation across representations from richness inside one representation. The finite-pool comparator is generic; the observed positive gaps do not establish a phenomenon exclusive to Brownian geometry or a systematic extra penalty from label dependence.
I thank the authors for clarifying all my questions. I maintain my positive recommendation for this submission.
Response to pJNx (1/2): population guarantees and their scope
Thank you for recognizing the relevance of same-sample representation selection and the organization of the paper. Your population question is important. The revision now separates the available fixed-class consequence from the additional dependence control needed for an arbitrary sample-generated family.
For a deterministic or independently learned representation z, fix B≥0 before the sample and let S∼Pn. With a measurable loss in [0,1] that is Lℓ-Lipschitz in prediction, the fixed-class empirical-Rademacher deviation inequality gives, with probability at least 1−δ, simultaneously for all f∈Fz,B(q), $ R(f)\leq\widehat R_S(f) +2L_\ell B\sqrt{\frac{\widehat M_{q,S}(z)}n} +3\sqrt{\frac{\log(2/\delta)}{2n}}. $ Here n≥1, 0<δ<1, and R and RS are population and empirical loss. The scoped population statement requires measurable predictors and a countable pointwise-dense loss subclass; an independently random representation also requires the conditional and joint measurability conditions. These are not new assumptions silently imposed on the arbitrary-family empirical theorem.
The fixed-representation result is submitted Corollary B.22, now revised Corollary B.25. It applies the standard fixed-class deviation theorem and scalar loss contraction (Mohri, Rostamizadeh and Talwalkar, 2018, Theorem 3.3 and Lemma 5.7). A separate expected/population-complexity calculation is not required for this high-probability step.
For a prespecified representation family, the same argument applies to its whole union loss class, with the corresponding measurability premises. Revised Corollary B.26 gives $ R(f)\leq\widehat R_S(f) +2L_\ell\widehat{\mathcal R}_S(\mathcal F_{\mathcal Z,B}^{(q)}) +3\sqrt{\frac{\log(2/\delta)}{2n}}, \qquad f\in\mathcal F_{\mathcal Z,B}^{(q)}, $ uniformly, so the empirical union bounds can be substituted when their displayed quantities are measurable and finite. This permits representation and head to be fitted on the same sample within that prespecified family; the selected representation need not be independent of the sample.
For an arbitrary family Z(S) generated from the sample, its realized conditional empirical complexity alone does not justify that population step. A containing prespecified class or an appropriate random-class dependence argument is needed. Remark B.27 gives a sample-generated singleton with zero training-state complexity but positive population loss, illustrating why conditioning on the realized family cannot discard that dependence. We retain this limitation explicitly; the arbitrary-family empirical results are not replaced by a fixed-class theorem. See pages 42--44 of the red revision.