PaperlayerView exact revision on arXiv

Source-linked AI summary

Sample-Weighted End-to-End Trace-Norm Geometry for Multitask Learning

Mahdi Mohammadigohari

arXiv:2609.29520v1cs.LG

TL;DR

Existing multitask generalization analyses often bound shared representations and task-specific functions separately, although such products can lose information. This paper characterizes the sample-size-weighted trace norm of the end-to-end task map through complexity, covariance elimination, and refactorization results. Locked unseen-suite evaluations support the joint geometry, while the least-sampled-quartile comparison with unweighted nuclear regularization remains unresolved.

  • Problem

    Existing bounds often control the shared network and task-specific functions separately, leaving the question of how their joint multitask complexity should be measured.

    Source: §1 · pp. 1–2

  • Method

    The paper studies a sample-size-weighted end-to-end trace norm, characterized through exact empirical complexity, task-covariance elimination, and equivalent intermediate-coordinate refactorization.

    Source: §1 · pp. 2–3

  • Results

    Locked unseen suites support the end-to-end geometry: weighted joint regularization improves average performance, correct task counts help in imbalanced cells, and the low-resource comparison with unweighted nuclear remains unresolved.

    Source: §1 · p. 4, §8 · p. 15

  • Takeaways & Limitations

    The controlled evaluations support the end-to-end sample-size-normalized task map as intrinsic, while leaving its least-sampled-quartile advantage over unweighted nuclear unresolved.

    Source: §1 · p. 4, §8 · p. 15

    The empirical-complexity identity is fixed-n; holding its normalized radius constant as sample size changes does not imply a vanishing rate.

    Source: §4 · p. 7

Abstract

from arXiv · show

Multitask models combine a shared representation with task-specific outputs, but generalization bounds often control the two components separately. Such products can discard relative orientation and cancellation and can change under equivalent transformations of intermediate coordinates even when the represented predictors are unchanged. We study instead the sample-size-weighted trace norm of the end-to-end map from task coefficients to input-space predictors. For its fixed-radius class, we derive the exact empirical Rademacher complexity. The same quantity is characterized by eliminating a positive-definite task covariance after the representation acts and, in finite-dimensional intermediate spaces, by optimizing the separated product over all equivalent invertible refactorizations. Explicit constructions show unbounded orientation and factorization gaps and an exponential depth gap for cancelling linear layers. As a geometric application, finite-to-one Lipschitz shared maps yield an exact Sobolev task Gram matrix determined by multiplicity and local directional distortion. We evaluate the corresponding convex regularizer in two protocol-locked unseen suites. Across 252 paired held-out comparisons, weighted joint nuclear regularization improves average population excess over unweighted nuclear regularization by 0.00764, with a stratified-bootstrap 95% interval [0.00465, 0.01110]. Correct task counts improve average and least-sampled-quartile excess over shifted counts by 0.01072 and 0.02847; all 15 imbalanced rank-suite cells are positive and the balanced effect is zero. Weighted joint nuclear also outperforms weighted Frobenius and independent ridge. The least-sampled-quartile comparison with unweighted nuclear remains unresolved, delimiting rather than contradicting the average advantage. All seven predeclared gates pass.

1 Introduction

The introduction argues that separate representation and task-function bounds can lose alignment and cancellation and can vary with intermediate coordinates even when predictions remain unchanged. It proposes the sample-size-weighted end-to-end trace norm and connects its theory, geometry, and controlled evaluation.

1 Introduction

  • 0.00764 overall improvement in average population excess over unweighted nuclear regularization is reported for weighted joint nuclear regularization.The least-sampled-quartile difference from unweighted nuclear is not statistically resolved.Source: §1 · pp. 3–4
  • The joint method substantially outperforms weighted Frobenius and independent ridge; results are zero when all task counts are equal, while its least-sampled-quartile difference from unweighted nuclear is not statistically resolved.Source: §1 · p. 4
  • The exact complexity formula applies to the full input-space RKHS class, while the experiments test controlled multitask regressions rather than real-data or full-network superiority.The Sobolev identity does not cover arbitrary rank-deficient ReLU layers.Source: §1 · p. 4
  • The sample-size-weighted trace-norm class has an exact empirical Rademacher complexity, also characterized by covariance elimination and equivalent intermediate-coordinate refactorization.The introduction presents the end-to-end norm as the intrinsic multitask complexity for combining representation and task-specific functions.Source: §1 · pp. 2, 4
  • Explicit constructions show that separated products can be unboundedly or exponentially looser, while separate singular-value summaries miss relative alignment.Layerwise norms may multiply exponentially with depth even when neighboring linear layers cancel.Source: §1 · pp. 3–4
  • For finite-to-one Lipschitz shared maps, a Sobolev formula uses multiplicity and local directional stretching to identify the represented task Gram matrix.The introduction also notes that task-only theory is recovered when the shared map is the identity.Source: §1 · pp. 3–4

