AF: Small: New classes of optimization methods for nonconvex large scale machine learning models.

智能系统，比如根据过去的兴趣推荐音乐或电影，或者根据标记的样本识别人脸或笔迹，通常使用“监督学习”从示例中学习。“系统试图找到一个预测函数：歌曲、电影、图像或笔运动的特征值的组合，在已知的输入上，产生与已知偏好一致的评分值。一些组合可能会添加简单的正或负权重参数（吉他越多越好，或者我真的不想要手风琴），而其他组合可能会更复杂（既不是太大声也不是太柔和）。 如果可以找到这样一个函数的参数，那么可以希望，在新的输入上，该函数将是偏好的良好近似。在科学计算中，有许多优化技术用于找到最佳参数。 所谓的“梯度法”就像一个团体徒步旅行，天黑后被困在山上;成员们想下山迅速返回山谷，但要小步走，以免绊倒。只要有一点点光，小组就可以发现更多关于其附近的信息，以1）建议最佳方向，2）采取更长的步骤而不会绊倒，或者3）将不同的成员派往不同的方向，以便有人找到最佳方法。当有许多参数（不仅仅是纬度和经度）时，有更多的方向要走。 简单的组合定义了简单的（也称为凸）谷，许多基于优化的学习方法（包括支持向量机（SVM），最小二乘法和逻辑回归）已被有效地应用于寻找最佳参数。 更复杂的组合有时会导致更好的学习，可能会定义非凸谷，因此已知的方法可能会陷入低谷，或者必须采取非常小的步骤-它们通常缺乏理论上的收敛保证，并且在实践中并不总是工作得很好。这个项目将探索机器学习的非凸优化，有三种类似于徒步旅行者的技术。光的使用：首先，将探索新的技术，利用近似二阶导数的随机方法，这有望提高性能的随机梯度方法，避免收敛到鞍点，并提高复杂性保证一阶方法。与已提出的其他此类技术相比，这些方法将是独特的，因为它们将被设置在信任区域框架内，对其的探索是该项目的第二个组成部分。几十年来，信赖域算法为非凸优化提供了更好的性能，但尚未完全用于机器学习，我们相信，当与二阶信息相结合时，可以实现显着的改进（理论上和实践上）。最后，为了使这些方法在大规模环境中有效，需要提供在所有数据可能不存储在单个计算机上的情况下解决信赖域子问题的技术。为了解决这个问题，并行和分布式优化技术将被开发用于解决信赖域子问题和相关问题。 这三个PI与十几个学生一起在利哈伊工作;他们的网站是他们传播研究论文、软件和每周活动新闻的一种方式。该项目由NSF CISE CCF数学基金会和NSF MPS DMS计算数学联合资助。

Intelligent systems that say, recommend music or movies based on past interests, or recognize faces or handwriting based on labeled samples, often learn from examples using "supervised learning." The system tries to find a prediction function: a combination of feature values of the song, movie, image, or pen movements, that, on known inputs, produces score values that agree with known preferences. Some combinations may add with simple positive or negative weight parameters (The more guitar the better, or I really don't want accordion), while others can be more complex (nether too loud nor too soft). If parameters for such a function can be found, then it can be hoped that, on a new input, the function will be a good approximation for the preference. In scientific computing, there are many optimization techniques used to find the best parameters. The type called "gradient methods" is like a group hike that gets caught in the hills after dark; the members want to go downhill to return to the valley quickly, but take small steps so as not to trip. With a little light, the group can discover more about its vicinity to 1) suggest the best direction, 2) take longer steps without tripping, or 3) send different members in different directions so that someone finds the best way. When there are many parameters (not just latitude and longitude) there are many more directions to step. Simple combinations define simple (aka convex) valleys, and many optimization-based learning methods (including support vector machines (SVM), least squares, and logistic regression) have been effectively applied to find the best parameters. More complex combinations that sometime lead to better learning, may define non-convex valleys, so the known methods may get stuck in dips or have to take very small steps -- they often lack theoretical convergence guarantees and do not always work well in practice. This project will explore non-convex optimization for machine learning with three techniques that are analogous to the hikers? use of the light: First, new techniques will be explored for exploiting approximate second-order derivatives within stochastic methods, which is expected to improve performance over stochastic gradient methods, avoid convergence to saddle points, and improve complexity guarantees over first-order approaches. Compared to other such techniques that have been proposed, these approaches will be unique as they will be set within trust-region frameworks, the exploration of which represents the second component of the project. Known for decades to offer improved performance for nonconvex optimization, trust region algorithms have not fully been explored for machine learning, and we believe that, when combined with second-order information, dramatic improvements (both theoretically and practically) can be achieved. Finally, for such methods to be efficient in large-scale settings, one needs to offer techniques for solving trust region subproblems in situations when all data might not be stored on a single computer. To address this, parallel and distributed optimization techniques will be developed for solving trust region subproblems and related problems. The three PIs work together with about a dozen students at Lehigh; their website is one way they disseminate research papers, software, and news of weekly activities. This project is funded jointly by NSF CISE CCF Algorithmic Foundations, and NSF MPS DMS Computational Mathematics.