CCSI/GMOS Student Seminar

Speaker 1: Dheeraj Nagaraj
Title 1: Learning Non-Linear Dynamical Systems near Optimally via Offline and Streaming Algorithms

Abstract 1: Learning from a single trajectory of Markov processes is important in Control Theory, Time Series Analysis and Reinforcement Learning. Most of the available works are either asymptotic or are no better than considering one in every mixing time samples and learning with i.i.d. data. Recent progress on non-asymptotic linear system identification has shown that the offline OLS estimator obtains near optimal estimation without the dependence on the mixing time. However, such methods fail in the presence of nonlinearities since we cannot obtain closed form expressions for the minimizer of the empirical loss.

In this talk, we will look at estimating generalized linear systems. By directly analyzing the iterates of the Quasi Newton method, we show similar bounds as linear systems, which do not depend on the mixing time in the most general settings. We then tackle the harder problem of streaming estimation by analyzing SGD with reverse experience replay (SGD-RER) and show that this too is nearly optimal with no mixing time dependence in the dominant error term.

Speaker 2: Tim Hsieh
Title 2: Certified counting and random constraint satisfaction problems

Abstract 2: A random 3SAT instance on n variables and Cn clauses is unsatisfiable with high probability once C is a large enough constant.  However, efficient algorithms to certify unsatisfiability of a random 3SAT instance are only known when C >> sqrt{n}.  Moreover, there are strong lower bounds against algorithms based on spectral and convex relaxation techniques when C << sqrt{n}, suggesting the possibility of an information-computation gap.  We investigate whether this information-computation gap prevails if we relax the algorithmic task a bit -- in particular instead of certifying that there are no satisfying assignments, we study the computational complexity of certifying an upper bound on the number of satisfying assignments for values of C << sqrt{n}.  In this talk, we will discuss the landscape of when this problem is algorithmically tractable and when there is evidence of intractability, along with some of the algorithmic ideas.

Based on joint work with Sidhanth Mohanty and Jeff Xu. https://arxiv.org/abs/2106.12710