2015优博公示提稀疏学习优化算法及理论研究

AlgorithmsandTheoriesDissertationSubmittedTsinghuainpartialfulfillmentoftherequirementforthedegreeofDoctorofControlScienceandGongDissertationSupervisor ProfessorZhangMay,关于使用的说本人完全了解有关保留、使用的规定，即：拥有在著作权定范围内的使用权，其中包（1）已获的必须按学校规定提交，学校可以采用影印、缩印或其他保存上交的；（2）为教学和科研目的，学校可以将公开的作为资料在馆、资料室等场所供校内师生阅读，或在校园网上供校内师生浏览部分内容；（3）根据《中民例暂行施办法，向国家馆送可以公。本人保证遵守上述规定（ 在后应遵守此规定作者签名 导师签名 期 期摘摘稀疏学习是近些年来机器学习领域一个十分活跃的研究课题，它具有直观的模型解释，是一个很好的数据预处理方式，能够节约空间和计算时间，在许多实际问题上有成功的应用。本文从优化算法和理论分析两个方面对稀疏学习问题进行了系统和深入的研究，主要研究成果包括：提出将投影牛顿法用于求解`1正则的最小二乘问题和非负矩阵分解问题。我们首先将上述两个优化问题分解(转化)成带盒型约束的最小二乘问题，然后通过在迭代中融入二阶信息，用投影牛顿法来快速求解。在一定条件下，投影牛顿法能够达到二次的收敛速率，同时我们用一些实用的技术来减少算法在每步迭代中的计算代价，使得投影牛顿法十分适合快速求解上述两个优化问题。提出了一个鲁棒的多任务特征学习算法，并对算法获得的解进行了理论分析。该算法将权重矩阵分解成两个矩阵之和，并对每个矩阵施加不同的惩罚，使其能够在学习到共享特征的同时，还能够检测到异常任务。我们对算法获得的解进行了理论分析，给出了参数估计误差和预测误差的界，在一定条件下，我们的算法能够获得真实共享的特征和异常的任务。提出了一个基于截断1,1正则的非凸多任务特征学习模型，并从算法和理论两个方面对该模型进行了深入的研究。为解决非凸模型对应的非凸优化问题，我们提出了一个多阶段多任务特征学习算法，并对算法进行了收敛性和可再生性在稀疏特征值条件下，多阶段多任务特征学习算法获得的解的参数估计误差的界比凸稀疏正则的多任务特征学习要好。提出了一个求解非凸优化问题的快速迭代收缩阈值算法，该算法比传统非凸优化算法的收敛速度要快很多，它能够快速地求解大规模的非凸优化问题，在大规模真实数据集上的实验结果表明了我们提出算法的有效性。：稀疏学习；优化算法；多任务学习；Sparselearninghasrecentlybeenanactiveresearchtopicinthefieldofmachinelearning.Ithasintuitiveinterpretationsandisagoodwaytopreprocessthedata;itsavesstoragespaceandcomputationaltime,andhasbeensuccessfullyappliedtosolveseveralreal-worldproblems.Inthisthesis,westudysparselearningintermsofitsoptimizationalgorithmsandtheories.Themaincontributionsofthisthesisinclude:Weproposefastoptimizationalgorithmstosolvetwoimportantsub-problems.OneisanefficientEuclideanprojectionalgorithminthegradientprojectionmethod.An-otherisanefficientmulti-stageconjugategradientalgorithmforsolvingthetrustregionstepprobleminthetrustregionNewtonmethod.WeproposetoadopttheprojectedNewtonmethodtoefficientlysolvethe`1regularizedleastsquaresandnonnegativematrixfactorizationproblems.Werecast( pose)thetwoproblemsaboveintoleastsquaresproblemswithboxconstraint,whichareefficientlysolvedbytheprojectedNewtonmethod.Insomeconditions,theprojectedtechniquestoreducethecomputationalcostperition,whichmakestheprojectedNew-tonmethodappropriatetosolvethetwoproblemsefficiently.Weproposearobustmulti-taskfeaturelearningalgorithmandpresentadetailed ysis.Thealgorithm posestheweightmatrixintothesumoftwomatricesandimposesdifferentpenaltiesontothem,whichenablesthealgorithmtosimul-taneouslycapturethesharedfeaturesandidentifyoutliertasks.Wealsopresentadetailedysisforthealgorithmintermsofparameterestimationandpredictionerrorbounds.Theysisalsoshowsthat,insomeconditions,ourproposedalgorithmcanobtaintheWeproposeanon-convexmulti-taskfeaturelearningformulation,basedonthecapped-`1,`1regularizer.Westudytheproposedformulationintermsofitsoptimizationalgorithmandtheoreticalysis.Tosolvethenon-convexoptimizationproblem,weproposeamulti-stagemulti-taskfeaturelearningalgorithm,inwhichweyzethecon-vergenceandreproducibilityissues.Wealsopresentadetailedtheoreticalysisfortheproposedalgorithm,whichshowsthat,inthesparseeigenvaluecondition,themulti-stagemulti-taskfeaturelearningalgorithmcanachieveabetterboundthanconvexmulti-taskfeaturelearningalgorithmsintermsoftheparameterestimationerror.Weproposeafastitiveshrinkageandthresholdingalgorithmtosolvenon-convexoptimizationproblems.Theproposedalgorithmconvergesmuchfasterthantradi-optimizationproblems.Experimentalresultsonlarge-scalereal-worlddatasetsdemon-:SparseLearning;OptimizationAlgorithm;Multi-TaskLearning;Non-convexProblems目第1章绪 研究背景和意 稀疏学习概 稀疏学习的几个基本问 稀疏学习的研究现 稀疏学习优化算 稀疏学习理论研 几个值得探索的研究问 本文的主要工作和结构安 第2章两个重要子问题的快速优化算 快速欧氏投影算 欧氏投影问 投影问题转化成寻根问 分片寻根 实验结果及分 快速求解信任区域步 信任区域步长问 共轭梯度 多阶段共轭梯度法 实验结果及分 本章小 第3章快速投影 快速投影法求解`1正则最小二乘问 对偶问 对偶投影法 算法细节及讨 实验结果及分 快速投影法求解非负矩阵分解问 非负矩阵分解问题 投影法求解非负最小二乘问 轮换优化求解非负矩阵分解问 相关工 实验结果及其分 本章小 第4章鲁棒多任务特征学 鲁棒多任务特征学习的建模和优 鲁棒多任务特征学习建 优化算 理论分 理论的 理论证 实验结果及分 比较算法和数据 实验设 合成数据实 真实数据实 本章小 第5章多阶段多任务特征学 非凸多任务特征学习模型及优化算 非凸多任务特征学习模 优化算 收敛和可再生性分 收敛性分 算法的可再生性分 参数估计误差的 理论证 定理5.3证明梗 详细证 实验结果及讨 比较算 合成数据实 真实数据实 本章小 第6章迭代收缩阈值法快速求解非凸优化问 算法 一般问 一些例 优化算 相关工 实验结果及分 实验设 实验评估和分 本章小 第7章总结与展 本文总 工作展 参考文 个人简历、在学期间的学 与研究成 1章绪论近几十年以来，机器学习的研究已经取得了巨大的发展，它已经成为人工智能和计算机领域的一个重要分支。尤其是在互联网高速发展的时代，机器学习成为从海量高维数据中探索内在规律的一个强有力的工具。在很多知名的互联网公司，如谷歌，，微软，BM等，机器学习成为他们分析和处理数据的一个重要之一。近些年来，具有稀疏结构的机器学习问题成为了机器学习领域一个很活跃的研究课题，尤其是在互联网数据呈现式增长的今天，它已经成为人们从海量数据中提取有用信息的重要工具。简单来讲，我们把具有稀疏结构的机器学习问题称之为稀疏学习(parselearn)。下面我们简要概述一下稀疏学习并阐述几个基本的研究问题。数据一般用向量或者矩阵来表示，稀疏意味着向量或者矩阵中的元素只有很少一部分为非零。稀疏性在实际应用当中是很常见的，比如在文本表示中，一个文档( )只包含词汇表or)一单词(rd)(图1所示)；在信号的小波变换(eletaformati)或者接近为零(如图1.2所示)；在人脸图像的示幅能成过完备基人脸图像的稀疏表示(如图1.3所示在息中只少一部分构成了某种疾病的致病。(a)词汇表 (b)某个文档中出现的单词图1.1 图 图像的小波变换(该图来自文献图 人脸的稀疏表示(该图来自文献稀疏性在实际问题中的大量和客观存在，使得稀疏学诸如信号处理，图像处理，人脸识别，文本分析，生物等等实际问题当中有着极其广泛的应用。这些实际的应用问题涉及到各种各样的稀疏学习算法，如压缩感知(compressedsensing)[1,3,4]，信号恢复(signalreconstruction)[5–7]，图像去模糊(imagedeblurring)[8,9]，文本聚类( clustering)[10,11]，图模型结构学习(graphicalmodelstructurelearning)[12,13]，特征选择(featureselection)[14–16]，稀疏编码(sparsecoding)[17–19]，稀疏逻辑回归(sparselogisticregression)[20,21]，稀疏主成分分析(sparseprincipalcomponentysis)[22]，非负矩阵分解(nonnegativematrixmactorization)[23–26]，多任务学习(multi-tasklearning)[16,27,28]，多核学习稀疏提供了一个对模型的直观解释，比如Tibshirani[14把基`1范数约束的最小二乘结果解释为特征选择。稀疏学习能够在学个模型的同时实现自稀疏学习是一种很好的数据预处理方式，它通过特征选择功能，大大减少稀疏学习使得向量或者矩阵绝大部分的分量都是零，通过稀疏和稀疏运算技术，为我们了空间和计算量。尤其是在世界数据呈现海量和的情况下，稀疏为我们在空间和运算量上所带来的节省更是稀疏会导致更好的性能，比如Ng[15]在研究特征选择时，稀疏逻辑回归是一种减少过拟合(overfitting)现象发生的有效方式之一[31]。在本节，我们以一个简单的线性模型的例子来说明一下稀疏学习的几个基本问题1。给定样本数据矩X=[xT···;xT]xi∈Rp和观测输出y= [y1···yn]T，假设它们满足下面的线性模型iyi=xTw?+i,i=1,···, (1-i其中i是服从正态分布或者次正态分布的噪声；w是真实的稀疏向量，也即支撑(SupportSet)i i?)

