Keywords: infinite features, column generation, Gabor features, kernels

We propose a principled framework for learning with infinitely many features, situations that are usually induced by continuously parametrized feature extraction methods. Such cases occur for instance when considering Gabor-based features in computer vision problems or when dealing with Fourier features for kernel approximations. We cast the problem as the one of finding a finite subset of features that minimizes a regularized empirical risk. After having analyzed the optimality conditions of such a problem, we propose a simple algorithm which has the flavour of a column-generation technique. We also show that using Fourier-based features, it is possible to perform approximate infinite kernel learning. Our experimental results on several datasets show the benefits of the proposed approach in several situations including texture classification and large-scale kernelized problems (involving about 100 thousand examples).

Introduction

While several recent works address the problem of automatic feature generation [START_REF] Bengio | Learning deep architectures for AI[END_REF], most of the time these features are still manually crafted based on specific domain knowledge. For instance, in several machine vision applications, features are extracted by appropriate preprocessing of images. One widely used feature extraction method is the Gabor filter [START_REF] Serre | Object recognition with cortex-like mechanisms[END_REF][START_REF] Choi | Simplified gabor wavelets for human face recognition[END_REF]. Similarly, wavelet decompositions or time-frequency representations are frequent feature extraction methods for signal classification problems [START_REF] Lee | Unsupervised feature learning for audio classification using convolutional deep belief networks[END_REF][START_REF] Yger | Wavelet kernel learning[END_REF][START_REF] Neumann | Efficient wavelet adaptation for hybrid wavelet-large margin classifiers[END_REF] . One major drawback of these feature generation methods is that they come along with several continuous parameters and thus they can potentially produce infinitely many features. In most applications, one deals with these large amount of features by selecting beforehand few parameter values of the feature extraction method and from these values, only few features are generated. Our objective in this work is to propose a principled learning framework that is able to deal with infinitely many features, usually induced by continuously parametrized feature extractors, without the need of deciding in advance some set of values for all the parameters. Hence, by adapting the value of these parameters to the classification task at hand, we aim at extracting better discriminative features.

Another motivation for dealing with continuously parametrized features comes from the recent development of random Fourier features for kernel approximation [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF]. This work of Rahimi et al. makes tractable large-scale kernel machines by approximating kernel using explicit feature maps. These mappings are built by first projecting data on a random direction and then by passing the resulting scalar value to a sine function. Instead of randomly building these projection directions before learning, owing to the framework we propose, we are able to learn these directions so that they better suit the data.

In this paper, we introduce a principled framework and an algorithm for dealing with such continuously parametrized features, in a supervised learning setting. The framework we propose is generic as it can deal with several settings, including single and multiple task learning, as well as with different convex and differentiable loss functions. The key point of the algorithm is the use of sparsity-inducing regularizers which allows us to select few features among the possibly infinite ones. The choice of these regularizers is not limited to the classical 1 norm but can also be structured sparsity-inducing ones including the 1 -2 or the 1 -∞ mixed-norms. After having reviewed related works in Section 2, we introduce in Section 3, the problem of learning with continuously parametrized features that we cast as the problem of finding a finite subset of features, minimizing a regularized empirical risk. Owing to the optimality conditions of this problem, we propose, in Section 4 a simple algorithm for its resolution, which iteratively selects novel features among all possible ones by means of randomization. In Section 5, we discuss about two families of parametrized feature maps that are of practical interest : Gabor filtering feature maps and explicit kernel feature maps. For this latter case, we uncover simple relations that show how approximate infinite kernel learning can also be achieved. Our experimental results in Section 6 shows, in several situations, the benefit of learning the feature parameters compared to state of the art approaches. Conclusion and perspectives are discussed in section 7. For a sake of reproducibility, the code used for producing the results in this paper will be made available on the author's webpage.

Related works

The problem of jointly learning feature parameters and a classifier is a problem that has already been addressed but essentially in the kernel learning framework [START_REF] Lanckriet | Learning the kernel matrix with semi-definite programming[END_REF][START_REF] Wang | Gaussian kernel optimization for pattern recognition[END_REF][START_REF] Yeung | Learning the kernel matrix by maximizing a kfd-based class separability criterion[END_REF]. To our knowledge the first works investigating this issue are the ones of Argyriou et al. [START_REF] Argyriou | A dc-programming algorithm for kernel selection[END_REF][START_REF] Argyriou | Learning convex combinations of continuously parameterized basic kernels[END_REF]. Indeed, in order to overcome the need of pre-defining bases kernel in multiple kernel learning (MKL) problem, they propose to learn a convex combination of continuously parametrized kernels. They solved the problem through a greedy algorithm that they further refined by means of a DC algorithm for selecting the novel kernel. In the same spirit, Gehler et al. [START_REF] Gehler | Infinite kernel learning[END_REF][START_REF] Gehler | Let the kernel figure it out: Principled learning of pre-processing for kernel classifiers[END_REF] introduced the so-called Infinite Kernel Learning (IKL) framework which basically aims at solving a MKL problem with an infinite number of base kernels. In practice, they use this IKL framework for learning the parameters of a Gaussian kernel. Algorithmically, the works of Argyriou et al. and Gehler et al. follow a similar trend which consists in iteratively solving a learning problem with a fixed number of already selected kernels and then in selecting a novel kernel. The algorithm we propose for dealing with our learning problem also follows this column generation approach. Independently to Gehler et al. [START_REF] Gehler | Infinite kernel learning[END_REF], Ozogur-Akyuz et. al. [START_REF] Ozogur-Akyuz | Learning with infinitely many kernels via semi-infinite programming[END_REF] have also investigated a theoretical framework for learning with infinitely many kernels.

Methods that alternate between a regularized empirical risk minimization and a feature (or kernel) generation step have already attracted attention especially in the boosting literature [START_REF] Mason | Boosting algorithms as gradient descent in function space[END_REF]. For instance, Demiriz et al. [START_REF] Demiriz | Linear programming boosting via column generation[END_REF] has proposed a similar algorithm for linear programming boosting with 1 penalization. Very recently, Shen et al. [START_REF] Shen | On the dual formulation of boosting algorithms[END_REF] also derived a resembling algorithm by carefully analyzing the dual formulation related to boosting problems. However, most of them only consider the binary classification case and the use of the 1 penalty.

Still in the boosting framework, Chapelle et al. [START_REF] Chapelle | Boosted multi-task learning[END_REF] have recently introduced a boosted multi-task framework that bears resemblance to the one we propose here. As a matter of fact, their work is a particular case of ours. Indeed, their framework only considers the use of the 1 penalty omitting thus some featurebased relatedness between the tasks that can be handled by mixed-norms [START_REF] Obozinski | Joint covariate selection and joint subspace selection for multiple classification problems[END_REF]. From an algorithmic point of view, they solved the boosted multi-task problem by means of an elegant path-following algorithm. While they can also handle infinite number of weak learners, they did not discuss the case of infinite number of features which is somewhat more general and can have broader applicability.

