January 2019 - talks - lists.cs.princeton.edu

Santiago Cuellar will present his Pre FPO on Wednesday, January 23, 2019 at 10am in CS 402.
by Nicki Gotsis 11 Jan '19

11 Jan '19

Santiago Cuellar will present his Pre FPO on Wednesday, January 23, 2019 at 10am in CS 402. The members of his committee are as follows: Andrew Appel (adviser), Readers: Chung-Kil (Seoul National University) and Zak Kincaid; Non readers: Lennart Beringer and Aarti Gupta All are welcome to attend. Abstract follows below. Concurrent Permission Machine for modular proofs of optimizing compilers with shared memory concurrency. Optimizing compilers change a program based on a formal analysis of its code and modern processors further rearrange the program order. It is hard to reason about such transformations, which makes them a source of bugs, particularly for concurrent shared-memory programs where the order of execution is critical. On the other hand, programmers should reason about their program in the source language, which abstracts such low level details. We present the Concurrent Permission Machine (CPM), a semantic model for shared-memory concurrent programs, which is: (1) sound for high-order Concurrent Separation Logic, (2) convenient to reason about compiler correctness, and (3) useful for proving reduction theorems on weak memory models. The key feature of the CPM is that it exploits the fact that correct shared-memory programs are permission coherent: threads have (at any given time) noncompeting permission to access memory, and their load/store operations respect those permissions. Compilers are often written with sequential code in mind, and proving the correctness of those compilers is hard enough without concurrency. Indeed, the machine-checked proof of correctness for the CompCert C compiler was a major advance in the field. Using the CPM to conveniently distinguish sequential execution from concurrent interactions, I show how to reuse the (sequential) CompCert proof, without major changes, to guarantee a stronger concurrent-permission-aware notion of correctness.

1 0

Linguang Zhang will present his Pre FPO "Towards a Robust Local Feature Pipeline" on Tuesday, January 15, 2019 at 1pm in CS 302
by Nicki Gotsis 11 Jan '19

11 Jan '19

Linguang Zhang will present his Pre FPO on Tuesday, January 15, 2019 at 1pm in CS 302. The members of his committee are as follows: Szymon Rusinkiewicz (advisor), Jia Deng, Adam Finkelstein, Thomas Funkhouser, and Olga Russakovsky. All are welcome to attend. Abstract follows below. Title: Towards a Robust Local Feature Pipeline Many computer vision applications including image matching, image-based reconstruction and localization rely on extracting and matching robust local features. A typical local feature pipeline first detects repeatable keypoints in the image (i.e., keypoint detector), and then computes a short vector to uniquely describe each keypoint (i.e., feature descriptor). Both the keypoint detector and the feature descriptor are conventionally hand-crafted based on what is intuitive to the designer. For example, corners or blobs are popular choices of keypoints, and the image gradient is a useful clue for descriptors. However, it is often difficult to define these principles to accommodate various applications. In this thesis, we study data-driven approaches which can more easily tailor the local feature pipeline for target applications. We start with a mobile robotics application that leverages local features extracted from ground texture images to achieve high-precision global localization. The second part of the thesis addresses the problem that existing keypoint detectors that are optimized for natural images suffer from sub-optimal performance on texture images. We therefore learn a keypoint detector specifically for each type texture using a deep neural network. Our detector automatically learns to identify keypoints that are distinctive in the target texture rather than relying on a set of pre-defined rules. Finally, we focus on a non-parametric approach for learning feature descriptors. Many well-performing local feature descriptors are trained using a triplet loss that includes a tunable margin, which limits its ability to generalize to other types of data and problems. We propose to replace the hard margin with a soft margin that self-tunes as learning progresses. To summarize, we first demonstrate through a novel visual-based localization system where a customized local feature pipeline is critical. Then, we tackle both the keypoint detector and the feature descriptor with generalizable data-driven approaches.

1 0

Borislav Hristov will present his Pre-FPO on Wednesday, Jan 9th, 2019 at 11am in LSI 200.
by Nicki Gotsis 08 Jan '19

08 Jan '19

Borislav Hristov will present his Pre-FPO on Wednesday, Jan 9th, 2019 at 11am in LSI 200. The members of his committee are as follows: Mona Singh (advisor), Barbara Engelhardt, Olga Troyanskaya, Ben Raphael, Bernard Chazelle Everyone is invited to attend his talk. Please see abstract below. Dramatically decreased cost of sequencing has enabled us to sequence the genomes of hundreds of individuals with various diseases. Yet, pinpointing the gene variants responsible for the development of heterogeneous diseases remains a particularly hard task because the same phenotypic outcome (disease) can result from a myriad of combinations of different alterations across the genome. In this talk, I will describe two projects that further our ability to computationally highlight potential disease causing genes by examining the disease genomes in the context of biological networks. First, I will present a novel network-based approach to uncover cancer-relevant genes from large-scale cancer genomics data. My approach tackles cancer mutational heterogeneity by utilizing per-individual mutational profiles. My method is based on the expectation that if a pathway is relevant for cancer, then (1) many individuals will have a somatic mutation within one of the genes comprising the pathway and (2) the genes comprising the pathway will interact with each other and together form a small connected subcomponent within the larger network. I will provide an intuitive formulation relying on balancing the size of the connected subgraph with covering many patients. I will describe a machine learning-like schema for selecting the value of the single required parameter and both an integer linear programming framework and a fast heuristic for optimizing the objective function. I will demonstrate the method’s outstanding ability to identify cancer-relevant genes, especially those mutated at very low rates. Second, I will describe a general computational framework that uses prior knowledge of disease associated genes to guide a network-based search for novel ones based on newly acquired information. While many methods that directly consider either the prior knowledge or the newly acquired information to uncover disease-relevant genes have been developed, I develop a new network-based approach that combines these two distinct types of information. I will show how such a framework built upon graph kernels and guided random walks has the power to uncover new disease associated genes by applying it to different heterogeneous diseases, including macular degeneration and eight cancer types.

1 0

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