EE Student Information

IT-Forum

IT-Forum: Algorithmic Obstructions in the Random Number Partitioning Problem

Topic: 
Algorithmic Obstructions in the Random Number Partitioning Problem
Abstract / Description: 

We consider the algorithmic problem of finding a near-optimal solution for the number partitioning problem (NPP). This problem appears in many practical applications, including the design of randomized controlled trials, multiprocessor scheduling, and cryptography; and is also of theoretical significance. The NPP possesses the so-called statistical-to-computational gap: when its input has distribution N(0,I_n), the optimal value of NPP is \Theta(2^{-n}) w.h.p.; whereas the best polynomial-time algorithm achieves the objective value of only 2^{-\Theta(\log^2 n)}, w.h.p.

In this work, we initiate the study of the nature of this gap for the NPP. Inspired by insights from statistical physics, we study the landscape of the NPP and establish the presence of the Overlap Gap Property (OGP), an intricate geometric property which is known to be a rigorous evidence of an algorithmic hardness for large classes of algorithms. By leveraging the OGP, we establish that (a) any sufficiently stable algorithm, appropriately defined, fails to find a near-optimal solution with energy below 2^{-\omega(n \log^{-1⁄5} n)}; and (b) a very natural Markov Chain Monte Carlo dynamics fails for find near-optimal solutions.

OGP regards the overlap structure of m-tuples of solutions achieving a certain objective value. When m is constant, we prove the presence of OGP for the objective values of order 2^{-\Theta(n)}, and the absence of it in the regime 2^{-o(n)}. Interestingly, though, by considering overlaps with growing values of m we prove the presence of the OGP up to the level 2^{-\omega(\sqrt{n\log n})}. Our proof of the failure of stable algorithms at values 2^{-\omega(n \log^{-1⁄5} n)} employs methods from Ramsey Theory from the extremal combinatorics and is of independent interest.

Based on arXiv:2103.01369. Joint work with David Gamarnik.

Date and Time: 
Friday, January 21, 2022 - 2:00pm

ISL Colloquium: Optimization in Theory and Practice

Topic: 
Optimization in Theory and Practice
Abstract / Description: 

