Structured Sparsity Methods in Machine Learning an Convex Optimisation

在过去的十年中，机器学习（ML）的理论发展对统计学，应用数学和其他科学研究领域产生了重大影响。特别是，ML和数值优化之间富有成效的相互作用已经出现，预计将导致理论和算法的突破，使ML方法更适用于许多具有实际意义的问题。拟议中的项目旨在在这个新兴的跨学科领域的关键时刻做出重大贡献，该领域迄今为止一直由美国和法国主导。许多ML技术可以被转换为在大量参数上最小化目标函数的问题。示例包括支持向量机以及用于半监督学习和多任务学习的最新技术。通常目标函数是凸的。因此，凸优化的思想在学习算法的设计、实现和分析中变得越来越重要。然而，到目前为止，ML几乎完全采用现成的方法进行凸优化，而没有充分利用该领域背后的丰富理论。这个建议的一个论点是，ML和数值优化之间需要更深入的相互作用。最终，将两个社区连接起来将促进沟通，核心优化的力量将更容易在ML中发挥作用，并导致优化的新领域。ML和优化之间的相互作用发挥特别重要作用的一个领域是使用稀疏诱导优化问题。使用稀疏诱导模型的一个基本原理是，当模型参数的数量远远大于观测值的数量时，对于快速和准确的学习，强烈需要稀疏的参数选择。基于这一成功，我们认为，现在是时候为结构稀疏约束下的矩阵学习问题开发一系列新的算法了。这意味着参数矩阵或其分解的许多分量在经由某种规则相关的位置中为零（例如，矩阵可以被约束为具有许多零行、许多零特征值、具有稀疏特征向量等）。也许最著名的例子，其中结构稀疏性已被证明是有益的是在协同过滤，其中目标函数被选择为有利于低秩矩阵，并在多任务学习中，目标函数被选择为有利于几个共同的相关变量在不同的回归方程。这些类型的优化问题最近才开始在ML和优化中得到解决，并且一些基本问题仍然开放，最重要的是利用底层稀疏假设和方法的统计学习分析的有效算法的研究。我们的提案是多学科的，涉及计算机科学之间的大量思想交流。（机器学习）和数学（数值优化），有三个主要目标。首先，我们的目标是开发新的和有效的算法来学习大型结构化矩阵，算法的快速收敛时，应保证应用到问题数据，有一个稀疏的解决方案。其次，在假设的稀疏性结构导致NP难问题并且第一个目标无法实现的情况下（这通常是低秩假设下的情况），我们的目标是识别易处理的凸松弛并了解它们对稀疏性的影响。第三，我们的目标是模型和算法比通用求解器具有更自然的解释（例如，最小最大的统计理由），这应该使从业人员更有可能接受新的方法。

Over the past ten years theoretical developments in machine learning (ML) have had a significant impact in statistics, applied mathematics and other fields of scientific research. In particular, fruitful interactions between ML and numerical optimisation have emerged that are expected to lead to theoretical and algorithmic breakthroughs with the potential to render ML methodologies significantly more applicable to many problems of practical importance. The proposed project aims to make significant UK contributions at a crucial juncture in this emerging interdisciplinary field that has so far been dominated by the US and France. Many ML techniques can be cast as problems of minimising an objective function over a large set of parameters. Examples include support vector machines as well as more recent techniques for semi-supervised learning and multi-task learning. Often the objective function is convex. Consequently, ideas from convex optimisation are becoming increasingly important in the design, implementation and analysis of learning algorithms. Up to now, however, ML has almost exclusively resorted to off the shelf methods for convex optimisation, without substantially exploiting the rich theory which lies behind this field. A thesis of this proposal is that there is a need for a deeper interplay between ML and numerical optimisation. Ultimately, bridging the two communities will facilitate communication and the power of core optimisation will be more easily brought to bear in ML and lead to new frontiers in optimisation. An area in which the interplay between ML and optimisation has a particularly important role to play is in the use of sparsity inducing optimisation problems. A rationale that drives the use of sparsity-inducing models is the observation that when the number of model parameters is much larger than the number of observations, a sparse choice of parameters is strongly desirable for fast and accurate learning. Building on this success, we believe that the time is now right for the development of a new line of algorithms for matrix learning problems under structured sparsity constraints. This means that many of the components of the parameter matrix or a decomposition thereof are zero in locations that are related via some rule (e.g the matrix may be constrained to have many zero rows, many zero eigenvalues, to have sparse eigenvectors, etc.).Perhaps the most well-know examples in which structured sparsity has proven beneficial are in collaborative filtering, where the objective function is chosen to favour low rank matrices, and in multi-task learning where the objective function is chosen to favour few common relevant variables across different regression equations. These types of optimisation problems have only recently started to be addressed in ML and optimisation, and several fundamental problems remain open, most importantly the study of efficient algorithms which exploit the underlying sparsity assumptions and a statistical learning analysis of the methods.Our proposal is multidisciplinary and involves substantial exchange of ideas between Computer Science (Machine Learning) and Mathematics (Numerical Optimisation), with three main goals. Firstly, we aim to develop novel and efficient algorithms for learning large structured matrices; fast convergence of the algorithms should be guaranteed when applied to problem data that have a sparse solution. Secondly, in the cases where the assumed sparsity structure leads to NP-hard problems and the first goal is unachievable (this is often the case under low-rank assumptions), we aim to identify tractable convex relaxations and understand their impact on sparsity. Thirdly, we aim for models and algorithms that have a more natural interpretation than generic solvers (e.g., a minimax statistical justification), which should make it more likely that practitioners will embrace the new methodology.