Graduate

Active Learning and Optimization for Next Generation Wireless Systems

Topic: 
Active Learning and Optimization for Next Generation Wireless Systems
Abstract / Description: 

Network management and configuration is an essential attribute of any wireless network with reliable self-tuning capabilities. However,the cost and overhead of network management has rarely been accounted for from a fundamental limit (information theoretic) perspective. In contrast to the past generations of networking solutions, on the other hand, in the ever-increasingly mobile and large-scale networks of tomorrow the network reconfiguration overhead may not be insignificant; this includes the initial beam alignment, link maintenance, spectrum sensing, packet resizing, etc. Our work aims to provide fundamental limits on the overhead associated with learning, network tuning, and optimization of network parameters.

Our approach relies on fundamental notions in information theory and statistics to quantify the networking overhead and utilizes recent data analytic and machine learning algorithms to develop practical learning/optimization algorithms. In the first part of the talk, we consider the problem of reliably and quickly searching for a parameter of interest in a large signal space in face of measurement-dependent noise. This problem naturally arises in many practical communications systems such as the directional link establishment and maintenance (beam alignment) as well as spectrum sensing for cognitive radios. In the second part of the talk, we consider an important variant of the search problem: data-driven (Bayesian and non-Bayesian) function maximization and its connection to network parameter tuning.


Sponsored by IEEE Santa Clara Valley Information Theory Society. Please register for this event.

Date and Time: 
Wednesday, September 26, 2018 - 11:25am to 12:25pm
Venue: 
Packard 202

EE380 Computer Systems Colloquium: The Case for Learned Index Structures

Topic: 
The Case for Learned Index Structures
Abstract / Description: 

Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not. In this talk, we take this premise and explain how existing database index structures can be replaced with other types of models, which we term learned indexes. The key idea is that a model can learn the sort order or structure of indexed data and use this signal to effectively predict the position or existence of records. We offer theoretical analysis under which conditions learned indexes outperform traditional index structures and we will delve into the challenges in designing learned index structures. Through addressing these challenges, our initial results show that learned indexes are able to outperform cache-optimized B-Trees by up to 70% in speed while saving an order-of-magnitude in memory over several real-world data sets. Finally, we will discuss the broader implications of learned indexes on database design and future directions for the ML for Database Systems research.


The Stanford EE Computer Systems Colloquium (EE380) meets on Wednesdays 4:30-5:45 throughout the academic year. Talks are given before a live audience in Room B03 in the basement of the Gates Computer Science Building on the Stanford Campus. The live talks (and the videos hosted at Stanford and on YouTube) are open to the public.

Stanford students may enroll in EE380 to take the Colloquium as a one unit S/NC class. Enrolled students are required to keep and electronic notebook or journal and to write a short, pithy comment about each of the ten lectures and a short free form evaluation of the class in order to receive credit. Assignments are due at the end of the quarter, on the last day of examinations.

EE380 is a video class. Live attendance is encouraged but not required. We (the organizers) feel that watching the video is not a substitute for being present in the classroom. Questions are encouraged.

Many past EE380 talks are available on YouTube, see the EE380 Playlist.

Date and Time: 
Wednesday, October 17, 2018 - 4:30pm
Venue: 
Gates B03

EE380 Computer Systems Colloquium: 2017 Turing Award Recipients on Computer Architecture

Topic: 
Computer Architecture
Abstract / Description: 

TBA


The Stanford EE Computer Systems Colloquium (EE380) meets on Wednesdays 4:30-5:45 throughout the academic year. Talks are given before a live audience in Room B03 in the basement of the Gates Computer Science Building on the Stanford Campus. The live talks (and the videos hosted at Stanford and on YouTube) are open to the public.

Stanford students may enroll in EE380 to take the Colloquium as a one unit S/NC class. Enrolled students are required to keep and electronic notebook or journal and to write a short, pithy comment about each of the ten lectures and a short free form evaluation of the class in order to receive credit. Assignments are due at the end of the quarter, on the last day of examinations.

EE380 is a video class. Live attendance is encouraged but not required. We (the organizers) feel that watching the video is not a substitute for being present in the classroom. Questions are encouraged.

Many past EE380 talks are available on YouTube, see the EE380 Playlist.

Date and Time: 
Wednesday, October 10, 2018 - 4:30pm
Venue: 
Gates B03

EE380 Computer Systems Colloquium: Interactive Autonomy: a human-centered approach for safe interactions

Topic: 
Interactive Autonomy: a human-centered approach for safe interactions
Abstract / Description: 

Today's society is rapidly advancing towards robotics systems that interact and collaborate with humans, e.g., semi-autonomous vehicles interacting with drivers and pedestrians, medical robots used in collaboration with doctors, or service robots interacting with their users in smart homes. In this talk, I will first discuss interactive autonomy, where we develop algorithms for autonomous systems that influence humans, and further leverage these effects for better safety, efficiency, coordination, and estimation. I will then focus on our efficient active learning methods to build predictive models of humans's preferences by eliciting comparisons from a mixed set of humans, and further analyzing the generalizability and robustness of the learned human models for safe and seamless interaction with robots.


