EE Student Information

The Department of Electrical Engineering supports Black Lives Matter. Read more.

• • • • •

EE Student Information, Spring & Summer Quarters 19-20: FAQs and Updated EE Course List.

Updates will be posted on this page, as well as emailed to the EE student mail list.

Please see Stanford University Health Alerts for course and travel updates.

As always, use your best judgement and consider your own and others' well-being at all times.

IT-Forum

IT Forum presents "Fundamental barriers to estimation in high-dimensions"

Topic: 
Fundamental barriers to estimation in high-dimensions
Abstract / Description: 

Modern large-scale statistical models require to estimate thousands to millions of parameters. Understanding the tradeoff between statistical optimality and computational tractability in such models remains an outstanding challenge. Under a random design assumption, we establish lower bounds to statistical estimation with two popular classes of tractable estimators in several popular statistical models. First, in high-dimensional linear models we show that a large gap often exists between the optimal statistical error and that achieved by least squares with a convex penalty. Examples of such estimators include the Lasso, ridge regression, and MAP estimation with log-concave priors and Gaussian noise. Second, in generalized linear models and low-rank matrix estimation problems, we introduce the class of 'general first order methods,' examples of which include gradient descent, projected gradient descent, and their accelerated versions. We derive lower bounds for general first order methods which are tight up to asymptotically negligible terms. Our results demonstrate a gap to statistical optimality for general first order methods in both sparse phase retrieval and sparse PCA.

This is joint work with Andrea Montanari and Yuchen Wu.

 

Date and Time: 
Friday, April 3, 2020 - 1:15pm
Venue: 
Zoom: stanford.zoom.us/j/516499996

IT Forum presents "What Hockey Teams and Foraging Animals Can Teach Us About Feedback Communication"

Topic: 
What Hockey Teams and Foraging Animals Can Teach Us About Feedback Communication
Abstract / Description: 

Suppose we wish to communicate over a memoryless channel with known statistics. How can the use of a feedback link from the receiver to the transmitter help? We introduce a novel mechanism for using feedback, called timid/bold coding, and we show that for some channels timid/bold coding yields a strict asymptotic improvement over the best non- feedback schemes. We also show that for a broad class of channels, feedback is useful if and only if timid/bold coding is applicable. The talk contains a puzzle (recently featured on the FiveThirtyEight website), a life lesson, a (potential) practical application, and some stochastic calculus.

This is joint work with Nirmal Shende and Yucel Altug.

Date and Time: 
Friday, March 6, 2020 - 1:15pm
Venue: 
Packard 202

RL forum presents "Temporal Abstraction in Reinforcement Learning with the Successor Representation"

Topic: 
Temporal Abstraction in Reinforcement Learning with the Successor Representation
Abstract / Description: 

Reasoning at multiple levels of temporal abstraction is one of the key abilities for artificial intelligence. In the reinforcement learning problem, this is often instantiated with the options framework. Options allow agents to make predictions and to operate at different levels of abstraction within an environment. Nevertheless, when a reasonable set of options is not known beforehand, there are no definitive answers for characterizing which options one should consider. Recently, a new paradigm for option discovery has been introduced. This paradigm is based on the successor representation (SR), which defines state generalization in terms of how similar successor states are. In this talk I'll discuss the existing methods from this paradigm, providing a big picture look at how the SR can be used in the options framework. I'll present methods for discovering "bottleneck" options, as well as options that improve an agent's exploration capabilities. I'll also discuss the option keyboard, which uses the SR to extend a finite set of options to a combinatorially large counterpart without additional learning.

Date and Time: 
Tuesday, February 25, 2020 - 2:00pm
Venue: 
Packard 202

IT Forum presents "Why should information theorists and probabilists care about blockchains?"

Topic: 
Why should information theorists and probabilists care about blockchains?
Abstract / Description: 

The invention of blockchains in 2008 opened up for the first time the possibility of large scale decentralized trust systems. In the past few years, the design and analysis of blockchains have received significant attention from cryptography, security and distributed systems communities. In this talk, I argue that there are many interesting problems for information theorists and probabilists as well. I will discuss two particular classes of problems: 1) security analysis of blockchains as convergence analysis of random tree processes; 2) the use of coding to efficiently scale blockchains. I will also briefly discuss a course I plan to teach in the Spring on the topic.

