Files
Abstract
Second-order methods are often more robust and efficient than first-order methods, particularly in scenarios where the eigenvalues of the Hessian matrix vary significantly in magnitude. However, computing and storing the Hessian, as well as solving the associated Newton systems, poses significant computational and memory challenges. This dissertation addresses this bottleneck under two parameter estimation problems: sparse Discrete Fourier Transform (DFT) recovery from incomplete signals and online statistical inference based on Newton methods. In Chapter 2, we propose a method to recover the sparse DFT of a signal that is both noisy and potentially incomplete, with missing values. The problem is formulated as a penalized least-squares minimization based on the inverse discrete Fourier transform (IDFT) with an L1-penalty term, reformulated to be solvable using a primal-dual interior point method (IPM). Although Krylov methods are not typically used to solve Karush-Kuhn-Tucker (KKT) systems arising in IPMs due to their ill-conditioning, we employ a tailored preconditioner and establish new asymptotic bounds on the condition number of preconditioned KKT matrices. Thanks to this dedicated preconditioner — and the fact that FFT and IFFT operate as linear operators without requiring explicit matrix materialization — KKT systems can be solved efficiently at large scales in a matrix-free manner. Numerical results from a Julia implementation leveraging GPU-accelerated interior point methods, Krylov methods, and FFT toolkits demonstrate the scalability of our approach on problems with hundreds of millions of variables, inclusive of real data obtained from the diffuse scattering from a slightly disordered Molybdenum Vanadium Dioxide crystal. Given the ubiquity of streaming data, online algorithms have been widely used for parameter estimation. In Chapter 3, we study an online sketched Newton method that leverages a randomized sketching technique to perform an approximate Newton step in each iteration, thereby eliminating the computational bottleneck of second-order methods. While existing studies have established the asymptotic normality of sketched Newton methods, a consistent estimator of the limiting covariance matrix remains an open problem. We propose a fully online covariance matrix estimator that is constructed entirely from the Newton iterates and requires no matrix factorization. Compared to covariance estimators for first-order online methods, our estimator for second-order methods is batch-free. We establish the consistency and convergence rate of our estimator, and coupled with asymptotic normality results, we can then perform online statistical inference for the model parameters based on sketched Newton methods. We also discuss the extension of our estimator to constrained problems, and demonstrate its superior performance on regression problems as well as benchmark problems in the CUTEst set.