Boston University
Optimization for linear structures: fast and differentially private algorithms
Abstract
dc:description.abstractLinear formulations---including linear regression, linear programming, and principal component analysis---occupy a central position in optimization. While these classic problems have been studied extensively, the modern computational era introduces two critical challenges: the need for algorithms that bridge the gap between asymptotic theoretical guarantees and practical, large-scale performance, and the necessity of protecting sensitive data through frameworks like differential privacy. This thesis investigates algorithmic advancements that address these requirements across three primary classes of problems. First, we explore \ellp-regression and quasi-self-concordant optimization. We develop new Iteratively Reweighted Least Squares-based algorithms that achieve state-of-the-art theoretical complexity while significantly outperforming existing benchmarks in practice. Second, we study linear programming by focusing on the densest subgraph problem as a case study for structure-aware optimization. We introduce several new algorithms---leveraging Multiplicative Weight Updates, Area Convexity, and Random Coordinate Descent---that bridge the gap between theoretical state-of-the-art and empirical efficiency. Next, we study solving linear programs under differential privacy. We provide differentially private algorithms based on a Rescaled Perceptron method that protect the privacy of individuals contributing to the problem's constraints, achieving the best known guarantee on the number of constraints violated. Finally, we investigate the principal component analysis problem under differential privacy. We introduce a new private power iteration method which maintains row-level privacy and adapts to the coherence of the input matrix, providing ``beyond-worst-case'' utility guarantees for matrices with low coherence.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Computer Science
- Grantor
- Boston University
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Nguyen, Ta Duy
- Advisor dc:contributor.advisor
-
- Ene, Alina
- ORCID dc:identifier.orcid
Subjects
dc:subject × 3Rights
dc:rights- Statement dc:rights
-
- Attribution 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53710