Part of this talk is on joint work with Amir Dembo and Ofer Zeitouni.

 

Date and Time: 
Friday, January 31, 2020 - 1:00pm
Venue: 
Packard 202

Q-Farm Quantum Seminar Series presents "Surprises from Time Crystals"

Topic: 
Surprises from Time Crystals
Abstract / Description: 

Time crystals are new states of matter that only exist in an out-of-equilibrium setting. I will review the state of this rapidly evolving field, focusing in particular on some of the remarkable properties of this phase, and the surprises coming out of its study. I will provide a detailed overview of existing experiments, with a view towards identifying the ingredients needed for an unambiguous observation of this phase in the future.

Date and Time: 
Wednesday, January 29, 2020 - 12:00pm
Venue: 
Hansen Physics & Astrophysics Building, 102/103

ISL & IT-Forum present "Approaching Capacity at Short Blocklengths"

Topic: 
Approaching Capacity at Short Blockengths
Abstract / Description: 

This talk explores a family of recent results directed to approaching capacity at short blocklengths on the order of 50-500 channel transmissions. Convolutional codes out-perform polar codes and LDPC codes to approach the random coding union bound with low complexity when used with an optimized CRCs and list decoding. This perspective rehabilitates "catastrophic" convolutional codes, which are more properly understood for finite blocklengths as clever expurgation rather than any sort of catastrophe. This approach also provides a low-complexity approach for maximum-likelihood decoding of high-rate BCH codes. The use of variable length coding, i.e. incremental redundancy controlled with simple ACK/NACK feedback, allows capacity to be closely approached by practical codes with fewer than 500 channel uses. This talk reviews the information-theoretic results of Polyanskiy with respect to ACK/NACK feedback, presents new results extending the classic approach of Horstein for full feedback, and shows how to optimize the number and length of incremental redundancy transmissions (and feedback transmissions) for a variable-length code with feedback (i.e. a type-II hybrid ARQ). The talk also shows how to avoid entirely the overhead of a CRC in a hybrid ARQ setting by directly computing the reliability of convolutional codeword decisions. Finally, attendees will learn about a novel communications architecture that allows the use of incremental redundancy even without feedback.

 

Date and Time: 
Friday, January 24, 2020 - 1:15pm
Venue: 
Packard 202

ISL Colloquium presents "Self-Programming Networks: Applications to Financial Trading Systems"

Topic: 
Self-Programming Networks: Applications to Financial Trading Systems
Abstract / Description: 

We describe Self-Programming Networks (SPNs), an ongoing research effort at Stanford for making cloud computing networks autonomous; that is, to enable the networks to sense and monitor themselves, and program and control themselves. We describe the goals and the architecture of SPNs and present two key outcomes: (i) Huygens, for scalable and accurate clock synchronization, and (ii) Simon, for fine-grained network telemetry using observations from the network’s edge. We also describe the relevance of this work to existing financial trading systems and demonstrate how, in future, it enables financial trading systems in the Cloud.


The Information Systems Laboratory Colloquium (ISLC) is typically held in Packard 101 every Thursday at 4:30 pm during the academic year. Coffee and refreshments are served at 4pm in the second floor kitchen of Packard Bldg.

The Colloquium is organized by graduate students Joachim Neu, Tavor Baharav and Kabir Chandrasekher. To suggest speakers, please contact any of the students.

Date and Time: 
Thursday, January 23, 2020 - 4:30pm
Venue: 
Packard 101

ISL & IT Forum present "Higher Criticism for discriminating frequency-tables and testing authorship"

Topic: 
Higher Criticism for discriminating frequency-tables and testing authorship
Abstract / Description: 

The Higher Criticism (HC) test is a useful tool for detecting the presence of a signal spread across a vast number of features, especially in the sparse setting when only few features are useful while the rest contain only noise. We adapt the HC test to the two-sample setting of detecting changes between two frequency tables. We apply this adaptation to authorship attribution challenges, where the goal is to identify the author of a document using other documents whose authorship is known. The method is simple yet performs well without handcrafting and tuning. Furthermore, as an inherent side effect, the HC calculation identifies a subset of discriminating words, which allow additional interpretation of the results. Our examples include authorship in the Federalist Papers and machine-generated texts.

