AF: Medium: Towards Provable Bounds for Machine Learning

机器学习（ML）的许多领域目前依赖于没有性能保证的启发式算法，事实上，底层问题在计算上是难以解决的。 拟议的项目将导致新的机器学习算法与可证明的保证。 PI将利用平均案例分析，半随机模型，近似，解的稳定性和近似线性代数的理论思想，并开发新的工具和技术。 这一奋进的好处将发生在各个领域。 理论计算机科学将受益于获得新的问题和研究议程，以及算法和数学工具的进一步发展。 机器学习将受益于获得新的模型（希望比目前使用的模型更容易处理），新的思维模式和新的算法。 证明算法边界的任务将提供对算法何时有效或无效的洞察，以及对现有算法的修改建议。该项目将涉及培训新一代研究生和博士后，他们将精通理论算法和机器学习。 PI在过去几年中获得了提供这种培训和指导的经验，并将继续这样做，包括与本科生合作。 PI将通过演讲，教学和创建新的课程材料（包括视频）来传播该项目的理念。 还将组织一次专门讨论研究专题的专门讲习班。 开源软件实现将基于发现的任何新的学习算法发布。

Many areas of machine learning (ML) currently rely on heuristic algorithms with no performance guarantees, and, in fact, the underlying problems are computationally intractable. The proposed project will lead to new machine learning algorithms with provable guarantees. The PIs will leverage theoretical ideas from average case analysis, semi-random models, approximation, solution stability, and approximate linear algebra, and develop new tools and techniques. Benefits from this endeavor will occur across fields. Theoretical computer science will benefit by gaining new problems and research agendas, and further development of algorithmic and mathematical tools. Machine learning will benefit by gaining new models (hopefully, more tractable than the ones currently in use), new modes of thinking, and new algorithms. The task of proving bounds on algorithms will provide insight into when they do or do not work, as well as suggest modifications to existing heuristics.The project will involve training a new generation of graduate students and postdocs who will be fluent both in theoretical algorithms and machine learning. The PIs gained experience in delivering this kind of training and mentoring during the past couple of years and will continue this, including working with the undergraduate students. The PIs will disseminate the ideas of this project by lecturing, teaching, and creating new course materials, including videos. One specialized workshop will also be organized, devoted to the topics of study. Open-source software implementation will be released based upon any new learning algorithms that are discovered.