Back to search

Boston University

Optimization for linear structures: fast and differentially private algorithms

Abstract

dc:description.abstract

Linear 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 × 3

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53710

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Nguyen, Ta Duy. Optimization for linear structures: fast and differentially private algorithms. doctoral thesis, Boston University, 2026. https://hdl.handle.net/2144/53710