论文标题
解决一类融合套索问题的解决方案路径的结构和算法
Structure and Algorithm for Path of Solutions to a Class of Fused Lasso Problems
论文作者
论文摘要
我们研究了一类融合的套索问题，其中序列中的估计参数反向其各自的观察值（保真度损失），$ \ ell_1 $ norm norm惩罚（正则化损失）在连续参数之间的差异（促进本地恒定）之间的差异。在许多应用中，在正规化项上有一个系数，通常表示为$λ$，该系数调整了两个损失之间的相对重要性。 在本文中，我们表征了最佳解决方案如何以$λ$的增量进化。我们表明，如果所有保真度损失函数都是凸面线性线性，则最多最多的$ o（nq）$ times的最佳值，对于$ n $变量的问题和总$ q $ breakpoints。另一方面，我们提出了一种算法，该算法求解\ emph {ash ash {all}变量的解决方案中的$ \ tilde {o}（nq）$时间$λ\ geq 0 $。有趣的是，我们发现每个变量的解决方案的路径最多可分为$ n $ tim凸面段。对于任意凸损耗函数的问题，对于给定的解决方案的精度，可以将损耗函数转换为凸形分段线性函数并应用上述结果，从而给出伪多项式界限，因为$ q $成为伪聚合量。 据我们所知，这是解决非二次忠实损失功能融合套索解决方案路径的第一项工作。
We study a class of fused lasso problems where the estimated parameters in a sequence are regressed toward their respective observed values (fidelity loss), with $\ell_1$ norm penalty (regularization loss) on the differences between successive parameters, which promotes local constancy. In many applications, there is a coefficient, often denoted as $λ$, on the regularization term, which adjusts the relative importance between the two losses. In this paper, we characterize how the optimal solution evolves with the increment of $λ$. We show that, if all fidelity loss functions are convex piecewise linear, the optimal value for \emph{each} variable changes at most $O(nq)$ times for a problem of $n$ variables and total $q$ breakpoints. On the other hand, we present an algorithm that solves the path of solutions of \emph{all} variables in $\tilde{O}(nq)$ time for all $λ\geq 0$. Interestingly, we find that the path of solutions for each variable can be divided into up to $n$ locally convex-like segments. For problems of arbitrary convex loss functions, for a given solution accuracy, one can transform the loss functions into convex piecewise linear functions and apply the above results, giving pseudo-polynomial bounds as $q$ becomes a pseudo-polynomial quantity. To our knowledge, this is the first work to solve the path of solutions for fused lasso of non-quadratic fidelity loss functions.