The Stanford EE Computer Systems Colloquium (EE380) meets on Wednesdays 4:30-5:45 throughout the academic year. Talks are given before a live audience in Room B03 in the basement of the Gates Computer Science Building on the Stanford Campus. The live talks (and the videos hosted at Stanford and on YouTube) are open to the public.

Stanford students may enroll in EE380 to take the Colloquium as a one unit S/NC class. Enrolled students are required to keep and electronic notebook or journal and to write a short, pithy comment about each of the ten lectures and a short free form evaluation of the class in order to receive credit. Assignments are due at the end of the quarter, on the last day of examinations.

EE380 is a video class. Live attendance is encouraged but not required. We (the organizers) feel that watching the video is not a substitute for being present in the classroom. Questions are encouraged.

Many past EE380 talks are available on YouTube, see the EE380 Playlist.

Date and Time: 
Wednesday, September 26, 2018 - 4:30pm
Venue: 
Gates B03

IT-Forum: Arbitrarily Varying Broadcast and Relay Channels

Topic: 
Arbitrarily Varying Broadcast and Relay Channels
Abstract / Description: 

Two models of an arbitrarily varying channel (AVC) are studied; both are relevant to modern networks under jamming attacks by an adversary or a hacker. The arbitrarily varying broadcast channel is considered when state information is available at the transmitter in a causal manner. Inner and outer bounds are established, on both the random code capacity region and the deterministic code capacity region with degraded message sets. The form of the bounds raises the question whether the minimax theorem can be generalized to rate regions, i.e. whether the order of the intersection over state distributions and the union over Shannon strategies can be interchanged. A sufficient condition is given, under which this assertion holds and the random code capacity region is determined. As an example, the arbitrarily varying binary symmetric broadcast channel is examined, showing that there are cases where the condition holds, hence the capacity region is determined, and other cases where there is a gap between the bounds. The gap implies that the minimax theorem does not always hold for rate regions.

In the second part of the talk, a new model is introduced, namely, the arbitrarily varying relay channel. The results include the cutset bound, decode-forward bound and partial decode-forward bound on the random code capacity, which require modification of the usual methods for the AVC to fit the block Markov coding scheme. The random code capacity is further determined for special cases. Then, deterministic coding schemes are considered, and the deterministic code capacity is derived under certain conditions, for the degraded and reversely degraded relay channel, and the case of orthogonal sender components. The following question is addressed: If the encoder-decoder and encoder-relay marginals are both symmetrizable, does that necessarily imply zero capacity? We show and explain why the answer is no. The random code capacity is determined for the arbitrarily varying Gaussian relay channel with sender frequency division, and the deterministic code capacity is bounded using the techniques of Csisz\'ar and Narayan's 1991 paper on the Gaussian AVC. It is observed that the gap vanishes as the input becomes less constrained. It is commonly believed that the primitive relay channel "captures most essential features and challenges of relaying, and thus serves as a good testbed for new relay coding techniques" (Kim, 2007). It is observed that in the arbitrarily varying case, this may no longer be true.

This work is part of a Ph.D. thesis under the supervision of Yossef Steinberg.

Date and Time: 
Friday, October 12, 2018 - 1:15pm
Venue: 
Packard 202

IT-Forum: Structured Cooperation for Channels with Feedback and beyond

Topic: 
Structured Cooperation for Channels with Feedback and beyond
Abstract / Description: 

The capacities of fundamental communication problems such as channels with feedback and two-way communications channels are characterized with multi-letter expressions. The challenge in simplifying these expressions is their exhaustive dependence on all information that is accumulated throughout the communication. In this talk, we aim to simplify such capacities by imposing a structure on the accumulated data via a new sequential quantization technique on a directed graph.

First application of this method is for channels with memory and feedback. We will show upper and lower single-letter bounds on the capacity. The bounds are expressed with structured auxiliary random variable (r.v.), a notion that suits problems of sequential nature. For all cases where the capacity is known, the bounds are tight (with small cardinality of the structured auxiliary r.v.). This reveals a simple capacity formula that captures the major role of structure in feedback problems. We will also present a simple and sequential coding scheme, which is based on the posterior matching principle, and achieves the lower bound (and the capacity in many cases).

As time permits, we will show that structure is beneficial for other communication scenarios such as two-way communication channels with common outputs and the energy harvesting model.

The talk is based on a joint work with Prof. Henry Pfister (Duke Univeristy), Prof. Haim Permuter (BGU) and Prof. Navin Kashyap (IISc).

Date and Time: 
Monday, October 8, 2018 - 4:15pm
Venue: 
Packard 202

IT-Forum: Data-Driven Policy Learning: Generalization and Optimization

Topic: 
Data-Driven Policy Learning: Generalization and Optimization
Abstract / Description: 

