Structured Sparsity Methods in Machine Learning an Convex Optimisation

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

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.