i:w?,

(1-的势(Cardinality)满足条件：⃒supp(w?⃒s≪p。稀疏学习的其中一个目的是在据矩阵X和观测输出向量y已知的情况下建立合适的模型，尽可能准确地恢复出真实的w?。具体来讲，稀疏学习往往需要求解下面的两个优化问题：min{l(w)+λr(w)} (1-wmin s.t.w∈ (1-wl(w)是一个损失函数，r(w)是一个稀疏正则项，λ>0是一个正则化𝒞是一个稀疏约束集。当损失函数，稀疏正则和约束集参数满足一定的条件时，(1-3)式与(1-4)式有相同的最优解(具体请见下页)。在稀疏学习中，人们往往关心 函数有最小二乘损失函数(也即二次损失函数)1l(w)=1‖y−Xw‖2 (1-2逻辑损失函数(也即指数损失函数)1∑︁ l(w)和铰链(HingeLoss)函

nn

1+exp(︁−yiwTxi) (1-l(w)

0,1−yiwTxi (1-(1-3)式的正则项

r(w)=w|1 (1-时，(1-3)式就是近年来研究得十分火热的`1正则稀疏学习问题；当约束𝒞

⎨w ⎩

|wi|

(1-时，(1-4)式就是`1约束的稀疏学习问题。`1正则稀疏学习问题与`1约束的稀疏学习问题关系密切，具体来讲，当l(w)是凸函数，r(w)𝒞(1-8)(1-9)式给定时，对于给定0λ+∞，存在t≥0(1-3)(1-4)式有相同的最优解，反之亦然[32](更具体的分析请见1.2.1节)。同时，我们可以直观地从一个简单的平面示意图来解释为`1约束的问题能够产生稀疏解。1.4可以看出，由于`1约束集边界的固有特点，使得目标函数的等值线与约束区域的切点正好是`1约束集的顶点近些年来，除开较早被研究的`1稀疏学习之外，大量各种各样的稀疏学习问题在机器学习，数据挖掘，信号处理，生物，计算机视觉等领域也受到了人们的特别关注。这些不同的稀疏学习问题主要体现在它们具有不同的正则项(约束)，常见的正则项和约束有`q范数(q1)︁`1,q(q1)︁，融合`11l(XWY)=1‖YXW‖2 2xi[xi1]w[wb]bl(w) 1 i=1log1+ex(︁yiwxi+b)。对于铰链损失函数也是类似的图 Lasso稀疏示意图(该图来自文献(FusedLasso)`1(GraphLasso和迹范数(TraceNorm等1，我们将它们概括如1.1所示，其∪i𝒢i={1···p}(𝒢i之间可以重合也可以不重合)；(j,k)︁∈ℰ表示第j个变量(结点)与第k个变量(结点)存在接边；迹范(TraceNorm)是作用在W上的，σi(W)Wi大的非零奇异值。1.1稀疏学习常用正则项和名 正则 约`1范 ‖w‖1=∑︁︀p|w ‖w‖≤

`范 ‖w‖=(∑p ‖w‖≤ `1,q范 ‖w‖1,q

i‖w𝒢i

‖w‖1,q≤融合`1范 ‖w‖FL=λ1∑︁i=1

|wi|+

p−1|wi− ‖w‖FL≤图上的`1范数‖w‖GL

|wi|+

(j,k)︁∈ℰ|wj− ‖w‖GL≤迹范 ‖W‖tr i ‖W‖tr≤(1-3((1-4式随着机器学习的迅猛发展，机器学习优化算法已经越来越受到人们的关注。国际机器学习大会(InternationlConereenachieLeg，简称ICML2)曾举办多个workshop3对机器学习的优化问题进行专门的讨论。神经信息处理系统大会(NelrmnProcesingems，简称NIPS4)更是在2008-2连 本文提到的一些”范数”`1范数的叫法，依然称它们为”范数” p-neuro/2008-March/000765.html 续五年举办了为izanforachieLearning”的workshop1。在一些比较有的国际大会上，一些以优化算法为主导的ttorial2也是频频出现，备受机器学习研究人员的欢迎。除此之外，专门针对机器学习优化算法的书籍Otimizanraceeag]已于1年在这些优化算法的专题讨论和书籍当中，有很大一部分内容是专门针对机器学习领域研究得十分火热的稀疏学习问题进行的。在互联网飞速发展的今天，海量的数据扑面而来，人们很容易迷失在数据的海洋里。稀疏学习为人们从海量数据中提取简洁有价值的信息提供了一个强有力的工具。然而，在解决一个实际的问题中，人们需要处理数据的容量远远超过了计算机的内存，甚至远远超出了一般计算机的硬盘容量。那么如何在有限容量的内存和硬盘条件下，设计出行之有效的算法来解决大规模的稀疏学习优化问题是人们一直十分关注的话题。稀疏学习优化算法的研究方兴未艾，一个重要的原因是不同的实际问题有不同的先验知识，从而使用不同的稀疏正则项，而发掘这些正则项所具有的特殊结构往往是稀疏学习优化算法设计人员十分关心的问题。近些年来，专门针对稀疏学习的快速优化算法大量涌现，这些算法大多是在一般优化方法的框架下，充分发掘损失函数特别是稀疏正则项的一些特殊结构，从而设计出高效算法的。目前有一些专门求解稀疏优化问题的软件包已经公布出来，供研究人员免费使用3。在下一节，会具体介绍近些年来在稀疏学习中几个非常经典的优化算法。(1-3((1-4式我们能否从理论上分析，在什么样的条件下，(1-3式所得到的ˆ能够很好地近真实的稀疏向量w?。一般地，人们用如下的三个指标来衡量一个稀疏学习 ∼mairal/tutorialcvpr2010/ ‖XˆX?q (1-‖ˆ (1-supp(ˆ (1-(1-10)，(1-11)和(1-12)式分别衡量了一个稀疏学习模型预测能力，参数估计能力和特征选择能力的好坏。一个好的稀疏学习模型，应该是能够使得(1-10)和11式尽量小，且(1-12)式尽量成立的模型。一般而言，(1-12)式的成立会导致(1-11)式比较小，进而导致(1-10)式比较小[34]。在下一节，会介绍一些在本节，从以下的三个方面来阐述一下稀疏学习的研究现状。首先，介绍一下近些年来几个经典的稀疏学习优化算法。其次，简要概述一些分析稀疏学习模型解性能的理论结果。最后，总结归纳一下当前及今后可能值得继续探索的几个研究问题。早在1996年，Tibshirani[14]就提出了下面的`1约束的最小二乘模型(也即著名的Lasso)： minl(w)=1‖y− s.t.‖w‖1≤ (1- (1-13)式是一个`1约束的{︁化问题，它与下面的`1}︁则优化问题紧密相关minf(w)=1‖y−Xw‖2+λ‖w‖1 (1- 下面我将从对偶的角度来说(1-13)(1-14)式的关系。µ≥0(1-13)式等式约束的拉格朗日乘子，那么我们可以得到(1- 式的拉格朗日函数为 ℒ(w,µ)=2‖y−Xw‖+µ‖‖1− (1-记w(µ)=arg

(w, (1-注意(1-13)式是一个凸优化问题且其满Slater条件[35]，所(1-13)式与下面 (1-?是上述对偶问题的一个最优解，那么由强对偶性可知道?(1-13)式的一个最优解。由(1-16)和(1-15)式可以得到：?ℒ{︁w,

1‖y−Xw‖2+?

– =argmin1‖y−Xw‖2+?1 (1- 注意?(1-13)式的一个最优解，那么(1-18)式可以知道λ(1-13)式不等式约束的最优拉格朗日乘?((1-17)式的最优解)(1-13)(1-14)式有相同的最优解在本小节，以稀疏(`1正则或者`1约束)最小二乘为例，详细阐述近些法是用来(1-13)式或(1-14)式，而不再详细阐述这两个问题之间的关系。在不引起歧义的情况下，为了表述的方便，我们`1正则`1约束的稀疏学习问题统称为Lasso。δj是一个p维向量且满足δj∈{+1−1}pj=1,2p么jj (1-13)式的优化问题，||w||1≤t实际上等价2p个线性不等式约δTwtj=1···2p。这(1-13)式实际上就是一个仿射约束的二次规划]p比较大时，直接LawsonHanson[37]设计的算法来2p个不等式约束的二次规划问题计算量太大。为此，Tibshirani[14]给出了一个加约束集算法来求解(1-13)式。G[δT···δTp]，定GℰG的一个子矩阵，它包j∈ℰ的所有δT，那么Tibshirani[14]加约束集算法流程如算法jj 1章绪论算法1:加约束集算法输入:X∈Rn×p,y∈Rnt∈ 22ˆ←ˆ︁ℰ←{︁j0},其中δj0sign(ˆiwhileℰ′{i:δTˆt}不是空集i ℰ←ℰ∪ 2ˆ=argminwl(w)=1‖y− s.t.Gℰw≤2输出:该算法从最简单的无约束最小二乘解ˆ(0)开始，如果当前解了目标约束集中的某个约束，就将这个约束加入到当前约束集中，然后进行下一轮的优化，直到解满足目标约束集中的全部约束。很显然，该算法在2p步之内必定会停止，但实验表明14]，算法一般会在.5p到.75p步停止。加约束集算法简单易懂，但它最大的问题是随着算法的不断向前推进，约束集中的约束个数越来越多，从而致算法的效率大大降低1范数的不可导性给高效求解1)式和)式的优化问题带来了一定的，为了解决不可导性所带来的问题，有人提出通过引入辅助变量的方法将难以处理的`1范数转化成其它容易处理的形式。Tibshirani[14]了另外一个算法，该算法引入了两个辅助变量+和−(正部和负部)，它们满ww+w−w+≥0w−≥0i=1,···p，这样(1-13)式就变成了下述的二次

p l(w,w)

1⃦⃦y−X(w−w)︁⃦ (w+w)≤t,w≥0,

≥2 2

(1-(1-19)式是一个含2p个变量，(2p+1)个不等式约束的二次规划问题，该问题可以用内点法[35,36]来求解。用类似于上述引入辅助变量的方法，(1- 式就转化成了如下的问题⎧

− minf(w,w)=1⃦⃦y−X(w−w)︁⃦+ (w+w) s.t.w≥0,

≥w+,w−

i

(1-1章绪论i 我们注意到，上式中的约束集相对(1-19)式而言少了一个不等式约∑︁︀p(w++w−)︁≤t，它只是一个简单的盒型约束(boxconstraint)1。盒型约束是人们比较喜欢的一个约束类型，因为盒型约束解耦的特殊结构能够为我们设计有效的优化算法提供方便Hsieh等人[38]利用盒型约束的特点提出了一个快速的坐标下降(coordinatedescent)算法[39]来求解支持向量机(SVM)的对偶问题，Chen等人[40]也是利用这个特殊的约束，利用坐标下降算法来求解超图[41]i 除了引入正部和负部的辅助变量之外，Kim等人[5]引入了一个不同的辅助u∈Rp，将(1-14)式转化成了以下的优化问题

⎪f(w,u)

‖y−Xw‖2+λ

u

s.t.−ui≤wi≤ (1-w,u

i⎭然后，Kim等人[5]提出用内点法来快速求解上式，有效解决了信号处理中的信号辅助变量法通过引入额外的变量，将一个`1正则优化问题转化成了一个线性约束的二次规划问题，这为设计有效的优化算法带来了方便，但它同时下的问题：辅助变量算法由于引入了额外的变量，使得转化后优化问题的变量个数增加了一倍，这往往会增大计算量。 范数的不可导性给我们求解优化问题带来了一定的，源于我们不知道最优ˆ每个wˆi的符号，如果我们知道了最优解每个分量的符号，那么(1-14)式就是一个目标函数可微的无约束二次规划问题，这样一个想法启发人们通过获得最优解的符号模(patternofsign)来求解问题。解的符号模ofsign可以表示为一个p维的向量s11]p，它满⎧⎪ sign(ˆ

(1-定义积极(activeset)

⎩ 𝒥={i:wˆi, (1- +∞1章绪论(1-14)式就等价于下面的无约束二次规划问min1‖y−Xw‖2+λsT

(1- 其中w𝒥表示w的一个子向量，它包i𝒥的元wi；X𝒥X的一个子矩阵，它包含所有i𝒥的列。由上述积极集的定义和优化问题我们很容易得到下面的闭式解(closed-formsolution)：ˆ𝒥=(XTX𝒥)−1(XTy− (1- ˆ𝒥c= (1-其中𝒥c𝒥的补集，当XTX𝒥奇异时，(XTX)︁1表示XTX𝒥的伪逆。虽然 上我们不能够预先知道积极集𝒥，但是我们可以通过一定的策略不断更新当前迭代解上的积极集𝒥1，并求解(1-24)式的优化问题，然后再更新当前迭代解上的积极集𝒥，……，如此往复直至算法收敛。算法的具体流程如算法2所示。于输入:X∈Rn×p,y∈Rnλ∈初始化积极集(1-25),(1-26)式得到当前解while当前解不符合最优解条件更新积(1-25),(1-26)式得到当前解ˆλsign(ˆ (1-⃦XT(y− ˆ ≤ (1-

具体ˆ(1-14式的最优解，当且仅0∈fwˆ)fwˆ)f(ww

处的次微分(sub-differential)，它是所有次梯度(sub-gradient)ˆT(Xˆˆ (1- 𝒥图 `1正则最小二乘解的路径示意图(该图来自于文献wˆ|1`1范数wˆ处的次微sign(ˆi)}︀ (1-)件。对于积极集算法来说，积极集𝒥的更新策略不同，就对应一个不同的算法，如Lee等人[18]，Roth和 [42]以及Kim和Park[43]分别根据不同的策略提出对于(1-14)式，正则化参数λ控制着解的稀疏程度，在实际的应用问题中，我们一般需要通过交叉验证的方法来λ，但是交叉验证的方法需要多次求解(1-14)式的优化问题，这样就造成了不必要的重复计算。(Homotopy)[32,44–48]能够求解出一个解的路径(solutionpath)，也即能够求解出在所有参数λ下的解，这在一定程度上能够解决上述所说的重复计算问题。同伦算法能够得到解的路径的一个重要原因(1-14)式最优解的每一个分量wˆiλ的一个分段线性函数(1.5所示，其中横轴表示参数λ，纵轴表示(1-14)式的ˆi)这样，如果我们能够找到分段线性曲线的折点(breakpoint)，那我们就可以得到wˆi关于参λ的解析(yticalsolution)，进而就可以得到在所有参λ下的(解的路下面我们就详细阐述一下同伦算法[45,48]。同伦算法本质上是一种积极集算法，因为它能够求出解的路径，所以把它单独作为一小节内容进行讨论。由0∈fwˆ)的最优解条件，我们可以得到：ˆ (1-sign(ˆ|ci|=λ,∀i∈ (1-c(k)为第k次迭代后的结果，那么在第k次迭代中，对于在积极集𝒥1的分量，它们的更新方向d(k)通过求解下列的线性方程得到：XTX𝒥d(k)= (1- 对于不在积极集𝒥的分量，它们的更新方向为d(k)= (1-在沿着d(k)w(k)进行更新的过程中，有两种情况会使得更新找到折点(此(1-31)式的最优解条件不满足)：不在积极集的元素c(k)在更新的过程中出现|c(k)|≥λ的情况，此时更新i为

λ–

λ+

⎬ (1- i<𝒥⎩1−xTXT 1+xTXTd(k) 𝒥 𝒥+记使步长达到γ(k)的索引为i++对于在积极集的元素w(k) ⎪w(k)⎪γ−= − (1-di∈𝒥 (k)di–记使步长达到γ(k)的索引为i−–同伦算法按照下式更新w(k)，就能找到折点(λ, w(k+1)=w(k)+minγ(k),γ(k) (1-{︁ 同时更新积极集

λ←λ−minγ(k),γ(k) (1- 𝒥←𝒥∪{i+}或𝒥← (1-详细的算法流程如算法3所示。算法最吸引人的地方是它利用最优解是正则化参数λ的线性分段函数的性质，通过寻找折点的方法来得到一个解路径。 𝒥算法3:同伦算法输入:X∈Rn×p,y∈Rnλ2⃦XT i初始化：k←0,𝒥←i:argmaxi⃦xTy⃦ iwhile停止条件不满足 k←k+ 由(1-33)，(1-34)式得到更新方向 (1-35)，(1-36)式得γ(k) 根据(1-38)式更新w(k(1-39)式更新积极输出:(λ,w(k)),k=1··梯度投影(gradientprojection)[36] 通过下列的迭代来求解(1-13)式的优化问题： w(k+1)=Π𝒞w(k)−η(k)∇l(w(k)) (1-η(k)是迭代的步长；∇l(w(k)l(w)ww(k)处的梯度；𝒞(1-13)`1范数约束集；Π𝒞(d)到𝒞的投影，它可以通过求解以下的优化问题来得到Π(d)=argmin1‖x− s.t.x∈𝒞={w:‖w‖≤t} (1- )的两个很关键的问题。梯度投影法的流程如算法4Berteas36]NonlinearPramming长的选择方法：常数步长tstepize，最小化准则miizanrue)步长，ijo准则(Armiorule)步长等。在一定的条件下，这些步长选择方法都能够保证收敛。这里我简要介绍一下如何用rmijo准则选择步长：定义(k)=βm(k)¯，其中β∈(01)η¯是常数，Armijo准则就是找到一个最小的非负整m(k)，使得下面等式成 l(w(k))−lΠ𝒞w(k)−η(k)∇l(w(k))≥σ∇l(w(k))Tw(k)−Π𝒞w(k)−η(k)∇l(w(k))(1-输入:X∈Rn×p,y∈Rnt>初始化迭代步数k←0，迭代初始值while收敛条件不 w(k+1)=Π𝒞w(k)−η(k)∇l(w(k))while步长η(k)不满足条件根据某一准则调整步长 w(k+1)=Π𝒞w(k)−η(k)∇l(w(k))k←k+输出:其中σ∈(︁0,1)是一个常数。在每步迭代中，如何给定一个初始的步长也是一个很重要的问题，一个使用得比较广泛的初始化方法是Barzilai-Borwein(BB)准则[51]。s(k)=w(k)− (1-r(k)=∇l(w(k))− (1-BB准则初始化步长η(k使得η(k)IHessian矩阵，也即η(k)s(k)≈r(k)过下面的式子来得到 )⃦ (s(k))T =argmin – η

(s(k))T

(1-此外BarzilaiBorwein[51]还提出了另一BB准则就是使α(k)IHessian矩阵的逆矩阵，然后取η(k)=1/α(k)，与上述的准则类似，通过近似s(k)≈αr(k)，我们可以得到:(k)T (k)Tα(k)=argα

αr(k)–

(s)=(r(k))T

⇒η(k)=(r)(s(k))T

在实际的优化算法中，根据4)和)式求出来的k)只是在第k程中的一个初始值，为保证收敛，不同的算根据不同的准则(过程中保证目标函数值是下降的)对这个初始的步长进行一定的调整(线搜索)然，除开上述介绍的步长选择准则外，还有很多的文献对步长的选择问题进行了研究[6,51–]。1章绪论求解投影问题一直是人们十分关注的一个话题，尤其是近几年来，各种各样的稀疏学习问题不断涌现，研究如何向各种类型的稀疏约束集(请见表1.1)进行投影的文献也就随着涌现出来161959–]。2`1范数的不可导性，直接用传(次)梯度下降法来求(1-14)式的优化问题，一般来说不是一个很好的选择，于是有人(1-14)式的损失函数l(w1‖y−Xw‖2和正则λr(w)λ‖w‖1区别对待，在求梯度的时候，只对l(w)发生作用，这正是近似梯(proximalgradient)法最基本的思想，下面我就详细2 (w)=l(w)+(w−u)T∇l(w)+1‖w−u‖2+λr(w). )

w =argminww

(k)(w)=arg

⃦w−

–η

+λr(w).(1-r(w)||w||1时，(1-48)式有闭 ¯ (1- ¯ thresholding)函数。直观上可以把近似梯度法看作一个两步操作的过程：首先对l(w)w=w(k)处进行一个梯度下降的操¯(k)，然后用软阈值函数¯单的就是选取u=w(k))和步长成为近似梯度法的两个最关键的问题。近些年来，大量用近似梯(或者它的变形算法)来求解优化问题的文献不断涌现出来[7–9,68–76]。在这些文献中，最具代表性的是Wright等人[7]提SpaRSA(SparseReconstructionbySeparableApproximation)算法和Beck等人[9]FISTA(FastItiveShrinkageThresholdingAlgorithm)算法(很多人也SpaRSA算法是在近似梯度法的一般框架下，用BB准则来初始化步长的，具体的算法流程如5所示。在算法5中，接受步长η(k)的条件为：f(w(k+1))

i=max(0,k−M),···

‖w(k+1)− (1-算法5:SpaRSA算法输入:X∈Rn×p,y∈Rnλ>初始化常数：β(01)αminαmax0αmin初始化迭代步数k←0和迭代初始值while收敛条件不 (1-45)式计η(k)←min(max(αmin,η(k)),while步长η(k)不满足条件 η(k)← (1-48)式得k←k+输出:σ∈(︁01)是一个很小的常数。M=0时，算法能够保证目标函数值是下降的，当M>0时，算法虽然不能保证目标函数值下降，但是在一定的条件下，算法是能够保证收敛的[7]。SpaRSA算法在实际的应用中，计算效率很高，这在一定程度上取决于该算法在考虑近似梯度法的特性基础上，充分利用BB准则来初始FISTA算法是对传统近似梯度法的一个改进，它采用与Nesterov方法[77–81]类似的思想，在k次迭代中，FISTA算法不u=w(k)处进行梯度下降的操作，而是在u=s(k)=w(k)+(t(k−1)−1)/t(k)(w(k)−w(k−1))[t(k)是在迭代过按照一定的准则进行更新的]处进行一个梯度下降的操作，得¯(k)，然后再用软阈值函数对s¯(k)做一个截断操作，具体的算法流程如算6所示。FISTA算法一个最大的特点就是在k次迭代中，进行梯度下降操作的位置w(k)w(k−1)的线性组合，而不是当前位w(k)，这样一个小小的改变，使得算法的收敛速率发生了质的变化。传统的近似梯度算法(在w(k)处进行梯度下降操作)的收敛速率可以表示为(︁1

(1-k其中k表示迭代的步数ˆ(1-14)式的最优解。而FISTA算法的收敛速率(︁1 (1-算法6:FISTA算法输入:X∈Rn×p,y∈Rn,λ>0,η0>1初始化:w(1)←w(0);t(0)←0;t(1)←1,β∈(02fork=1,2,··· α(k)←t(k−1)−1;s(k)←w(k)+α(k)(w(k)− forj=0,1,2,··· η(k)←β w(k+1)←S(s(k)−η(k)∇l(s(k)), iff(w(k+1))≤Qη(k),s(k)if收敛条件满足ˆ←w(k);iter←k;fval←ft(k+1)←

;2输出:ˆ,iter,f除了上面几小节所介绍的几个优化算法外，还有很多用来求(1-13)式或(1-14)式稀疏优化问题的算法，如嫁接法(Grafting)[82]，近似算(Approxima-tionmethod)[83]，坐标下降(coordinatedescent)[84–86]，η-技巧[87]等等方法，更详细的算法介绍，请见综述性文献[50,88,89]。在上面几小节，虽然我们`1正则(`1约束最小二乘问题为例来详细阐述比如：加约束集算法能够解`1约束的一般优化问(即损失函数可以是任意的凸函数)。类似地，辅助变量法也能够求解一般损失函数`1正则优化问题。解所有凸约束的凸优化问题。近些年来，除开`1约束的稀疏学习问题被研究得如火如荼之外，一些其它约束的稀疏学习问题也逐渐们关注起来，比如`q范数，(ElasticNet)[90]，融`1范数(FusedLasso)[67,91]，`1,q范数[92]，迹范数(tracenorm)[93](GroupSparsity)[94–96]，树形结构稀疏[97,98]，层次化范数(hierarchicalnorm)[98,99]等稀疏学习问题。求解带有这些稀疏约束的优化问题，一个十分关键的步骤是研究如何向这些约束集上进行快速而准确的投类似于梯度投影法，近似梯度法是一个求解凸正则优化问题的一般框架，它能够求解形(1-3)式的一般优化问题证凸损失函数Loss(w)可微且梯度Lipschitz连续的条件下Nesterov方法来求(1-3)式，都能够达到O(1/k2)的收敛速率[79,81]。与梯度投影法类似，在不同的正则项下，快速求解(1-48)式的优化问题，也是人们很关心的一个话题。也不例外，它主要包括两方面的假设：对数据矩阵(X)和对噪声()的假设。对数据(X)RIP(RestrictedIsometryProperty)条件：RIP条件CandesTao[100]在研究压缩感知(compressivesensing)时提出。我们先介绍两个很重要的常RIC(RestrictedIsometryConstant)ROC(RestrictedOrthogonalConstant)。对于整数kk′≤p,kk′≤p，我们分别称使得下列不等式成立的最小常数δkθk,k′RIC常数和ROC常(1−β‖≤‖Xβ‖2≤(1+ (1- Xβ,Xβ′≤θk,k′ (1-ββ分别kk稀疏的向量，也即‖β‖0≤k,′0≤k′⟨·⟩表示内积。从上述定义可以知道，RIC常数δkROC常数θk,k′是衡量数据矩X正交性的两个常数CandesTao在压缩感知文[100]给出了以下RIPδs+θs,s+θs,2s< (1-其中，s=‖w?‖0表示真实向量w?的非量个数。后来经过很多其他学者的深入研究，很多RIP条件的变形被相继提出，这里我们不对每RIP条件进行详细的介绍，只是将近些年来出现的一些主要的RIP条件概括如表1.2所示。表 RIP条RIP条 相关文θ,s Candesδ2s 2−1≈0.4142δ3s3δ4s Candes等人δ2sθs,2s Candesδ1.25sθs,1.25s Cai等人δ2s Foucartδ2s< δ2s Moδs Cai等人RE(RestrictedEigenvalue)条件：RE条件由Bickel等人[109]提出，它假设定义在矩阵XTX上的一个受限制的最小特征值κ(sc大于零。具体地，RE条κ(s,c) {︁1,···,p}:|𝒥|≤s𝒥c‖1≤c‖∆𝒥

√n

> (1-其中，c>0是一个常数，s=‖w?‖0。通常情况下，为简单起见，人们一般取𝒥=supp(w?)[109]。iMC(MutualCoherence)条件：MC条件由Donoho等人[110]提出。定义MC常iM

(1-1≤i,≤,j‖xi‖‖x那么MC条件就是假设下列的不等式成立其中，s‖w?‖0

M−1+s

or 2s−

(1-一致性时提出，它包括如下的IR(StrongIrrepresentableCondition)和IR条件(WeakIrrepresentableCondition)： Strong:XTcX(︁XTX

sign(w? ≤1− (1-Weak

T

∞≤ (1-Xc X 𝒥 其中，η∈(01)是一个常数，𝒥=supp(w?)对于某一个具体的矩阵X，虽然我们一般都无法验证它们是否满足上述列出的几种条件(或假设)，但当数据矩阵中的元素采样于某些特殊的分布时，一些条件能够以大概率满足。同时，这些条件都是对数据矩阵X的一个刻划，它们的一个共同特点是：都要求XTX不能太，这体现为XTX的条件数(最大特征值与最小特征值的比值)不应该太大，换句话说，XTX应该是一个”对角线元素占优的矩阵”。有关用于稀疏学习理论的条件(或假设)，以及它们之间的关系，请参考VandeGeerBuhlmann的[112]。对噪声()的假最常见的噪声假设有两(Gaussian)噪声假设和次高(Sub-Gaussian)噪声假设。假设i(i1···n服从独立同分布的高斯分布N(0σ2)假设i(i=1···n)服从独立同分布均值为零的次高斯分布，即σ>0，使得对于任意的t∈R：iEexp(ti)≤ (1-i我们称满足上述不等式的随量服从次高斯分布，是因为它的矩生函数(momentgeneratingfunction)的上界是均值为零的高斯随量的矩生函数。具体地，如果一个高斯随量服从分布N(0,σ2)，那么根据矩生函数∫︁

2Eexp(tx) exp(tx) exp− =

(x−σ2t)2 = (1-另外，根据Hoeffding引理，我们可以得到：对于任意均值为零的随x∈[a,b]，下列的不等式成E(exp(tx))≤

(︁t2(b−a)28

(1-由此可见，任何均值为零的高斯随量和均值为零的有界随量都是次高斯随量，所以次高斯假设是一个比高斯假设更一般的假设，它在许多上一小节介绍的几个假设 (或条件)，都是近些年来研究稀疏学习理论的基形式。在本小节，我们具体介绍在不同条件假设)下个的理果。我们首先介绍一下与 114) 式不同但与其有着密切联系的压缩感知。压缩以表如下模形：min‖w‖1,s.t.‖y−Xw‖≤ (1-wγ=E‖‖(1-1)式中噪声大小的一个度量(1-64)(1-14)式的联系体现在：当在(1-64)式和(1-14)式中分别选取合适的γ和λ时，(1-64)式与(1-14)有相同的最优解

(1-64)式的最优解，假设RIP条件成立且‖w?‖0s， (1-其中C是一个与RIC常数(ROC常数)有关的一个常数。在无噪声的情况下(γ=0)，我们可以得到˜=w?，也即此时我们可以通过求解(1-64)式完全恢复出真实的信号w?。这里我们需要说明的是，在不同的文献里，可能会用到如表1.2中不同的RIP条件C的表达式可能也会有所不同，但它们所得到的理论结果都可以写(1-65)式所示的统一形式。接着我们介绍几个(1-14)式的解进行理论分析的结果。它们分别从预测性定理1.1[109]i∼N(0σ2)XTX/n的对角线元素1s=‖w?‖0。假REκ(s3)>0的形式成立，(1-14)式中正则化参数λ满足λ=Aσ√︀nlog (1-其中，A2√2，那么，对于任意的n≥1，下列的不等式以大于等于1p1−A2/8概率成立

logp (1- ⃦κ2 ⃦ ? X(ˆ−w)︁⃦≤κ2 slog (1-ˆ上述定理是在RE条件和噪声假设下，以大概率得到了参数估计性能和预测性能的上界。但由于上述的参数估计误差是以`1范数的形式出现的，在这个参数估计误差的理论基础上很难得到特征选择一致性的结论。Lounici[117]在对(1-14)式进行理论分析时，给出了一个以`∞范数来度量的参数估计误差的界，从这个参数估计误差的界我们能够得到特征选?的结论，只要我们假设真实w每一个非量都大于某一个阈值，且对(1-14)式的最优解理

做一个简单的后定理1.2[117]令i∼N(0σ2)XTX/n的对角线元素1s=‖w?‖0。假MCM≤7n(α>1)的形式成(1-14)式中正则化参数λ满足λ= nlog (1-其中，A2√2，那么，对于任意的n≥1，下列的不等式以大于等于1p1−A2/8的⃦ˆ− ≤

√ logp (1- 其中ˆ是(1-14)式的一个最优解；c1=31+ 上述定理给出了一个`∞范数的参数估计误差的界，下面的定理在此基础上，再一些合理的假设和后处理，得到了如下的特征选择一致性结论定理1.3：[117]假设定理1.2中的条件成立满 w?> logp (1-() 其中，c2≥2c1。 √

⎨ˆ|ˆ=⎩

log

(1-那么下列的符号一致性以大于等于1p1−A2/8的概率成立SIGN(˜ (1-i我们SIGN(˜SIGN(w?称之为符号一致性，它表示对于所有i∈{︁1···p}，w˜iw?的符号都相同。显然，符号一致性是一个比特征选择一致性更强的结论。除了上述的符号一致性结论外，ZhaoYu[111]在研究特征选择一致性时，当iIR条件成立时，(1-14)式的最优解ˆ以大概率满足下列的符号一致性SIGN(ˆ (1-Wainwright[118]也在之后给出了一个在MC条件下(文中的MC条件与上一小节给出的MC条件稍微有些不同)符号一致性的理论分析。当然，稀疏学习的理论研究远远不止我们在上文介绍的几个，我们只是列出了近些年来几性的研究成果。关于稀疏学习理论研究的文献DantzigSelector[103,109,117,119,120]，自适Lasso(AdaptiveLasso)[121,122],组稀疏(GroupSparsity)[94,123,124]，贪婪稀疏学(GreedySparseLearning)[125–127]，非凸稀疏学习(Non-convexSparseLearning)[34,113,116,128,129]等。稀疏学习作为近些年来机器学习领域的一个很重要的研究分支，除了.2节所介绍的优化算法和理论分析之外，还有很多值得我们去进一大规模稀疏学习优化问大规模稀疏学习问题是人们一直都很关注的一个话题，如何在有限的资源条件下，更好更快地求解稀疏学习优化问题是研究人员和工业界都很关心的一个问题。特别是在世界着海量和维数据的情形之下，寻求能够求解大规模稀疏学习优化问题的算法是一个很重要也很实际的需求。在1.2.1节，我们介绍了近些年来在稀疏学习领域很经典的几个优化算法，但这些算法都是基于批量式的，也即这些算法都要求预先把数据读进内存，而且在每一步迭代的过要用到所有的数据。当数据量超出内存的容量甚至是硬盘的容量时，这些批量式的优化算法就不能满足需求了。为了解决这一问题，(Oe)优化算法(机Stchac)优化算法)和并行(或者分布式)优化算法就应运而生。与批量式优化算法不同的是，优化算法每次迭代过只用一个样本或者很少的一些样本，一方面为每一步迭代减少了运算量，另一方面它可预先把数据读进内存，这就使得求解大规模的稀疏学习问题成为了可能。近些年来，式的稀疏优化算法大量涌现[74–7630–13]，这些算法大多可以近似看作是1.2.1节所介绍的一阶优化算法(包括梯度投影法和近似梯度法)的版本，也即在每次迭代过，这些的算法只需要用到一个样本或者很少的几个样本，单从算法的角度来讲，这些的优化算法都十分的简单，它们的主要步骤都要求(1-41)(1-48)式的优化问题。由此可见，研究快速有效的投影算法对于优化算法也是至关重要的一步。但优化算法在每步迭代中没有用优化算法的收敛性分析不同于批量式的优化算法。概括来说，优化算法一∙优化算法的收敛性分析∙优化算法收敛性能的好坏，也即算法得到的收敛值与我们期望得到的最优值之间误差到底有多大，这一般通过后悔值(regret)来衡量。∙优化算法的收敛速率分析类似于批量式优化算法，如何将二阶信息融入到优化算法中以加快算法的收敛速度[13435]也是在设计优化算法时需要考虑的一个问题。在算法中融入二阶信息虽然会加快收敛的速度，但必然会增加算法在每步迭代中的计算量，而如何在每步的计算量和最终的收敛速率上做一个合适的折中，也是人们很关心的一个问题。并行优化算法是把原始的优化任务分解成为很多的子任务，同时把相应的数据分布在不同的计算机上，每台计算机根据自己分配的子任务分别进行运算，最终通过多台计算机的协作运算，得到优化问题的最优解。近几年来，已经有一些并行(或者分布式)优化算法用于解决大规模的稀疏学习优化问题136]并行优化算法的是如何将原始的优化问题分解成合适的子任务，并将其放入到现有的一些并行计算框架中运行。对于任务分解，一般来说，我们可以从特征[13739]和样本[13638]两个维度进行；对于并行计算框架，目前具有代表性的有两个：MPI140]和MpReduce141]。结构稀疏学习模面所介绍的稀疏学习优化算法和理论分析中，我们基本是以1正则(或1约束)最小二乘问题为例进行阐述的，但稀疏学习的研究范畴远远不止这些。不同的应用问题有各自不同的特点和先验知识，我们应该根据这些先验知识建立更加适合特定应用问题的稀疏学习模型，这主要体现在两方面：一是损失函数应该根据问题的不同而相应地有所不同，比如在回归问题中，我们倾向于用最简单的最小二乘损失函数，而在分类问题中，我们则倾向于用逻辑损失函数或者是铰链损失函数。但上述所说到的几个模型都是线性或者广义线性的，而实际应用问题很有可能是高度非线性的系统，此时我们就应该考虑用非线性的模型。非线性的模型从某种程度上也许能够更好地对实际问题进行建模，但它往往要比线性模型复杂得多，求解相应优化问题的计算量也大大增加。如何在模型复杂度和计算量上做一个折中是人们需要常常考虑的一个问题。二是稀疏正则(或者约束)应该尽量融入实际应用问题的先验知识。研究得最多的1正则化没有过多地考虑变量之间的结构信息，而在一些实际的应用问题中，我们往往能够获取一些带有结构信息的先验知识，人们由此提出了一些具有特定结构的稀疏正则模型，比如融合1范数(FusedLasso)91]稀疏模型，组稀疏模型(Groupprity)9495],树形结构稀疏模型798]，层次化范数(hierarchiclorm)9899]1范数(rahLass)1213]稀疏模型，迹范数(raceorm)[9342]稀疏模型等。根据需要解决的实际问题的特定结构建立更加合理的结构化稀疏学习模型是今后一个值得深入探索的问题。非凸稀疏学习模使模型得到稀疏解的本来想法是要对其施加`0范数1惩罚，但由于`0范数问题变得十分的，于是人们提出用`1范数来近`0范数来得到稀疏解。由于`1范数是凸的，这使得很多凸优化技术可以很好地应用到稀疏学习优化问题中，这也是近些年来稀疏学习优化算法大量涌现的重要原因之一。基于`1范数的稀疏学习模型，虽然能够产生稀疏解，也在优化上面具有一定的优势，但其对`0范数的近仍然不是太好，因为`1范数对模型的惩罚会随着变量绝对值的增大而线性增大，而`0范数对所有非零变量的惩罚都是1，这使得`1范数会带来过惩罚的来更好地近`0范数正则[34,113,116,128,129]，这些正则有一个共同点，那就是它们都`0`1范数的一个插值。直观上来想，由于非凸正则`0范数正则的更好近性，这些非凸的稀疏正则学习模型应该比基于`1范数的稀疏学习模型具有更好的性能。事实上，一些学者已经给出了一些理论上的结果，他们非凸稀疏学习模型的性能在某些条件下的确是优于凸模型的[34,113,116,129]，这主要体 `0伪范数”`1范数的叫法，依然称它现在：在同样的条件下，非凸稀疏学习模型能够得到比凸稀疏学习模型更强的结论，或者非凸稀疏学习模型能够在比较弱的条件下得到与凸稀疏学习模型类似的结论。这其实也是稀疏学习理论研究最的一个问题：尽可能在弱的条件(假设)限于比较简单的情况：损失函数是最小二乘函数，非凸稀疏正则也没有过多地考虑结构化信息。如何将这些相对简单的非凸稀疏学习的理论结果推广到更加一般的非凸稀疏学习模型中(包括更加一般的的损失函数和有结构化信息的非凸正则项)，是一个值得去深入研究的问题。同时，虽然现有的一些文献[34,116]已经提出了一类求解非凸稀疏学习优化问题的方法，但它们相对求解凸稀疏学习问题而言计算量仍然很大。如何将非凸的稀疏学习模型应用到具有海量和维数据的实际应用问题中，并开发出实用的优化算法也是一个很有意义的问题。稀疏学习的广泛应用前稀疏学近些年来被研究得如此火热，这与它被广泛用于解决各种各样的实际问题是分不开的，这包括多任务学习(Mli-askLearning)162728]，协同滤波(CollaborateFilg)143]，图像去噪(ImageDenoisig)144]，信号恢复(Sigeconstrction)[5–7]，生物(iomedicine)145–147]等。特别是在互联网和生物医药两个领域，稀疏学习是一个非常自然而又有效的应用工具。在互联网世界里，数据呈现出海量和维的特点，在维的数据中选择或者提取有用的特征是对计之前的一个至关重要的环节，而稀疏学习是一个特征选择或者提取的有效工具，实用而又有前景的研究问题。在生物领域，由于样本需要花费高昂的费用，因此能够提供给研究人员使用的样本就很少，而生物本身的特点决定了样本的维数都很高，所以人们往往会着样本少维数高的问题，比如人们经常要用有成千上万个(特征)，而样本数很少的数据(几十个到上百个)来研究某一种病的致病原因，弄清楚它主要是由哪些所引起的，这就需要我们从少量的样本中解决特征选择的问题。近些年来的研究成果表明148]，稀疏学处理维数远大于样本个数的问题上具有很大的优势，因此研究稀疏学生物领域的应用问题是一个很有前景的研究课题。本文的主要工作和结构安本文从优化算法和理论分析两方面对稀疏学习相关问题进行了系统和深入11章绪论 鲁棒多任务特 图 本文组织结构特定的稀疏优化问题进行研究。在理论分析方面，我们分别提出了一个凸的和一个非凸的稀疏学习模型，并将其应用于多任务特征学习中，同时，我们对新模型从理论上进行了研究，分析了两个模型在多任务特征学习中的理论性能。本文的组织结构如图1.67123章和6章属于优化算法方面的研究，第4章和第5章属于理论分析方面的研究(这章也对优化算进行了研究)，第7章对全文进行总结。具体章节安排如下第2章，两个重要子问题的快速优化算法。面我们提到，快速的欧氏投影是投影梯度算法中很关键的一步。在本章，我们提出了一个快速的分段线性寻根算法，该算法能够快速求解向一类稀疏约束集进行欧氏投影的问题。此外，为解决信任区域法的关键步骤–信任区域步长求解问题，我们提出了一个快速的多阶段共轭梯度算法。第3章，快速投影法。为了提高优化算法的收敛速度，融入了二次信息的投影法用于求解1正则最小二乘和非负矩阵分解问题，投影法在一定条件下，能够达到二次的收敛速率。此外，我们还将一些数值计算技巧应用于投影法中，这大大减少了算法每步的计算代价。第4章，鲁棒多任务特征学习。我们提出了一个具有发现异常任务机制的稀疏多任务特征学习模型，该模型将多任务特征学习权重矩阵分解成为两个矩阵之和的形式，一个矩阵用于学习任务之间共享的特征，另一个矩阵用于发现异常的任务。同时我们对模型进行了理论的研究，分析了模型的理论性能。5章，多阶段多任务特征学习。我们提出了一个非凸的稀疏多任务特征学法进行了理论分析，分析表明，在一定条件下，我们非凸稀疏多任务特征6章，迭代收缩阈值法快速求解非凸优化问题。针5章中对非凸优化问题的求解不是十分高效的问题(相对于凸优化问题来说)，我们提出了一个快速7章，总结与展望。我们对全文的工作进行了总结，并对将来可能的研究2章两个重要子问题的快速优化算法在第1章，我们知道大多数的优化算法都是迭代进行的，而在迭代过快速求解一些重要的子问题是使得优化算法快速有效的一个关键步骤。在本章中，着重讨论两个重要子问题的快速优化算法：一是在梯度(GradientProjectionProjectedGradient)法中欧氏投(EuclideanProje