Session: Advances in Solving Large-Scale Problems: Accelerated Methods and Sharp Analyses (II)
Chair: Liwei Jiang Sen Na
Cluster: Optimization Under Uncertainty and Data-driven Optimization
Talk 1: Online Learning Guided Quasi-Newton Methods: Improved Global Non-Asymptotic Guarantees
Speaker: Ruichen Jiang
Abstract: Quasi-Newton methods are popular iterative algorithms known for their superior practical performance over gradient-descent-type methods. However, existing theoretical results for this class of algorithms fail to fully justify their observed advantages. In this talk, we discuss our recent efforts to address this issue. Specifically, in the strongly convex setting, we propose the first “globally” convergent quasi-Newton method that achieves an explicit “non-asymptotic superlinear” rate. We show that the rate presented for our method is provably faster than gradient descent after at most $O(d)$ iterations, where $d$ is the problem dimension. Additionally, in the convex setting, we present an accelerated variant of our proposed method that provably outperforms the accelerated gradient method and converges at a rate of $O(\min\{1/k^2, \sqrt{d \log k }/ k^{2.5}\})$, where $k$ is the number of iterations. To attain these results, we diverge from conventional approaches and construct our quasi-Newton methods based on the Hybrid Proximal Extragradient framework and its accelerated variants. Furthermore, a key algorithmic concept in our methods is an online learning framework for updating the Hessian approximation matrices. Specifically, we relate our method's convergence rate to the regret of a specific online convex optimization problem in the matrix space and choose the sequence of Hessian approximation matrices to minimize its overall regret.
Talk 2: Accelerated stochastic approximation with state-dependent noise
Speaker: Tianjiao Li
Abstract: We consider a class of stochastic smooth convex optimization problems under rather general assumptions on the noise in the stochastic gradient observation. As opposed to the classical problem setting in which the variance of noise is assumed to be uniformly bounded, herein we assume that the variance of stochastic gradients is related to the “sub-optimality” of the approximate solutions delivered by the algorithm. Such problems naturally arise in a variety of applications, in particular, in the well-known generalized linear regression problem in statistics. However, to the best of our knowledge, none of the existing stochastic approximation algorithms for solving this class of problems attain optimality in terms of the dependence on accuracy, problem parameters, and mini-batch size. We discuss two non-Euclidean accelerated stochastic approximation routines—stochastic accelerated gradient descent (SAGD) and stochastic gradient extrapolation (SGE)—which carry a particular duality relationship. We show that both SAGD and SGE, under appropriate conditions, achieve the optimal convergence rate, attaining the optimal iteration and sample complexities simultaneously. However, corresponding assumptions for the SGE algorithm are more general; they allow, for instance, for efficient application of the SGE to statistical estimation problems under heavy tail noises and discontinuous score functions. We also discuss the application of the SGE to problems satisfying quadratic growth conditions, and show how it can be used to recover sparse solutions. Finally, we report on some simulation experiments to illustrate numerical performance of our proposed algorithms in high-dimensional settings.
Talk 3: SQP for physics-informed machine learning
Speaker: Qi Wang
Abstract: A methodology for physics-informed machine learning is presented, which incorporates prior information in the training problem through hard constraints, rather than the typical modern practice of using soft constraints (i.e., regularization terms or penalty methods). The methodology is based on a recently proposed stochastic-gradient-based SQP algorithm and is extended to use Adam-type step computation in the presence of hard constraints. The effectiveness of the method is demonstrated through numerical experiments on physics-informed learning problems.