Since the framework we present also deals with multi-task learning, it has strong connections with other works of the literature. In particular, we can mention those of Argyriou et al. [START_REF] Argyriou | An algorithm for transfer learning in a heterogeneous environment[END_REF][START_REF] Argyriou | Convex multi-task feature learning[END_REF][START_REF] Argyriou | When is there a representer theorem? vector versus matrix regularizers[END_REF] which address the problem of learning shared lowdimensional representations in multi-task learning. Similarly to our approach, they aim at learning some features that are jointly of interest for several tasks. In the same trend, the work of Obozinski et al. [START_REF] Obozinski | Joint covariate selection and joint subspace selection for multiple classification problems[END_REF] and Rakotomamonjy et al. [START_REF] Rakotomamonjy | pq penalty for sparse linear and sparse multiple kernel multi-task learning[END_REF] are also contributions that are worth mentioning as they aim at feature selection in a multi-task learning problem. Globally, we can consider our work as an extension of ideas presented in the above ones to the case of infinite number of features.

A piece of work that addresses a problem similar to ours is the one of Rosset et al. [START_REF] Rosset | 1 regularization in infinite dimensional feature spaces[END_REF] which generalizes the 1 penalized regression problem to infinite dimensional feature spaces by means of some probability measures. Algorithmically, they proposed a path-following method for computing a regularization path. While their theoretical framework is very appealing, the resulting algorithm is not practical as the path-following algorithm applies only to some specific feature maps. Furthermore, as stated by the authors themselves, the algorithm proves to be rather numerically unstable.

While the problem we investigate seems similar to those studied in other works and in other contexts, the learning framework and algorithm we propose, contribute to the state of the art by several aspects. Compared to the work of Rosset et al., we propose a novel framework which leads to a simple, stable and tractable algorithm. Furthermore, our framework can handle different convex and differen-tiable loss functions as well as single and multiple task learning. Hence, it can deal with regression and multi-class problems. It is not limited to the use of 1 regularizer as the randomization approach can cope with more complex sparsity-inducing regularizers. The algorithm we derive from this framework is very simple and can deal with large-scale problems. Then, when considering kernel learning, our approach using mixed-norm sparsity-inducing regularizers and explicit feature maps can be proved to be equivalent to an approximate infinite kernel learning. Compared to the genuine IKL algorithm, our method is more efficient and is able to deal with large-scale problems (e.g datasets with about 100 thousands of training examples).

Learning features maps

We now introduce our model for learning with infinitely many features in a single and multiple task supervised learning framework. We also provide the optimality conditions of the resulting optimization problem and derive a simple alternating optimization algorithm for solving this problem.

Framework

Suppose we are given T tasks to be learned from

T different datasets (x i,1 , y i,1 ) n1 i=1 , • • • , (x i,T , y i,T ) n T i=1
, where any x i,t ∈ X and y i,t ∈ Y and n t denotes the t-th dataset size. In the sequel, we note y (t) the vector of components y i,t . For these tasks, we have at our disposal an uncountable set of possible feature maps and we want to use only few of these features in the decision functions of all the tasks, some features being shared by all tasks, some other being specific to some given tasks. This framework which seeks a compromise between specific and shared features corresponds to the one proposed Evgeniou et al. [START_REF] Evgeniou | Regularized multi-task learning[END_REF] and recently named as dirty model multi-task learning by Jalali et al. [START_REF] Jalali | A dirty model for multitask learning[END_REF]. We denote by ϕ any finite set of d feature maps ϕ = {φ θm (•)} d m=1 with d ∈ N and θm being some parameters related to the feature maps. Formally, we thus have ϕ ∈ F with F = {φ θm (•)} d m=1 : d ∈ N, θm ∈ P ∀m P being the parameter space. Similarly to Evgeniou et al. [START_REF] Evgeniou | Regularized multi-task learning[END_REF], we define the decision function of each task, as

f t (x) = d j=1 (w j,t + wj )φ θj (x) + b t
where {b t } are bias parameters, {w i,t } and { wi } are respectively the components of the weight vector w t specific to the task t and w a weight vector shared by all tasks. Note that in our model, the feature parameters {θ j } are learnt from the data. We also define Φ (t) ∈ R n×d as the matrix with elements

Φ (t) i,j = φ j (x i,t
T t=1 nt i=1 L t (y i,t , Φ (t) i,• (w t + w) + b t ) + λsΩs( w) + λpΩp(w 1 , • • • , w T ) (1)
where for any t, L t (•, •) is a convex and differentiable loss function that measures the discrepancy between the true and predicted label of an example for task t, Ωs and Ωp being some sparsity-inducing regularization terms on the weight vectors w and w 1 , • • • , w t and λs, λp being some hyperparameters that balance between the loss function and the regularization terms. Typical possible loss functions are the square, the logistic or the squared-hinge loss functions. Note that for T = 1, by setting λp = ∞, this optimization problem boils down to be the usual single task learning problem. Since we want to select only few features among all possible ones, we have chosen the regularization terms to be sparsity-inducing ones like a 1 or a mixed-norm regularizers, for instance,

Ωs( w) = d j=1 | wj | or Ωp(w 1 , • • • , w T ) = d j=1 T t=1 |w j,t | q ) 1/q = j W j,• q with W ∈ R d×T defined as W = [w 1 w 2 • • • w T ] and W j,• being row j of W.
Note that if the j-th row of W is equal to zero, then the feature Φ (t) j is not involved in the decision function of any task.

Optimality conditions

The key point of the algorithmic derivation comes from the optimality conditions induced by the sparsity-inducing regularizers. Our derivation is applicable for several forms of sparsity-inducing regularizers but for a sake of clarity, we will restrict ourselves to Ωp as 1q mixed-norms (with 1 < q < ∞) either applied to group of features for single task learning or to group of tasks for multiple task learning. Furthermore, for the same reason, we assume that Ωs = w 1 , and omitted the bias terms {b t } in the decision functions.

For a fixed set of features ϕ, the inner optimization problem in Equation ( 1), denoted as the restricted master problem, boils down to be a simple sparse multi-task learning problem. Sparsity is induced by the non-differentiable 1q regularization term, and plays a central role in the derivation of the optimality conditions of the full problem [START_REF] Argyriou | Convex multi-task feature learning[END_REF]. We now provide some necessary and sufficient conditions for a couple of feature matrix and weight vectors to be optimal first for the restricted master problem then for the full problem.