2 Related work

Prior work studies network complexity through parameter or layerwise bounds, invariant function-space measures, and multitask relations such as output kernels and trace norms. This paper instead studies the trace norm of the full map from task coefficients to input-space predictors, while limiting its claims about architecture coverage and minimax optimality.

Neural-network bounds and Koopman operators

  • Earlier neural-network bounds use norm, margin, path, compression, or Koopman-operator analyses, while this paper does not improve individual layer bounds.Its focus is what is lost by measuring representation and task factors separately.Source: §2 · pp. 4–5

Invariance and function-space complexity

  • Function-space and parameterization-invariant approaches address equivalent representations, but this paper’s operator theorem ranges over all invertible intermediate-coordinate changes, not only those realizable by a fixed architecture.Only a subset of those changes may be realizable within a given architecture.Source: §2 · p. 5

Trace norms, matrix factorization, and multitask learning

  • The paper’s main distinction is measuring the trace norm after the shared representation acts, rather than measuring task heads or output kernels alone.The paper does not claim the trace norm, covariance elimination, or sample-size weighting individually as new.Source: §2 · p. 5

Sobolev composition operators and the area formula

  • The Sobolev task-Gram identity uses the area formula to place multiplicity and directional stretching inside the task Gram matrix.The paper connects that matrix to its statistical end-to-end trace norm.Source: §2 · p. 5

Closest operator-theoretic work

  • The paper differs from related Koopman generalization work by analyzing the full end-to-end predictor map rather than a product of shared-operator and task norms.It does not claim that every architecture fills the full trace-norm class, that the Sobolev result covers arbitrary rank-deficient ReLU layers, or that its empirical penalty is minimax optimal.Source: §2 · p. 6

3 Task-indexed setting and the end-to-end task map

The section sets up task-indexed samples and represents all task predictors together as a map from task coefficients into the input-space RKHS. A shared representation and task functions may factor this map, but the results do not require that factorization to be unique or observed.

3 Task-indexed setting and the end-to-end task map

  • For each task, observations are sampled independently from its task distribution, and the task sample sizes form n with diagonal count matrix D_n.The passages define n=(n_1,…,n_T) and D_n=diag(n_1,…,n_T).Source: §3 · p. 6
  • The setup uses a scalar input-space RKHS and distinguishes operator, Hilbert–Schmidt, and nuclear norms.The kernel is denoted k_0; the passage also introduces positive-definite task matrices and invertible maps on a finite-dimensional Hilbert space.Source: §3 · p. 6
  • A bounded map F from task coefficients to the input-space RKHS collects the predictors, with each task predictor given by f_t=Fe_t.The sample-based class is considered through independent Rademacher variables and task-balanced empirical Rademacher complexity.Source: §3 · p. 6
  • When available, the end-to-end map factors as the Koopman composition operator K_θ times the task map G_g, but the results do not require this factorization to be unique or observed.Source: §3 · p. 6

4 End-to-end trace-norm complexity

For the fixed-radius sample-size-weighted end-to-end trace-norm class, the section gives an exact empirical Rademacher complexity and relates the same geometry to task covariance elimination and intermediate-coordinate refactorization. Its bounds retain fixed-radius and architecture-specific scope conditions.

4 End-to-end trace-norm complexity

  • Theorem 1 gives an exact empirical Rademacher-complexity formula for the fixed-radius end-to-end trace-norm class, pairing that norm with the operator norm of the random sample map.The simpler Hilbert–Schmidt expression can be loose.Source: §4 · p. 7
  • For equal task sample sizes n, the normalized norm is ||F||*/√n, so fixed normalized radius τ corresponds to the expanding unnormalized ball ||F||*≤τ√n.For a fixed predictor map, its normalized radius instead decreases as n^-1/2; a sequence of learned classes needs a controlled radius schedule, localization, or model-selection argument.Source: §4 · p. 7
  • A regularized empirical-risk minimizer has a prespecified radius when λ is fixed before sampling; data-selected λ requires independent validation or an explicit model-selection correction.For task-balanced binary logistic loss with zero logits, the stated loss bound is C_0=log 2.Source: §4 · p. 7
  • Under pairwise-orthogonal sample representers with kernel diagonal κ, the Hilbert–Schmidt relaxation is larger by a factor T in the stated construction.Source: §4 · p. 7

