AF: Small: Linear Algebra++ and applications to machine learning

非监督学习的许多领域(即，使用尚未被人类标记的数据进行学习)目前依赖于启发式算法，这些算法缺乏对解质量或运行时间的可证明保证。事实上，按照目前的表述，潜在的问题通常是众所周知的，在计算上很难处理(用专业术语来说，就是NP难)。这一建议确定了一大组这些问题，这些问题可以被视为经典线性代数问题(如解线性系统、秩计算和特征值/特征向量)上的扭曲-涉及非负性和稀疏性等约束。PI建议将这组问题统称为线性代数。该项目将寻求为这些问题开发具有可证明保证的算法。方法将是对现实投入的结构做出适当的假设。这些算法将应用于无监督学习中的问题，如主题建模、自然语言处理、语义嵌入、稀疏主成分分析(PCA)、深度网络等。这项工作将带来新的、更高效的大数据处理算法，并将带来可证明的质量保证。它将为机器学习带来新的严格方法。(PI最近的一些工作表明，新的严格方法可能非常实用。)它将通过扩大它的范围和它的标准算法工具包来推进理论计算机科学的最新水平。它将从根本上为经典线性代数和应用数学贡献新的原语。该项目将培养新一代的研究生，他们将流利地掌握理论算法和机器学习。在过去的几年里，PI在这类工作和培训方面有着良好的记录，并将继续这方面的工作，包括与本科生和本科生研究经验(REU)的合作。作为该项目的一部分，任何新发现的算法都将作为开放源代码发布。和平协会还计划在今后几年内开展一系列其他外联活动，包括：(A)举办讲习班。(B)2016-17年在西蒙斯研究所开设一个关于机器学习可证明界限的特别学期或学年，由他共同组织。(C)基于他的新研究生课程的一本关于研究生算法的新书，这本书试图重新定位算法培训，以应对当今的计算机科学问题。(D)针对广大听众的一系列演讲，他每年都会举办几次。这些技术将建立在PI和其他人在非负矩阵分解、稀疏编码、交替最小化等问题上的最新进展的基础上。它们涉及平均案例分析、经典线性代数、凸优化、数值分析等，也涉及全新的想法。它们可能会对机器学习和算法产生革命性的影响。

Many areas of unsupervised learning (i.e, learning with data that has not been labeled by humans) currently rely on heuristic algorithms that lack provable guarantees on solution quality or running time. In fact the underlying problems - as currently formulated - are often known to be computationally intractable (NP-hard, to use a technical term). This proposal identifies a big set of these problems that can be seen as twists - involving constraints such as nonnegativity and sparsity - on classical linear algebra problems like solving linear systems, rank computation, and eigenvalues/eigenvectors. The PI has proposed calling this set of problems collectively as Linear Algebra++. The project will seek to develop algorithms with provable guarantees for these problems. The methodology will be to make suitable assumptions about the structure of realistic inputs. The algorithms will be applied to problems in unsupervised learning, in areas such as topic modeling, natural language processing, semantic embeddings, sparse principle components analysis (PCA), deep nets, etc.The work will lead to new and more efficient algorithms for big data processing that will come with provable guarantees of quality. It will bring new rigorous approaches to machine learning. (Some recent work of the PI shows that the new rigorous approaches can be quite practical.) It will advance the state of art in theoretical computer science by expanding its range and its standard toolkit of algorithms. It will contribute fundamentally new primitives to classical linear algebra and applied mathematics.The project will train a new breed of graduate students who will be fluent both in theoretical algorithms and machine learning. The PI has a track record in this kind of work and training during the past few years and will continue this including working with undergrads and Research Experiences for Undergraduates (REU) students. Any new algorithms discovered as part of this project will be released as open source code. The PI also plans a series of other outreach activities in the next few years including (a) A workshop. (b) A special semester or year at the Simons Institute in 2016-17 on provable bounds in machine learning which he will coorganize. (c) A new book on graduate algorithms based upon his new grad course, which tries to re-orient algorithms training for today's computer science problems. (d) A series of talks aimed at broad audiences, of which he gives several each year.The techniques will build upon recent progress by the PI and others on problems such as nonnegative matrix factorization, sparse coding, alternating minimization etc. They involve average case analysis, classical linear algebra, convex optimization, numerical analysis, etc., as well involve completely new ideas. They could have a transformative effect on machine learning and algorithms.