We take two approaches to analyze the success of our method. First, we show that, in practice, the discriminating words identified by the test: have low variance across documents belonging to a corpus of homogeneous authorship. We conclude that in testing a new document against the corpus of an author, HC is mostly affected by words characteristic of that author and is relatively unaffected by topic structure. Finally, we analyze the power of the test in discriminating two multinomial distributions under sparse and weak perturbations model. We show that our test has maximal power in a wide range of the model parameters, even though these parameters are unknown to the user.

Date and Time: 
Friday, January 10, 2020 - 1:15pm
Venue: 
Packard 202

ISL Colloquium and IT-Forum present "A Notion of Entropy for Sparse Marked Graphs and its Applications in Graphical Data Compression"

Topic: 
A Notion of Entropy for Sparse Marked Graphs and its Applications in Graphical Data Compression
Abstract / Description: 

Many modern data sources arising from social networks, biological data, etc. are best viewed as indexed by combinatorial structures such as graphs, rather than time series. The local weak limit theory for sparse graphs, also known as the objective method, due to Benjamini, Schramm, Aldous, Steele, Lyons and others, provides a framework which enables one to make sense of a stationary process indexed by graphs. The theory of time series is the engine driving an enormous range of applications in areas such as control theory, communications, information theory and signal processing. It is to be expected that a theory of stationary stochastic processes indexed by combinatorial structures, in particular graphs, would eventually have a similarly wide-ranging impact.

Employing the above framework, we introduce a notion of entropy for probability distributions on rooted graphs. This is a generalization of the notion of entropy introduced by Bordenave and Caputo to graphs which carry marks on their vertices and edges. Such marks can represent information on real-world data. For instance, in a social network graph where each node represents an individual and edges represent friendships, a vertex mark represents the type of an individual, while edge marks represent shared data between friends. The above notion of entropy can be considered as a natural counterpart for the Shannon entropy rate in the world of graphical data. We illustrate this by introducing a universal compression scheme for marked graphical data. Furthermore, we introduce an algorithm that can perform such a compression with low complexity.

This talk is based on joint work with Venkat Anantharam.

Date and Time: 
Friday, December 6, 2019 - 1:15pm
Venue: 
Packard 202

ISL & IT Forum present "An information-theoretic solution to random access communication"

Topic: 
An information-theoretic solution to random access communication
Abstract / Description: 

The emergence of networks of many devices in the context of cyber-physical systems underscores the need for novel solutions for communication over random access channels. Most protocols currently in place rely on collision avoidance and are woefully ill-suited to handling high variation in the number and variety of communicators. We ask the question of whether it is possible, in a scenario where no one knows how many transmitters are active, for the receiver to almost always recover the messages sent by all active transmitters. Surprisingly, we find that not only is reliable decoding possible in this regime, but it is possible to attain both the capacity and the dispersion of the multiple access channel in operation. Our strategy relies on ''semi-rateless'' codes: decoding attempts are made at a sparse set of pre-determined decoding times, and the decoder is tasked with recovering from the channel output the messages of the active transmitters. Once the decoder determines that reliable decoding can be made, a positive acknowledgement (ACK) is sent to the encoders, indicating the end of that communication epoch and the start of a new one. The feedback ensures that the collection of active transmitters remains fixed during each epoch. These semi-rateless codes work for both channel and source coding; for source coding, our semi-rateless scheme achieves the optimal performance up to the first three order terms in the Gaussian approximation of the optimal rate. The analysis includes a refinement of the random coding argument ensuring the existence of a deterministic code that meets multiple constraints simultaneously, a random-coding union achievability bound for multiple access, and a sharp converse bound for multiple access source coding via a connection to composite hypothesis testing.

Based on joint works (ArXiv:1801.09018, ArXiv:1902.03366) with M. Effros, R. C. Yavas, S. Chen.

Date and Time: 
Friday, November 22, 2019 - 1:15pm
Venue: 
Packard 202

Pages

Subscribe to RSS - IT-Forum