Constrained Learning with Universally Learnable Concept Classes

Technical Summary: Constrained Learning with Universally Learnable Concept Classes

1. Problem Setting

The paper addresses constrained statistical learning over infinite-dimensional hypothesis classes in a fully non-convex setting. The objective is to minimize a primary prediction risk $R_0(\phi)$ subject to $m$ constraints $R_i(\phi) \leq 0$ (for $i=1,\dots,m$), where risks are expectations of potentially non-convex loss functionals under distinct data distributions $D_i$.

The core difficulty arises from a structural tension between two requirements for a viable learning theory:

1. Strong Duality (Population Level): To guarantee that the Lagrangian dual problem faithfully characterizes the primal constrained problem (zero duality gap), the hypothesis class must be decomposable (closed under measurable splicing). This property, linked to Lyapunov convexity for vector measures, ensures the set of attainable risk vectors is convex even if individual functionals are not. However, decomposable spaces (e.g., $L_p$ spaces) are too large to admit statistical generalization guarantees (vanishing Rademacher complexity) from finite data.
2. Statistical Generalizability (Empirical Level): To ensure learnability from finite samples, the hypothesis class must have controlled statistical complexity (e.g., decaying Rademacher complexity). Standard choices like Reproducing Kernel Hilbert Spaces (RKHS) norm balls satisfy this but are not decomposable, leading to irreducible approximation errors (near-PACC results) where constraint violations cannot be driven to zero regardless of sample size.

Existing approaches often compromise by using a single finite-complexity class, resulting in "near-PACC" guarantees with residuals that do not vanish with more data. This paper seeks to resolve this tension to achieve exact or near-exact learnability without such irreducible residuals.

2. Methodology

The authors propose a variable-complexity framework using dense RKHS classes and Dual Empirical Risk Minimization (DERM).

• Population Problem over Universal RKHS: The population constrained problem is posed over a universal RKHS $\mathcal{H}_K$ that is dense in a decomposable envelope space $\mathcal{G}$ (e.g., an $L_p$ space). While $\mathcal{H}_K$ itself is not decomposable, its density in $\mathcal{G}$ allows the transfer of strong duality properties from $\mathcal{G}$ to $\mathcal{H}_K$ via continuity arguments.
• Empirical Problem with Growing Norm Balls: The learner operates on a sequence of closed norm balls $B_{Q_n} = \{f \in \mathcal{H}_K : \|f\|_{\mathcal{H}_K} \leq Q_n\}$, where the radius $Q_n$ grows with the sample size $n$ such that $Q_n \to \infty$ but $Q_n/\sqrt{n} \to 0$.
  • This ensures the search space eventually exhausts the RKHS (capturing the population solution).
  • Simultaneously, the statistical complexity (Rademacher complexity) of the ball $B_{Q_n}$ vanishes as $O(Q_n/\sqrt{n})$, ensuring uniform convergence.
• DERM Algorithm: The learner maximizes the empirical dual function over non-negative multipliers and then minimizes the empirical Lagrangian over the current ball $B_{Q_n}$.
• Feasibility Analysis: Since non-convexity prevents the Lagrangian from attaining its infimum or guaranteeing that a single predictor realizes the dual subgradient, the authors introduce the closure–realization gap $\varepsilon^\star_\infty$. This geometric constant measures the distance between the superdifferential of the dual function and the set of risk vectors realizable by predictors within the RKHS.

3. Key Contributions

1. Universal (Near-)PACC Learnability:
The paper establishes agnostic universal Probably Approximately Correct with Constraints (PACC) learnability. Unlike distribution-free PAC learning, the sample complexity here is allowed to depend on the underlying distributions (specifically via the Slater margin and Tikhonov complexity), which the authors argue is necessary due to the high expressivity of RKHSs.

• Exact Learnability: When the closure–realization gap $\varepsilon^\star_\infty = 0$ (e.g., under dual differentiability), the learner achieves exact feasibility and optimality.
• Near-PACC Learnability: When $\varepsilon^\star_\infty > 0$, the learner achieves optimality and feasibility within a residual exactly equal to $\varepsilon^\star_\infty$. Crucially, this residual is an intrinsic property of the problem geometry, not an artifact of a fixed modeling choice, and vanishes under benign conditions.

2. Feasibility Certificates without Primal Attainment:
In the fully non-convex regime, the constrained primal problem may not have an attained solution. The paper proves that DERM outputs are asymptotically feasible and near-optimal up to the gap $\varepsilon^\star_\infty$, even without assuming the existence of a primal minimizer. This is achieved through a variational argument on the dual side, utilizing the Levin–Valadier representation of superdifferentials.

3. Explicit Statistical Rates:
The authors derive an explicit, polynomial sample threshold for learning the optimal value. They introduce Tikhonov complexity $T^\varepsilon_n$, defined as the minimal RKHS norm required to reach an $\varepsilon$-optimal Lagrangian level set. Under a standard source condition on the regularization path, they show that $T^\varepsilon_n$ is finite and derive a sample complexity of $O(\varepsilon^{-\max\{4, 2(1-\beta)/\beta\}})$, where $\beta$ characterizes the source condition.

4. Necessity of the Universal Framework:
The paper proves that in the unconstrained specialization of their setting, no distribution-free sample threshold exists due to the unbounded capacity of universal RKHSs. Thus, the universal learning framework (where rates depend on the distribution) is not merely convenient but canonical for dual algorithms over large hypothesis classes.

4. Main Results

• Theorem 1: Establishes that DERM over dense RKHSs with growing norm balls is universally PACC learnable.
  • Part (i): Exact learnability of the optimal value with an explicit threshold.
  • Parts (ii)–(v): Feasibility and near-optimality guarantees controlled by the closure–realization gap $\varepsilon^\star_\infty$.
  • Part (vi): Exact PACC learnability when $\varepsilon^\star_\infty = 0$.
• Corollary 1: Provides an explicit polynomial sample complexity bound under a source condition.
• Lemma 1: Characterizes the closure–realization gap, showing it vanishes if the dual function is differentiable at the optimum.

5. Significance and Claims

The paper claims to resolve the fundamental structural tension between population-level strong duality (requiring decomposability) and finite-sample generalizability (requiring low complexity). By leveraging the density of universal RKHSs in decomposable envelopes, the authors demonstrate that one can inherit the exact duality properties of large spaces while maintaining statistical control through norm-ball restrictions.

The significance lies in moving beyond "near-PACC" results with irreducible residuals. The paper argues that previous residuals were artifacts of fixed parametric approximations, whereas their residual ($\varepsilon^\star_\infty$) is a geometric constant of the problem itself, which provably vanishes in benign geometries. This provides a theoretical foundation for constrained learning in non-convex settings (e.g., deep learning with fairness or safety constraints) without relying on convex surrogates that may fail to preserve constraint feasibility under heterogeneous distributions.

Limitations acknowledged by the authors:

• The recovery condition (Assumption 5) required for feasibility is only verified by a general criterion in the exact regime ($\varepsilon^\star_\infty=0$).
• The agnostic claim for feasibility relies on this assumption, whereas the value learning is attainment-free.
• The DERM procedure is a specification of an idealized algorithm; computational implementation and convergence of practical primal-dual schemes are left for future work.
• The explicit rates rely on a source condition; without it, the threshold is finite but non-explicit.