Show simple item record

dc.contributor.advisorSinger, Yaron
dc.contributor.advisorParkes, David
dc.contributor.advisorRush, Alexander S.
dc.contributor.advisorMitzenmacher, Michael
dc.contributor.authorBalkanski, Eric
dc.date.accessioned2019-12-12T09:23:51Z
dc.date.created2019-05
dc.date.issued2019-05-15
dc.date.submitted2019
dc.identifier.citationBalkanski, Eric. 2019. The Adaptive Complexity of Submodular Optimization. Doctoral dissertation, Harvard University, Graduate School of Arts & Sciences.
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:42029793*
dc.description.abstractIn this thesis, we develop a new optimization technique that leads to exponentially faster algorithms for solving submodular optimization problems. For the canonical problem of maximizing a non-decreasing submodular function under a cardinality constraint, it is well known that the celebrated greedy algorithm which iteratively adds elements whose marginal contribution is largest achieves a 1-1/e approximation, which is optimal. The optimal approximation guarantee of the greedy algorithm comes at a price of high adaptivity. The adaptivity of an algorithm is the number of sequential rounds it makes when polynomially-many function evaluations can be executed in parallel in each round. Since submodular optimization is regularly applied on very large datasets, adaptivity is crucial as algorithms with low adaptivity enable dramatic speedups in parallel computing time. Submodular optimization has been studied for well over forty years now, and somewhat surprisingly, there was no known constant-factor approximation algorithm for submodular maximization whose adaptivity is sublinear in the size of the ground set n. Our main contribution is a novel optimization technique called adaptive sampling which leads to constant factor approximation algorithms for submodular maximization in only logarithmically many adaptive rounds. This is an exponential speedup in the parallel runtime for submodular maximization compared to previous constant factor approximation algorithms. Furthermore, we show that no algorithm can achieve a constant factor approximation in \tilde{o}(log n) rounds. Thus, the adaptive complexity of submodular maximization, i.e., the minimum number of rounds r such that there exists an r-adaptive algorithm which achieves a constant factor approximation, is logarithmic up to lower order terms.
dc.description.sponsorshipEngineering and Applied Sciences - Computer Science
dc.format.mimetypeapplication/pdf
dc.language.isoen
dash.licenseLAA
dc.subjectSubmodular optimization, adaptivity, optimization from samples, learning, algorithms
dc.titleThe Adaptive Complexity of Submodular Optimization
dc.typeThesis or Dissertation
dash.depositing.authorBalkanski, Eric
dc.date.available2019-12-12T09:23:51Z
thesis.degree.date2019
thesis.degree.grantorGraduate School of Arts & Sciences
thesis.degree.grantorGraduate School of Arts & Sciences
thesis.degree.levelDoctoral
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy
thesis.degree.nameDoctor of Philosophy
dc.type.materialtext
thesis.degree.departmentEngineering and Applied Sciences - Computer Science
thesis.degree.departmentEngineering and Applied Sciences - Computer Science
dash.identifier.vireo
dash.author.emailebalkans@gmail.com


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record