Runtime guarantees for regression problems
Runtime guarantees for regression problems
复制标题
回归问题的运行时保证
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Richard Peng
中科院分区：
文献类型：
--
作者：
Hui Han Chin;A. Madry;G. Miller;Richard Peng
我们研究理论运行时保证在各种推理问题中出现的一系列优化问题。这些问题是由套索框架激励的，并在机器学习和计算机视觉中应用了应用。我们的工作在算法图理论中显示了这些问题与核心问题之间的密切联系。尽管此连接证明了获得运行时保证的困难，但它也提出了一种使用最初为图算法开发的技术的方法。
然后，我们证明这些问题中的大多数可以作为分组的最小二乘问题提出，并为此配方提供有效的算法。我们的算法依赖于解决二次最小化问题的例程，而二次最小化问题又等同于求解线性系统。还提供了一些有关图像处理任务的初步实验工作。
We study theoretical runtime guarantees for a class of optimization problems that occur in a wide variety of inference problems. These problems are motivated by the LASSO framework and have applications in machine learning and computer vision. Our work shows a close connection between these problems and core questions in algorithmic graph theory. While this connection demonstrates the difficulties of obtaining runtime guarantees, it also suggests an approach of using techniques originally developed for graph algorithms.
We then show that most of these problems can be formulated as a grouped least squares problem, and give efficient algorithms for this formulation. Our algorithms rely on routines for solving quadratic minimization problems, which in turn are equivalent to solving linear systems. Some preliminary experimental work on image processing tasks are also presented.