4.1 Exact end-to-end covariance elimination

  • The exact complexity equality applies to the ambient end-to-end class, while a particular Koopman or neural-network class receives an upper bound unless it can realize the functions attaining equality.The radius must be prespecified, selected independently, or handled through an explicit model-selection correction.Source: §4 · p. 8, §4.1 · p. 9
  • Optimizing a positive-definite task covariance after the representation acts gives the end-to-end trace-norm geometry; a singular nonzero weighted Gram matrix yields an unattained infimum over that cone.For F=F_θ,g, the weighted Gram matrix is formed after the representation acts, rather than from terminal task functions alone.Source: §4.1 · p. 8
  • In finite-dimensional intermediate spaces, the joint value is the best separated product over invertible coordinate changes, though an architecture-specific equality requires its balancing change to be realizable or approximable.The represented predictor family can have lower rank than the terminal task map.Source: §4.1 · p. 9

5 Why separate representation and task bounds can be loose

The section shows that separate representation and task summaries can lose relative alignment and change under equivalent refactorizations even when predictions stay fixed. Explicit constructions extend the gap to cancelling deep linear layers, while retaining the distinction between a computable upper bound and a uniformly sharp one.

5 Why separate representation and task bounds can be loose

  • The joint geometry is the best separated product over equivalent invertible intermediate-coordinate changes, and it is invariant under the paired refactorization (K R, R^-1 G).Source: §5 · pp. 9–10
  • Equivalent factorizations of one fixed predictor map can make the separated product arbitrarily loose without changing any prediction.Source: §5 · p. 10
  • Separate singular values alone cannot uniformly characterize joint complexity, because relative singular directions affect the combined geometry.The construction holds the representation singular values and separated products equal across the compared task maps.Source: §5 · p. 10
  • Adjacent expanding and contracting linear-layer pairs can represent the identity while their layerwise norm product grows exponentially with depth.A layerwise product remains a computable upper bound, but cannot be uniformly sharp without restrictions controlling cancellation and relative alignment.Source: §5 · pp. 10–11

6 A geometric application: Sobolev pullbacks of finite-to-one shared maps

For finite-to-one Lipschitz shared maps, the paper derives a Sobolev identity that expresses task geometry through multiplicity and directional distortion. It also identifies scope boundaries for pointwise complexity bounds and extends the geometry to empirical, distribution-weighted Grams.

6 A geometric application: Sobolev pullbacks of finite-to-one shared maps

  • The finite-to-one Sobolev formula sums over every preimage, encoding multiplicity and local directional distortion in the pullback task geometry.For the stated boundedness conditions, composition extends to a bounded operator and the bilinear identity extends to all pairs in H1.Source: §6 · pp. 11–12
  • For Φ(x)=2|x|, multiplicity is 1 and derivative distortion is 4 on the realized image, leaving L2 energy unchanged while multiplying derivative energy by four.Both fields vanish on the unrealized negative half of the target interval.Source: §6 · p. 12
  • The exact Sobolev energy identity applies in dimensions d≥2, but a direct pointwise Rademacher bound requires a smoother RKHS or another evaluation-continuous space.On bounded one-dimensional intervals, H1 has bounded point evaluation and the geometry can be inserted directly into Theorem 1.Source: §6 · p. 12
  • Non-injectivity induces a quotient structure at the terminal level: the joint spectrum depends only on task functions modulo ker K.The factorization through the quotient by ker K is unique and injective.Source: §6 · p. 12
  • The distribution-weighted pullback Gram depends on end-to-end predictors and their input derivatives, so it is unchanged by hidden-coordinate transformations preserving those predictors.An unlabeled sample gives an unbiased estimator of the probability-weighted Gram; recovering the unnormalized Lebesgue Gram under a general sampling density requires importance weights.Source: §6 · pp. 12–13

7 Controlled empirical evaluation

The paper evaluates a convex weighted-joint estimator on two protocol-locked unseen suites of controlled multitask regressions. Weighted joint nuclear regularization improves average population excess over unweighted nuclear, while the least-sampled-quartile comparison remains unresolved.

7 Controlled empirical evaluation

  • The evaluation uses controlled multitask regression with exact predictor maps, convex penalties, and population excess risk, not real-data or full-network benchmarking.The final statistical claims come from two unseen suites whose protocol, solver, paths, metrics, bootstrap, and gates were locked before evaluation.Source: §7 · p. 13

