Regularization Techniques for Learning with Matrices

By Sham M. Kakade, Shai Shalev-Shwartz, Ambuj Tewari. 2009

219 citations recorded by the source corpus.

There is growing body of learning problems for which it is natural to organize the parameters into a matrix. As a result, it becomes easy to impose sophisticated prior knowledge by appropriately regularizing the parameters under some matrix norm. This work describes and analyzes a systematic method for constructing such matrix-based regularization techniques. In particular, we focus on how the underlying statistical properties of a given problem can help us decide which regularization function is appropriate. Our methodology is based on a known duality phenomenon: a function is strongly convex with respect to some norm if and only if its conjugate function is strongly smooth with respect to the dual norm. This result has already been found to be a key component in deriving and analyzing several learning algorithms. We demonstrate the potential of this framework by deriving novel generalization and regret bounds for multi-task learning, multi-class learning, and multiple kernel learning.

Subfields: Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

An Overview of Multi-task Learning (2018, neutral): “Thenthereare manystudiestoanalyzegeneralizationboundsofdif-ferentMTLapproaches,includinge.g. [7,134]for thefeaturetransformapproach,[135]forthefea-tureselectionapproach,[24,135–138]forthelow-rankapproach,[136]forthetask-relationlearning approach,and[138]forthedirtyapproach.”
A Survey on Multi-Task Learning (2017, methodology): “[224] analyze both batch and online multi-task models with (group) sparse regularizations and trace norm regularization based on a famous inequality originally derived in online learning and the Rademacher complexity.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “[107].”
The Benefit of Multitask Representation Learning (2015, background): “There is a wealth of recent literature on the Rademacher complexity of matrices with spectral regularizers (see e.g. Kakade et al., 2012; Maurer and Pontil, 2013, and references therein), while it is unclear to us how Baxter’s method could be applied if the feature map is constrained by a bound on,…”
Excess risk bounds for multitask learning with trace norm regularization (2012, methodology): “[18] introduces a general and elegant method to derive bounds for learning techniques which employ matrix norms as regularizers.”
Multi-Task Learning and Algorithmic Stability (2015, methodology): “Kakade et al. (2012) investigate the regularization techniques for learning with matrices and apply the analysis to multi-task learning.”
A Vector-Contraction Inequality for Rademacher Complexities (2016, background): “A valuable ressource for this approach is [8].”
Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning (2016, background): “MTL learning guarantees are centered around the notion of (global) Rademacher complexities; notions that were introduced to the machine learning community by [7, 9, 34, 31, 30], and employed in the context of MTL by [45, 46, 26, 48, 47, 49].”
Multitask learning meets tensor factorization: task imputation via convex optimization (2014, background): “On the other hand, the conventional matrix-based multitask learning (MTL) [2, 3, 13, 16] may fail to capture the higher order structure if we consider learning a flat features × tasks matrix and would require at least r samples, where r is the rank of the matrix to be learned, for each task.”
Proximal Stochastic Dual Coordinate Ascent (2012, background): “The function g ( w ) is 1 -strongly convex with respect to the norm (cid:107) · (cid:107) 1 over R d (see for example Kakade et al. [2012]).”
Large-scale Multi-label Learning with Missing Labels (2013, methodology): “Our proofs do not follow either from existing techniques for learning with matrix predictors (for instance Kakade et al. (2012)) or from results on matrix completion with trace norm regularization Shamir & Shalev-Shwartz (2011) due to the complex interplay of feature vectors and missing labels that…”
Compiling Combinatorial Prediction Games (2018, unknown): “By Theorem 3 in (Kakade et al., 2012), it follows that F ∗δ is (1 + δ)d-smooth with respect to the norm ‖ · ‖∞.”
Spectral Filtering for General Linear Dynamical Systems (2018, methodology): “For conciseness, whenever the norm of such a 4-tensor is taken, we establish the notation for the mixed matrix norm These are the straightforward analogues of the matrix norms deﬁned in [KSST12], and appear in the regularization of the online prediction algorithm.”
Active Multi-task Learning via Bandits (2015, methodology): “Kakade [19] introduced a general and elegant algorithm to derive bounds for the method which employs matrix norms as regularization.”