Back to search

Boston University

A regularization perspective on spectral sparsification

Abstract

dc:description.abstract

In this thesis, we study how to obtain faster algorithms for spectral graph sparsifi-cation by applying continuous optimization techniques. Spectral sparsification is thetask of reducing the number of edges in a graph while maintaining a spectral ap-proximation to the original graph. Our key conceptual contribution is the connectionbetween spectral sparsification and regret minimization in online matrix games, i.e.,online convex programming over the positive semidefinite cone. While this connec-tion was previously noted [24, 47], we formally reduce graph sparsification to a matrixregret minimization problem, which we solve by applying mirror descent with a non-entropic regularizer. In this way, we not only obtain a new proof of the existenceof linear-sized spectral sparsifiers, originally given by [19], but improve the runningtime from Ω(n4)([19, 54]) to almost quadratic. More generally, our framework canalso be applied for the matrix multi-armed bandit online learning problem to reducethe regret bound to the optimalO(√nT), compared to theO(√nTlog(n) given bythe traditional matrix-entropy regulariz

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
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Liao, Zhenyu
Advisor dc:contributor.advisor
  • Orecchia, Lorenzo

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Liao, Zhenyu. A regularization perspective on spectral sparsification. doctoral thesis, Boston University, 2019. https://hdl.handle.net/2144/38975