7.1 Estimator and locked protocol

  • The two locked suites contain 252 paired held-out comparisons and vary dimensions, task counts, ranks, imbalance, samples, noise, spectra, angles, and seeds.Seven gates were fixed before evaluation, with the possible low-resource advantage of unweighted nuclear declared as a boundary rather than a gate.Source: §7.1 · p. 13

7.2 Locked confirmatory results

  • 0.00764: weighted joint nuclear improves average population excess over unweighted nuclear regularization, with a 95% interval of [0.00465, 0.01110].The pooled win rate is 68.7%, with positive suite means in replication (0.00217) and structural transfer (0.01174); the corresponding low-resource difference is unresolved at −0.00112 [−0.00336, 0.00124].Source: §7.2 · p. 14, Figure 1 · p. 14
  • 0.01072 and 0.02847: correct counts improve population and least-sampled-quartile excess over shifted counts, respectively.Effects vanish at balance and have positive means in all 15 imbalanced cells for both metrics.Source: §7.2 · p. 14, Figure 2 · p. 14

8 Discussion and conclusion

The discussion frames the end-to-end task map as the relevant geometry and states the scope of the theory and experiments. The supplied population-bound, one-dimensional specialization, and proof passages add specific conditions and arguments.

8 Discussion and conclusion

  • The exact empirical-complexity formula concerns the ambient joint nuclear ball; architecture-specific equality requires a richness argument.The Sobolev theorem covers finite-to-one maps, not arbitrary rank-deficient ReLU layers, and confirmation uses controlled linear regression rather than natural data or an end-to-end trained network.Source: §8 · p. 14

A Population-risk consequence

  • The population-bound theorem assumes each task loss is Lℓ-Lipschitz and takes values in [0, Bℓ], and states a high-probability bound uniformly for every F in B_n(τ).The probability is at least 1−δ for δ∈(0,1).Source: A Population-risk consequence · p. 18

B One-dimensional anchored specialization

  • In the one-dimensional anchored Cameron–Martin specialization, bounded qϕ lets composition extend to a bounded operator, and the pullback identity supplies the multitask Gram matrix used by Theorem 1.The specialization assumes a Lipschitz finite-to-one map fixing the origin with |ϕ′|>0 almost everywhere.Source: B One-dimensional anchored… · pp. 18–19

C.1 Proof of Theorem 1 and Corollary 1

  • The empirical-complexity proof attains equality with a rank-one nuclear-norm extremizer aligned to the sample operator’s top left and right singular vectors.The proof combines this equality with the preceding operator calculations and takes the Rademacher expectation.Source: §C.1 · p. 19

C.2 Proof of Corollary 2

  • The Corollary 2 proof places the realizable class inside B_n(Γρ) using the nuclear norm’s ideal property, then applies Theorem 1.The supplied proof passage gives this containment-and-application argument.Source: §C.2 · p. 20

C.3 Proof of Theorems 2 and 3 and Corollary 3

  • The refactorization proof uses the polar decomposition K=UA; when K is injective, A is invertible and choosing R=A attains the infimum.For non-injective K, the proof instead establishes the infimum through a limiting construction.Source: §C.3 · p. 20

C.4 Proof of Theorem 4

A fixed predictor can have arbitrarily different separated-product values under equivalent intermediate-coordinate changes. The construction keeps the joint norm fixed while the separated product grows quadratically.

C.4 Proof of Theorem 4

  • For the fixed predictor Fe1=e2, the construction changes intermediate coordinates while preserving the end-to-end predictor and its joint norm of 1.The starting maps are K=I2 and Ge1=e2; the transformed task map is G_a=R_aG.Source: §C.4 · p. 21
  • The construction establishes an unbounded gap between the separated product and joint geometry, so no universal reverse constant holds.The end-to-end map remains fixed throughout the rescaling.Source: §C.4 · p. 21
  • a²: the separated product is ∥K_a∥op∥G_a∥*=a² for a≥1, despite the unchanged predictor.The source states that choosing a sufficiently large rules out every universal reverse constant.Source: §C.4 · p. 21

C.5 Proof of Proposition 1 and Corollary 4

The constructions hold the task maps’ marginal singular values and the separated product fixed while changing their alignment, producing different joint geometries. The resulting ratio can be arbitrarily large.

