Stochastic Optimization and Subgraph Search

In this thesis, we study randomized algorithms for numerical linear algebra and pattern matching algorithms for multiplex networks. We first analyze the convergence of two classes of randomized iterative methods for solving large linear systems of equations. In particular, we analyze sketch-and-project methods with adaptive sampling strategies and parallelized randomized Kaczmarz methods with averaging. We observe empirically that the convergence of these methods reflects the worst-case convergence theory. We later discuss subgraph matching and various related problems including inexact search. We introduce filtering algorithms that are specialized to multiplex networks. In both the exact and inexact settings, we aim to understand the entire solution space rather than simply finding one match for a given pattern. We observe that there are often a combinatorially large number of matches depending on the amount of symmetry in the pattern and data