UIUC Student Talks
The 10th Annual CSL Student Conference — Organizing Committee is pleased to announce the following UIUC student talks. Please click on the “Abstract” under each speaker to see her/his abstract.
Session 1: Control, Networks, and Robots
Shaileshh Bojja Venkatakrishnan
Ph.D. student, CSL, UIUC
Deterministic Near-Optimal P2P Streaming
Venu: CSL B02
Time: 11:00 – 11:20, Feb 26 2015
Abstract
We consider streaming over a peer-to-peer network in which peers are allowed to enter or leave the system adversarially and arbitrarily. Previous approaches for streaming have either used randomized distribution graphs or structured trees with randomized maintenance algorithms. Randomized graphs handle peer churn well but have only probabilistic connectivity guarantees, while structured trees have good connectivity but have proven hard to maintain under peer churn. We improve upon both approaches by presenting a novel distribution structure with a deterministic and distributed algorithm for maintenance under peer churn. The algorithm has a constant repair time for connectivity, and near optimal delay. As opposed to order results, the guarantees provided by our algorithm are exact and hold for any network size. Extensions of the algorithm to include peers with heterogenous capacities and more general traffic patterns such as multiple source broadcast are also considered.
Speaker Bio
Shaileshh Bojja Venkatakrishnan is a PhD student in CSL under the supervision of Prof. Pramod Viswanath. He received the B.Tech. degree from the Indian Institute of Technology – Madras in 2012 and the M.S. degree from UIUC in 2014, all in ECE. He was also an intern at Qualcomm Research from May to August 2013. His research interests are in distributed algorithms, information theory and wireless communications.
Qiaomin Xie
PhD student, ECE, UIUC
Pandas: An Efficient Priority Algorithm for Near-Data Scheduling
Venu: CSL B02
Time: 11:20 – 11:40, Feb 26 2015
Short Abstract
We propose Pandas (Priority Algorithm for Near-DAta Scheduling) and integrate it into the Hadoop FIFO and Fair Schedulers. Pandas serves to balance data locality and cluster utilization so that the system throughput is drastically improved over all load conditions. In particular, high data locality is achieved when no hot-spots are present and high utilization is achieved when hot-spots occur. The main idea is load balancing on local tasks, which at the same time serves as an estimate to assist the decision on remote task assignment. Together, the overall system throughput is drastically increased.
On the theoretical side, assuming an exponential distribution for task processing times, we show that Pandas is throughput-optimal [1], i.e., it is robust to variation in job inter-arrival times, and can accommodate any load if there exists an algorithm that can accommodate it without making the system unstable. We have also shown that Pandas is heavy-traffic optimal in all traffic scenarios, i.e., it asymptotically minimizes the average delay as the system becomes critically loaded. This makes Pandas the only known heavy-traffic optimal algorithm for this problem. More.
Speaker Bio
Qiaomin Xie is a Ph.D. candidate at the Depratment of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, working with Prof. Yi Lu. She received her B.S. degree from the Department of Electronic Engineering at Tsinghua University in 2010, and her M.S. in 2012 from the Department of Electrical and Computer Engineering at UIUC. She is a co-recipient of the Performance Best Paper award. Her main research interests are in developing efficient architectures and algorithms for large and complex networks, such as Cloud. Currently, she is working on scheduling and resource allocation problems in cloud infrastructures.
Derek Chen
Masters student, AE, UIUC
Simultaneous State Estimation of UAV Trajectories Using Probabilistic Graph Models
Venu: CSL B02
Time: 12:15–12:35, Feb 26 2015
Short Abstract
We present a new technique for sensor fusion and batch estimation of UAV trajectories. Traditionally, the goal of GPS UAV state estimation estimates current state and predicts a future state. Our technique not only estimates and predicts our current and future states, but also rectifies past states based on the current and future measurements through GPS and IMU sensor fusion allowing for a better mapping of a UAV’s trajectory. More.
Speaker Bio
Derek Chen is currently a Masters student in the Department of Aerospace Engineering at the University of Illinois at Urbana-Champaign. He graduated with his B.S. degree in Aerospace Engineering in May 2014. His research interests are in autonomous systems and sensor fusion for navigation.
Javier Puig-Navarro
PhD student, AE, UIUC
Time-Critical Coordination of Multiple UAVs with Absolute Temporal Constraints
Venu: CSL B02
Time: 12:35 –12:55, Feb 26 2015
Short Abstract
This presentation will give an overview of a time-critical coordination control law to support multi-vehicle missions that impose both absolute and relative temporal specifications on the trajectories of the vehicles. The proposed cooperative strategy yields robust behavior against external disturbances by allowing the vehicles to negotiate their speeds along the paths in response to information exchanged over an inter-vehicle communication network. Simulation results of a sequential auto-landing scenario will be presented to demonstrate the efficacy of the control law for group coordination. More.
Speaker Bio
Javier Puig-Navarro is a PhD student in the Department of Aerospace Engineering at the University of Illinois at Urbana-Champaign (UIUC). He earned an MS in aerospace engineering from the Polytechnical University of Valencia, Spain. During the last year of the MS program, he was an exchange student at UIUC, where he completed his MS thesis. His research interests are cooperative strategies for unmanned aerial vehicles, robust and nonlinear controls and its applications to flight control systems and very flexible aircraft.
Session 2: Machine Learning, Statistics, and Artificial Intelligence I
Patrick Johnstone
Ph.D. student, ECE, UIUC
Local Linear Convergence on Sparse Optimization Problems
Venu: CSL B02
Time: 15:30 –15:50, Feb 26 2015
Short Abstract
The Fast Iterative Soft Thresholding Algorithm (FISTA), introduced by Beck and Teboulle, is a well-known approach to solving problems where the objective function is the sum of a smooth and non-smooth term. We show that FISTA obtains local linear convergence for Sparse optimization. Specifically we show that after a finite number of iterations, FISTA reduces to minimizing a local function on a reduced support subject to an orthant constraint. We provide explicit bounds on the number of iterations for this to occur thus generalizing the analysis of ISTA by Hale et al. More.
Speaker Bio
Patrick Johnstone is a PhD candidate in ECE under the supervision of Prof. Pierre Moulin. He received the Bachelor of Electrical Engineering degree from the University of New South Wales in Sydney, and the M.S. degree in Electrical Engineering from UIUC. His interests include developing fast algorithms to solve optimization problems, with applications in signal processing and machine learning.
Ching-pei Lee
PhD student, CS, UIUC
Distributed Box-Constrained Quadratic Optimization for Dual Linear SVM
Venu: CSL B02
Time: 15:50 –16:10, Feb 26 2015
Abstract
This talk proposes a communication-efficient dual block coordinate descent algorithm with a fast line search method for distributedly training linear support vector machines (SVM), under the setting that the data instances are disjointly stored on machines. At each iteration, our algorithm obtains a descent direction by solving a block-separable quadratic approximation problem that can be decomposed into disjoint parts. Each sub-problem only relies on the local data of one machine, and can thus be solved independently without communication. We then analytically calculate the optimal step size for this descent direction using an efficient approach that requires only O(1) communication cost. With this optimal step size, our approach establishes global linear convergence, or equivalently O(log(1/epsilon)) iteration complexity for obtaining an -accurate solution, for solving the non-strongly-convex linear SVM dual problem. Experimental results show that our approach is significantly faster than state of the art distributed algorithms for linear SVM.
Speaker Bio
Ching-Pei Lee is a first year computer science Ph.D student in University of Illinois at Urbana-Champaign and he is currently a research assistant to Professor Dan Roth. His research interests include both the theory and practice of nonlinear optimization with their applications to machine learning. Recently, he has focused on distributed and parallel optimization algorithms for training machine learning models with extremely large data.
He is one of the main contributors of the distributed linear classification package, distributed-liblinear, developed by professor Chih-Jen Lin’s team in National Taiwan University.
Yanjun Li
Graduate student, CSL, UIUC
A Unified Framework for Identifiability Analysis in Bilinear Inverse Problems with Applications to Subspace and Sparsity Models
Venu: CSL B02
Time: 16:45 –17:05, Feb 26 2015
Short Abstract
In this talk, we define identifiability of a BIP (Bilinear Inverse Problem) up to a group of transformations. We derive necessary and sufficient conditions for such identifiability, i.e., the conditions under which the solutions can be uniquely determined up to the transformation group. Applying these results to BGPC (blind gain and phase calibration), we derive sufficient conditions for unique recovery under several scenarios, including subspace, joint sparsity, and sparsity models. For BGPC with joint sparsity or sparsity constraints, we develop a procedure to compute the relevant transformation groups. We also give necessary conditions in the form of tight lower bounds on sample complexities, and demonstrate the tightness of these bounds by numerical experiments. The results for BGPC not only demonstrate the application of the proposed general framework for identifiability analysis, but are also of interest in their own right. More.
Speaker Bio
Yanjun Li received the B.S. degree in Automation from Tsinghua University (Beijing, China) in 2012. In the fall of 2012, he joined the University of Illinois at Urbana-Champaign, where he is currently a graduate student at the Departments of Electrical and Computer Engineering, and research assistant at the Coordinated Science Laboratory. His current research interests include compressed sensing and multi-linear structured signal processing and their applications to inverse problems.
Aolin Xu
PhD student, ECE, UIUC
Information-theoretic lower bounds for distributed function computation
Venu: CSL B02
Time: 17:05 –17:25, Feb 26 2015
Abstract
Distributed computation over networks of noisy channels arises in applications such as estimation in sensor networks and consensus of multiple agents connected by noisy communication links. In this talk, we focus on the situation in which each node aims to compute a common function of the random observations of all the nodes, where the nodes are connected by point-to-point channels with finite Shannon capacity. We use information-theoretic techniques to obtain lower bounds on the minimum time needed by any scheme to achieve a certain accuracy at each node.
Our results are derived using a combination of cutset bounds that capture the communication constraints, and a novel lower bound on mutual information, which captures the influence of the joint distribution of local observations and the structure of the function of interest on the computation time, via the excess distortion probability and a quantity called small ball probability. This mutual information lower bound can be viewed as a continuum generalization of Fano’s inequality, and it recovers the conventional Fano’s inequality as a special case. In the particular case of linear functions, the small ball probability can be expressed in terms of L´evy concentration functions of sums of independent random variables, for which tight estimates are available under various regularity conditions, leading to strict improvements over existing results in certain regimes.
Speaker Bio
Aolin Xu is a PhD student in the Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign. He received the BS degree in 2007 from Beijing University of Posts and Telecommunications, and MS degree in 2010 from Tsinghua University, all in electrical engineering. His research interests include statistical inference and learning under communication constraints, information theory, and communication systems.
Session 3: Machine Learning, Statistics, and Artificial Intelligence II
Bihan Wen
M.S. student, ECE, UIUC
Online Sparsifying Transform Learning and Big Data Applications
Venu: CSL B02
Time: 11:00 – 11:20, Feb 27 2015
Abstract
Techniques exploiting the sparsity of signals in a transform domain or dictionary have been popular in signal processing. Adaptive synthesis dictionaries have been shown to be useful in applications such as signal denoising, and medical image reconstruction. More recently, the learning of sparsifying transforms for data has received interest. The sparsifying transform model allows for cheap and exact computations. In this work, we present a methodology for online learning of square sparsifying transforms. Such online learning can be particularly useful when dealing with big data, and for signal processing applications such as real-time sparse representation and denoising. As we show in this work, online transform learning involves cheap computations and modest memory requirements. Moreover, strong convergence guarantees are provided for online transform learning. We also present big data applications based on online transform learning scheme including large-scale image processing (sparse representation, and denoising), as well as a video denoising framework based on online 3-D sparsifying transform learning (VIDOLSAT) which has low computational and memory costs, and can handle streaming video. Our numerical experiments show promising performance for the proposed VIDOLSAT compared to popular prior or state-of-the-art methods.
Speaker Bio
Bihan Wen received the B.Eng. degree in electrical and electronic engineering from Nanyang Technological University, Singapore, in 2012. He is currently pursuing the M.S. degree in Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign, Urbana, IL, USA. His current research interests include signal and image processing, machine learning, and big data applications.
Johannes Traa
PhD student, ECE, UIUC
Spectral Learning of HMM Variants
Venu: CSL B02
Time: 11:20 – 11:40, Feb 27 2015
Abstract
We propose a learning approach for the Mixture of Hidden Markov Models (MHMM) based on the Method of Moments (MoM). Computational advantages of MoM make MHMM learning amenable for large data sets. It is not possible to directly learn an MHMM with existing learning approaches, mainly due to a permutation ambiguity in the estimation process. We show that it is possible to resolve this ambiguity using the spectral properties of a global transition matrix even in the presence of estimation noise. We demonstrate the validity of our approach on synthetic and real data.
This work was presented at the Neural Information Processing Systems (NIPS) conference in December 2014.
Speaker Bio
Johannes Traa got his B.S. in EE from Northwestern University in 2011 and an M.S. in ECE from UIUC in 2013. He is currently pursuing his Ph.D. at UIUC in Paris Smaragdis’s group. In the summers of 2012-2014, he interned with the theory group at Lyric Labs, Analog Devices. His research interests include audio source separation and localization, sound mixture analysis with additive modeling techniques like non-negative matrix factorization, and applications of various areas of statistics (e.g. compositional, directional) to audio problems. More recently, he has worked with fellow lab partner Cem Subakan on spectral learning techniques for time series models.
Kai-Wei Chang
PhD student, CS, UIUC
Practical Learning Algorithms for Structured Prediction
Venu: CSL B02
Time: 11:50 –12:10, Feb 27 2015
Abstract
The desired output in many machine learning tasks is a structured object such as a tree, a clustering of nodes, or a sequence. Learning accurate prediction models for such problems requires training on large amounts of data and exploring complex output structures, often resulting in scalability problems. We describe a collection of results that address these problems from both modelling and algorithmic perspectives – by carefully selecting and caching samples, structures, or latent items.
Our results lead to efficient learning algorithms for structured prediction models, leading to reduction in problem size, improvements in training and evaluation speed and improved performance. We have used our algorithms to learn expressive models from large amounts of annotated data and achieve state-ofthe art performance on several natural language processing tasks.
Speaker Bio
Kai-Wei Chang is a doctoral candidate advised by Prof. Dan Roth in the Department of Computer Science, University of Illinois at Urbana-Champaign. His research interests lie in designing practical machine learning techniques for large and complex data and applying them to real world applications. He has been working on various topics in Machine Learning and Natural Language Processing, including large-scale learning, structured learning, coreference resolution, and relation extraction. Kai-Wei was awarded the KDD Best Paper Award in 2010 and won the Yahoo! Key Scientific Challenges Award in 2011.
Motahhare Eslami
PhD student, CS, UIUC
Exposure to the Invisible: Algorithm Awareness from the Individual to the Collective
Venu: CSL B02
Time: 12:10–12:30, Feb 27 2015
Short Abstract
Today, algorithms exert great power in the curation of everyday online content by prioritizing, classifying, associating, and filtering information. In doing so, they can exert power to shape the users’ experience and even their perception of the world. While such powerful algorithms are omnipresent online, they are rarely highlighted in the interface, leaving users unaware of their presence. Although the lack of users’ awareness about these hidden processes can sometimes indicate a successful design, in some cases this invisibility can cause problems. The increasing prevalence of these invisible algorithms coupled with such substantial influences raises many questions. Here, I present innovative approaches that my colleagues (from Computer Science department and Coordinated Science Laboratory) and I have done to answer these questions. More.
Speaker Bio
Motahhare Eslami is a PhD Candidate at Computer Science department, University of Illinois at Urbana-Champaign. Her research interests are in social computing, human computer interaction, and data mining areas. In particular, she has performed research to analyze and understand people’s behavior in online social networks. Her research has published at prestigious conferences and also received Honorable Mention Award at Facebook Midwest Regional Hackathon (2013). Motahhare has been nominated as a Google PhD Fellowship Nominee (2015) by the University of Illinois as one of the two students from the entire College of Engineering.
Yonatan Bisk
Ph.D. student, CS, UIUC
Unsupervised Grammar Induction From Raw Text
Venu: CSL B02
Time: 12:30 –12:50 Feb 27 2015
Abstract
From digital assistants to web search, the assumption that computers should understand human language and answer our questions is becoming commonplace, but computers’ actual ability to do so is severely limited by the need for expensive, handlabeled training data. Specifically, most modern systems require a syntactic parser to produce linguistic analyses as input in lieu of raw text but these parsers only exist in a handful of languages and their training relies on years of linguists creating resources. In this work we present an alternative unsupervised approach, which means that the computer automatically discovers the linguistic structure of a language from raw text. Much as a child learns language from hearing their parents speaking around them, we will present state-of-the-art work on the unsupervised learning of grammars from raw text. Previous work has aimed to discover syntactic structure without identifying the specific grammatical roles every word is playing. These roles are fundamental to downstream tasks making, our label-producing grammar induction the first unsupervised approach to be directly comparable to supervised systems, and potentially the first that could be used in their stead.
Speaker Bio
Yonatan Bisk is a 6th year PhD student in Computer Science at the University of Illinois at Urbana-Champaign working with Professor Julia Hockenmaier on the automatic discovery of linguistic structures from text. His work fundamentally differs from most syntactic work in the field by focusing on unsupervised methods. >This allows for the creation of language processing systems without the help of linguists by discovering latent patterns in written text.
Session 4: Privacy and Security
Muhammad Naveed
PhD student, CS, UIUC
Controlled Functional Encryption
Venu: CSL B02
Time:15:30 –15:50, Feb 27 2015
Short Abstract
In this work, we propose a new cryptographic model called “Controlled Functional Encryption (C-FE)” that allows us to construct realistic and efficient constructions. As in functional encryption, C-FE allows a user (client) to learn only certain functions of encrypted data, using keys obtained from an authority. However, we allow (and require) the client to send a fresh key request to the authority every time it wants to evaluate a function on a ciphertext. We obtain efficient solutions by carefully combining CCA2 secure public-key encryption with Yao’s garbled circuit. Our main contributions in this work include developing and formally defining the notion of C-FE; designing efficient and practical constructions of C-FE schemes achieving these definitions for specific and general classes of functions; and evaluating the performance of our constructions on various application scenarios. More.
Speaker Bio
Muhammad Naveed is a fourth year PhD student in computer science at the University of Illinois at Urbana-Champaign. He works on novel models that can bring modern cryptographic technology to real applications. He is also interested in systems security and genomics privacy. For more details visit his homepage at www.naveed.pro.
Shashank Agrawal
PhD student, CS, UIUC
Cryptographic Agents: Towards a Unified Theory of Computing on Encrypted Data
Venu: CSL B02
Time: 15:50 –16:10, Feb 27 2015
Short Abstract
We provide a new framework of cryptographic agents that unifies various modern “cryptographic objects” — identity-based encryption, fully-homomorphic encryption, functional encryption, and various forms of obfuscation – similar to how the Universal Composition framework unifies various multi-party computation tasks like commitment, coin-tossing and zero-knowledge proofs. These cryptographic objects can all be cleanly modeled as “schemata” in our framework. More.
Speaker Bio
Shashank Agrawal is a PhD student at the University of Illinois Urbana-Champaign. He is interested in cryptography and secure multi-party computation. He is a recipient of the C.L. and Jane W.-S. Liu Award and the Feng Chen Memorial Award, given by the Computer Science department at UIUC.
Wei Yang
PhD student, CS, UIUC
Improving Mobile Application Security via Bridging User Expectations and Application Behaviors
Venu: CSL B02
Time: 17:10 –17:30, Feb 27 2015
Short Abstract
To keep malware out of mobile application(app) markets, existing techniques analyze the security aspects of app behaviors and summarize patterns of these security aspects to determine what apps do. However, malware and benign apps could present the same behaviors(e.g., sending SMS). The difference is that the behaviors of malware are unexpected while the behaviors of benign apps are expected by users. User expectations (reflected via user perception in combination with user judgment) should be incorporated into security analysis to determine whether app behaviors are within user expectations. This presentation presents our recent work on bridging the semantic gap between user perceptions of the app behaviors and the actual app behaviors. More.
Speaker Bio
Wei Yang is a PhD student in CS department of UIUC, under the supervision of Prof. Tao Xie. His primary research interest is software engineering and security. His past research experience spans the spectrum from automated testing (ORBIT), through text analysis (WHYPER), to malware detection (AppContext). He is generally interested in tools and techniques for helping programmers test and write bug-free and secure mobile applications. He has recently focused on using program analysis, natural language processing techniques and cognitive analysis to bridge the gap between user perceptions and app behaviors in mobile applications.