On robustness and adaptivity properties of mirror descent in high-dimension

最小化目标函数的问题自然出现在绝大多数统计学习问题中。有丰富的优化方法可以解决这一任务，其中许多方法都有强有力的理论和经验保证。最简单、最广为人知的此类方法之一是梯度下降法，以及它的随机变量和广义镜像下降法。然而，理论上通常研究的场景涉及非污染的训练数据。考虑到如今学习算法必须处理的海量数据，人们预计会有不可忽视的污染，这将对预测器的质量产生影响。例如，在存在离群值的情况下，可以通过在学习阶段之前使用一些过滤方法来进行学习。这通常是计算密集型的，研究起来相当困难，因为不同类型的异常值需要不同的方法。如果优化算法与这一预处理步骤具有相同的效果，人们可能会期望大量的计算节省和统一的方法来处理这类问题。这个项目的主要目标是了解镜像下降是否对“异常值”具有健壮性，以及它是否可能适应数据中的不同类型的污染。这个项目试图回答的问题如下：-是否有一个统一的方法来研究涉及不同类型数据污染的统计学习问题？可以证明，多大的污染会导致任何学习算法具有较差的预测保证？镜像映射的选择(以及诱导几何的选择)如何影响镜像下降算法的健壮性？是否有一个镜像图的选择来保证算法适应不同类型的数据污染？-这些潜在的发现可以在多大程度上应用，以解释在不同模型(如深度神经网络)中经验观察到的稳健性特性？Huber在上个世纪开始的统计稳健性工作主要关注稳健估计，而不是稳健预测。这一研究领域中使用的技术，以及关于高维统计、镜像下降和在线学习的文献，为解决上述问题提供了一个潜在的起点(例如，在“两全其美”的问题中)。我们希望通过结合上述领域流行的不同方法，该项目的最终结果将是对稳健学习的新的理论理解，类似于经典的学习理论框架。该项目属于EPSRC统计与应用概率和EPSRC理论计算机科学研究领域。

The problem of minimising an objective function naturally arises in the vast majority of statistical learning problems. There is a rich plethora of optimisation methods for solving this task, many of them with strong theoretical and empirical guarantees. One of the simplest and most well-known such methods is gradient descent, along with its stochastic variants and the generalized mirror descent. However, the scenarios commonly studied in theory involve non-contaminated training data. Given the enormous amounts of data learning algorithms have to process nowadays, one would expect non-negligible contaminations that would have an impact on the quality of the predictors. Learning in the presence of outliers can be done, for example, by using some filtration method prior to the learning phase. This often turns out to be computationally intensive and rather difficult to study, as different types of outliers require different approaches. If the optimisation algorithm would have the same effect as this pre-processing step, one might expect significant computational savings and a unified approach to dealing with such problems.The main goal of this project is to understand if mirror descent is robust to 'outliers', and if it possibly adapts to different types of contaminations in the data. The questions this project tries to answer are the following:- Is there a unified approach to studying statistical learning problems that involve different types of data contamination? What amount of contamination can provably cause any learning algorithm to have poor predictive guarantees?- How is the choice of the mirror map (and hence of the induced geometry) affecting the robustness properties of the mirror descent algorithm? Is there a choice of the mirror map that guarantees the algorithm is adaptive to different types of data contamination?- To what extent can these potential findings be applied in order to explain the robustness properties observed empirically in different models, e.g. deep neural networks?The work on statistical robustness, started in the previous century by Huber, mostly focuses on robust estimation, rather than robust prediction. Techniques used in this area of research offer a potential starting point to approach the above-mentioned questions, along with literature on high-dimensional statistics, mirror descent, and online learning (for example, as in the 'best of both worlds' problem). Our hope is that by combining different methods that are popular in the aforementioned areas, the final result of this project will be a novel theoretical understanding of robust learning, analogous to the classical learning theory framework.This project falls within the EPSRC Statistics and applied probability and EPSRC Theoretical computer science research areas.