- talks - lists.cs.princeton.edu

Fwd: TOMORROW, January 9, 2019 at 4:30pm in 101 Sherrerd Hall - Jason Lee, University of Southern California
by Jen Rexford 08 Jan '19

08 Jan '19

> > Speaker: > Jason Lee, Marshall School of Business, University of Southern California > Title: > On the Foundations of Deep Learning: SGD, Overparametrization, and Generalization > Day: > Wednesday, January 9, 2019 > Time: > 4:30 pm > Room: > 101 Sherrerd Hall > > > Abstract: > We provide new results on the effectiveness of SGD and overparametrization in deep learning. > a) SGD: We show that SGD converges to stationary points for general nonsmooth , nonconvex functions, and that stochastic subgradients can be efficiently computed via Automatic Differentiation. For smooth functions, we show that gradient descent, coordinate descent, ADMM, and many other algorithms, avoid saddle points and converge to local minimizers. For a large family of problems including matrix completion and shallow ReLU networks, this guarantees that gradient descent converges to a global minimum. > b) Overparametrization: We show that gradient descent finds global minimizers of the training loss of overparametrized deep networks in polynomial time. > c) Generalization: For general neural networks, we establish a margin-based theory. The minimizer of the cross-entropy loss with weak regularization is a max-margin predictor, and enjoys stronger generalization guarantees as the amount of overparametrization increases. > d) Algorithmic and Implicit Regularization: We analyze the implicit regularization effects of various optimization algorithms on overparametrized networks. In particular we prove that for least squares with mirror descent, the algorithm converges to the closest solution in terms of the bregman divergence. For linearly separable classification problems, we prove that the steepest descent with respect to a norm solves SVM with respect to the same norm. For over-parametrized non-convex problems such as matrix sensing or neural net with quadratic activation, we prove that gradient descent converges to the minimum nuclear norm solution, which allows for both meaningful optimization and generalization guarantees. > > > > Bio: > Jason Lee is an assistant professor in Data Sciences and Operations at the University of Southern California. Prior to that, he was a postdoctoral researcher at UC Berkeley working with Michael Jordan. Jason received his PhD at Stanford University advised by Trevor Hastie and Jonathan Taylor. His research interests are in statistics, machine learning, and optimization. Lately, he has worked on high dimensional statistical inference, analysis of non-convex optimization algorithms, and theory for deep learning. >

1 0

Minsung Kim will present his General Exam on January 14, 2019 at 3pm in CS 402.
by Nicki Gotsis 07 Jan '19

07 Jan '19

Minsung Kim will present his General Exam on January 14, 2019 at 3pm in CS 402. The members of his committee are as follows: Kyle Jamieson (adviser), Jennifer Rexford, and Andrew Houck (ELE). Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract : User demand for increasing amounts of wireless capacity continues to outpace supply, and so to meet this demand, significant progress has been made in new MIMO wireless physical layer techniques. Higher-performance systems now remain impractical largely because their algorithms are extremely computationally demanding. For optimal performance, an amount of computation that increases at an exponential rate both with the number of users and with the data rate of each user is often required. The base station's computational capacity is thus becoming the limiting factor on wireless capacity. QuAMax is the first large MIMO wireless base station design that addresses this issue with a fundamentally different type of computation called quantum annealing. QuAMax solves computationally-demanding MIMO maximum likelihood signal detector. We argue that using quantum computing assisted technology in the future could hold the potential to overcome computational limits of digital electronics on the number of mobile users that a MIMO base station with a particular number of antennas could effectively serve. We have implemented QuAMax on the 2,031 qubit D-Wave 2000Q quantum annealer, the state-of-art of the field. Our experimental results evaluate that implementation on real and synthetic MIMO channel traces, showing under what conditions the quantum annealer can maintain optimal maximum likelihood performance for 30 user, 30 AP antenna QPSK communication, or 60 user, 60 AP antenna BPSK communication. Our work paves the way for quantum hardware and software to significantly expand the performance envelope of Massive MIMO. Reading list : [1] King, Andrew D and McGeoch, Catherine C. "Algorithm engineering for a quantum annealing platform." arXiv preprint arXiv:1410.2628 (2014) [2] E. D. Dahl. "Programming with D-Wave: Map Coloring Problem." D-Wave whitepaper (2013) [3] Perdomo-Ortiz, Alejandro, et al. "A performance estimator for quantum annealers: Gauge selection and parameter setting." arXiv preprint arXiv:1503.01083 (2015). [4] King, James, et al. "Benchmarking a quantum annealing processor with the time-to-target metric." arXiv preprint arXiv:1508.05087 (2015). [5] Venturelli, Davide, and Alexei Kondratyev. "Reverse quantum annealing approach to portfolio optimization problems." arXiv preprint arXiv:1810.08584 (2018). [6] Halperin, Daniel, et al. "802.11 with multiple antennas for dummies." ACM SIGCOMM Computer Communication Review 40.1 (2010) [7] Chan, Albert M., and Inkyu Lee. "A new reduced-complexity sphere decoder for multiple antenna systems." Communications, 2002. ICC 2002. IEEE International Conference on . Vol. 1. IEEE, 2002. [8] Nikitopoulos, Konstantinos, et al. "Geosphere: Consistently turning MIMO capacity into throughput." ACM SIGCOMM Computer Communication Review . Vol. 44. No. 4. ACM, 2014. [9] Barbero, Luis G., and John S. Thompson. "Fixing the complexity of the sphere decoder for MIMO detection." IEEE Transactions on Wireless Communications 7.6 (2008). [10] Abari, Omid, et al. "Enabling High-Quality Untethered Virtual Reality." NSDI . 2017.

