Second-order Hessian-free methods for statistical learning and stochastic optimization

机器学习在过去十年中的成功对数学优化社区产生了深远的影响，并重新引起了人们对随机梯度下降方法的兴趣。这种方法的优点是提供廉价的迭代，允许在优化开始时快速进行，并避免存储密集矩阵，这在处理非常大量的参数时是禁止的。然而，他们有困难的收敛接近解决方案，依靠消失的步长，以保证理论收敛。该算法可能会出现困难，以达到附近的解决方案，这取决于起点。我们研究了二阶Hessian自由策略，以利用现有的非线性规划理论，同时允许随着数据和决策变量的数量而扩展。该方法依赖于自适应样本平均近似（SAA），控制相对于所实现的估计的目标函数减少时，相比于统计噪声的样本大小，在一个信任区域的框架和标准方差减少技术。在每次迭代中，拟牛顿候选迭代可以得到没有显式矩阵存储，我们探讨了如何使用典型的估计问题的结构，以改善的方法。拟议的研究的第二个目标是利用我们在模型上获得的统计信息来制定更好的早期停止策略。它们尤其重要，因为需要靠近解决方案的大样本，从而导致代价高昂的迭代。另一个好处是可以为建模者提供一些关于找到的解决方案的剩余不确定性的信息。我们还探讨了不独立和相同分布的观察结果的影响，因为它们可能导致有偏见的解决方案，并且当模型用于制定影响个人的政策时，可能对某些社会社区产生负面影响，例如在交通或能源方面。类似地，模型误设定对于分析算法收敛性和解决方案鲁棒性都很重要。我们考虑的另一个重要方面是可行集，因为机器学习中使用的大多数优化算法仅针对无约束问题设计。然而，许多真实的应用，例如在能源中，包括非线性约束，其表达式可以依赖于实现的不确定性，并且不保证可行集是凸的。一个标准的方法是转向旨在找到一个KKT解决方案的方法，但随机逼近方法在这方面受到的关注要少得多，SAA方法也提出了额外的挑战，因为自适应采样策略面临更多的困难，以利用信息几何和样本可能必须进行调整时，它是重要的，以满足所有或几乎所有的情况下的一些约束。

The success of machine learning this last decade has had a deep impact in the mathematical optimization community and renewed interest in methods as stochastic gradient descent. Such an approach has the advantage to provide cheap iterations, allowing fast progress at the beginning of the optimization, and to avoid the storage of dense matrices, prohibited when dealing with a very large number of parameters. They however have difficulties to converge close to the solution, relying to vanishing step sizes to guarantee theoretical convergence. The algorithm can present difficulties to reach a vicinity of solution depending on the starting point. We investigate second-order Hessian-free strategies to capitalize on the existing nonlinear programming theory, while allowing to scale with the number of data and decision variables. The methods rely on adaptive sample average approximations (SAA), controlling the sample size with respect to the achieved estimated objective function reduction when compared to the statistical noise, within a trust-region framework and standard variance reduction techniques. At each iteration, quasi-Newton candidate iterates can be obtained without explicit matrix storage, and we explore how to use the structure of typical estimation problems to improve the approach. A second objective of the proposed research consists in capitalizing on the statistical information that we obtain on the model to develop better early stopping strategies. They are especially important as large samples are required close to the solution, leading to costly iterations. Another benefit is the possibility to provide the modeler with some information about the residual uncertainty at the found solution. We also explore the effect of observations that are not independently and identically distributed, as they could lead to biased solutions, and possibly have a negative impact on some social communities when the model is used to elaborate policies that impact individuals, for instance in transportation or energy. Similarly, model misspecifications are important to analyze, both in terms of algorithm convergence and in terms of solution robustness. Another important aspect that we consider is the feasible set as most of the optimization algorithms used in machine learning are designed for unconstrained problems only. However, many real applications, for instance in energy, include nonlinear constraints whose expressions can depend on the realization of the uncertainty, and the feasible set is not guaranteed to be convex. A standard approach is to turn to methods aiming to find a KKT solution, but stochastic approximation methods have received much less attention in this context, and SAA methods present additional challenges too, as adaptive sampling strategies face more difficulties to exploit the information geometry and the sample can have to be adjusted when it is important to satisfy some constraints for all or nearly all scenarios.