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

无监督学习的许多领域（即使用未被人类标记的数据进行学习）目前依赖于启发式算法，这些算法在解决方案质量或运行时间上缺乏可证明的保证。事实上，这些潜在的问题——正如目前表述的那样——通常被认为是计算上难以解决的（用一个技术术语来说是NP-hard）。这一建议确定了这些问题的一大集合，这些问题可以被视为扭曲-涉及诸如非负性和稀疏性等约束-在经典线性代数问题上，如求解线性系统，秩计算和特征值/特征向量。PI提议将这组问题统称为线性代数++。该项目将寻求开发对这些问题具有可证明保证的算法。方法将是对实际投入的结构作出适当的假设。这些算法将应用于无监督学习的问题，如主题建模、自然语言处理、语义嵌入、稀疏主成分分析（PCA）、深度网络等领域。这项工作将为大数据处理带来新的、更有效的算法，这些算法将具有可证明的质量保证。它将为机器学习带来新的严格方法。（PI最近的一些工作表明，新的严格方法可以非常实用。）它将通过扩展它的范围和它的标准算法工具包来推进理论计算机科学的艺术状态。它将从根本上为经典线性代数和应用数学贡献新的原语。该项目将培养一批精通理论算法和机器学习的新型研究生。在过去的几年里，PI在这类工作和培训方面有着良好的记录，并将继续与本科生和本科生研究经验（REU）学生合作。在这个项目中发现的任何新算法都将作为开源代码发布。PI还计划在今后几年开展一系列其他外联活动，包括(a)讲习班。(b) 2016- 2017年，他将在西蒙斯研究所（Simons Institute）共同组织一个关于机器学习可证明界限的特殊学期或一年。(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.