IT-Forum

ISL Colloquium presents "The Well Tempered Lasso"

Topic: 
The Well Tempered Lasso
Abstract / Description: 

We study the complexity of the entire regularization path for least squares regression with 1-norm penalty, known as the Lasso. Every regression parameter in the Lasso changes linearly as a function of the regularization value. The number of changes is regarded as the Lasso's complexity. Experimental results using exact path following exhibit polynomial complexity of the Lasso in the problem size. Alas, the path complexity of the Lasso on artificially designed regression problems is exponential. We use smoothed analysis as a mechanism for bridging the gap between worst case settings and the de facto low complexity. Our analysis assumes that the observed data has a tiny amount of intrinsic noise. We then prove that the Lasso's complexity is polynomial in the problem size. While building upon the seminal work of Spielman and Teng on smoothed complexity, our analysis is morally different as it is divorced from specific path following algorithms. We verify the validity of our analysis in experiments with both worst case settings and real datasets. The empirical results we obtain closely match our analysis.

Joint work with Prof. Yuanzhi Li (CMU).

Date and Time: 
Thursday, January 28, 2021 - 4:30pm

IT Forum presents "Towards Model Agnostic Robustness"

Topic: 
Towards Model Agnostic Robustness
Abstract / Description: 

It is now common practice to try and solve machine learning problems by starting with a complex existing model or architecture, and fine-tuning/adapting it to the task at hand. However, outliers, errors or even just sloppiness in training data often lead to drastic drops in performance.

We investigate a simple generic approach to correct for this, motivated by a classic statistical idea: trimmed loss. This advocates jointly (a) selecting which training samples to ignore, and (b) fitting a model on the remaining samples. As such this is computationally infeasible even for linear regression. We propose and study the natural iterative variant that alternates between these two steps (a) and (b) - each of which individually can be easily accomplished in pretty much any statistical setting. We also study the batch-SGD variant of this idea. We demonstrate both theoretically (for generalized linear models) and empirically (for moderate-sized neural network models) that this effectively recovers accuracy in the presence of bad training data.

This work is joint with Yanyao Shen and Vatsal Shah and appears in NeurIPS 2019, ICML 2019 and AISTATS 2020.

Date and Time: 
Thursday, October 29, 2020 - 4:30pm
Venue: 
Registration required

IT-Forum presents "A Very Sketchy Talk"

Topic: 
A Very Sketchy Talk
Abstract / Description: 

We give an overview of dimensionality reduction methods, or sketching, for a number of problems in optimization, first surveying work using these methods for classical problems, which gives near optimal algorithms for regression, low rank approximation, and natural variants. We then survey recent work applying sketching to column subset selection, kernel methods, sublinear algorithms for structured matrices, tensors, trace estimation, and so on. The focus in the talk will be on fast algorithms.


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 every Friday at 1:15 pm during the academic year.

Until further notice, the IT Forum convenes exclusively via Zoom (on Fridays at 1:15pm PT) due to the ongoing pandemic. To avoid "Zoom-bombing", we ask attendees to input their email address here https://stanford.zoom.us/meeting/register/tJwkf-uvqjoqHNIWxY4HHon4K107QMo22PVR to receive the Zoom meeting details via email.


The ISL Colloquium meets weekly during the academic year. Seminars are each Thursday at 4:30pm PT, unless indicated otherwise.

Until further notice, the ISL Colloquium convenes exclusively via Zoom (on Thursdays at 4:30pm PT) due to the ongoing pandemic. To avoid "Zoom-bombing", we ask attendees to input their email address here https://stanford.zoom.us/meeting/register/tJckfuCurzkvEtKKOBvDCrPv3McapgP6HygJ to receive the Zoom meeting details via email.

Date and Time: 
Friday, November 13, 2020 - 1:15pm
Venue: 
Zoom

IT-Forum presents "High-accuracy Optimality and Limitation of the Profile Maximum Likelihood"

Topic: 
High-accuracy Optimality and Limitation of the Profile Maximum Likelihood
Abstract / Description: 

Symmetric properties of distributions arise in multiple settings, where for each of them separate estimators have been developed. Recently, Orlitsky et al. showed that a single estimator, called the profile maximum likelihood (PML), achieves the optimal sample complexity universally for many properties and any accuracy parameter larger than $n^{-1/4}$, where $n$ is the sample size. They also raised the question whether this low-accuracy range is an artifact of the analysis or a fundamental limitation of the PML, which remained open after several subsequent work.

In this talk, we provide a complete answer to this question and characterize the tight performance of PML in the high-accuracy regime. On the positive side, we show that the PML remains sample-optimal for any accuracy parameter larger than $n^{-1/3}$ using a novel chaining property of the PML distributions. In particular, the PML distribution itself is an optimal estimator of the sorted hidden distribution. On the negative side, we show that the PML as well as any adaptive approach cannot be universally sample-optimal when the accuracy parameter is below $n^{-1/3}$, and characterize the exact penalty for adaptation via a matching adaptation lower bound.

Based on joint work with Kirankumar Shiragur. The full papers are available online at https://arxiv.org/abs/2004.03166 and https://arxiv.org/abs/2008.11964.


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 every Friday at 1:15 pm during the academic year.

Until further notice, the IT Forum convenes exclusively via Zoom (on Fridays at 1:15pm PT) due to the ongoing pandemic. To avoid "Zoom-bombing", we ask attendees to input their email address here https://stanford.zoom.us/meeting/register/tJwkf-uvqjoqHNIWxY4HHon4K107QMo22PVR to receive the Zoom meeting details via email.

Date and Time: 
Friday, September 25, 2020 - 1:15pm
Venue: 
Zoom registration req'd

Learning to Bid in Repeated First-price Auctions

Topic: 
Learning to Bid in Repeated First-price Auctions
Abstract / Description: 

First-price auctions have very recently swept the online advertising industry, replacing second-price auctions as the predominant auction mechanism on many platforms. This shift has brought forth important challenges for a bidder: how should one bid in a first-price auction where it is no longer optimal to bid one's private value truthfully and hard to know the others' bidding behaviors? To answer this question, we study online learning in repeated first-price auctions, and consider various scenarios involving different assumptions on the characteristics of the other bidders' bids, of the bidder's private valuation, of the feedback structure of the auction, and of the reference policies with which our bidder competes. For all of them, we characterize the essentially optimal performance and identify computationally efficient algorithms achieving it. Experimentation on first-price auction datasets from Verizon Media demonstrates the promise of our schemes relative to existing bidding algorithms.

Based on joint work with Aaron Flores, Erik Ordentlich, Tsachy Weissman, and Zhengyuan Zhou. The full papers are available online at https://arxiv.org/abs/2003.09795 and https://arxiv.org/abs/2007.04568


 

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 every Friday at 1:15 pm during the academic year.

Until further notice, the IT Forum convenes exclusively via Zoom (on Fridays at 1:15pm PT) due to the ongoing pandemic. To avoid "Zoom-bombing", we ask attendees to input their email address here https://stanford.zoom.us/meeting/register/tJwkf-uvqjoqHNIWxY4HHon4K107QMo22PVR to receive the Zoom meeting details via email.

Date and Time: 
Friday, September 18, 2020 - 1:15pm
Venue: 
Zoom

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 to Wednesday, February 26, 2020 - 1:55pm
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 to Saturday, February 1, 2020 - 12:55pm
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 to Thursday, January 30, 2020 - 11:55am
Venue: 
Hansen Physics & Astrophysics Building, 102/103

Pages

Subscribe to RSS - IT-Forum