标题： 稀疏优化的多级框架及其在逆协方差估计和逻辑回归中的应用 显示英文标题

标题： A multilevel framework for sparse optimization with application to inverse covariance estimation and logistic regression

摘要： 求解l1正则化优化问题在计算生物学、信号处理和机器学习领域中很常见。 这种l1正则化用于找到凸函数的稀疏最小值。 一个著名的例子是LASSO问题，其中l1范数对二次函数进行正则化。 提出了一种多级框架，以高效求解此类l1正则化的稀疏优化问题。 我们利用了解的期望稀疏性，并创建了一个类似类型的层次问题，按顺序遍历以加速优化过程。 该框架被用于求解两个问题：(1)稀疏逆协方差估计问题，以及(2)l1正则化逻辑回归。 在第一个问题中，在假设其为稀疏的情况下，对多元正态分布的未知协方差矩阵的逆进行估计。 为此，需要求解一个l1正则化的对数行列式优化问题。 由于时间和内存限制，这个任务对于大规模数据集尤其具有挑战性。 在第二个问题中，将l1正则化添加到逻辑回归分类目标中，以减少对数据的过拟合并获得稀疏模型。 数值实验表明，该多级框架在加速这两种问题的现有迭代求解器方面是高效的。 显示英文摘要

摘要： Solving l1 regularized optimization problems is common in the fields of computational biology, signal processing and machine learning. Such l1 regularization is utilized to find sparse minimizers of convex functions. A well-known example is the LASSO problem, where the l1 norm regularizes a quadratic function. A multilevel framework is presented for solving such l1 regularized sparse optimization problems efficiently. We take advantage of the expected sparseness of the solution, and create a hierarchy of problems of similar type, which is traversed in order to accelerate the optimization process. This framework is applied for solving two problems: (1) the sparse inverse covariance estimation problem, and (2) l1-regularized logistic regression. In the first problem, the inverse of an unknown covariance matrix of a multivariate normal distribution is estimated, under the assumption that it is sparse. To this end, an l1 regularized log-determinant optimization problem needs to be solved. This task is challenging especially for large-scale datasets, due to time and memory limitations. In the second problem, the l1-regularization is added to the logistic regression classification objective to reduce overfitting to the data and obtain a sparse model. Numerical experiments demonstrate the efficiency of the multilevel framework in accelerating existing iterative solvers for both of these problems.