Data-driven algorithm selection and tuning in optimization and signal processing
Data-driven algorithm selection and tuning in optimization and signal processing
复制标题
DOI：
10.1007/s10472-020-09717-z
复制
发表时间：
2020-11
影响因子：
1.2
通讯作者：
J. D. Loera;Jamie Haddock;A. Ma;D. Needell
中科院分区：
文献类型：
--
作者：
J. D. Loera;Jamie Haddock;A. Ma;D. Needell
机器学习算法通常依赖于优化子程序，并且众所周知，它可以为许多类型的问题提供非常有效的结果。在这里，我们翻转依赖并提出相反的问题：机器学习算法能否为优化问题带来更有效的结果？我们的目标是训练机器学习方法，以自动提高优化和信号处理算法的性能。作为概念证明，我们使用我们的方法来改进数据科学中两个流行的数据处理子程序：压缩感知中的随机梯度下降和贪婪方法。我们提供的实验结果证明答案是“是”，机器学习算法确实导致更有效的优化问题的结果，并显示了未来的潜力，这一研究方向。除了我们的实验工作，我们证明了相关的可能近似正确（PAC）学习定理，我们感兴趣的问题。更确切地说，我们证明了存在一种学习算法，它以很高的概率选择优化给定分布的问题实例输入集的平均性能的算法。
Machine learning algorithms typically rely on optimization subroutines and are well known to provide very effective outcomes for many types of problems. Here, we flip the reliance and ask the reverse question: can machine learning algorithms lead to more effective outcomes for optimization problems? Our goal is to train machine learning methods to automatically improve the performance of optimization and signal processing algorithms. As a proof of concept, we use our approach to improve two popular data processing subroutines in data science: stochastic gradient descent and greedy methods in compressed sensing. We provide experimental results that demonstrate the answer is “yes”, machine learning algorithms do lead to more effective outcomes for optimization problems, and show the future potential for this research direction. In addition to our experimental work, we prove relevantProbably Approximately Correct(PAC) learning theorems for our problems of interest. More precisely, we show that there exists a learning algorithm that, with high probability, will select the algorithm that optimizes the average performance on an input set of problem instances with a given distribution.