The problem of learning good treatment assignment rules from observational data lies at the heart of many challenges in data-driven decision making. While there is a growing body of literature devoted to this problem, most existing results are focused on the binary-action case (i.e., where one action corresponds to assignment to control and to assignment to treatment). In this paper, we study the offline multi-action policy learning problem with observational data and, building on the theory of efficient semi-parametric inference, propose and implement a policy learning algorithm that achieves asymptotically minimax-optimal regret. To the best of our knowledge, this is the first result of this type in the multi-action setup and provides a substantial performance improvement over the existing learning algorithms. We additionally investigate the application aspects of policy learning by working with decision trees, and discuss two different approaches for solving the key step of the learning algorithm to exact optimality, one using a mixed integer program formulation and the other using a tree-search based algorithm.

This is joint work with Susan Athey and Stefan Wager.


 

The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:15 pm during the academic year.

The Information Theory Forum is organized by graduate students Yanjun Han and Yihui Quek. To suggest speakers, please contact any of the students.

Date and Time: 
Friday, October 5, 2018 - 1:15pm
Venue: 
Packard 202

IT-Forum presents Representations, fairness, and privacy: information-theoretic tools for machine learning

Topic: 
Representations, fairness, and privacy: information-theoretic tools for machine learning
Abstract / Description: 

Information theory can shed light on the algorithm-independent limits of learning from data and serve as a design driver for new machine learning algorithms. In this talk, we discuss a set of flexible information-theoretic tools called the principal inertia components (PICs) that can be used to (i) understand fairness and discrimination in machine learning models, (ii) provide an estimation-theoretic view of privacy, and (iii) characterize data representations learned by complex learning models. The PICs enjoy a long history in both the statistics and information theory, and provide a fine-grained decomposition of the dependence between two random variables. We illustrate these techniques in both synthetic and real-world datasets, and discuss future research directions.

Date and Time: 
Friday, September 28, 2018 - 1:15pm
Venue: 
Packard 202

ISL Colloquium: Battling Demons in Peer Review

Topic: 
New Battling Demons in Peer Review
Abstract / Description: 

Peer review is the backbone of scholarly research. It is however faced with a number of challenges (or "demons") such as subjectivity, bias/miscalibration, noise, and strategic behavior. The growing number of submissions in many areas of research such as machine learning has significantly increased the scale of these demons. This talk will present some principled and practical approaches to battle these demons in peer review:

(1) Subjectivity: How to ensure that all papers are judged by the same yardstick?

(2) Bias/miscalibration: How to use ratings in presence of arbitrary or adversarial miscalibration?

(3) Noise: How to assign reviewers to papers to simultaneously ensure fair and accurate evaluations in the presence of review noise?

(4) Strategic behavior: How to insulate peer review from strategic behavior of author-reviewers?

The work uses tools from statistics and learning theory, social choice theory, information theory, game theory and decision theory. (No prior knowledge on these topics will be assumed.)


The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Thursday at 4:15 pm during the academic year.

The Information Theory Forum is organized by graduate students Martin Zhang, Farzan Farnia, and Zhengyuan Zhou. To suggest speakers, please contact any of the students.

Date and Time: 
Thursday, October 25, 2018 - 4:15pm
Venue: 
Packard 202

ISL Colloquium: New Breakthroughs in Scheduling Theory

Topic: 
New Breakthroughs in Scheduling Theory
Abstract / Description: 

Scheduling policies are at the heart of computer systems. The right scheduling policy can dramatically reduce response times, ensure fairness, provide class-based priority, etc., without requiring additional resources. While stochastic response time analysis of different scheduling policies has been the focus of thousands of theoretical papers, results are limited to analyzing a relatively small number of "simple" scheduling policies.

In this talk, we introduce the SOAP class of scheduling policies: Schedule Ordered by Age-based Priority. The SOAP policies include almost all scheduling policies in the literature as well as an infinite number of variants which have never been analyzed, or maybe even conceived. SOAP policies include the highly intractable SERPT policy (Shortest-Expected-Remaining-Processing-Time), as well as the famously complex Gittins Index policy. SOAP also includes all sorts of "combination" policies, like a policy that performs Shortest-Job-First on jobs with known size and Foreground-Background scheduling on jobs with unknown size, or a policy that is allowed to preempt jobs only when they hit certain ages. In this talk we present a stochastic response time analysis of all SOAP policies via a single universal framework.

Joint work with: Ziv Scully and Alan Scheller-Wolf

Appeared in ACM SIGMETRICS/POMACS 2018. APS 2018 Best Student Paper Finalist.


The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Thursday at 4:15 pm during the academic year.

The Information Theory Forum is organized by graduate students Martin Zhang, Farzan Farnia, and Zhengyuan Zhou. To suggest speakers, please contact any of the students.

Date and Time: 
Thursday, October 11, 2018 - 4:15pm
Venue: 
Packard 202

Pages

Subscribe to RSS - Graduate