Restricted master and first-order optimality conditions

When we have a fixed number of features, we want to solve the so-called restricted master problem min

w1,••• ,w T , w T t=1 nt i=1 L t (y i,t , Φ (t)
i,• (w t + w))

J +λsΩs( w) + λpΩp(w 1 , • • • , w T ) (2)
We have supposed that the loss functions are convex and differentiable while the sparsity-inducing regularizers are typically convex and non-differentiable. For simplicity, we supposed that

Ωs( w) = j | wj | and Ωp(w 1 , • • • , w T ) = d j=1 T t=1 w q j,t 1/q = i W j,• q with W = [w 1 w 2 • • • w T ]. Partial derivatives of J with respects to w j,m is ∂J ∂w j,m = i Φ (m) i,j L m (y i,m , Φ (m) i,• (wm + w)) L m (•, •)
being the derivative of Lm with respects to its second parameter. Hence, the t-th component of the gradient vector ∇ Wj,• J is (with a slight abuse of notation)

[∇ Wj,• J] t = Φ (t) j L t (y (t) , Φ (t) (w t + w))
Now we can state that a set of vectors w 1 , • • • , w T and w is optimal for our objective function given in Equation (2) with the above regularizers if and only if there exists some subgradients g j ∈ ∂ W j,• q . so that

∇ Wj,• J q ≤ λp if W j,• = 0 ∇ Wj,• J + λpg j = 0 if W j,• = 0 (3)
with q so that 1 q + 1 q = 1 and if and only if

|[∇ w J] j | ≤ λs if w j = 0 [∇ w J] j + λs sign ( wj ) = 0 if w j = 0 (4) with [∇ w J] j = t Φ (t) j L t (y (t) , Φ (t) (w t + w)).

Optimality conditions of the full problem

Now, we are in position for deriving the optimality conditions of Problem (1).

Proposition 1: Suppose that 1 < q < ∞, and q is so that 1 q + 1 q = 1 and consider the feature matrices {Φ (t) } t and the weight vectors {w t } t , w optimizing the related restricted master problem. These vectors and matrices are also optimal for the full problem given in Equation ( 1) if and only if, ∀j = {1, • • • , d}, there exists a vector g j subgradient of ∂ W j,• q so that ∇ Wj,• J( w , {w t }) + λpg j = 0 for j so that ∃t, w j,t = 0 (5)

∇ Wj,• J( w , {w t }) q ≤ λp for j so that ∀t, w j,t = 0 (6)

h q ≤ λp for any φ ∈ ϕ (7)
[∇ wJ ] j + λssign( w j ) = 0 for j so that wj = 0 (8)

[∇ wJ ] j ≤ λs for j so that wj = 0 (9)

T t=1 φ L t (y i,t , Φ (t) i,• ( w + w t )) ≤ λs for any φ ∈ ϕ ( 10
)
where

J( w , {w t }) = T t=1 nt i=1 L t (y i,t , Φ (t)
i,• (w t + w )), the t-th component of the gradient vector ∇ Wj,• J is (with a slight abuse of notation) t) , Φ (t) (w t + w )) and the vector h ∈ R T being the vector which t-th component is