Join us for coffee and snacks at 3:30pm in the Grove outside Packard (near Bytes' outdoor seating). This week's speaker will join us via Zoom, which will be screened in Packard 101, and streamed for those unable to attend in person.


Complexity analysis in optimization seeks upper bounds on the amount of work required to find approximate solutions of problems in a given class with a given algorithm, and also lower bounds, usually in the form of a worst-case example from a given problem class. The relationship between theoretical complexity bounds and practical performance of algorithms on "typical" problems varies widely across problem and algorithm classes, and relative interest among researchers between the theoretical and practical aspects of algorithm design and analysis has waxed and waned over the years. This talk surveys complexity analysis and its relationship to practical algorithms in optimization, with an emphasis on linear programming and convex and nonconvex nonlinear optimization, providing historical (and cultural) perspectives on research in these areas.

Date and Time: 
Thursday, November 18, 2021 - 3:30pm
Venue: 
Packard Grove / Packard 101

IT-Forum: Differentially Private Covariance-adaptive Mean Estimation

Topic: 
Differentially Private Covariance-adaptive Mean Estimation
Abstract / Description: 

Mean estimation in Mahalanobis distance is a fundamental problem in statistics: given i.i.d. samples from a high-dimensional distribution with unknown mean and covariance, the goal is to find an estimator with small Mahalanobis distance from the true mean. To protect the privacy of the individuals who participate in the dataset, we study statistical estimators which satisfy differential privacy, a condition that has become a standard criterion for individual privacy in statistics and machine learning.


We present two differentially private mean estimators for multivariate (sub)Gaussian distributions with unknown covariance. All previous estimators with the same accuracy guarantee in Mahalanobis loss either require strong a priori bounds on the covariance matrix or require that the number of samples grows superlinearly with the dimension of the data, which is suboptimal. Our algorithms achieve nearly optimal sample complexity (matching that of the known-covariance case) by adapting the noise added due to privacy to the distribution's covariance matrix, without explicitly estimating it.
Joint work with Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman.

Date and Time: 
Friday, November 12, 2021 - 1:00pm

Safe and Efficient Reinforcement Learning for Power System Control

Topic: 
Safe and Efficient Reinforcement Learning for Power System Control
Abstract / Description: 
Inverter-based resources such as solar and storage provide us with more flexibility in the control of power systems. Through their power electronic interfaces, complex control functions can be implemented to quickly respond to changes in the system. Recently, reinforcement learning has emerged as a popular method to find these nonlinear controllers. The key challenge with a learning-based approach is that stability and safety constraints are difficult to enforce on the learned controllers. Using a Lyapunov theory-based approach, we show how to explicitly engineer the structure of neural network controllers such that they guarantee system stability. The resulting controllers only use local information and outperform conventional droop as well as strategies learned purely by using reinforcement learning.
Date and Time: 
Thursday, November 11, 2021 - 4:00pm
Venue: 
Packard 101

IT-Forum: Estimating and optimizing Information Measures using neural networks and its application in communication

Topic: 
Estimating and optimizing Information Measures using neural networks and its application in communication
Abstract / Description: 

In this talk we will develop a principled framework for neural estimation and optimization of information measures, which is then leveraged to estimate the feedforward and feedback capacities of general channels. To that end we propose a novel Directed Information Neural Estimator (DINE) that complements the Mutual Information Neural Estimation (MINE), and then develop methods for optimizing DINE and MINE over the channel input distributions. More specifically, two optimization methods are proposed, one for continuous channel input spaces and the other for discrete. While capacity estimation is the main application considered in this talk, we will discuss how the developed estimation and optimization techniques are applicable in additional scenarios where (maximized) Directed Information is of interest such as probability density estimation for processes with memory, causality identification and machine learning in general.

The talk is based on a joint work with Dor Tzur, Ziv Aharoni and Ziv Goldfeld.

Date and Time: 
Friday, November 5, 2021 - 1:00pm
Venue: 
Linvil Room, Allen Bldg.

ISL Colloquium: KO codes: Inventing Non-linear Encoding and Decoding for Reliable Wireless Communication via Deep-learning

Topic: 
KO codes: Inventing Non-linear Encoding and Decoding for Reliable Wireless Communication via Deep-learning
Abstract / Description: 

Landmark codes underpin reliable physical layer communication, e.g., Reed-Muller, BCH, Convolution, Turbo, LDPC and Polar codes: each is a linear code and represents a mathematical breakthrough. The impact on humanity is huge: each of these codes has been used in global wireless communication standards (satellite, WiFi, cellular). Traditionally, the design of codes has been driven by human-ingenuity and hence the progress is sporadic. Can we automate and accelerate this process of discovering codes?

In this talk, I will talk about KO codes, a new family of computationally efficient deep-learning driven codes that outperform the state-of-the-art reliability performance on the standardized AWGN channel. KO codes beat state-of-the-art Reed-Muller and Polar codes, under the low-complexity successive cancellation decoding, in the challenging short-to-medium block length regime on the AWGN channel. We show that the gains of KO codes are primarily due to the nonlinear mapping of information bits directly to transmit real symbols (bypassing modulation) and yet possess an efficient, high performance decoder. The key technical innovation that renders this possible is design of a novel family of neural architectures inspired by the computation tree of the Kronecker Operation (KO) central to Reed-Muller and Polar codes. These architectures pave way for the discovery of a much richer class of hitherto unexplored nonlinear algebraic structures. And more interestingly, despite having a lot of encoding and decoding structure, KO codes exhibit striking similarity to random Gaussian codes!


To avoid Zoom-bombing, we ask attendees to sign in via the above URL to receive the Zoom meeting details by email.

Please join us for a coffee half hour starting at 3:30pm at the Grove outside Packard.

Date and Time: 
Thursday, October 7, 2021 - 4:00pm
Venue: 
Packard 101 + Zoom (registration req'd)

ISL Colloquium: Sequential Decision Making: How Much Adaptivity Is Needed Anyways?

Topic: 
Sequential Decision Making: How Much Adaptivity Is Needed Anyways?
Abstract / Description: 

Adaptive stochastic optimization under partial observability is one of the fundamental challenges in artificial intelligence and machine learning with a wide range of applications, including active learning, optimal experimental design, interactive recommendations, viral marketing, Wikipedia link prediction, and perception in robotics, to name a few. In such problems, one needs to adaptively make a sequence of decisions while taking into account the stochastic observations collected in previous rounds. For instance, in active learning, the goal is to learn a classifier by carefully requesting as few labels as possible from a set of unlabeled data points. Similarly, in experimental design, a practitioner may conduct a series of tests in order to reach a conclusion. Even though it is possible to determine all the selections ahead of time before any observations take place (e.g., select all the data points at once or conduct all the medical tests simultaneously), so-called a priori selection, it is more efficient to consider a fully adaptive procedure that exploits the information obtained from past selections in order to make a new selection. In this talk, we introduce semi-adaptive policies, for a wide range of decision-making problems, that enjoy the power of fully sequential procedures while performing exponentially fewer adaptive rounds.

 

Note: This talk will be held in person in Packard 101, and has been pushed back to 4:45pm to accommodate the new class schedule.

The talk will be streamed on Zoom for those who cannot attend (registration required).


This talk is hosted by the ISL Colloquium. To receive talk announcements, subscribe to the mailing list isl-colloq@lists.stanford.edu.


Please join us for a coffee half hour starting at 4:15pm at the Bytes outdoor tables outside of Packard.

Date and Time: 
Thursday, September 30, 2021 - 4:45pm
Venue: 
Packard 101

IT-Forum: "Between tractable and intractable problems in reinforcement learning"

Topic: 
Between tractable and intractable problems in reinforcement learning
Abstract / Description: 

Markov decision processes (MDPs) capture some of the most important aspects of decision making under uncertainty and as such they are at the heart of many efforts to decision making under uncertainty. However, MDPs are "flat" with no structure and as such, planning and learning in MDPs with multidimensional state spaces, common in applications, is provably intractable. Yet, reinforcement learning methods have been quite successful in providing strong solutions to some of these seemingly intractable problems. In this talk I will present my view of how to think about these successes by presenting a framework where the key idea is to give algorithms hints that can create backdoors to crack otherwise intractable problems. The talk will then dive into categorizing hints based on whether they can indeed succeed at doing this for the special case when the hints are given in the form of constraints on how value functions look like in the context of planning with generative models, also known as simulation optimization. As we shall see, seemingly minor differences between hints can cause some hints to work, while others fail.

Date and Time: 
Thursday, June 10, 2021 - 4:30pm

IT-Forum: "The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions"

Topic: 
The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions
Abstract / Description: 

The Gittins scheduling policy minimizes the mean response in the single-server M/G/1 queue in a wide variety of settings. Most famously, Gittins is optimal when preemption is allowed and service requirements are unknown but drawn from a known distribution. Gittins is also optimal much more generally, adapting to any amount of available information and any preemption restrictions. However, scheduling to minimize mean response time in a multiserver setting, specifically the central-queue M/G/k, is a much more difficult problem.

In this work we give the first general analysis of Gittins in the M/G/k. Specifically, we show that under extremely general conditions, Gittins's mean response time in the M/G/k is at most its mean response time in the M/G/1 plus a term that grows logarithmically in the heavy-traffic limit, namely as the system load approaches capacity. A consequence of this result is that Gittins is optimal in the heavy-traffic M/G/k if the service requirement distribution has finite (2 + ε)th moment for any ε > 0. This is the most general result on minimizing mean response time in the M/G/k to date.

To prove our results, we combine properties of the Gittins policy and Palm calculus in a novel way. Notably, our technique overcomes the limitations of tagged job methods that were used in prior scheduling analyses.

Joint work with Isaac Grosof and Mor Harchol-Balter. Paper link: https://ziv.codes/publications/#the-gittins-policy-is-nearly-optimal-in-the-mgk-under-extremely-general-conditions

Date and Time: 
Friday, May 21, 2021 - 1:00pm to Saturday, May 22, 2021 - 12:55pm

Algorithms & Friends Seminar presents "Modeling the Heterogeneity in COVID-19’s Reproductive Number and Its Impact on Predictive Scenarios"

Topic: 
Modeling the Heterogeneity in COVID-19’s Reproductive Number and Its Impact on Predictive Scenarios
Abstract / Description: 

The correct evaluation of the reproductive number R for COVID-19 — which characterizes the average number of secondary cases generated by each typical primary case— is central in the quantification of the potential scope of the pandemic and the selection of an appropriate course of action. In most models, R is modelled as a universal constant for the virus across outbreak clusters and individuals— effectively averaging out the inherent variability of the transmission process due to varying individual contact rates, population densities, demographics, or temporal factors amongst many. Yet, due to the exponential nature of epidemic growth, the error due to this simplification can be rapidly amplified and lead to inaccurate predictions and/or risk evaluation. From the statistical modeling perspective, the magnitude of the impact of this averaging remains an open question: how can this intrinsic variability be percolated into epidemic models, and how can its impact on uncertainty quantification and predictive scenarios be better quantified? In this talk, we discuss a Bayesian perspective on this question, creating a bridge between the agent-based and compartmental approaches commonly used in the literature. After deriving a Bayesian model that captures at scale the heterogeneity of a population and environmental conditions, we simulate the spread of the epidemic as well as the impact of different social distancing strategies, and highlight the strong impact of this added variability on the reported results. We base our discussion on both synthetic experiments — thereby quantifying of the reliability and the magnitude of the effects — and real COVID-19 data.


 

Hosted by the Algorithms and Friends Seminar

Date and Time: 
Monday, April 5, 2021 - 12:00pm to Tuesday, April 6, 2021 - 11:55am

Pages

Subscribe to RSS - IT-Forum