稀疏学习由于其简约特性和计算优势而获得了越来越多的关注。稀疏学习问题等价于最优子集选择问题,这是一个NP完全问题。已有的稀疏学习方法大多基于启发式的规则或正则项近似,但这些方法缺乏相应的理论保证,并且难以有效地在精度和稀疏度之间进行权衡。松弛和取舍技术是一种广泛应用的算法设计技术,已被验证了在NP难问题的近似算法设计上极为有效。本文将松弛和取舍技术扩展到稀疏学习问题,提出并设计了一个新的稀疏学习的一般框架。本文的主要贡献如下:1.重写稀疏学习问题。首先将稀疏学习问题写为l0惩罚的子集选择问题,然后通过引入布尔变量将其等价地重写为l1约束的混合整数规划。2.提出了新的基于松弛和取舍的l0的近似算法,并具体研究了支持向量机和深度神经网络两个典型案例。3.给出所提出新的l0范数近似方法的理论分析,包括近似误差接和时间复杂性分析。本文提出的方法在学习的同时可以获得稀疏的解的结构。与已有方法相比,所提出的方法具有可证明的近似保证,可以有效地在稀疏度和精度之间进行权衡,并且具有很强的可扩展性。