[∇ Wj,• J( w , {w t })] t = Φ (t) j L t (y (t) , Φ (t) (w t + w )) the j-th component of ∇ wJ being [∇ wJ ] j = t Φ (t) j L t (y (
h t = φ L t (y (t) , Φ (t) (w t + w )).
Proof Let us first show that if {Φ (t) } t and the weight vectors {w t } t , w are optimal for the full problem then the above conditions hold. Note that in the following, we only develop the arguments for the optimality conditions related to the vectors {w t } t as those related to w are similar. The first two inequalities directly come from the optimality conditions of the restricted master problem. These conditions are easily derived by writing that 0 belongs to the subdifferential of the nonsmooth objective function. In order to prove the third inequality, we rather show that if there exists a φ for which this inequality [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] is not verified then {Φ (t) } t , {w t } t and w are not optimal. Indeed, if such a φ exists, we can build Φ(t) = [Φ (t) φ] and ŵt = [w T t 0] T for all t. According to the optimality conditions of the restricted master problem associated to Φ(t) , ŵt are not optimal. Hence, reoptimizing this problem leads to a decrease of the objective value. Thus, {Φ (t) } t , {w t } t and w were not optimal for the full problem since Φ(t) can induce a lower objective value.

Let us now prove that conversely if these conditions hold then, {Φ (t) } t , {w t } t and w are optimal for problem [START_REF] Argyriou | Convex multi-task feature learning[END_REF]. Again owing to the optimality conditions of the restricted master problem, satisfying the inequalities 5, 6, 8 and 9 means that {Φ (t) } t , {w t } t are optimal for this restricted master problem. Thus, it suffices to show that when adding any of the feature φ for which the third and sixth inequalities hold into the active feature set, no decrease in objective value can be obtained. This latter point naturally stands since building Φ(t) = [Φ (t) φ] and re-optimizing the associated restricted master problem will lead to the optimal solutions with {[w T t 0] T } t and [ w T 0] T which means that the objective value has not decreased.

Algorithm 1 Feature generation approach for solving problem (1).

1: set ε > 0 2: k ← 0 3: Set Φ (t) = [ ]
for every task; % empty matrix 4: Set wt = 0, w = 0, bt = 0 for every task 5: repeat 6:

φ ← feature for which constraints ∇ W j,• J( w, {wt}, {bt}) q ≥ λp + ε or

| T t=1 φ L t (y i,t , Φ (t) i,• ( w + wt) + bt)| > λs + ε 7: if φ = ∅ then 8: Break 9:
end if 10:

for every task t, Φ (t) ← [Φ (t) φ] ; % feature concatenation 11:

{wt}, {bt}, w ← result of the restricted master problem with feature matrix {Φ (t) } 12:

if stopping criterion reached then 13: Break 14:

end if 15:

k ← k + 1 16: until maximal number of iterations k is reached

Feature generation algorithm

The optimality conditions of problem (1) suggest a strategy based on feature generation for its resolution. Indeed, it seems reasonable to consider an iterative approach where at each iteration, one solves the restricted master problem with the current feature matrices {Φ (t) }, looks for a feature that violates either constraint [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] or [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF], updates the feature matrices with that feature and re-optimizes. Our algorithm will be based on this iterative scheme which involves (i) a procedure that solves the restricted master problem (ii) a procedure that returns a violating constraint feature. Before delving into the implementation details of these two steps, we provide more insights into this algorithm. We first show under which hypotheses the proposed algorithm is able to solve problem given in Equation (1).

Proposition 2: Suppose that the restricted master problem is solved exactly, then if we are also able to solve the problems max φ ∈ϕ, φ =1 h q and max

φ ∈ϕ, φ =1 T t=1 φ L t (y i,t , Φ (t) i,• ( w + w t )) (11)
exactly then, our algorithm solves our learning problem with a pre-defined tolerance ε > 0 on the non-active feature constraints [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] or [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF], which means that we have

h q ≤ λp + ε and T t=1 φ L t (y i,t , Φ (t) i,• ( w + w t )) ≤ λs + ε h being the vector of components h t = φ L t (y (t) , Φ (t) (w t + w ))
. Furthermore that ε-approximate solution provided by the algorithm involves a finite set of features.

Proof For proving this lemma, we just need to show that our algorithm decreases the problem's objective value at each iteration and thus, since the objective value is lower bounded, in the limit the algorithm's output will satisfy the problem's optimality conditions. Consider a current iteration with active feature set {Φ (t) }, with d features, and optimal related weights {w t } and w . Now, if we optimize conditions [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF] and get objective values respectively lower than λp + ε and λs + ε, then {Φ (t) } t , {w t } t and w are optimal for the full problem with a tolerance ε. If one of the objective value of conditions [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF] is greater than λp + ε or λs + ε, then adding φ, the feature that maximizes violated constraints, to the active feature set leads to a strict decrease in the objective function.

Remark that this proposition tells us that our algorithm provides us an approximate solution and as the iterations go, under the assumption of proposition 2, resulting {w t } and w converge towards the solution of the problem. However, it does not give us any guarantee about whether the solution can be attained with a finite number of features. This problem is more intricate and we have left it for future works. We can however highlight that in the context of infinite kernel learning, under some mild assumptions on the kernels, it is possible to show that the problem solution only involves a finite number of kernels. We thus conjecture that similar conditions can be brought out for our learning problem [START_REF] Argyriou | Convex multi-task feature learning[END_REF].

The next proposition tells us that the proposed algorithm improves the objective value of problem (1) at each iteration as long as the feature φ added to the active set violates constraints [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] or [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF].

Proposition 3: Supposing that the restricted master problem is solved exactly, then at a given iteration k, adding to the the feature matrices {Φ (t) } any feature that violates constraints [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] or [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF] leads to a decrease in objective value of the full problem [START_REF] Argyriou | Convex multi-task feature learning[END_REF].

Proof Suppose that at a given iteration, we have solved the minimization over w for {Φ ((t) } t and obtained the optimal weight vector {w t } and w . Consider φ ∈ ϕ so that φ violates either its constraints [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] or [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF] and define for the next iteration, { Φ(t) = [Φ (t) φ]}, {w † t = [w t 0]} t and w † = [ w 0]. Note that these weight vectors {w † t } and w † are not optimal for { Φ(t) }. Indeed φ also violates these constraints 7 or 10 since for any task t, we have L t (y (t) , Φ (t) (w t + w )) = L t (y (t) , Φ(t) (w † t + ŵ † s )) thus re-optimizing over the w would lead to a decrease in the objective value.

Note that the hypothesis regarding the restricted master problem seems not to be necessary for the proof. However, it plays a central role since it guarantees that the optimality conditions given in Proposition 1 are satisfied and thus they guarantee that {w t } and w are optimal for the current {Φ (t) }. In practice, depending on how loose the optimality conditions of the restricted master problem are, it may occur that the objective value of the full problem does not decrease. In such situations, it is possible to re-optimize the restricted master problem with tighter optimality conditions.

On the algorithmic implementation

After having presented the learning framework, the algorithm and analyzed its properties, we discuss in this section the implementation of the restricted master problem and explain how violating constraints can be found.

ADMM algorithm for the restricted master problem

The restricted master problem can be considered as a classical multi-task learning problem with sparsity-inducing regularizers. Several algorithms for solving such a problem have been recently proposed in the literature, including proximal methods [START_REF] Chen | Accelerated gradient method for multi-task sparse learning problem[END_REF] or path-following approach [START_REF] Obozinski | Joint covariate selection and joint subspace selection for multiple classification problems[END_REF]. While a proximal method suits to our problem, we have chosen to consider another algorithm based on alternating direction method of multipliers (ADMM) [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]. This choice is essentially motivated by two reasons. First, ADMM approaches integrate some second-order information in the alternate minimization approach, while taking advantage of the simple proximal closed-form solutions resulting from the regularizers. In practice, ADMM proves to be significantly faster than FISTA especially when the number of features is small, which is a frequent situation for our restricted master problem. Secondly, ADMM provably converges even for proximal operators which do not have a closed-form solutions, which is the case for 1 < q < ∞ and q = 2.

In the sequel we detail the different steps of the ADMM algorithm used for solving our restricted master problem. However, we first provide a brief review on ADMM approach.

Generality

The ADMM approach [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF][START_REF] Eckstein | On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators[END_REF] is an algorithm that solves a general problem of the form :

min x,y f (x) + g(y) (12)
st.

Ax + By = c (13)
where the variable is (x, y) ∈ R n1×n2 , f : R n1 → R and g : R n2 → R are given convex functions, A ∈ R m×n1 and B ∈ R m×n2 and c ∈ R m . ADMM is based on a augmented Lagrangian approach where the Lagrangian is :

L(x, y, z) = f (x) + g(y) + z T (Ax + By -c) + ν 2 Ax + By -c 2 ,
z ∈ R m being the multiplier associated to the linear constraints and ν > 0 a predefined parameter balancing the violation of the linear constraints. Augmented Lagrangian method [START_REF] Nocedal | Numerical optimization[END_REF] suggests to iteratively minimize the Lagrangian function with respects to x and y and then to update the Lagrangian multiplier z with a dual ascent. Instead, ADMM proposes to take into account the special structure of the problem and to minimize the Lagrangian serially with respects to x and y.

In practice, this leads to an algorithm which general scheme is of the form

x (k+1) ∈ arg min x L(x, y (k) , z (k) ) (14)
y (k+1) ∈ arg min y L(x (k+1) , y, z (k) ) (15)
z (k+1) = z (k) + ν(Ax + By -c) ( 16
)
When B is the identity matrix, it has been proved [START_REF] Eckstein | On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators[END_REF] that under very mild conditions, this algorithm converges to a solution of problem 12. A more general convergence result, involving less restrictive conditions on B has been recently provided in the work of Mota et al [START_REF] Mota | A proof of convergence for the alternating direction method of multipliers applied to polyhedral-constrained functions[END_REF].

Application of the ADMM to the restricted master problem

When the feature matrices are fixed, we look at the solution of the following problem :

min w1,••• ,w T , w T t=1 nt i=1 L t (y i,t , Φ (t) i,• (w t + w)) + λsΩs( w) + λpΩp(w 1 , • • • , w T ) (17)
Before applying the above-described ADMM algorithm, we perform some variable splitting in order to decouple the impact of the different losses and regularizers on the variables to optimize. Supposing that all loss functions L t are a squared Hinge loss, then problem 17 is equivalent to min {wt},{ut},{at}, w,ũ,{bt}

T t=1 L t (a t ) + λsΩs(ũ) + λpΩp(u 1 , • • • , u T ) st. a t = 1 -Y t (Φ (t) (w t + w) + b t ) ∀t ũ = w ũt = wt ∀t (18)
with the overload notation L t (a) = max(0, a) max(0, a) with the max being applied component-wise to the vector a and each a t being a vector of R nt and Y t = diag(y t ). Discussions about the use of other loss functions are reported in the sequel. Now, we can proceed with the augmented Lagrangian which writes :

L = T t=1 L t (a t ) + λsΩs(ũ) + λpΩp(u 1 , • • • , u T ) (19)
+ t µ t (1 -Y t (Φ (t) (w t + w) + b t ) -a t ) + t ξ t 2 1 -Y t (Φ (t) (w t + w) + b t ) -a t 2 + t ν t (w t -u t ) + t η t 2 w t -u t 2 + ν ( w -ũ) + η 2 w -ũ 2
where µ t ∈ R nt and ν t ∈ R d . Now that the Lagrangian has been formed, the ADMM algorithm consists in optimizing this Lagrangian wrt to each primal variable and then in updating the dual variables.

Optimizing a t One of the advantage of the ADMM approach and the variable splitting we choose is that the problem nicely decouples. Hence, optimizing the Lagrangian wrt to a t simply boils down to

min at L t (a t ) + µ T t (z t -a t ) + ξ t 2 z t -a t 2 (20)
with z t = 1-Y t (Φ (t)
i,• (w t + w)+b t . After some simple "gather the terms" algebras, this problem is actually equivalent to :

min at ξ t 2 a t -(z t + 1 ξ t µ t ) 2 + L t (a t ) (21)
Regularizer Ωp

prox λΩ V Ωp(W) = t wt 1 sign(vt)(|vt| -λ) + Ωp(W) = t wt 2 (1 -λ v t ) + vt Ωp(W) = d j=1 W j,• 1 sign(W j,• )(|W j,• | -λ) + Ωp(W) = d j=1 W j,• 2 (1 - λ W j,• ) + W j,•
Table 1 Example of regularizers and their proximal operators which is the proximal operator of L t applied to the vector z t + 1 ξt µ t . Hence, at optimality we have

a t = prox 1 ξ t Lt(•) (z t + 1 ξ t µ t ) (22)
which can be simple to obtain if the loss function admits a closed-form proximal operator.

Optimizing u t and ũ By proceeding in the same way, the solutions of the Lagrangian minimization with respects to u t and ũ, are:

u t = prox λp η t Ωp (w t + 1 η t ν t ) and ũ = prox λs η Ωs ( w + 1 η ν) ( 23
)
where we made the hypothesis that the proximal operator of Ωp decouples with respect to the vectors {u t } t . Note that if the regularizer Ωp does not decouple then the proximal operator would have involved matrix U as a variable duplicate and W and ν t would have been matrices. Table 1 presents some usual proximal operators that are of interest for our works.

Optimizing w t and b t This minimization problem can be written as:

min wt,bt µ T t (1 -Y t (Φ (t) (w t + w) + b t ) -a t )+ ξt 2 1 -Y t (Φ (t) (w t + w) + b t ) -a t 2 + ν T t (w t -u t ) + ηt 2 w t -u t 2 (24
) For the subsequent derivations, we drop the task-related subscript t. First-order optimality conditions with respects to w t and b t are :

-Φ T Y T µ + ν -ξΦ T Y T 1 + ξΦ T Φ(w + w) + ξbΦ T 1 + ξΦ T Y T a t -ηu + ηw = 0 -µ T Y T 1 -ξ1 T Y T (1 -a) + ξ1 T Φw + ξ1 T 1b = 0 (25)
which can be satisfied by solving the following set of linear equations

ξΦ T Φ + ηI ξΦ T 1 ξ1 T Φ ξ1 T 1 w b = Φ T Y T µ -ν + ξΦ T Y T (1 -a) + ηu -ξΦ T Φ w µ T Y T 1 + ξ1 T Y T (1 -a) (26)
We can remark that these linear equations have to be solved several times during the process of the ADMM iterations. However, only the second member changes through a and u along these ADMM iterations. Hence, one can compute the inverse of the left-hand side only a single time so that subsequent system resolutions only reduce to one matrix multiplication.

Loss function

Lt(at) at square loss a T t at at = Yt -Φ (t) (wt + w) -bt square hinge loss (at) T + (at) + at = 1 -Yt(Φ (t) (wt + w) -bt) hinge loss

1 T (at) + at = 1 -Yt(Φ (t) (wt + w) -bt)

Loss function Lt(at) prox 1 ξ L t z square loss a T t at 1 1+2/ξ z square hinge loss (at) T + (at) + 1 1+2/ξ z if z ≥ 0 z otherwise hinge loss 1 T (at) +    z -1 ξ 1 if z ≥ 1 ξ 1 z if z ≤ 0 0 otherwise
Table 2 Loss functions Lt(•), corresponding form of at and proximal operator of the losses. Note that the Hinge loss does not apply to our framework since it is not differentiable.

Optimizing w Minimizing the Lagrangian with respect to w is achieved in a similar way as above. Indeed, the minimization problem is

min w t µ T t (1 -Y t (Φ (t) (w t + w) + b t ) -a t )+ t ξt 2 1 -Y t (Φ (t) (w t + w) + b t ) -a t 2 + νT ( w -ũ) + η 2 w -ũ 2 (27)
Deriving the objective function and equating the derivative to 0 leads to the following equation

t ξ t Φ (t) T Φ (t) + ηI w = t Φ (t) T Y T t µ t + ξ t Φ (t) T Y T t (1 -a t ) - t ξ t Φ (t) T Φ (t) w t - t ξ t Φ (t) T 1b t -ν + ηũ (28)
which is a simple linear system to solve.

What if we change the loss function? The above derivations focus on squared Hinge loss and binary classification problem. A change in the loss function would impact two things in Equation ( 18) : the form of L t (•) and the equality constraints giving the relation between a t , w t , w and b t . The former would impact the resolution of {a t } in the proximal operator defined in Equation 22. This means that for loss functions which proximal operators are simple, the algorithm follows the same flow except that the closed-form proximal computation changes. For some other loss functions, typically the square loss, the equality constraints defining a t take the following form :

a t = Y t -(Φ (t) (w t + w) + b t ) ∀t
Consequently, the linear systems given in Equations ( 27) and ( 28) involving w t , w, b t also take slightly different forms that we have not clearly specified but that can be easily derived from simple algebras. Table 2 recaps some typical loss functions L t (•), the form of the related a t and the resulting proximal operators.

Algorithm 2 ADMM for our restricted master problem update w by solving the linear system defined by Equation (28) 8:

update {at} using the proximal operators defined in Equation ( 22). 9:

update {ut} and ũ using the proximal operators defined in Equation ( 23). 10:

% Updating Lagrangian multipliers 11:

µt ← µt + ξt(zt -at) ∀t 12:

νt ← νt + ηt(wt -ut) ∀t 13:

ν ← ν + η( w -ũ) ∀t 14: until stopping criterion is met

Discussions on complexity

All the steps needed for solving the restricted master problem with d features are summarized in Algorithm 2. We can note that the algorithm is rather simple and involves essentially two computationally heavy steps : the two linear systems that have to be solved at each iteration. In a ADMM approach, it is difficult to evaluate the number of iterations needed before convergence as this number depends on the choice of ξ t and {η t }. From experience, we can state that about few hundred iterations are typically needed before convergence, for the values of ξ t and {η t } used in the experiments. Now, let us have a closer look at the computational complexity needed for each iteration. We first remark that for the linear equations ( 26) and ( 28), the involved matrices do not change over the iterations and thus their inverses can be pre-computed at the cost of O(d 3 ). Once this is done, solving the systems at each iteration consists only in a matrix-vector multiplication which takes O(d 2 ). The other steps make use of proximal operators. If we consider proximal operators that are simple enough as those considered in Tables 1 and2, we can suppose that each component-wise operation in these operator can be computed in O(1). Accordingly, updating {a t }, {u t } respectively takes O( t n t ) and O(dT + d). Hence, the major computational burden of this ADMM algorithm for solving our restricted master problem is the matrix inversion needed for the linear systems. Note however, that by construction, as we add one feature at a time in the global Algorithm (1), d typically remains small. We can also highlight that this algorithm is linear in the number of examples and this allows us to tackle large-scale problems.

Finding a violating constraint

For finding the feature which violates the most its constraints, we need to solve the two optimization problems given in Equation [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]. For some specific cases, these problems can be simple and may have a closed-form solutions. This is the case for the first problem when q = 2 and a square loss function is considered. However, in a general situations, these problems may be non-convex and difficult to optimize notably because of the mixed-norm structure and the non-linearities induced by the feature maps. Fortunately, Proposition 3 suggests us that any feature that violates one of the two constraints in [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF] can be integrated to the active feature set {Φ (t) } and re-optimizing the restricted master problem using these novel feature matrices would lead to a decrease in objective value. Hence, instead of optimizing problems [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF], it suffices to find an approximate maximum of these problems which can be simply done by randomizing over a small number of feature parameters. For this purpose, our strategy consists in sampling kr random feature parameters and then in looking for the best feature, according to Equations [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF], among those kr features. This conceptually simple heuristic allows us to avoid a difficult optimization problem and besides it is rather cheap. Indeed, it can be easily shown that the computational cost of evaluating kr features according to Equations ( 11) is about O(krnT ) where n = t n t .

5 Some useful feature maps and discussions

In this section, we will describe some examples of feature maps that are continuously parametrized and that are of practical interest.

Gabor features

Because they provide a simple and good model of the cortical simple cell receptive fields of vision system [START_REF] Serre | Object recognition with cortex-like mechanisms[END_REF], Gabor filters are frequently used in computer vision and pattern recognition problems as a feature extractor, especially for texture recognition problems [START_REF] Bianconi | Evaluation of the effects of gabor filter parameters on texture classification[END_REF][START_REF] Clausi | Designing gabor filters for optimal texture separability[END_REF]. Typically, a Gabor filter is of the form

F (z, y) = exp - z 2 0 2σ 2 z - y 2 0 2σ 2 y cos(2πf 0 z 0 )
with z 0 = z cos θ + y sin θ and y 0 = -z sin θ + y cos θ, and σz, σy, f 0 and θ being some parameters that control the Gabor filter scale, frequency and orientation.

For producing features from an image, one first computes the convolution of the image with a set of these Gabor filters (with varying parameters), then obtains the features as the collection of the filtering response on all image points or on pre-specified landmarks of the image, or even as the average or the maximum of the filter responses over the image or part of the image. In most applications dealing with Gabor filters, in order to keep the feature extraction step tractable; these filter parameters are restricted to few values : for instance typically, 4 or 8 orientations θ are considered. Such an approach would naturally lead to a lack of optimality in the Gabor filter response as soon as the image characteristic does not fit to the filter banks. Hence, being able to learn with all possible Gabor filters should overcome this issue and should result in improved performances of Gabor feature based recognition systems.

Explicit kernel feature maps

Recent works have proposed methods for approximating well-known and frequently used kernels such as the intersection kernel [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF] or the Gaussian kernel [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF]. For instance, Rahimi et al. have shown that under some mild conditions, a shift-invariant kernel like the Gaussian one can be arbitrarily well approximated by a kernel of the form

K(x, x ) = 1 D D j=1 zv j (x) T zv j (x )
with {zv j (•)} D j=1 being some Fourier feature maps of the form

zv(x) = [cos(v T x) sin(v T x)]
where v is a direction vector that has been sampled from the Fourier transform of that shift-invariant kernel, and D being the number of involved feature maps.

Instead of pre-defining some vectors {v j } before learning as suggested in [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF], we propose to apply our framework for selecting better random directions {v j }. In practice, we sample k R number of vectors v according to the probability distribution related to the target kernel (e.g the Gaussian kernel), compute the features zv from these vectors and select among them the one that violates the most its constraints. Note that since zv is itself composed of two related features, these two features should form a group of features in the mixed-norm regularization term of our optimization problem.

Low-rank kernel approximation interpretation: Because, we are using a sparsity-inducing norm in our learning framework, we actually select a subset of feature maps. For large values of the regularization parameters λp and λs, only few features {zv j } j will be kept in the final decision functions. Hence, if the number of selected features is lower than the number of training examples, then, we can interpret the resulting kernel approximation as a low-rank kernel approximation, since the Gram matrix of entries:

[ K(xn, xm)]n,m = 1 Nz Nz j=1 zv j (xn) T zv j (xm)
∀n, m will be of rank Nz, Nz being the number of features kept by our algorithm. This low-rank kernel approximation is of interest in several ways : it makes large-scale kernel machines tractable and the resulting model becomes cheap to evaluate since only few features are in play. Our experimental results will support these statements.

Approximate infinite kernel learning: the work of Rahimi et al. [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF] also shows that approximating different families of shift-invariant kernels can be easily done by only changing the probability distribution from which the vectors v are sampled. Hence, it becomes possible to perform approximate multiple kernel learning. Indeed, since according to Rahimi et al., a shift-invariant kernel can be approximated by

1 D D j=1 zv j (x) T zv j (x )
it is easy to show (owing to linearity of the Fourier transform) that a convex combination of pre-defined shift-invariant kernels M m=1 dmkm(x, x ) can be approximated by

m D j=1 dm D z m vj (x) T z m vj (x )
with z m vj (•) being the explicit feature map of direction v j related to kernel km(•, •). Furthermore, the uniform convergence property of the Fourier features presented by Rahimi et al. still applies to this sum of kernels.

According to these simple findings, it becomes easy to perform approximate infinite kernel learning. Indeed, in practice, we can do this approximation by randomly selecting a Gaussian kernel bandwidth, and by randomly generating groups of features zv(•) related to that kernel. Then, among the groups of features that have been generated, we keep the one that maximizes the constraint violations [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] or [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF] and re-optimize the restricted master problem. This procedure is then re-iterated until a stopping criterion is met.

Formally, for this approximate IKL, in a single task learning case, an 1 -∞ mixed-norm penalty has to be considered in order for the features from same group to have the same weighting coefficients. In practice, the choice of the mixed norm has few impacts.

One pass mini-batch feature selection interpretation

When dealing with continuously parametrized features, instead of using our infinite set of features framework, it would have been possible to generate a huge but finite number of features and then perform a classical 1 -like feature selection. From this point of view of very high-dimensional feature selection, we can understand our algorithm as a method performing one-pass mini-batch feature selection; minibatch because we process a chunk of features at a time and select the one that maximizes constraint violation and one-pass because, due to the randomization and the continuous parametrization of the features, with high probability, a given feature will be visited only a single time during the randomization, although a very similar feature can be randomly drawn. As in the work of Bordes et al. [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF] which also considers one-pass optimization, our experiments show that when using an infinite or a very large number of features, a one-pass feature selection optimization approach does not induce any loss of performance while being computationally more efficient.

Numerical experiments

We have conducted some experiments which emphasize the effectiveness of our method, denoted as GrFL for Group Feature Learning, in two contexts : large-scale kernel approximation and automated parameter selection. We show that compared to baseline method such as classical 1 feature selection with pre-defined features, denoted as fixed feat or compared to competing algorithms such as IKL and lowrank kernel approximations, our approach is able to provide decision functions with equivalent or significantly better accuracy and for similar performance, i) that use less features and thus are cheaper to evaluate and ii) that need less time for training. Note that for all the following experiments, kernel and regularization parameters of all methods have been set by cross-validation and we have set ξ t = max(10/n t , 0.1) and η t = max (10, d).

Efficiency comparison on the restricted master problem

Our first experiment aims at evaluating the efficiency of our ADMM algorithm for solving the restricted master compared to an algorithm like FISTA [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] which is based on gradient descent and proximal operator. For this purpose, we have considered two UCI multiclass problems (Wines and multiple features) that we handle through our multi-task framework by defining each binary one-against-all problem as a task. The algorithm runs on the original features which numbers are respectively 13 and 649. As we only want to evaluate the training time of these algorithms we have used 95% of the datasets as training examples. We have used an 1 -1 regularizer for Ωp(•) and considered the same stopping criterion for both algorithms, which is based on approximated KKT conditions or a maximal number of iterations (3000). Running time and objective value achieved by both algorithms after convergence are reported in Table 3. They clearly show that for similar objective values, ADMM yields faster convergence. Note that for the multi feat problem, when λ = 1, FISTA stops because of the maximal number of iterations and thus has a lower running time, but provides significantly worse objective values. Figure 1 gives an example of how the objective value varies across time for the two considered datasets.

Gabor filter based texture classification

In this other experiment, we provide empirical evidences that substantial performance gain can be achieved by automatically learning the feature parameters compared to the use of fixed pre-defined ones jointly with an embedded feature selection method. Results of an approach considering the restricted master prob- lem with a random subset of size k sel of the features visited by our algorithm, denoted as selected feat, have also been reported for a sake of evaluating the computational gain of using "one-pass" feature selection. For this latter approach, in order to have results in a reasonable amount of time we have fixed k sel to 3000 features. The regularization parameters of all algorithms have been selected among λ = [START_REF] Argyriou | Convex multi-task feature learning[END_REF][START_REF] Argyriou | A dc-programming algorithm for kernel selection[END_REF][START_REF] Argyriou | When is there a representer theorem? vector versus matrix regularizers[END_REF][START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF]. This texture recognition problem consists in classifying 16 × 16 patches extracted from three Brodatz textures D2, D29 and D92. For each texture, we have extracted varying number (from 100 to 10000) of overlapping patches from the left side of the image for training and 5000 patches from the right side for testing. The multiclass problem is handled in the same way as for the previous experiment. Regarding the feature generation, we have proceeded as follows. For a given Gabor function, a feature is obtained by computing the inner product of all translated version of the Gabor function located at some pre-defined positions with the image patch and then by summing the absolute value of the responses over the positions. When Gabor parameters are pre-defined in advance, we generate a number k S of features that depends on the number of samples used for each parameter θ, f 0 , σz and σy . For our group feature learning case, the number k R of sampled features used for checking constraint violations is fixed to k R = min(k S , 500).

Results are summarized in Figure 2 where we can note the drastic gain in performance achieved by our algorithm. We also note that as the number of predefined parameters used for the Gabor feature increases, the performance gap between the two approaches decreases but is still manifest. Compared to the embedded feature selection approach selected feat, our GrFL method does not provide any gain in performance but its running time is reduced by an order of magnitude (although we already limited the number of features in the selected feat approach).

Medium-scale and large-scale datasets

We have compared the IKL algorithm of Gehler et al. [START_REF] Gehler | Let the kernel figure it out: Principled learning of pre-processing for kernel classifiers[END_REF] and our approximate IKL on two medium-scale binary classification datasets Adult( reduced to randomly selected 10000 examples) and spamdata. We do not expect our approximated kernel to perform better than IKL but rather to be more efficient and to be cheaper to evaluate. For our approximate IKL, we have randomly sampled 20 values of Gaussian bandwidth in the interval [START_REF] Argyriou | When is there a representer theorem? vector versus matrix regularizers[END_REF]100] and for each of these values, we have randomly sampled 59 directions v. Among all these features, the one violating the most its constraints is included in the active feature set. Note that since zv(x) is composed of two features, these latter are jointly regularized in our model by means of a 1 -2 mixed-norm for Ωp(w).

Figure 3 depicts the performance comparisons of the two approaches. These plots show that while our GrFL algorithm induces some slight loss of performances in small-scale situations, in other situations, substantial gain in computational time may be obtained. Furthermore, as shown in Figure 4, the number of features selected by our algorithm is by an order or magnitude lower than the number of support vectors selected by IKL. Our last experiment shows that our algorithm can handle large scale kernelized problems and that it is competitive compared to other large-scale kernel machines like the low-rank decomposition method of Bach [START_REF] Bach | Predictive low-rank decomposition for kernel methods[END_REF]. For this purpose, we have considered the Adult and IJCNN1 datasets which respectively have 48842 and 141691 examples and 14 and 22 features. For these two datasets, we have compared the performance of our algorithm using both single Gaussian kernel approximation (GrFL) and multiple Gaussian kernel approximation (GrFL-M ) sampling strategies and the low-rank decomposition method of Bach et al. denoted as (CSI). For all methods, the considered Gaussian kernel bandwidth is chosen among σ 2 = {2.5, 5, 10, 15}, and the regularization parameters for GrFL and GrFL-M have been selected among the values [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF]50,100,500] while for CSI, we chose from [10 -7 , 10 -6 , • • • , 10 -3 ]. Note that for our methods, we have sampled at each constraint violation checking, 50 features zv for each possible bandwidth value which means that for GrFL and GrFL-M, we evaluated respectively 50 and 200 features.