1 0

Zhuqi Li will present his General Exam on Wednesday, January 9, 2019 at 10am in CS 402.
by Nicki Gotsis 02 Jan '19

02 Jan '19

Zhuqi Li will present his General Exam on Wednesday, January 9, 2019 at 10am in CS 402. The members of his committee are Kyle Jamieson (adviser), Jennifer Rexford, and Wyatt Lloyd. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract: Conventional thinking treats the wireless channel as a given constraint. Therefore, wireless network designs to date center on the problem of the endpoint optimization that best utilizes the channel, for example, via rate and power control at the transmitter or sophisticated decoding mechanisms at the receiver. We instead explore whether it is possible to reconfigure the environment itself to facilitate wireless communication. In this work, we instrument the environment with a large array of inexpensive antennas (LAIA) and design algorithms to configure them in real time. Our system achieves this level of programmability through rapid adjustments of an on-board phase shifter in each LAIA device. We design a channel decomposition algorithm to quickly estimate the wireless channel due to the environment alone, which leads us to a process to align the phases of the array elements. Variations of our core algorithm can then optimize wireless channels on the fly for single- and multi-antenna links, as well as nearby networks operating on adjacent frequency bands. We design and deploy a 36-element passive array in a real indoor home environment. Experiments with this prototype show that, by reconfiguring the wireless environment, we can achieve a 24% TCP throughput improvement on average and a median improvement of 51.4% in Shannon capacity over the baseline single-antenna links. Over the baseline multi-antenna links, LAIA achieves an improvement of 12.23% to 18.95% in Shannon capacity. The book I am going to use is "Computer Networks: A Systems Approach 4th Edition" by Larry L. Peterson, Bruce S. Davie. The list of papers are: [1] Cerf, Vinton, and Robert Kahn. "A protocol for packet network intercommunication." IEEE Transactions on communications (1974) [2] Kung, Hsiang-Tsung, and John T. Robinson. "On optimistic methods for concurrency control." ACM Transactions on Database Systems (TODS) (1981) [3] Bharghavan, Vaduvur, et al. "MACAW: a media access protocol for wireless LAN's." ACM SIGCOMM Computer Communication Review (1994) [4] Perry, Jonathan, et al. "Spinal codes." ACM SIGCOMM 2012 [5] Miu, Allen, Hari Balakrishnan, and Can Emre Koksal. "Improving loss resilience with multi-radio diversity in wireless networks." ACM MobiCom 2005. [6] Gollakota, Shyamnath, and Dina Katabi. Zigzag decoding: combating hidden terminals in wireless networks. ACM SIGCOMM 2008. [7] Liu, Vincent, et al. "Ambient backscatter: wireless communication out of thin air." NSDI. 2013. [8] Qiao, Yue, et al. "PhyCloak: Obfuscating Sensing from Communication Signals." NSDI. 2016. [9] Abari, Omid, et al. "Enabling High-Quality Untethered Virtual Reality." NSDI. 2017. [10] Xiong, Xi, et al. "Customizing indoor wireless coverage via 3D-fabricated reflectors." ACM BuildSys 2017.

1 0

Elena Balashova will present her Pre FPO "Structure-Aware Shape Synthesis" on December 13, 2018 at 12:30pm in CS 105.
by Nicki Gotsis 07 Dec '18

07 Dec '18

