You are an expert at summarizing long articles. Proceed to summarize the following text: 
sparsity encodes key structural information about data and permits estimating unknown , high - dimensional vectors robustly . no wonder , sparsity has been intensively studied in signal processing , machine learning , and statistics , and widely applied to many tasks therein . but the associated literature has grown too large to be summarized here ; so we refer the reader to  @xcite as starting points . sparsity constrained problems are often cast as instances of the following high - level optimization problem @xmath0 where @xmath1 is a differentiable loss - function , @xmath2 is a convex ( nonsmooth ) regularizer , and @xmath3 is a scalar . alternatively , one may prefer the constrained formulation @xmath4    both formulations   and   continue to be actively researched , the former perhaps more than the latter . we focus on the latter , primarily because it often admits simple but effective first - order optimization algorithms . additional benefits that make this constrained formulation attractive include :    * even when the loss @xmath1 is nonconvex , gradient - projection remains applicable ; * if the loss is separable , it is easy to derive highly scalable incremental or stochastic - gradient based optimization algorithms ; * if only inexact projections onto @xmath5 are possible ( a realistic case ) , convergence analysis of gradient - projection - type methods remains relatively simple .    in this paper , we study a particular subclass of   that has recently become important , namely , _ groupwise sparse regression_. two leading examples are multitask learning  @xcite and group - lasso  @xcite . a key component of these regression problems is the regularizer @xmath6 , which is designed to enforce ` groupwise variable selection'for example , with @xmath6 chosen to be a _ mixed - norm_.    [ def.mn ] let @xmath7 be _ partitioned _ into subvectors @xmath8 , for @xmath9$]$ ] as a shorthand for the set @xmath10 . ] . the @xmath11-_mixed - norm _ for @xmath12 , @xmath13 , is then defined as @xmath14    the most practical instances of   are @xmath15-norms , especially for @xmath16 . the choice @xmath17 yields the ordinary @xmath18-norm penalty ; @xmath19 is used in group - lasso  @xcite , while @xmath20 arises in compressed sensing  @xcite and multitask lasso  @xcite . less common , though potentially useful versions allow interpolating between these extremes by letting @xmath21 ; see also  @xcite . definition  [ def.mn ] can be substantially generalized : we may allow the subvectors @xmath22 to overlap ; or to even be normed differently  @xcite . but unless the overlapping has special structure  @xcite , it leads to somewhat impractical mixed - norms , as the corresponding optimization problem   becomes much harder . since our chief aim is to develop fast , scalable algorithms for  , we limit our discussion to @xmath15-norms  this choice is widely applicable , hence important  @xcite . before moving onto the technical part , we briefly list the paper s main contents :    * batch and online ( stochastic - gradient based ) algorithms for solving  ; * theory of and algorithms for fast projection onto @xmath15-norm balls ; * application to @xmath15-norm based multitask lasso ; both batch and online versions ; * application to computing projections for matrix mixed - norms ; * a set of open problems . we begin by developing some basic theory . our aim is to efficiently implement a generic ` first - order ' algorithm : generate a sequence @xmath23 by iterating @xmath24 where @xmath25 is a stepsize , @xmath26 is an estimate of the gradient , and @xmath27 is the projection operator that enforces the constraint @xmath28 . below we expand on the most challenging component of iteration   when applied to mixed - norm regression , namely efficient computation of the projection operator @xmath27 . formally , the ( orthogonal ) _ projection operator _ @xmath29 is defined as @xmath30 closely tied to projection is the _ proximity operator _ @xmath32 where @xmath33 is a convex function on @xmath34 . operator   generalizes projections : if in   the function @xmath33 is chosen to be the indicator function for the set @xmath35 , then the operator @xmath36 reduces to the projection operator @xmath27 . alternatively , for convex @xmath2 and @xmath33 , operators @xmath27 and @xmath36 are also intimately connected by duality . indeed , this connection proves key to computing a projection efficiently whenever its corresponding proximity operator is ` easier ' . the idea is simple ( see e.g. ,  @xcite ) , but exploiting it effectively requires some care ; let us see how . let @xmath37 be the lagrangian for  ; and let the optimal dual solution be denoted by @xmath38 . assuming strong - duality , the optimal primal solution is given by @xmath39 but to compute  , we require the optimal @xmath38the key insight on obtaining @xmath38 is that it can be computed by solving a single nonlinear equation . here is how . first , observe that if @xmath40 , then @xmath41 , and there is nothing to compute . thus , assume that @xmath42 ; then , the optimal point @xmath43 satisfies @xmath44 next , observe from   that for a fixed @xmath45 , the point @xmath46 equals the operator @xmath47 . consider , therefore , the nonlinear function ( residual ) @xmath48 which measures how accurately equation   is satisfied . the optimal @xmath38 can be then obtained by solving @xmath49 , for which the following lemma proves very useful . [ lemm : mono ] let @xmath6 be a gauge is nonnegative , positively homogeneous , and disappears at the origin  @xcite ] , and let @xmath50 be as defined in  . then , there exists an interval @xmath51 $ ] , on which @xmath50 is monotonically decreasing , and differs in sign at the endpoints .    by assumption on @xmath52 , it holds that @xmath53 . we claim that for @xmath54 , where @xmath55 denotes the _ polar _ of @xmath2 , the optimal point @xmath56 . to see why , suppose that @xmath57 , but @xmath58 . then , @xmath59 . but since @xmath60 is strictly convex , the inequality @xmath61 also holds for any @xmath62 . thus , it follows that @xmath63 , whereby , for @xmath64 , the optimal @xmath46 must equal @xmath65 . hence , we may select @xmath66 . monotonicity of @xmath67 follows easily , as it is the derivative of the concave ( dual ) function @xmath68 . finally , @xmath69 , so it differs in sign .    since @xmath50 is continuous , changes sign , and is monotonic in the interval @xmath70 $ ] , it has a unique root therein . this root can be computed to @xmath71-accuracy using bisection in @xmath72 iterations . we recommend not to use mere bisection , but rather to invoke a more powerful root - finder that combines bisection , inverse quadratic interpolation , and the secant method ( e.g. , matlab s ` fzero ` function ) . pseudocode encapsulating these ideas is given in algorithm  [ algo2 ] . after the generic approach above , let us specialize to projections for the case of central interest to us , namely , @xmath27 with @xmath73 . algorithm  [ algo2 ] requires computing the upper bound @xmath66 . to that end lemma  [ lem.dual ] , which actually proves much more , proves useful . [ lem.dual ] let @xmath74 ; and let @xmath75 be `` conjugate '' scalars , i.e. , @xmath76 and @xmath77 . the polar ( dual - norm ) of @xmath78 is @xmath79 .    by definition , the norm dual to an arbitrary norm @xmath80 is given by @xmath81 to prove the lemma , we prove two items : ( i ) for any two ( conformally partitioned ) vectors @xmath62 and @xmath82 , we have @xmath83 ; and ( ii ) for each @xmath82 , there exists an @xmath62 for which @xmath84 . let @xmath62 be a vector partitioned conformally to @xmath82 , and consider the inequality @xmath85 which follows from hlder s inequality . define @xmath86 $ ] and @xmath87 $ ] , and invoke hlder s inequality again to obtain @xmath88 . thus , from definition   we conclude that @xmath89 . to prove that the dual norm actually equals @xmath90 , we show that for each @xmath82 , we can find an @xmath62 that satisfies @xmath91 , for which the inner - product @xmath92 . define therefore @xmath93some juggling with indices suggests that we should set @xmath94 where @xmath95 denotes the @xmath96-the element of the subvector @xmath22 ( similarly @xmath97 ) . to see that   works , first consider the inner - product @xmath98 next , we check that @xmath99 . consider thus , the term @xmath100 . using   we have @xmath101 thus , it follows that @xmath102 where the last equality holds because @xmath76 . finally , from   it follows that @xmath103 since by definition @xmath104 . this concludes the proof . the next key component for algorithm  [ algo2 ] is the proximity operator @xmath105 . for @xmath106 , this operator requires solving @xmath107 fortunately , problem   separates into a sum of @xmath108 _ independent _ , @xmath109-norm proximity operators . it suffices , therefore , to only consider a subproblem of the form @xmath110 for @xmath17 , the solution to   is given by the _ soft - thresholding _ operation  @xcite : @xmath111 where operator @xmath112 performs elementwise multiplication . for @xmath19 , we get @xmath113 while the case @xmath20 is slightly more involved . it can be solved via the _ moreau decomposition _ @xcite , which , for a norm @xmath114 implies that @xmath115 for @xmath116 , the dual - norm ( polar ) is @xmath117 ; but projection onto @xmath18-balls has been extremely well - studied see e.g. ,  @xcite . for @xmath118 ( different from @xmath119 and @xmath120 ) , problem  ( [ eq.17 ] ) is much harder . fortunately , this problem was recently solved in  @xcite , using nested root - finding subroutines . but unlike the cases @xmath121 , the proximity operator for general @xmath122 can be computed only approximately ( i.e. , in  ( [ eq:18 ] ) , each iteration generates only approximate @xmath46 ) . we now make a brief digression , which is afforded to us by the above results . our digression concerns mixed - norms for matrices , as well as their associated projection , proximity operators , which ultimately depend on the results of the previous section . our discussion is motivated by applications in  @xcite , where the authors used mixed - norms on matrices to simultaneously . we define mixed - norms on matrices by building upon the classic _ schatten-@xmath122 matrix norms _ @xcite , defined as : @xmath123 where @xmath124 is an arbitrary complex matrix , and @xmath125 is its @xmath126th singular value . now , let @xmath127 be an arbitrary set of matrices , and let @xmath128 . we define the matrix @xmath129-norm by the formula @xmath130 as for the vector case , we have a similar lemma about norms dual to  .    [ lem.hold ] let @xmath124 and @xmath131 be matrices such that @xmath132 is well - defined . then , for @xmath133 , such that @xmath134 , it holds that @xmath135    from the well - known _ von neumann _ trace inequality  @xcite we know that @xmath136 now invoke the classical hlder inequality and use definition   of matrix mixed - norms to conclude . [ lem.mtxdual ] let @xmath128 ; and let @xmath137 be their conjugate exponents . the norm dual to @xmath138 is @xmath139 .    by the triangle - inequality and lemma  [ lem.hold ] we have @xmath140 applying hlder s inequality to the latter term we obtain @xmath141 now , we must show that for any @xmath142 , we can find an @xmath143 such that   holds with equality . to that end , let @xmath144 be the svd of matrix @xmath145 . setting @xmath146 , we see that @xmath147 ; since both @xmath148 and @xmath149 are diagonal , this reduces to the vector case  ( [ eq:35 ] ) , completing the proof .    * projections onto @xmath150-norm balls : * + as for vectors , we now consider the matrix @xmath151-norm projection @xmath152 algorithm  [ algo2 ] can be used to solve  . the upper bound @xmath153 can be obtained via lemma  [ lem.mtxdual ] . it only remains to solve proximity subproblems of the form @xmath154 since both @xmath155 and @xmath156 are unitarily invariant , from corollary  2.5 of  @xcite it follows that if @xmath145 has the singular value decomposition @xmath157 , then   is solved by @xmath158 , where the vector @xmath159 is obtained by solving @xmath160 we note in passing that operator   generalizes the popular singular value thresholding operator  @xcite , which corresponds to @xmath17 ( trace norm ) . we describe two realizations of the generic iteration   that can be particularly effective : ( i ) spectral projected gradients ; and ( ii ) stochastic - gradient descent . the simplest method to solve  ( [ eq.9 ] ) is perhaps _ gradient - projection _ @xcite , where starting with a suitable initial point @xmath161 , one iterates @xmath162 we have already discussed @xmath27 ; the other two important parts of   are the stepsize @xmath163 , and the gradient @xmath164 . even when the loss @xmath1 is not convex , under fairly mild condition , we may still iterate   to obtain convergence to a stationary point  see  ( * ? ? ? * chapter 1 ) for a detailed discussion , including various strategies for computing stepsizes . if , however , @xmath1 is convex , we may invoke a method that typically converges much faster : _ spectral projected gradient _ ( spg )  @xcite . spg extends ordinary gradient - projection by using the famous ( nonmonotonic ) _ spectral stepsizes _ of barzilai and borwein  @xcite ( bb ) . formally , these stepsizes are @xmath165 where @xmath166 , and @xmath167 . spg substitutes stepsizes   in   ( using safeguards to ensure bounded steps ) . thereby , it leverages the strong empirical performance enjoyed by bb stepsizes  @xcite ; to ensure global convergence , spg invokes a nonmontone line search strategy that allows the objective value to occasionally increase , while maintaining some information that allows extraction of a descending subsequence . [ [ inexact - projections ] ] inexact projections : + + + + + + + + + + + + + + + + + + + +    theoretically , the convergence analysis of spg  @xcite depends on access to a subroutine that computes @xmath27 _ exactly_. obviously , in general , this operator can not be computed exactly ( including for many of the mixed - norms ) . to be correct , we must rely on an _ inexact _ spg method such as  @xcite . in fact , due to roundoff error , even the so - called exact methods run inexactly . so , to be fully correct , we must treat the entire iteration   as being inexact . such analysis can be done ( see  e.g. ,  @xcite ) ; but it is not one of the main aims of this paper , so we omit it . suppose the loss - function @xmath1 in   is separable , that is , @xmath168 for some large number @xmath169 of components ( say @xmath170 ) . in such a case , computing the entire gradient @xmath164 at each iteration  ( [ eq:9 ] ) may be too expensive , and it might be more preferable to use stochastic - gradient descent ( sgd ) instead . in its simplest realization , at iteration @xmath171 , sgd picks a random index @xmath172 $ ] , and replaces @xmath173 by a stochastic estimate @xmath174 . this results in the iteration @xmath175 where @xmath163 are suitable ( e.g. , @xmath176 ) stepsizes . again , some additional analysis is also needed for   to account for the potential inexactness of the projections . we present below numerical results that illustrate the computational performance of our methods . in particular , we show the following main experiments :    1 .   running time behavior of our root - finding projection methods , including * comparisons against the method of  @xcite for @xmath177 projections * some results on @xmath15 projections for a few different values of @xmath122 . 2 .   application to the @xmath177-norm multitask lasso  @xcite , for which we show * running time behavior of spg , both with our projection and that of  @xcite ; * derivation of and numerical results with a sgd based method for mtl .      for ease of comparison , we use the notation of  @xcite , who seem to be the first to consider efficient projections onto the @xmath178-norm ball . the task is to solve @xmath179 where @xmath180 is a @xmath181 matrix , and @xmath182 denotes its @xmath126th row .    in our comparisons , we refer to the algorithm of  @xcite ( c implementation)aquattoni / codetoshare/ _ ] , as ` qp , ' and to our method as ` fp ' ( also c implementation ) . the experiments were run on a single core of a quad - core amd opteron ( 2.6ghz ) , 64bit linux machine with 16 gb ram . we compute the optimal @xmath183 , as @xmath184 varies from @xmath185 ( more sparse ) to @xmath186 ( less sparse ) settings . tables  [ tab.1][tab.3 ] present running times , objective function values , and errors ( as measured by the constraint violation : @xmath187 , for an estimated @xmath183 ) . the tables also show the absolute difference in objective value between qp and fp . while for small problems , qp is very competitive , for larger ones , fp consistently outperforms it . although on average fp is only about twice as fast as qp , it is noteworthy that despite fp being an `` inexact '' method ( and qp an `` exact '' one ) , fp obtains solutions of accuracy many magnitudes of order better than qp . .runtime and accuracy for qp and fp on a @xmath188 matrix @xmath189 . [ cols=">,>,>,>,>,>",options="header " , ]     the results in table  [ tab : data ] indicate that for large - scale problems , the savings accrued upon using our faster projections ( in combination with spg ) can be substantial . we now show a running comparison between three methods : ( i ) spg@xmath190 , ( ii ) spg@xmath191 , and ( iii ) sgd ( with projection step computed using fp ) . for our comparison , we solve mtlon a subset of the cmu newsgroups datasettextlearning/ _ ; we use the reduced version of  @xcite . ] . the dataset corresponds to 5 feature selection tasks based on data taken from the following newsgroups : computer , politics , science , recreation , and religion . the feature selection tasks are spread over the matrices @xmath192 , each of size @xmath193 , while the dependent variables @xmath194 correspond to class labels . figure  [ fig.cmu ] reports running time results obtained by the three methods in question ( all methods were initialized by the same @xmath195 ) . as expected , the stochastic - gradient based method rapidly achieves a low - accuracy solution , but start slowing down as time proceeds , and eventually gets overtaken by the spg based methods . interestingly , in the first experiment , spg@xmath190takes much longer than spg@xmath191to convergence , while in the second experiment , it lags behind substantially before accelerating towards the end . we attribute this difference to the difficulty of the projection subproblem : in the beginning , the sparsity pattern has not yet emerged , which drives spg@xmath190to take more time . in general , however , from the figure it seems that either sgd or spg@xmath191yield an approximate solution more rapidly so for problems of increasingly larger size , we might prefer them . we described mixed - norms for vectors , which we then naturally extended also to matrices . we presented some duality theory , which enabled us to derive root - finding algorithms for efficiently computing projections onto mixed - norm balls , especially for the special class of @xmath15-mixed norms . for solving an overall regression problem involving mixed - norms we suggested two main algorithms , spectral projected gradient and stochastic - gradient ( for separable losses ) . we presented a small but indicative set of experiments to illustrate the computational benefits of our ideas , in particular for the multitask lasso problem .      * designing fast projection methods for certain classes of non - separable mixed norms . some algorithms already exist for particular classes  @xcite . * studying norm projections with additional simple constraints ( e.g. , bounds ) . * extending the fast methods of this paper to non - euclidean proximity operators . * exploring applications of matrix mixed - norm regularizers . tomioka , r. , suzuki , t. , sugiyama , m. : augmented lagrangian methods for learning , selecting , and combining features . in : s.  sra , s.  nowozin , s.j . wright ( eds . ) optimization for machine learning . mit press ( 2011 )
joint sparsity offers powerful structural cues for feature selection , especially for variables that are expected to demonstrate a `` grouped '' behavior . 
 such behavior is commonly modeled via group - lasso , multitask lasso , and related methods where feature selection is effected via mixed - norms . several mixed - norm based sparse models have received substantial attention , and for some cases efficient algorithms are also available . 
 surprisingly , several _ constrained _ sparse models seem to be lacking scalable algorithms . 
 we address this deficiency by presenting batch and online ( stochastic - gradient ) optimization methods , both of which rely on efficient projections onto mixed - norm balls . 
 we illustrate our methods by applying them to the multitask lasso . 
 we conclude by mentioning some open problems .    _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ * keywords : * mixed - norm , group sparsity , fast projection , multitask learning , matrix norms , stochastic gradient _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _