Excess risk bounds for multitask learning with trace norm regularization

1 Introduction

• The paper bounds the excess risk of empirical risk minimization, the gap between the learned operator’s risk and that of the best operator in the candidate set.The bounds hold with a stated probability because the risk is random.Source: §1 · p. 3
• Trace-norm multitask learning constrains task weight vectors to depend on one another, unlike independent single-task learning.The framework models inputs in a finite- or infinite-dimensional separable Hilbert space, assumes bounded inputs, and uses a bounded Lipschitz loss.Source: §1 · pp. 2–3
• The bounds include both a distribution-dependent form and a data-dependent form, with covariance operators characterizing the data dependence.The theorem’s stated quantities include task-averaged uncentered data and empirical covariance operators.Source: §1 · pp. 3–4
• When data occupy a very low-dimensional subspace, trace-norm multitask learning may offer no benefit over standard single-task bounds.For a one-dimensional support, the bound is always worse than standard single-task bounds; the text gives a contrasting benefit when intrinsic dimension is high, approximation error is small, and K/M is small.Source: §1 · pp. 4–5
• The bounds do not depend on input-space dimension, and the RKHS setting reduces empirical risk minimization to a finite-dimensional problem in nT^2 variables.The RKHS example permits learning large classes of nonlinear functions.Source: §1 · p. 5
• Unequal task sample sizes can be handled by replacing the trace norm with a weighted trace norm; the theorem then uses average sample size.This modification reduces to Theorem 1 when all task sample sizes are equal.Source: §1 · p. 5
• The proof uses Rademacher averages and random-matrix tail bounds, and establishes auxiliary bounds on sums of nonnegative operators.The auxiliary concentration results are described as potentially independently useful.Source: §1 · p. 5

• Foundational multitask analyses use covering numbers and Rademacher averages, while bounds maximal rather than average task risk under a special relatedness assumption.Source: §2 · p. 5
• Matrix completion is related under a simple basis-vector input distribution, but its bounds do not transfer directly because it assumes known inputs and fixed revealed entries per column.Source: §2 · p. 6
• The multitask method in derives fast rates and shared-feature recovery using coordinate sparsity and restricted eigenvalues, assumptions absent here, and a different regularizer.Source: §2 · p. 6
• The dimension-independent bound in has task-count rate T^-1/4 rather than p ln(T)/T.Source: §2 · p. 6
• The matrix-norm method in [18] gives a data-dependent bound, but its related bound (2) is unclear for unequal task sample sizes and diverges as d and T grow together.The section also describes estimating the expectation of (2) to obtain a distribution-dependent bound similar to Theorem 1(i).Source: §2 · p. 6

Notation

• H, H′, and H′′ denote finite- or infinite-dimensional separable real Hilbert spaces, with operators defined through adjoints, ranges, kernels, and positivity.The operator norm is the supremum of ∥Ax∥ over unit-norm inputs.Source: §3 · p. 7
• Compact self-adjoint operators admit eigenvector expansions, and the section defines eigenvalue-based positivity, operator monotonicity of ln, and trace and trace-norm notation.For nonnegative operators, the largest eigenvalue equals the operator norm.Source: §3 · pp. 7–8

Tools

• The proof uses Hölder’s inequality for linear maps in the form |tr(A∗B)| ≤ ∥A∥1∥B∥∞.Source: §3 · p. 8
• Qw denotes the rank-one operator ww∗, also written w ⊗ w, and the covariance operators in Theorem 1 are expressed using this notation.Source: §3 · p. 8
• The technical toolkit includes independent uniform {0,1} random variables, conjugate exponents, and lemmas on scalar inequalities and tail-probability bounds.The section also uses partial integration in a lemma proof.Source: §3 · p. 8

4 Sums of random operators

• Theorem 6 reduces operator concentration to a finite-dimensional invariant subspace containing the operators’ ranges.The section invokes Theorem 5 on the matrices representing the restricted operators.Source: §4 · pp. 9–10
• Theorem 7 applies when independent nonnegative operators have ranges in a fixed finite-dimensional subspace and satisfy a subexponential moment condition.This result assumes a deterministic subspace containing the ranges of all possible realizations; its bound is strongly dimension-dependent.Source: §4 · pp. 9–10
• Theorem 8 is presented as a generalization of Oliveira’s result that removes the identical-distribution assumption and gives smaller constants.The authors attribute the result and its proof essentially to Oliveira, while also citing.Source: §4 · p. 11
• Theorem 8 bounds sums using the random span of realized operator ranges, allowing rank-one operators with infinite-rank expectations by taking d = N.The theorem requires 0 ⪯ A_k ⪯ I and a bound on the dimension of the span of their ranges.Source: §4 · pp. 11–12

5 Proof of Theorem 1

• For unequal sample sizes, the proof uses a weighted trace norm and replaces n in Theorem 1 with the average sample size n̄.Here n̄ = (1/T) times the sum of task sample sizes, so n̄T is the total number of examples; equal sample sizes recover Theorem 1.Source: §5 · p. 13
• The proof begins with a Rademacher-complexity bound for the empirical-to-true risk difference and controls the remaining term using Hoeffding’s inequality.The stated Hoeffding bound holds with probability at least 1 − δ and has a term ln(1/δ)/(2n̄T).Source: §5 · pp. 13–14
• The operator ranges in the heterogeneous-sample argument lie in a subspace of dimension at most n̄T, enabling the use of Theorem 7 after verifying a subexponential moment bound.The proof identifies the moment bound as the content of the following lemma.Source: §5 · pp. 13–15
• Theorem 7 cannot bound the covariance term when its rank is infinite, so the proof instead applies Theorem 8 to the rank-one operators using d = n̄T.This addresses the absence of a finite-dimensional subspace containing the ranges of all the operators in that covariance term.Source: §5 · p. 16