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

点击翻译按钮获取中文摘要

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.