Adult

Table 4 reports the average performance over 10 different splits of the data. At first, we are interested in accuracy performance for a given budget of features (from 10 to 500) using 70% of the examples for training and the rest for testing.

Then, we have fixed the maximal number of features at 100 and have made varied the ratio number of training examples vs number of examples. We can see that for most situations, our approach using the multiple kernel sampling strategy performs significantly better than other methods. For the IJCNN1 dataset, for both sampling strategies, we get better performances of about 4% better than CSI. Regarding running time, building the models GrFL and GrFL-M with at most 50 features using 70% of the examples for training take about 330 and 410 seconds for the Adult dataset and 1300 and 1400 seconds for the IJCNN1 dataset using a (non-optimized) Matlab code on a single core Xeon machine with 24 Gbytes of memory. With just a slight computational overhead, we are thus able to mix features derived from different kernels and achieve better performances.

Conclusions

We proposed in this paper, a novel framework and a novel algorithm for learning with infinitely many features, which has been made possible by using sparsityinducing regularizers. We have analyzed the optimality conditions of such regularized problems with infinite number of features. From these analyzes, we derived a simple algorithm which iteratively selects feature parameters. The algorithm, built around an alternating direction methods of multipliers approach, is generic enough to handle different loss functions and different types of regularizers, as well as single or multiple task learning paradigm.