Elena Balashova will present her Pre FPO "Structure-Aware Shape Synthesis" on December 13, 2018 at 12:30pm in CS 105. The members of her committee are as follows: Tom Funkhouser (adviser), Szymon Rusinkiewicz, Vivek Singh (Siemens), Adam Finkelstein, Olga Russakovsky All are invited to attend. Abstract follows below. Abstract: Shape synthesis is an important area of computer vision and graphics that concerns creation of new shapes and reconstruction from partial data. Its goal is to learn a model that can generate shapes within an object category suitable for novel shape creation, interpolation, completion, editing, and other geometric modeling applications. Existing tools learn shape properties from large collections of shapes. Although these methods have been very successful at learning how to synthesize the coarse shapes of objects in categories with highly diverse shapes, they have not always produced examples that reconstruct important structural elements of a shape. In this talk, I describe how structure can be incorporated into the synthesis process, and how it can be used to improve generative models. I discuss how the specific properties of the data influence the effect and design of chosen structure. First, I introduce a template-defined skeleton structure for learning a part-aware generative model in typography, where the shapes have a known structure and can be explained by a small number of templates. Next, I describe a semantic landmark-based structure and how it can be used to improve a generative model of examples with extremely varied topology by means of a geometric shape-structure consistency loss. Finally, I present a scenario of noisy archaeological wall painting (fresco) reconstruction from eroded fragments, where there is no well-defined structure and exponentially many arrangement possibilities – in this case, I show that structure can inferred and assembled through consistency of arrangement

1 0

Colloquium Speaker-Thomas Anderson TODAY at 12:30 and 4:30
by Emily C. Lawrence 06 Dec '18

06 Dec '18

Colloquium Speaker Thomas Anderson from the University of Washington Giving TWO TALKS on Thursday, December 6 Thursday, December 6 - 12:30pm Computer Science - Room 105 “High Performance Operating Systems in the Data Center” Abstract: The ongoing shift of enterprise computing to the cloud provides an opportunity to rethink operating systems for this new setting. I will discuss two specific technologies, kernel bypass for high performance networking and low latency non-volatile storage, and their implications for operating system design. In each case, delivering the performance of the underlying hardware requires novel approaches to the division of labor between hardware, the operating system kernel, and the application library. Thursday, December 6 - 4:30pm Computer Science - Room 104 “A Case for An Open Source CS Curriculum” Abstract: Despite rapidly increasing enrollment in CS courses, the academic CS community is failing to keep pace with demand for trained CS students, leading to escalating starting salaries for our students. Further, the knowledge of how to teach students up to the state of the art is increasingly segregated into a small cohort of schools who mostly cater to students from families in the top 10% of the income distribution. Even in the best case, those schools lack the aggregate capacity to teach more than a small fraction of the nation's need for engineers and computer scientists. MOOCs can help, but they are mainly effective at retraining existing college graduates. In practice, most low and middle income students need a human teacher. In this talk I argue for building an open source CS curriculum, with autograded projects, instructional software, textbooks, and slideware, as an aid for teachers who want to improve the education in advanced CS topics at schools attended by the children of the 90%. I will give as an example our work on replicating teaching advanced operating systems and distributed systems. Bio: Tom Anderson is the Warren Francis and Wilma Kolm Bradley Chair in the Paul G. Allen School of Computer Science and Engineering at the University of Washington. His research interests span all aspects of building practical, robust, and efficient computer systems, including distributed systems, operating systems, computer networks, multiprocessors, and security. He is a member of the National Academy of Engineering and the American Academy of Arts and Sciences, as well as winner of the USENIX Lifetime Achievement Award, the USENIX STUG Award, the IEEE Koji Kobayashi Computer and Communications Award, the ACM SIGOPS Mark Weiser Award, and the IEEE Communications Society William R. Bennett Prize. He is also an ACM Fellow, past program chair of SIGCOMM and SOSP, and he has co-authored twenty-one award papers and one widely used undergraduate textbook.

1 0

REMINDER: Colloquium Speaker-Thomas Anderson tomorrow at 12:30 and 4:30
by Emily C. Lawrence 05 Dec '18

05 Dec '18

