eCommons

 

COMPUTATIONALLY EFFICIENT AND ROBUST METHODS FOR LARGE-SCALE OPTIMIZATION AND SCIENTIFIC COMPUTING

dc.contributor.authorCharisopoulos, Vasilis
dc.contributor.chairDavis, Dameken_US
dc.contributor.committeeMemberLewis, Adrianen_US
dc.contributor.committeeMemberDamle, Anilen_US
dc.contributor.committeeMemberBenson, Austinen_US
dc.date.accessioned2024-04-05T18:46:16Z
dc.date.available2024-04-05T18:46:16Z
dc.date.issued2023-08
dc.description355 pagesen_US
dc.description.abstractThis thesis is concerned with the design and analysis of computationally efficient algorithms for large-scale optimization and scientific computing. It aims to address two primary challenges: on one hand, to expand our understandingof the behavior of first-order optimization methods, which enjoy widespread success solving challenging problems such as training deep neural networks. On the other hand, to design algorithms for fundamental problems in scientific computing that can carefully balance the tradeoffs between communication and statistical efficiency arising in distributed environments. We start by studying the performance of iterative schemes for computingeigenvectors of symmetric matrices when the approximation quality is measured using a “row-wise” variation of the commonly used subspace distance, which is a more suitable error proxy for spectral algorithms used in certain graph problems. We obtain improved convergence rates and propose novel stopping criteria that enable substantial computational savings. We next turn to the problem of computing eigenvectors in distributed environments, wherein multiple views of a data matrix are scattered across a network with multiple machines communicating with a central coordinator. Reducing communication is essential for high performance, but common solutionaggregation heuristics for this problem fail due to the invariance of eigenvectors to rotations and reflections. We introduce a communication-efficient algorithm for distributed eigenvector estimation that enjoys deterministic error guarantees and nearly optimal statistical performance when applied to distributed principal component analysis (PCA). Distributed algorithms are prone to failure in the presence of adversaries and silent / soft errors, which can change a fraction of responses in the network arbitrarily. We address this shortcoming in the context of eigenvector estimation by designing an outlier-robust extension of our communication-efficient method that can tolerate a constant fraction of of “malicious” nodes; in contrast, existing approaches break down in the presence of just a few corruptions. We next study robust signal recovery in the blind deconvolution problem. Weshow that nonsmooth recovery formulations for this problem exhibit favorable local conditioning under mild assumptions and are robust to outliers or gross corruptions – properties which are not shared by their smooth counterparts. As a result, we prove that first-order methods for robust signal recovery converge rapidly at a dimension-independent rate when initialized in a neighborhood of the solution set. We complement our analysis with a spectral initialization method that leads to a globally convergent two-stage method. Finally, we present a superlinearly convergent first-order method for nonsmooth optimization, inspired by Newton’s method for solving nonlinear equations. In contrast to prior work, our method can be applied to problems withnonisolated solution sets and allows for the use of automatic differentiation oracles, which are common in modern machine learning. We also develop a numerically efficient implementation that outperforms standard “low-complexity” iterative methods on a suite of signal processing problems.en_US
dc.identifier.doihttps://doi.org/10.7298/mayz-z062
dc.identifier.otherCharisopoulos_cornellgrad_0058F_13721
dc.identifier.otherhttp://dissertations.umi.com/cornellgrad:13721
dc.identifier.urihttps://hdl.handle.net/1813/114592
dc.language.isoen
dc.titleCOMPUTATIONALLY EFFICIENT AND ROBUST METHODS FOR LARGE-SCALE OPTIMIZATION AND SCIENTIFIC COMPUTINGen_US
dc.typedissertation or thesisen_US
dcterms.licensehttps://hdl.handle.net/1813/59810.2
thesis.degree.disciplineOperations Research and Information Engineering
thesis.degree.grantorCornell University
thesis.degree.levelDoctor of Philosophy
thesis.degree.namePh. D., Operations Research and Information Engineering

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Charisopoulos_cornellgrad_0058F_13721.pdf
Size:
6.41 MB
Format:
Adobe Portable Document Format