Optimization for large-scale doubly-penalized ANOVA modeling and understanding accelerated gradient methods
Creators: name: Fu, Penghui
Publisher: name: No Publisher Supplied
Year: 2023

description: Optimization plays a central role in modern statistics and machine learning. The analysis of large-scale and complex data facilitates the study of efficient and scalable algorithms. First-order methods, which mainly rely on gradients or subgradients, have become the workhorse in this trend due to their relatively low per-iteration cost and ease of parallelization. This dissertation considers two topics around first-order methods. The first topic is the development of efficient computational methods for large-scale doubly-penalized ANOVA modeling. The second topic is about theoretically understanding the mechanism of accelerated gradient methods, which is a profound phenomenon in optimization. Doubly penalized ANOVA modeling (DPAM) is a recently proposed nonparametric regression method based on functional analysis-of-variance (ANOVA) decomposition of the underlying regression functions, with component functions jointly penalized by hierarchical total variations (HTVs) and empirical norms. The existing backfitting algorithm AS-BDT (active-set block descent and thresholding) is not designed to handle large datasets, especially with non-sparse blocks. We propose two primal-dual algorithms, including both batch and novel stochastic versions, and also a new majorization-minimization (MM) algorithm as large-scale alternatives to AS-BDT. The new stochastic versions are delicately designed to resolve the difficulty of dealing with the non-separable empirical-norm penalty, which makes existing stochastic algorithms intractable. The validity and advantage of our stochastic primal-dual algorithms compared with their batch versions and the existing AS-BDT algorithm are demonstrated through extensive numerical experiments on real and simulated datasets, especially in large-scale and non-sparse settings. Stemming from the ground-breaking algorithm in cite{nesterov1983method}, the acceleration phenomenon has been widely established in the optimization literature, where after suitable modifications of a first-order method, the convergence guarantee can be improved, even attaining the complexity lower bound with a similar cost as before. However, the underlying mechanism and driving force of acceleration are not yet fully understood, even with regard to Nesterov's original acceleration on gradient descent for unconstrained smooth and convex minimization. We formulate general classes of first-order gradient algorithms and establish sufficient conditions for when the algorithms achieve Nesterov’s acceleration in both the strongly and general convex settings via concise Lyapunov analyses. By comparing the convergence rates of our discrete algorithms and their limiting ordinary differential equations (ODEs), the conditions for acceleration can be partially explained but a considerable gap exists. In addition, we propose a novel Hamiltonian assisted gradient method (HAG), which offers a framework that provides simple, meaningful, and unified interpretations of our conditions.