Novel Frameworks for Auctions and Optimization by Zeyuan Allen-Zhu B.S. in Mathematics and Physics, Tsinghua University (2010) S.M. in Electrical Engineering and Computer Science, MIT (2012) Submitted to the Department of Electrical Engineering and Computer Science in partial fulfillment of the requirements for the degree of Doctor of Science at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY September 2015 (cid:13)c Massachusetts Institute of Technology 2015. All rights reserved. Author .............................................................. Department of Electrical Engineering and Computer Science August 17, 2015 Certified by.......................................................... Jonathan A. Kelner Associate Professor of Applied Mathematics Thesis Supervisor Certified by.......................................................... Silvio Micali Ford Professor of Engineering Thesis Supervisor Accepted by......................................................... Leslie A. Kolodziejski Chair, Department Committee on Graduate Theses 2 Novel Frameworks for Auctions and Optimization by Zeyuan Allen-Zhu Submitted to the Department of Electrical Engineering and Computer Science on August 17, 2015, in partial fulfillment of the requirements for the degree of Doctor of Science Abstract This thesis contains two parts. Part I introduces novel frameworks for modeling uncertainty in auctions. This enables us to provide robust analysis to alternative specifications of preferences and information structures in Vickrey and VCG auctions. Part II introduces novel frameworks for understanding first-order methods in op- timization. This enables us to (1) break 20-year barriers on the running time used for solving positive linear programs, (2) reduce the complexity for solving positive semidefinite programs, and (3) strengthen the theory of matrix multiplicative weight updates and improve the theory of linear-sized spectral sparsification. Thesis Supervisor: Jonathan A. Kelner Title: Associate Professor of Applied Mathematics Thesis Supervisor: Silvio Micali Title: Ford Professor of Engineering 3 4 To my mum, Xiaoli Xu 5 6 Acknowledgments 暮色苍茫看劲松，乱云飞渡仍从容。天生一个仙人洞，无限风光在险峰。 — Zedong Mao I would like to thank Professor Silvio Micali for his careful and close supervision in the past five academic years. Not only his inspiring and idiosyncratic talk in mechanism design inspired me to enter the field of game theory, it was also his very first choice that brings me to the theory family of MIT CSAIL. I cannot appreciate more on this. It was also my extreme fortune to be supervised by Professor Jonathan Kelner who nurtured me, supported me, and inspired me with his knowledgeable experiences and insightful comments to nearly all the research areas surrounding computer science. It was such a wonderful experience and a unique memory to be co-supervised by both Silvio and Jon during my doctoral studies, and there are lots of things that I can continue to learn from them regarding how they have become such world-class researchers. I would like to thank Professors Shafi Goldwasser and Nir Shavit for their special and precious encouragements during many periods of my graduate program. I would like to thank Alessandro Chiesa who introduced me all the secrets about MIT, so that I can integrate into this big family without difficulty. I would like to thank Lorenzo Orecchia who discussed with me all of the crazy ideas so that I can bravely start a new research direction when there are only two years left in my graduate program. Beyond this thesis, I am fortunate to have collaborated extensively with, in al- phabetical order, Rati Gelashvili, Silvio Lattanzi, Zhenyu Liao, Vahab Mirrokni, Sasa Misailovic, IlyaRazenshteyn, MartinRinard, NirShavit, ChristianSommerandYang Yuan, and more or less with many others at MIT. I am also grateful for the supports thatIhavereceivedbeyondresearch, includingthatfromourinstructors, ourstudents and our secretaries in the CSAIL Theory Group. Last but not least, I never forget to thank my dearest mother for her unceasing support and unselfish dedication to my family, my education, throughout the past 27 years. For all of the above, and the unnamed, please allow me to express my deepest gratitude, now and always. Financial Acknowledgements. This thesis and my graduate study at MIT are fully supported by • 9 months of Greater China Fellowship, • 3 months Big George Ventures Fund from Ray Sidney, • 6 months of Simons Award from the Simons Foundation, • 3 months of Bridge Fund from the MIT EECS department, • 4.5 months of Teaching Assistantship from Professor David Karger, 7 • 9 months of Research Assistantship from Professor Jonathan Kelner, and • 25.5 months of Research Assistantship from Professor Silvio Micali. I would like to sincerely thank all of the supporters above that make my study at MIT possible. Besides, I would also like to thank the Akamai Foundation and the Simons Foundation that put together $22,000 travel and equipment money that has made my collaborations outside MIT more than easy and enjoyable. Other Acknowledgements. I would like to thank a United Airline operated flight and the Simons Institute at Berkeley at which places the results of Chapter 8 of this thesis was obtained. I would like to thank the MIT office 32-G804 and its owner at the time, Cong Yan, without its quite location and the owner’s hospitality the main result of Chapter 6 of this thesis cannot be produced. Part I of this thesis, namely, Chapters 1, 2 and 3 were obtained at my MIT CSAIL office 32-G636 with the presence of my lovely officemates. The rest of Part II, namely, Chapters 4, 5 and 7 were obtained at my MIT Math desk E17-301A as well as a bright and amazing common study room of the Ashdown House. I would like to thank MIT that provides awesome research environments like these. 8 Contents I Novel Frameworks for Auctions 14 1 Knightian Analysis of the Vickrey Mechanism 15 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2.1 Notation for Multi-Unit Auctions . . . . . . . . . . . . . . . . 18 1.2.2 Knightian Valuation Uncertainty . . . . . . . . . . . . . . . . 19 1.3 The First Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.4 The Second Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.5 The Third Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.A Knightian Revelation Principle . . . . . . . . . . . . . . . . . . . . . 26 1.B Proof of Theorem 1.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.C Proof of Theorem 1.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.D Proof of Corollary 1.10 . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.E Proof of Theorem 1.14 . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.E.1 A Structural Lemma . . . . . . . . . . . . . . . . . . . . . . . 32 1.E.2 Deducing Theorem 1.14 from Lemma 1.18 . . . . . . . . . . . 34 1.F The Set of Undominated Strategies is Non-Empty . . . . . . . . . . . 36 1.G The Work of Lopomo, Rigotti, and Shannon . . . . . . . . . . . . . . 37 2 Knightian Self Uncertainty in the VCG Mechanism for Unrestricted Combinatorial Auctions 39 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.1.1 Theorem 2.1: VCG Auction in Undominated Strategies . . . . 40 2.1.2 Theorem 2.2: VCG Auctions in Regret-Minimizing Strategies 41 2.1.3 The Meaningfulness of Theorem 2.2 and a Rationality Bridge Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.1.4 In Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.1.5 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.3 Classical and Knightian Basic Notions . . . . . . . . . . . . . . . . . 45 2.4 A Weaker Version of Theorem 2.1 . . . . . . . . . . . . . . . . . . . . 47 9 2.5 Proof of Theorem 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.A Theorem 2.1: How to Obtain a Stronger Result and a Characterization 55 2.A.1 Geometric Description of V(K ) . . . . . . . . . . . . . . . . . 56 i 2.B Proof of One Side of Theorem 2.1a . . . . . . . . . . . . . . . . . . . 59 2.B.1 Case 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.B.2 Case 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 2.B.3 Case 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.C Proof of Theorem 2.1b . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.C.1 Construction of The Hard Instance . . . . . . . . . . . . . . . 69 2.C.2 Putting Things Together . . . . . . . . . . . . . . . . . . . . . 72 2.D Theorem 2.2 with Mixed Strategies . . . . . . . . . . . . . . . . . . . 74 2.D.1 Why Allowing Mixed Strategies Yields a Different Result . . . 74 2.D.2 Proof of Theorem 2.2(cid:48) . . . . . . . . . . . . . . . . . . . . . . 75 3 Bridging Utility Maximization and Regret Minimization 81 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.2 Basic Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.3 Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.4 Implications for Mechanism Design . . . . . . . . . . . . . . . . . . . 85 3.5 Pure vs. Mixed Strategies . . . . . . . . . . . . . . . . . . . . . . . . 86 II Novel Frameworks for Optimization 87 4 Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent 89 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.1.1 UnderstandingFirst-OrderMethods:GradientDescentandMir- ror Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.1.2 Our Conceptual Question . . . . . . . . . . . . . . . . . . . . 94 4.1.3 Accelerated Gradient Method From Linear Coupling . . . . . 95 4.1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.2.1 Review of Primal Descent . . . . . . . . . . . . . . . . . . . . 97 4.2.2 Review of Mirror Descent . . . . . . . . . . . . . . . . . . . . 98 4.2.3 Remark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.3 Warm-Up Accelerated Gradient Method with Fixed Step Length . . . 100 4.4 Final Accelerated Gradient Method with Variable Step Lengths . . . 103 4.5 Strong Convexity Version of Accelerated Gradient Method . . . . . . 105 4.A Several Remarks on First-Order Methods . . . . . . . . . . . . . . . . 106 4.A.1 Importance of Non-Euclidean Norms . . . . . . . . . . . . . . 106 10