Colloquium Speaker Thomas Anderson from the University of Washington Giving TWO TALKS on Thursday, December 6 Thursday, December 6 - 12:30pm Computer Science - Room 105 “High Performance Operating Systems in the Data Center” Abstract: The ongoing shift of enterprise computing to the cloud provides an opportunity to rethink operating systems for this new setting. I will discuss two specific technologies, kernel bypass for high performance networking and low latency non-volatile storage, and their implications for operating system design. In each case, delivering the performance of the underlying hardware requires novel approaches to the division of labor between hardware, the operating system kernel, and the application library. Thursday, December 6 - 4:30pm Computer Science - Room 104 “A Case for An Open Source CS Curriculum” Abstract: Despite rapidly increasing enrollment in CS courses, the academic CS community is failing to keep pace with demand for trained CS students, leading to escalating starting salaries for our students. Further, the knowledge of how to teach students up to the state of the art is increasingly segregated into a small cohort of schools who mostly cater to students from families in the top 10% of the income distribution. Even in the best case, those schools lack the aggregate capacity to teach more than a small fraction of the nation's need for engineers and computer scientists. MOOCs can help, but they are mainly effective at retraining existing college graduates. In practice, most low and middle income students need a human teacher. In this talk I argue for building an open source CS curriculum, with autograded projects, instructional software, textbooks, and slideware, as an aid for teachers who want to improve the education in advanced CS topics at schools attended by the children of the 90%. I will give as an example our work on replicating teaching advanced operating systems and distributed systems. Bio: Tom Anderson is the Warren Francis and Wilma Kolm Bradley Chair in the Paul G. Allen School of Computer Science and Engineering at the University of Washington. His research interests span all aspects of building practical, robust, and efficient computer systems, including distributed systems, operating systems, computer networks, multiprocessors, and security. He is a member of the National Academy of Engineering and the American Academy of Arts and Sciences, as well as winner of the USENIX Lifetime Achievement Award, the USENIX STUG Award, the IEEE Koji Kobayashi Computer and Communications Award, the ACM SIGOPS Mark Weiser Award, and the IEEE Communications Society William R. Bennett Prize. He is also an ACM Fellow, past program chair of SIGCOMM and SOSP, and he has co-authored twenty-one award papers and one widely used undergraduate textbook.

1 0

Colloquium Speaker: Andrew Goldberg, TODAY at 12:30
by Emily C. Lawrence 04 Dec '18

04 Dec '18

Colloquium Speaker Andrew Goldberg from Amazon.com Tuesday, December 4 - 12:30pm Computer Science - Room 105 “Lost in Translation: Production Code Efficiency” When software engineers re-implement a high-performance research prototype code, one often observes one to two orders of magnitude drop in performance. This holds even if both implementations use the same language. The gap is even wider when one goes from a simple language (e.g., C++) to a more sophisticated one (e.g., Java). One of the root causes of this phenomenon is the misinterpretation by software engineers of what they learn in school. Theoretical computer scientists ignore constant factors for the sake of machine-independent analysis. Programming language researchers focus on compilers that automatically handle low-level OS and architectural issues such as memory management. Software engineering professors emphasize abstraction and re-usability. Many software engineers learn to ignore constant factors, rely on compilers for the low-level efficiency, and use generic primitives for re-usability. This is tempting to do as one has to worry about fewer issues when coding, and one needs to know fewer primitives and data structures. However, in practice constant factors do matter, compilers do not always take advantage of computer architecture features, and generic primitives may be less efficient than the simple ones sufficient for the task. Ignoring these issues can lead to significant loss of computational efficiency and increased memory consumption. Power consumption also increases significantly. In this talk we give several examples of inefficient program fragments and discuss them. These examples show that software engineers need to pay attention to low-level details when choosing data . Bio: Andrew Goldberg is a Senior Principal Scientist at Amazon.com, Inc. His research interests are in design, analysis, and computational evaluation of algorithms and data structures, algorithm engineering, computational game theory, electronic commerce, and parallel and distributed algorithms, and complexity theory. His algorithms are widely used in industry and academia. Goldberg got his Ph.D. degree in Computer Science from MIT in 1987, where he was a Hertz Foundation Fellow. Before joining Amazon in 2014, he worked at GTE Laboratories, Stanford University, NEC Research Institute, InterTrust Technologies, Inc., and Microsoft Research. Goldberg received a number of awards for his research contributions, including the NSF Presidential Young Investigator Award and the ONR Young Investigator Award. He is a Fellow of ACM and SIAM.

1 0

CSML and Astrophysics Colloquium: Julian Kates-Harbeck, Tuesday 12/11
by Emily Lawrence 03 Dec '18

03 Dec '18

