- talks - lists.cs.princeton.edu

Harry Kalodner will present his general exam on Tuesday, May 17, 2016 at 12pm in CS 302.
by Nicki Gotsis 10 May '16

10 May '16

Harry Kalodner will present his general exam on Tuesday, May 17, 2016 at 12pm in CS 302. The members of his committee are Arvind Narayanan (adviser), Nick Feamster, and Aarti Gupta. 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 Bitcoin, initially designed as a system for the issuance and transfer of electronic cash, provides a foundation for the construction of complex and powerful applications. The underlying technology of Bitcoin, the blockchain, is a powerful tool to secure information and coordinate exchanges between mutually distrustful parties. New methods of analysis and system design must be developed to understand and make take advantage of these tools. Namecoin is a cryptocurrency modeled after Bitcoin which implements a decentralized alternative to DNS. The public nature of blockchain technology provides direct visibility into how the system is used in practice. I discuss a number of techniques used to analyze the use and function of Namecoin. I then discuss some major pitfalls of Namecoin’s design and lessons that can be learned in the development of future systems. Taking lessons from the design of Namecoin, I describe a proposed system, IPCoin, designed to replace the centralized structure of the RPKI. Currently a core group of central entities hold the power to disrupt the routing of packets on the internet. IPCoin provides a method of removing this centralization, thus minimizing the attack surface available for disrupting core functionality of the internet. IPCoin provides a system for the fair distribution of IP address ranges, the ability to securely control these ranges, and the easy auditing of the global consensus state of the system. Reading List: Books: Ross J. Anderson. 2008. Security Engineering: A Guide to Building Dependable Distributed Systems (2 ed.). Wiley Publishing. (Chapters 5, 6, 7, 10, 21) Larry L. Peterson and Bruce S. Davie. 2011. Computer Networks, Fifth Edition: A Systems Approach (5th ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. (Chapters 1,2,3,4) Arvind Narayanan. 2016. Bitcoin and Cryptocurrency Technologies. (Chapters 2, 3, 9, 10, 11) Papers: 1. Bitcoin: Nakamoto, Satoshi. "Bitcoin: A peer-to-peer electronic cash system." Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A. Kroll, Edward W. Felten. "Research Perspectives and Challenges for Bitcoin and Cryptocurrencies.” IEEE Security & Privacy, 2015. Jeremy Clark, Joseph Bonneau, Edward W. Felten, Joshua A. Kroll, Andrew Miller, Arvind Narayanan. "On Decentralizing Prediction Markets and Order Books." WEIS 2014. Sarah Meiklejohn, Marjoir Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geoffrey M. Voelker, Stefan Savage. "A fistful of bitcoins: Characterizing payments among men with no names." In Proceedings of the ACM Internet Measurement Conference (IMC), pages 127–140, New York, 2013. ACM Muneeb Ali, Jude Nelson, Ryan Shea, Michael J. Freedman. "Blockstack: Design and Implementation of a Global Naming System with Blockchains.” To appear in USENIX ATC’16. Meni Rosenfeld. "Overview of colored coins." http://bitcoil.co.il/BitcoinX.pdf, December 2012. 2. BGP and RPKI K. Butler, T. Farley, P. McDaniel and J. Rexford. "A survey of BGP security issues and solutions." Proc. IEEE, vol. 98, no. 1, pp. 100-122, 2010 M. Lepinski and S. Kent, “An Infrastructure to Support Secure Internet Routing,” IETF, RFC 6480, February 2012. Danny Cooper , Ethan Heilman , Kyle Brogle , Leonid Reyzin , Sharon Goldberg. "On the risk of misbehaving RPKI authorities." Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks, p.1-7, November 21-22, 2013. College Park, Maryland Ethan Heilman , Danny Cooper , Leonid Reyzin , Sharon Goldberg. "From the consent of the routed: improving the transparency of the RPKI." Proceedings of the 2014 ACM conference on SIGCOMM, August 17-22, 2014, Chicago, Illinois, USA

1 0

Yida Wang will present his FPO, " Large-scale analyses of functional interactions in the human brain" on Tuesday, 5/17/2016 at 3:00PM in A32 Peretsman-Scully Hall.
by Nicki Gotsis 10 May '16

10 May '16

Yida Wang will present his FPO," Large-scale analyses of functional interactions in the human brain" on Tuesday, 5/17/2016 at 3:00PM in A32 Peretsman-Scully Hall. The members of his committee are Kai Li (adviser), readers: Jon Cohen and Nick Turk-Browne; nonreaders: Olga Troyanskaya and Sebastian Seung. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follow below. Abstract: A grand challenge in neuroscience is to understand how a human brain functions. Much previous research has focused on studying the activities of brain regions. However, the functional interactions between brain regions are not well understood. This dissertation focuses on computational methods to analyze data from functional magnetic resonance imaging (fMRI) scanners to study the functional interactions in the human brain. This dissertation proposes, designs and implements efficient systems to conduct full correlation matrix analysis (FCMA) as an unbiased way to explore functional interactions in the human brain. Since a straightforward way to study FCMA would take years to complete one run with a typical neuroscience study dataset on a modern compute server, no previous attempt has been made in the past. This dissertation makes several contributions. First, we proposed and implemented parallel algorithms and optimizations on a multi-processor cluster, which improved FCMA computation by three orders of magnitude. Second, we demonstrated that FCMA can effectively show functional interactions in the human brain by conducting a neuroscience study on an fMRI dataset. Our study successfully identified functional interactions between certain brain regions. Third, we proposed and implemented optimization methods for FCMA for emerging many-core processors such as the Intel Xeon Phi coprocessors and improved the performance of computing FCMA by another order of magnitude. On a 96-node Xeon Phi cluster, our system can finish an FCMA study with a typical dataset in minutes. Finally, we proposed, designed and implemented a service for real-time, closed loop neuroscience studies. Our real-time FCMA can process and analyze brain volumes from multiple fMRI experiments on a 40-node compute cluster simultaneously and send the neurofeedback to each fMRI scanner over the Internet within 1.5 seconds. This system uses a novel method to improve the performance and utilization of compute nodes while meeting the real-time requirements in the presence of node failures.

1 0

Talk: June Andronick Monday May 16, 11:00am
by Nicole E. Wagenblast 10 May '16

10 May '16

Talk: Interrupts in OS code: let’s reason about them. Yes, this means concurrency. June Andronick, Data61 Monday, May 16th, 11:00am Computer Science 105 Existing modelled and verified operating systems (OS’s) typically run on uniprocessor platforms and run with interrupts mostly disabled. This makes formal reasoning more tractable: execution is mostly sequential. The eChronos OS is a real-time OS used in tightly constrained devices, running on (uniprocessor) embedded micro-controllers. It is used in the DARPA-funded HACMS program, where it runs the flight control software of a high-assurance quadcopter. To provide low latency, the eChronos OS runs with interrupts enabled and provides a preemptive scheduler. In terms of verification, this means that concurrency reasoning is required, which significantly increases the complexity: application and OS instructions may be interleaved with interrupt handler instructions. In our work we explicitly model the effect of interrupts and their handling by the hardware and OS. We provide a general formal model of the interleaving between OS code, application code and interrupt handlers. We then instantiate this model to formalise the scheduling behavior of the eChronos OS, and prove the main scheduler property: the running task is always the highest-priority runnable task. June Andronick is a Senior Researcher at Data61|CSIRO (formerly NICTA). Her research focuses on increasing the reliability of critical software systems, by mathematically proving that the code behaves as expected and satisfies security and safety requirements. She contributed to the seL4 correctness proof and now focuses on concurrency reasoning for OS code. She leads the concurrency software verification research in Data61, and is deputy leader of the Trustworthy Systems group. She was recognised in 2011 by MIT's Technology Review as one of the world's top young innovators (TR35). She holds a PhD in Computer Science from the University of Paris-Sud, France.

1 0

Jennifer Gossels will present her general exam on Tuesday, May 17, 2016 at 2pm in CS 402.
by Nicki Gotsis 10 May '16

10 May '16

Jennifer Gossels will present her general exam on Tuesday, May 17, 2016 at 2pm in CS 402. The members of her committee are Jennifer Rexford (adviser), Aarti Gupta, and Nick Feamster. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Abstract: Internet service providers (ISPs) need to minimize congestion in their backbones to maximize performance and make efficient use of network resources. For this reason, traffic engineering (TE) is an old, well-studied problem. However, standard TE efforts primarily focus on link capacities as constraints and ignore the limited memory available for switches to store their forwarding rule tables. When faced with insufficient memory, these solutions resort to the suboptimal strategy of tunneling packets end-to-end. End-to-end tunneling is suboptimal because it implicitly assumes that all edge switches have abundant memory and all interior switches do not. However, switches comprising ISP backbones are heterogeneous. Hence, end-to-end tunneling fails to take advantage of the large rule tables of some interior nodes. In this talk, we discuss our approach to traffic engineering in the presence of heterogeneous switch resources. Specifically, we distinguish between interior nodes with limited memory (little nodes) and those with just as much memory as edge switches (big nodes). Based on this little node-big node model, we formulate two novel variations of the multicommodity flow linear program. We show preliminary results, using real toplogy and traffic data, demonstrating that our optimization formulations significantly reduce network congestion compared to end-to-end tunneling. These results hold even if only 10 or 20 percent of interior nodes are big nodes. Reading List: Textbook [8] Classic Networking [10] Segment Routing [1, 2] Related Work [3, 4, 5, 6, 11] Other SDN [7, 9] References [1] Bhatia, R., Hao, F., Kodialam, M. S., and Lakshman, T. V. Optimized Network Traffic Engineering using Segment Routing. In Proceedings IEEE INFOCOM 2015 (2015), IEEE. [2] Filsfils, C., Nainar, N. K., Pignataro, C., Cardona, J. C., and Francois, P. The Segment Routing Architecture. In 2015 IEEE Global Communications Conference (GLOBECOM) (Dec 2015), pp. 1–6. [3] Hartert, R., Vissicchio, S., Schaus, P., Bonaventure, O., Filsfils, C., Telkamp, T., and Francois, P. A Declarative and Expressive Approach to Control Forwarding Paths in Carrier-Grade Networks. In SIGCOMM (2015). [4] Heorhiadi, V., Reiter, M. K., and Sekar, V. Simplifying software-defined network optimization using SOL. In 13th USENIX Conference on Networked Systems Design and Implementation (Santa Clara, CA, Mar. 2016), NSDI ’16. [5] Hong, C.-Y., Kandula, S., Mahajan, R., Zhang, M., Gill, V., Nanduri, M., and Wattenhofer, R. Achieving High Utilization with Software-Driven WAN. In Proceedings of the ACM SIGCOMM 2013 Conference (New York, NY, USA, 2013), SIGCOMM ’13, ACM. [6] Jain, S., Kumar, A., Mandal, S., Ong, J., Poutievski, L., Singh, A., Venkata, S., Wanderer, J., Zhou, J., Zhu, M., Zolla, J., Holzle, U., Stuart, S., and Vahdat, A. ¨ B4: Experience with a Globally-Deployed Software Defined WAN. In Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM (New York, NY, USA, 2013), SIGCOMM ’13, ACM. May 9, 2016 1 Jennifer Gossels General Exam Abstract and Reading List [7] Levin, D., Canini, M., Schmid, S., Schaffert, F., and Feldmann, A. Panopticon: Reaping the Benefits of Incremental SDN Deployment in Enterprise Networks. In Proceedings of the 2014 USENIX Annual Technical Conference (June 2014), USENIX ATC ’14, USENIX Association, pp. 333–345. [8] Peterson, L. L., and Davie, B. S. Computer Networks: A Systems Approach, 5th ed. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2011. [9] Qazi, Z. A., Tu, C.-C., Chiang, L., Miao, R., Sekar, V., and Yu, M. SIMPLE-fying Middlebox Policy Enforcement Using SDN. In Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM (New York, NY, USA, 2013), SIGCOMM ’13, ACM. [10] Saltzer, J. H., Reed, D. P., and Clark, D. D. End-to-End Arguments in System Design. ACM Transactions on Computer Systems 2, 4 (Nov. 1984). [11] Soule, R., Basu, S., Marandi, P. J., Pedone, F., Kleinberg, R. D., Sirer, E. G., and ´ Foster, N. Merlin: A Language for Provisioning Network Resources. In Proceedings of the 10th ACM International Conference on Emerging Networking Experiments and Technologies (2014), CoNEXT ’14.

1 0

Ruth Dannenfelser will present her general exam on Tuesday, May 17, 2016 at 11:30am in Genomics, CIL 253.
by Nicki Gotsis 10 May '16

10 May '16

Ruth Dannenfelser will present her general exam on Tuesday, May 17, 2016 at 11:30am in Genomics, CIL 253. The members of her committee are Olga Troyanskaya (adviser), Mona Singh, and Barbara Engelhardt. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ABSTRACT Large-scale genomic studies now give more predictive power than ever, allowing us to profile the composition of tissues, study cellular functions, and understand organismal traits at an unprecedented level of detail. This is particularly important for studying complex diseases, such as cancer, where small patient specific differences play critical roles in development and progression. The intratumoral immunological landscape has been shown to be an important determinant of outcome with functions in both promotion and inhibition of tumor growth. Thus far, direct detailed studies of the cell composition of tumor infiltration have been limited; with some studies giving approximate quantifications using immunohistochemistry and other small studies obtaining measurements by isolating cells from newly excised tumors and sorting them using flow cytometry. These technical challenges, combined with the substantial overlap between cell surface and secreted proteins, make routine profiling of tumor-infiltrating lymphocytes difficult. We propose a solution to this problem by leveraging over 2,000 samples from existing gene expression studies in a machine learning framework to derive robust markers capable of quantification. Our method is generalizable, can be used to profile the levels of any cell type of interest, and allows for retroactive analysis of published data without requiring additional experimentation. Herein we focus on quantifying the key lymphocytes in the immune response across breast cancer studies. Most notably we find that estrogen receptor activity and genomic complexity are the key factors driving variation in lymphocyte infiltration across individual tumors. Furthermore, we discuss the clinical implications of our findings, specifically preliminary changes in normal breast tissue associated with increased cancer risk and the indirect beneficial effect of anti-estrogen therapy. Reading List: Books: 1. An Introduction to Bioinformatics Algorithms by Jones and Pevzner 2. Artificial Intelligence: A Modern Approach by Russell and Norvig (Chapters: 13 Uncertainty, 14 Probabilistic Reasoning, 20 Statistical Learning Methods) Papers: 3. Irizarry et al., Exploration, normalization, and summaries of high density oligonucleotide array probe level data. Biostatistics (2003). 4. Piccolo et al., Multiplatform single-sample estimates of transcriptional activation. PNAS (2013). 5. Newman et al., Robust enumeration of cell subsets from tissue expression profiles. Nature Methods (2015). 6. Chikina and Troyanskaya., Accurate quantification of functional analogy among close homologs. PLoS Comp Bio (2011). 7. Greene et al., Understanding multicellular function and disease with human tissue-specific networks. Nature Genetics (2014). 8. McGary et al., Systematic discovery of nonobvious human disease models through orthologous phenotypes. PNAS (2010). 9. Smedley et al., PhenoDigm: analyzing curated annotations to associate animal models with human diseases. Database (2013). 10. Rooney et al., Molecular and genetic properties of tumors associated with local immune cytolytic activity. Cell (2015). 11. Curtis et al., The genomic and transcriptomic architecture of 2,000 breast tumours reveals novel subgroups. Nature (2012).

1 0

Nicholas Turner will present his generals exam on Monday, May 16, 2016 at 2pm in CS 402
by Nicki Gotsis 09 May '16

09 May '16

Nicholas Turner will present his generals exam on Monday, May 16, 2016 at 2pm in CS 402. The members of his committee are Sebastian Seung (adviser), Tom Funkhouser, and Jianxiong Xiao 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:* Connectomics studies neural circuits by extracting their structural properties from electron microscopy (EM) images. Current state-of-the-art approaches use convolutional neural networks as a step towards segmenting aligned stacks of EM images. One application of these methods attempts to study the mouse retina. However, current practices have featured poor performance in describing the geometry of ganglion cell somata, which are difficult to segment as they can feature large image staining gaps. I will present work addressing two related challenges. First, I will demonstrate how we can preprocess the image stack to improve the segmentation accuracy of current approaches. These improvements allow us to quantify basic properties of ganglion cell somata. Second, I will present preliminary work motivated by these results to provide segmentation across multiple layers of tissue by means of a single multiscale model. *Reading List:* Bishop, Christopher M. "Pattern Recognition." *Machine Learning* (2006). Ian Goodfellow, Yoshua Bengio, and Aaron Courville. "Deep Learning." Book in preparation for MIT Press, 2016. J. S. Kim, M. J. Greene, A. Zlateski, K. Lee, M. Richardson, S. C. Turaga, M. Purcaro, M. Balkam, A. Robinson, B. F. Behabadi, M. Campos, W. Denk, H. S. Seung, and EyeWirers. Space-time wiring specificity supports direction selectivity in the retina. <http://www.ncbi.nlm.nih.gov/pubmed/24805243> *Nature**509*, 331-6 (2014). Sanes, Joshua R., and Richard H. Masland. "The types of retinal ganglion cells: current status and implications for neuronal classification." *Annual review of neuroscience* 38 (2015): 221-246. Ciresan, Dan, et al. "Deep neural networks segment neuronal membranes in electron microscopy images." *Advances in neural information processing systems*. 2012. S. C. Turaga, K. L. Briggman, M. Helmstaedter, W. Denk, and H. S. Seung. *Maximin affinity learning of image segmentation*. CoRR. abs/0911.5372 (2009). S. C. Turaga, J. F. Murray, V. Jain, F. Roth, M. Helmstaedter, K. Briggman, W. Denk, and H. S. Seung. Convolutional networks can learn to generate affinity graphs for image segmentation. <http://www.ncbi.nlm.nih.gov/pubmed/19922289>*Neural Comput.* *22*, 511-38 (2010). Glorot, Xavier, and Yoshua Bengio. “Understanding the difficulty of training deep feedforward neural networks.” <http://jmlr.csail.mit.edu/proceedings/papers/v9/glorot10a/glorot10a.pdf> *Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS’10). Society for Artificial Intelligence and Statistics*. 2010. Bengio, Yoshua. "Learning deep architectures for AI." *Foundations and trends® in Machine Learning* 2.1 (2009): 1-127. I. Arganda-Carreras, S.C. Turaga, D.R. Berger, D. Cireşan, A. Giusti, L.M. Gambardella, J. Schimdhuber, D. Laptev, S. Dwivedi, J.M. Buhmann, T. Liu, M. Seyedhosseini, T. Tasdizen, L. Kamentsky, R. Burget, V. Uher, X. Tan, C. Sun, T.D. Pham, E. Bas, M.G. Uzunbas, A. Cardona, J. Schindelin, H.S. Seung. Crowdsourcing the creation of image segmentation algorithms for connectomics <http://journal.frontiersin.org/article/10.3389/fnana.2015.00142/abstract>. Front Neuroanat *142*, (2015).

1 0

Yichen Chen will present his general exam on Monday, May 16, 2016 at 12pm in CS302
by Nicki Gotsis 09 May '16

09 May '16

Yichen Chen will present his general exam on Monday, May 16, 2016 at 12pm in CS302 The members of his committee are Han Liu, adviser (ORFE), Mengdi Wang (ORFE), Elad Hazan, and Sanjeev Arora 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. Title:Random multi-constraint projection and an online primal-dual method for discounted markovian decision process Abstract: In this talk I will first discuss the problem of solving an optimization problem subject to large number of constraints. Usual approach like stochastic gradient descent fails in the sense that the projection step is too computationally expensive. We propose a class of algorithms that perform both stochastic gradient descent and random feasibility updates simultaneously. Our algorithm does not subject to the heavy computation of projection. I will show the almost sure convergence of these algorithms, and analyze the iterates’ feasibility error and optimality error, respectively. The rate analysis and numerical experiments reveal that the algorithm using the polyhedral-set projection scheme is the most efficient one within known algorithms. Then I will discuss an on going work that uses online primal-dual method to recover the optimal policy under Markovian Decision Process. We focus on the black-box model where transition probabilities and state transition cost are unknown. We propose a stochastic primal-dual algorithm for solving the linear formulation of the Bellman equation. The algorithm updates the primal and dual iterates by using sample state transitions and sample costs generated by the simulator. We show that the t-th averaged dual iterate can be implemented as a near-optimal randomized policy, achieving an efficiency loss of the order 1/ sqrt(t). Moreover, we provide a thresholding procedure that recovers the exact optimal policy from the dual iterates with high probability. Book: Richard S Sutton and Andrew G Barto. Introduction to reinforcement learning, volume 135. MIT Press Cambridge, 1998. Reading List: [1] Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming: an overview. In Decision and Control, 1995., Proceedings of the 34th IEEE Conference on, volume 1, pages 560–564. IEEE, 1995. [2] Nicolo Cesa-Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. In Advances in Neural Information Processing Systems, pages 1160–1168, 2013. [3] Randy Cogill. Primal-dual algorithms for discounted markov decision pro- cesses. In Control Conference (ECC), 2015 European, pages 260–265. IEEE, 2015. [4] Daniela Pucci de Farias and Benjamin Van Roy. The linear programming approach to approximate dynamic programming. Operations Research, 51(6):850–865, 2003. [5] Vijay V Desai, Vivek F Farias, and Ciamac C Moallemi. Approximate dy- namic programming via a smoothed linear program. Operations Research, 60(3):655–674, 2012. [6] Luc Devroye, Gabor Lugosi, and Gergely Neu. Random-walk perturba- tions for online combinatorial optimization. Information Theory, IEEE Transactions on, 61(7):4099–4106, 2015. [7] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484–489, 2016. [8] John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal- difference learning with function approximation. Automatic Control, IEEE Transactions on, 42(5):674–690, 1997. [9] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279–292, 1992. [10] Yinyu Ye. The simplex and policy-iteration methods are strongly polyno- mial for the markov decision problem with a fixed discount rate. Mathe- matics of Operations Research, 36(4):593–603, 2011.

1 0

Haipeng Luo will present his FPO, "Optimal and Adaptive Online Learning" on Monday, 5/16/2016 at 2pm in CS 302.
by Nicki Gotsis 09 May '16

09 May '16

Haipeng Luo will present his FPO, "Optimal and Adaptive Online Learning" on Monday, 5/16/2016 at 2pm in CS 302. The members of his committee are Robert Schapire (adviser), readers: Elad Hazan and Satyen Kale (Yahoo); nonreaders: Sanjeev Arora and Barbara Engelhardt. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follow below. Online learning is one of the most important and well-established machine learning models. Generally speaking, the goal of online learning is to make a sequence of accurate predictions “on the fly,” given some information of the correct answers to previous prediction tasks. Online learning has been extensively studied in recent years, and has also become of great interest to practitioners due to its e↵ectiveness in dealing with non-stationary data as well as its applicability to large-scale applications. While many useful ideas are well-established in the o✏ine learning setting where a set of data is available beforehand, their counterparts in the online setting are not always straightforward and require more understanding. Moreover, existing online learning algorithms are not always directly applicable in practice. One important reason is that they usually rely on sophisticated tuning of parameters, a delicate approach that can yield sound theoretical guarantees, but that does not work well in practice. Another reason is that existing algorithms are usually guaranteed to work well in one particular situation or another, but not all. A single algorithm that can ensure worst-case robustness while still enjoying the ability to exploit easier data at the same time is relatively rare and certainly desirable in practice. Motivated by all the above issues, this thesis focuses on designing more practical, adaptive and ready-to-use online learning algorithms, including • novel online algorithms which combine expert advice in an optimal and parameter-free way and work simultaneously under di↵erent patterns of data as well as di↵erent evaluation criteria; • a novel and rigorous theory of online boosting which studies improving the accuracy of any existing online learning algorithm by training and combining several copies of it in a carefully designed manner; iii • a family of highly e#cient online learning algorithms which make use of second order information of the data and enjoy good performance even when dealing with ill-conditioned data. In summary, this thesis develops and analyzes several novel, optimal and adaptive online learning algorithms which greatly improve upon previous work and have great practical potential.

1 0

Matvey Arye will present his FPO, " Data Processing Across Continents" on Tuesday, 5/17/2016 at 10:00am in CS 402.
by Nicki Gotsis 09 May '16

09 May '16

Matvey Arye will present his FPO, " Data Processing Across Continents" on Tuesday, 5/17/2016 at 10:00am in CS 402. The members of his committee are Michael Freedman (adviser), readers: Andrea LaPaugh and Kai Li; nonreaders: Jennifer Rexford and Nick Feamster. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follow below. An increasing number of data sources create data across the globe. These include everything from server logs owned by Internet-scale companies to military intelligence systems. This thesis addresses the question of how to enable near-real-time analytical queries on such data. Existing systems tend to centralize such data into a single datacenter before analyzing it. However, in light of low and asymmetric bandwidth provisioning in and between certain geographic regions, centralizing all data can be both slow and costly. This thesis have addressed this problem with three complementary research directions. First, we describe a system that queries the data in a distributed manner and centralizes only the data that is needed to fulfill the query. Our system incorporates edge storage and customizable degradation operators in its programming model. These elements allow the system to adjust the data-volumes transferred to match available bandwidth. Second, we explore some challenges due to the interaction between an application level dynamic quality adaptation control loop and TCP (which has its own control loop). These two control loops can create negative feedback e↵ects which reduces system throughput below what the network can sustain. These insights are translated into the domain of Internet video streaming and several solutions are proposed. Our solutions enable video flows to achieve above 90% of its fair-share of throughput, while industry players often achieve less than 50% of their fair-share. Finally, we present a case study of how to optimize queries for wide-area analysis. We optimize the top-k query, which addresses questions of popularity and is thus ubiquitous in modern computer systems. Our algorithms reduce both the bandwidth usage and number of rounds used by such queries. In particular, we propose the first exact two-round top-k algorithm (which still transfers 19% less bytes than the best previously-known exact 3-round algorithm). Our 2-or-3-round exact algorithm transfers 31% less bytes than the best previously-known approximate algorithm. Finally, our approximate algorithm uses 40% less bandwidth than previous algorithms with stronger guarantees.

1 0

Brian Bullins will present his general exam Monday, May 16, 2016 at 4pm in CS 402.
by Nicki Gotsis 09 May '16

09 May '16

Brian Bullins will present his general exam Monday, May 16, 2016 at 4pm in CS 402. The members of his committee are Elad Hazan (adviser), Sanjeev Arora, and Barbara Engelhardt. 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: Linear regression is a common learning technique for determining the linear relationship between multiple variables and how they may affect a certain outcome. A standard example is that of medical diagnosis, whereby the data gathered for a given patient provides information about their susceptibility to certain illnesses. A major drawback to this process is the work necessary to collect the data, as it requires running numerous tests for each person. In such cases it may be necessary to impose limitations on the amount of data available for each example. For medical diagnosis, this might mean having each patient only undergo a subset of tests. In this talk I will discuss the problem of regression where the learner is allowed to observe only a limited number of attributes per example, known as the limited attribute observation model. In particular, we provide the first lower bounds giving a limit on the precision attainable by any algorithm for several variants of regression, notably regression with absolute loss and squared loss, as well as for classification with hinge loss. We complement this with a general purpose algorithm which achieves an upper bound in terms of the precision limit. This is joint work with Elad Hazan and Tomer Koren. Reading List: Books: Introduction to Online Convex Optimization. Elad Hazan Understanding Machine Learning: From Theory to Algorithms. Shai Shalev-Shwartz and Shai Ben-David Papers: Linear Regression with Limited Observation. E. Hazan and T. Koren Classification with Low Rank and Missing Data. E. Hazan, R. Livni, and Y. Mansour Convergence rates of sub-sampled Newton methods. M. Erdogdu and A. Montanari Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. R. Johnson and T. Zhang Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. J. Duchi, E. Hazan, and Y. Singer Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization. J. Abernethy, E. Hazan, and A. Rakhlin Cubic regularization of Newton method and its global performance. Y. Nesterov and B.T. Polyak Deep learning via Hessian-free optimization. J. Martens Escaping from Saddle Points — Online Stochastic Gradient Descent for Tensor Decomposition. R. Ge, F. Huang, C. Jin, and Y. Yuan Online Learning of Eigenvectors. D. Garber, E. Hazan, and T. Ma On the saddle point problem for non-convex optimization. R. Pascanu, Y. Dauphin, S. Ganguli, and Y. Bengio

1 0