matH of Algorithms, Data, and Decisions (HADD) Research Group
The matH of Algorithms, Data, and Decisions (HADD) Research Group (Prof. Haddock) is recruiting students for multiple projects in Spring 2027 (with possible funded positions in Summer 2027):
The first project investigates how randomized sketching techniques can be adapted to constrained least-squares problems, with a particular focus on active-set methods for nonnegative least squares (NLS). While randomized methods and sketch-and-project algorithms have dramatically improved the efficiency of unconstrained least-squares solvers, their extension to constrained settings remains poorly understood. Many important data analysis and machine learning pipelines rely on constrained least-squares subroutines, especially those involving nonnegativity or simplex constraints, yet existing randomized approaches often fail to preserve the combinatorial and geometric structure that active-set methods depend on.
The primary goal of the research is to understand how sketching affects the geometry of constrained least-squares problems and to develop theory and algorithms that allow sketching to be safely and effectively integrated into active-set methods. In particular, the project aims to identify conditions under which sketching preserves the active set (i.e., the support of the solution) and to characterize when and why sketched problems may lead to incorrect constraint identification. Ultimately, this work seeks to bridge the gap between randomized numerical linear algebra and classical combinatorial optimization methods.
The second project investigates how randomized iterative methods can be made robust to adversarial corruptions in large-scale linear systems, with a particular focus on column-action methods such as Quantile Randomized Gauss-Seidel (QRGS). Randomized row-action methods like Randomized Kaczmarz have well-understood convergence guarantees, and quantile-based variants (QRK) are known to converge to the solution of the uncorrupted system even when a fraction of the right-hand side is arbitrarily corrupted. Column-action methods, which update a single coordinate at a time and keep a small memory footprint, have received far less attention in this setting. Existing analyses do not extend to them directly, because the quantile mask that removes suspect equations changes at every iteration and is not aligned with the set of truly clean equations.
The primary goal of the research is to prove that QRGS converges linearly in expectation to the solution of the uncorrupted problem, and to characterize when and why it does. A second aim is to extend these ideas to sketch-and-project methods, including block and sketched variants that combine quantile-based trimming of the residual with sketching of the system, and to determine what conditions on the sketch and the corruption level preserve robustness. Ultimately, this work seeks to bridge the gap between corruption-robust optimization and randomized numerical linear algebra, and to give a unified theory for corruption-robust row-, column-, and sketch-based iterative solvers.
We consider the mathematics of data, models for making decisions with data, and methods for training such models. Recent work in this group has focused upon iterative methods for problems suffering from adversarial corruption, randomized iterative methods for tensor decomposition and regression, and methods for learning on graphs and hypergraphs.
These projects would allow development of randomized methods, which are particularly efficient for large-scale data, in a new regime of problems where solutions must satisfy given constraints or where the problem-defining data has been corrupted or adversarially perturbed.