Optimism and Robustness: Learning From Structured and Semi-Random Inputs

Traditionally, algorithms have been studied under two regimes: worst-case analysis, which makes no assumptions about the input, and average-case analysis, which assumes that inputs are drawn from a certain distribution. However, real-world inputs rarely conform to either of these extremes. A new paradigm known as “beyond worst-case analysis” seeks to bridge the gap between the two. In this thesis, we study several problems and their algorithms under appropriate beyond worst-case models, aiming to provide more realistic and practically relevant performance guarantees. In the first part of this thesis, we focus on improving algorithm performance on non-worst-case inputs (structured inputs). In Chapter 2, we study the Boolean satisfiability problem (SAT) in the framework of learning-augmented algorithms, where the problem instance is provided with a prediction that contains partial information of an optimal solution. We study both the decision and optimization problem of SAT under two forms of predictions, namely the subset advice and the label advice. In Chapter 3, we study non-center-based clustering under Bilu-Linial stability assumptions, which assumes that the problem instance has a unique optimal solution that stays unchanged under small perturbation of the input. We focus on the minimizing sum-of-radii (MSR) and minimizing sum-of-diameters (MSD) objectives, and provide polynomial time solutions under stability assumptions. In the second part of this thesis, we focus on enhancing algorithm robustness to contamination in average-case inputs (semi-random inputs). In the context of low-rank matrix recovery problems, this means a monotone adversary can add arbitrary data from the distribution to break the necessary regularity conditions satisfied by fully random inputs. In Chapter 4, we study the matrix completion problem, whose goal is to recover a ground-truth matrix from incomplete and noisy observations of its entries. In Chapter 5, we study the matrix sensing problem, where the goal is to recover the ground-truth matrix based on linear measurements from a given set of sensing matrices.

Author dc:creator

• Xing Gao (112909)

• Mathematics

Statement dc:rights

• In Copyright

DOI dc:identifier

https://doi.org/10.25417/uic.31451128.v1

OAI identifier oai:identifier

oai:figshare.com:article/31451128