C.5 Proof of Proposition 1 and Corollary 4

  • The two constructions have identical marginal singular-spectrum inputs and the same separated product, but their joint geometries differ.The task maps each have one nonzero singular value equal to one, and the shared map is the same in both constructions.Source: §C.5 · p. 21
  • For the two alignments, the joint norms are a and a^-1, while both separated products equal a.The constructions use G0e1 = e1 and Gπ/2e1 = e2.Source: §C.5 · p. 21
  • The ratio between the joint geometries is a^2, so no statistic based only on the marginal singular spectra can approximate the joint geometry within any finite factor.The construction allows a to be arbitrary.Source: §C.5 · p. 21

C.6 Proof of Theorem 5

The proofs connect cancellations in layerwise norms, Sobolev composition identities, quotient operators, and empirical complexity bounds. Deterministic constructions illustrate how separated layerwise products can diverge from end-to-end geometry.

C.6 Proof of Theorem 5

  • For linear maps, each adjacent cancelling pair is the identity, but multiplying the 2m individual pullback norms gives a^2m.For any task map into the intermediate space, the joint end-to-end map remains that task map.Source: §C.6 · p. 21

C.7 Proof of Theorem 6 and Corollary 5

  • The Sobolev composition proof uses the chain rule and area formula to establish a bilinear identity, then identifies the task Gram matrix by applying it to pairs of task functions.Density gives a bounded extension, identified with ordinary composition almost everywhere.Source: §C.7 · pp. 21–22

C.8 Proof of Corollary 6

  • For anchored one-dimensional functions, the chain rule and area formula establish the quadratic identity on the smooth core, and density extends it to Cameron–Martin functions.The bilinear identity follows by polarization; the stated boundedness condition is qϕ ∈ L∞.Source: §C.8 · p. 22

C.9 Proof of Proposition 2

  • Passing a bounded operator through the quotient by its kernel preserves its operator norm, and the identity for a composed map follows by composition.The quotient norm is defined by taking the infimum over representatives differing by an element of the kernel.Source: §C.9 · p. 22

C.10 Proof of Theorem 7

  • The empirical loss-class bound is proved by ghost-sample symmetrization, contraction, and two McDiarmid applications combined by a union bound.The replacement sensitivity is bounded by Bℓwti for observation (t, i).Source: §C.10 · p. 23

D.1 Deterministic constructions

  • With a = 2 and m cancelling pairs, the end-to-end map is the identity while the product of layer norms grows exponentially with the number of pairs.The deterministic figure panels use closed-form constructions, not fitted models or random samples.Source: §D.1 · pp. 23–24, Figure 3 · p. 23

D.2 Direct-convex implementation

The implementation uses normalized nuclear paths and residual-certified optimization, with numerical preflight preceding a locked evaluation on unseen suites. The reported diagnostics say all seven prespecified criteria and numerical checks pass.

D.2 Direct-convex implementation

  • The nuclear estimator uses a transformed variable, singular-value soft thresholding, and an FISTA step of 0.99/LM; smooth controls use exact taskwise linear systems.Each nuclear path is checked against its zero-solution threshold, and the selected solution must meet a proximal fixed-point residual tolerance.Source: §D.2 · p. 24

D.3 Development and numerical preflight

  • Development studies fixed the solver, paths, and numerical tolerances; residual-certified stopping and adequate path coverage were required before confirmation.No development result was pooled with the confirmatory analysis or counted as independent evidence.Source: §D.3 · p. 24

D.4 Protocol lock, unseen suites, and pairing

  • The protocol fixed the solver, candidate paths, suite configurations, pairing, bootstrap, metrics, and success criteria before either unseen suite was evaluated.Each suite has four interleaved held-out angles and five interleaved development angles.Source: §D.4 · p. 24, Table 1 · p. 25
  • Development angles were used only for regularization selection, while held-out angles were reserved for final effect evaluation.Inputs and observation noise were shared across methods and angles within each fixed suite–rank–imbalance–seed–split stratum.Source: §D.4 · p. 24

D.5 Suite-level and pooled effects

  • Table 2 reports suite-level paired effects, with positive values favoring weighted joint nuclear regularization.The caption identifies the effects’ direction but does not provide their cell values.Source: Table 2 · p. 25

D.6 Numerical diagnostics

  • All seven prespecified criteria and numerical integrity and path-adequacy checks pass; the balanced-cell correct-versus-shifted mean is exactly zero.The pooled bootstrap uses 5,000 replicates and 63 complete strata; the low-resource comparison with unweighted nuclear remains unresolved.Source: §D.6 · p. 25
Loading 2609.29520v1…