We also discussed two useful situations where features are indeed infinitely many : continuously parametrized Gabor features and randomized kernel approximations. We reported experimental results showing the benefits that can be achieved by learning the feature parameters using our framework instead of pre-fixing them in advance.

For future works, we plan to provide a theoretical analysis of this learning framework. In particular, taking inspirations from related works [START_REF] Cortes | Generalization bounds for learning kernels[END_REF][START_REF] Ying | Generalization bounds for learning the kernel[END_REF], we are interested in studying its generalization performance. In addition, we plan to better analyze the learning problem by providing conditions on the families of features for having a solution with finite number of features and to deploy our algorithm on real-world applications dealing in particular to computer vision problems.

Fig. 1

 1 Fig. 1 Examples of objective value evolution wrt to time for the proximal algorithm FISTA and the ADMM approach. (left) Wines dataset. (right) multi feat dataset.

Fig. 2

 2 Fig. 2 Classification performance on three Brodatz textures classification in a multiclass one-against-all context using squared Hinge loss context. Performances of our algorithm, a fixed feature and a selected feature approach are reported. Top plots respectively show the accuracy and the running time vs the number of pre-computed Gabor features with 1000 training examples per class. Bottom plots depict the same measures but with varying number of training examples per class. For these plots, the fixed feat algorithm considers only k S = 81 features.

