论文标题
有效投影算法对加权L1球
Efficient Projection Algorithms onto the Weighted l1 Ball
论文作者
论文摘要
在许多优化和机器学习问题中，预计梯度下降已被证明有效。加权$ \ ell_1 $球在稀疏系统识别和功能选择方面有效。在本文中，我们提出了三种新的高效算法，用于将任何有限长度向量的矢量投射到加权$ \ ell_1 $球上。前两个算法具有线性最差的复杂性。第三个在实践中具有竞争激烈的表现，但最坏的情况具有二次复杂性。这些新算法是基于预计梯度下降的机器学习方法的有效工具，例如压缩感应，特征选择。我们通过将有效的压缩传感算法适应加权投影来说明这种有效性。我们使用非常大的向量证明了新算法在基准测试上的效率。例如，它仅需要8毫秒，即Intel I7第三代，以投影尺寸为$ 10^7 $的向量。
Projected gradient descent has been proved efficient in many optimization and machine learning problems. The weighted $\ell_1$ ball has been shown effective in sparse system identification and features selection. In this paper we propose three new efficient algorithms for projecting any vector of finite length onto the weighted $\ell_1$ ball. The first two algorithms have a linear worst case complexity. The third one has a highly competitive performances in practice but the worst case has a quadratic complexity. These new algorithms are efficient tools for machine learning methods based on projected gradient descent such as compress sensing, feature selection. We illustrate this effectiveness by adapting an efficient compress sensing algorithm to weighted projections. We demonstrate the efficiency of our new algorithms on benchmarks using very large vectors. For instance, it requires only 8 ms, on an Intel I7 3rd generation, for projecting vectors of size $10^7$.
