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

智能系统根据过去的兴趣来推荐音乐或电影，或者根据标记的样本识别人脸或笔迹，这些智能系统经常使用“监督学习”从例子中学习。系统试图找到预测函数：歌曲、电影、图像或钢笔动作的特征值的组合，在已知输入上产生与已知偏好一致的分数值。一些组合可能会添加简单的正负权重参数(吉他越多越好，或者我真的不想要手风琴)，而另一些组合可能会更复杂(既不太响也不太软)。如果可以找到这样的函数的参数，则可以希望在新的输入上，该函数将是该偏好的良好近似值。在科学计算中，有许多优化技术用于寻找最佳参数。一种叫做“梯度法”的方法就像一群人在天黑后被困在山上；成员们想要下山快速返回山谷，但要小步走，以免绊倒。有了一点光，团队可以更多地了解附近的情况：1)建议最好的方向；2)不绊倒地走更长的路；3)让不同的成员朝着不同的方向前进，以便有人找到最好的方式。当有许多参数(不仅仅是纬度和经度)时，步进的方向会更多。简单的组合定义了简单的(又称为凸)山谷，许多基于优化的学习方法(包括支持向量机、最小二乘和Logistic回归)已被有效地应用于寻找最佳参数。更复杂的组合有时会带来更好的学习，可能会定义非凸谷，因此已知的方法可能会陷入低谷或不得不采取非常小的步骤--它们通常缺乏理论上的收敛保证，并且在实践中并不总是很好地工作。这个项目将探索机器学习的非凸优化，使用三种类似于徒步旅行者的技术？LIGH的用法：首先，将探索在随机方法中利用近似二阶导数的新技术，这有望改善随机梯度方法的性能，避免收敛到鞍点，并改善一阶方法的复杂性保证。与已提出的其他此类技术相比，这些方法将是独特的，因为它们将设置在信任区框架内，对信任区框架的探索是项目的第二个组成部分。几十年来，信赖域算法为非凸优化提供了更好的性能，但尚未被充分探索用于机器学习，我们相信，当与二阶信息相结合时，可以实现显著的改进(无论是理论上还是实践上)。最后，为了使这种方法在大规模环境中有效，需要提供在可能无法将所有数据存储在一台计算机上的情况下解决信任域子问题的技术。为了解决这一问题，将开发并行和分布式优化技术来解决信赖域子问题和相关问题。这三位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.