Speaker: Julian Kates-Harbeck Title: Disruption Prediction in Tokamak Fusion Reactors via Deep Learning at Scale Day: Tuesday, December 11, 2018 Time: 4:30 pm Room: CSML, Classroom 103 Host: CSML & Astrophysics; Professors Peter Ramadge and Steven Crowley Abstract: The prediction and avoidance of large-scale plasma instabilities called "disruptions" is a crucial step towards successful power generation from magnetic confinement fusion in tokamaks. Inspired by the recent success of deep learning (DL) algorithms in generalizing and learning from multi-modal and high-dimensional data across diverse domains, we present a new approach to forecast disruptions based on convolutional and recurrent neural networks. Our method for the first time overcomes the key limitations of past work in that it (i) delivers reliable predictions on machines other than the one it was trained on - a crucial requirement for large and powerful future reactors that cannot afford "training" disruptions; (ii) utilizes high-dimensional training data such as profiles to add new physics information and boost predictive performance; and (iii) engages supercomputing at the largest scale to deliver solutions with improved accuracy and speed. Trained on experimental data from the largest tokamaks in the US (DIII-D) and the world (JET), our algorithm moreover can be tuned for physics-specific tasks such as prediction with long warning times, and opens up possible avenues for moving forward the goal from passive disruption prediction to active reactor control and optimization. Bio Julian Kates-Harbeck received his bachelor's degree in physics at Stanford and earned a master's in computer science (with a focus on artificial intelligence and machine learning) at the same university. Before entering graduate school, he co-founded a tech startup, where he was responsible for product, hiring, and strategy. He is currently pursuing a PhD in physics at Harvard, studying dynamics on complex social and biological networks. He also works on various scientific challenge problems that can be impacted by -- and drive the development of -- state of the art methods in artificial intelligence.

1 0

CSML Colloquium: Neil Lawrence, Monday 12/10
by Emily Lawrence 03 Dec '18

03 Dec '18

Speaker: Neil Lawrence, University of Sheffield Title: Machine Learning and the Physical World Day: Monday, December 10, 2018 Time: 4:00 pm Room: Julius Romo Rabinowitz 399 Host: Ryan P. Adams and CSML Abstract: Machine learning is a data driven endeavor, but real world systems are physical and mechanistic. In this talk we will review approaches to integrating machine learning with real world systems. Our focus will be on emulation (otherwise known as surrogate modeling). Bio: Neil Lawrence is Professor of Machine Learning at the University of Sheffield and the co-host of Talking Machines. He is currently on leave of absence based at Amazon in Cambridge where he is a Director of Machine Learning. Neil's main research interest is machine learning through probabilistic models. He focuses on both the algorithmic side of these models and their application. His recent focus has been on the deployment of machine learning technology in practice, particularly under the banner of data science. He is also the co-host of the Talking Machines podcast. http://inverseprobability.com/biog.html

1 0

Amy Tai will present her FPO "Leveraging Distributed Storage Redundancy in Datacenters" on Monday, 12/10/2018 at 2pm, in CS 105.
by Nicki Gotsis 03 Dec '18

03 Dec '18

Amy Tai will present her FPO "Leveraging Distributed Storage Redundancy in Datacenters" on Monday, 12/10/2018 at 2pm, in CS 105. The members of her committee are as follows: Examiners: Michael Freedman (adviser), Kai Li, and Jennifer Rexford; Readers: Wyatt Lloyd and Kyle Jamieson A copy of her thesis is available upon request. Everyone is invited to attend her talk. The talk abstract follows below: All distributed storage systems replicate data objects, providing built-in redundancy that is designed to help the system withstand failures. Such redundancy is unavoidable because withstanding failures is a critical goal of distributed systems, and redundancy is the only way to tolerate failures that cause loss of data access. However, with the proliferation of data, it is becoming ever more paramount to reduce the costs of distributed storage systems. To balance the need to reduce storage costs and the need to withstand failures, this thesis explores two ways we can leverage the unavoidable redundancy in distributed storage systems to eliminate additional storage overheads in other parts of the storage stack. The first system we present is Replex. The key end-to-end observation in this work is that distributed secondary indices duplicate the work done by replication. Secondary indices often store full copies of data objects, in addition to the replicas of data objects that are created by default to handle failures. In Replex, we eliminate the additional storage overhead of secondary indices by treating them as data replicas during replication time. The second system we present is DIRECT. The key end-to-end observation here is that the redundancy created by replication can and should be used to correct bit errors at the hardware level. Traditionally, disks are expected to abstract bit errors from software, and in fact flash devices are shipped with aggressive internal error correction mechanisms to prevent errors from percolating to the user for the calculated lifetime of the device. In DIRECT, we argue that the underlying premise that disks should not expose bit errors is incorrect. In doing so, DIRECT enables the use of flash devices well beyond their advertised lifetime, which is a huge cost savings for datacenter operators. Therefore, by applying existing storage redundancy to enable two key properties in datacenter storage systems– secondary indexing and flash reliability– this thesis shows that distributed storage systems can be designed without burdensome storage overheads. 1

1 0