Fig. 3

 3 Fig. 3 Performance accuracy and computational time vs number of training examples for (left) Adult. (right) spamdata.

Fig. 4

 4 Fig.4Comparison of the number of features kept for the final decision functions of our algorithm and IKL for dataset (left) Adult. (right) spamdata.

  ) . Columns of Φ (t) correspond to feature maps φ j applied to the training examples of task t and are denoted as Φ

	Φ (t) j are normalized to unit-norm. Our objective is to find the best finite subset of
	features that leads to the lowest regularized empirical risk. This translates to the
	following optimization problem :
	min ϕ∈F	min {wt}t, w,{bt}t
		(t) j . Rows of Φ (t) are noted as Φ (t) i,• . We also suppose that all

  Set {ξt}, {ηt} and η to positive values 2: Initialize variables {wt}, w, {ut}, ũ, {bt}, {at}.

	3: Initialize Lagrangian multipliers {µt}, {νt}, ν.
	4: repeat
	5:	% Updating primal variables
	6:	update {wt} and bt by solving the T linear systems defined by Equation (26)
	7:

1:

Table 3

 3 Comparing the running time and objective values achieved by ADMM and FISTA for two UCI datasets and different regularization parameter values.

			FISTA		ADMM
	dataset	λ	Time	Obj. Val	Time	Obj. Val
	mfeat	5	785.47 ± 68.3 208.0 ± 1.60 207.37 ± 24.00 205.9 ± 1.51
	mfeat	1	1238.85 ± 107.9 54.30 ± 0.50 1378.9 ± 169.5	52.23 ± 0.5
	wines	5	0.33 ± 0.06	43.99 ± 0.6	0.09 ± 0.0	43.98 ± 0.6
	wines	0.1	13.08 ± 2.3	2.14 ± 0.0	0.50 ± 0.0	2.14 ± 0.0

Table 4

 4 Accuracy in % on two large scale problems. Comparing single (GrFL) and multiple kernel (GrFL-M) feature approximation to low-rank decomposition. The left table gives algorithms performance for a given number of features while the right table shows performances for increasing number of training examples and 100 features. Performances in bold are significantly better than those of CSI according to a Wilcoxon signed rank test with p = 0.05.

	IJCNN1

This work was supported in part by the IST Program of the European Community, under the PASCAL2 Network of Excellence, IST-216886. This publication only reflects the authors views. This work was partly supported by grants from the ASAP ANR-09-EMER-001, ANR JCJC-12 Lemon and ANR Blanc-12 Greta. LITIS, EA 4108