Schedule - UTA 7.532 - Tuesday, 3:30pm

Date                Title                                                                                                                                 Speaker                                        Notes
07.16.2015     "A simpler sublinear algorithm for approximating the triangle count"                     Karthikeyan Shanmugam          [.pdf]
07.23.2015     "Stay on path: PCA on graph paths"                                                                             Tasos Kyrillidis                             [.pdf]
08.06.2015     "Asymptotically tight steady-state queue length bounds ... "                                       Subhashini Krishnasamy        [.pdf]
08.13.2015     "Similarity search in high dimensions via hashing"                                                      Erik Lindgren                           [.pdf]

08.20.2015     "Perturbed iterate analysis for asynchronous stochastic optimization"                     Shanshan Wu                          [.pdf]
08.27.2015      "Telling cause from effect in deterministic linear dynamical systems"                     Murat Kocaoglu                        [.pdf]
09.03.2015     "A nearly-linear time framework for graph-structured sparsity"                                Suriya Gunasekar                     [.pdf]
09.10.2015      "Scalable large near-clique detection in large-scale networks via sampling"          Ethan Elenberg                        [.pdf]
09.17.2015      "A new sampling technique for tensors"                                                                      Srinadh Bhojanapalli           [.pdf]
09.24.2015      "A brief history of stochastic multi-armed bandits"                                                    Rajat Sen                              [.pdf]
Abstract
In this talk we will discuss some of the most important results in the context of the stochastic Multi-Armed Bandit(MAB) problem. Multi Armed Bandit problems have huge practical significance and a rich theoretical history which dates back to the seminal paper by Lai and Robbins from 1985, in which they characterize the regret lower-bounds for a wide class of policies. These lower bounds were later generalized to a larger class of policies by Salomon et. al.  However, the proof of these lower bounds may seem mysterious and involve a delicate change of measure argument. In this talk we will see a relatively less known lower bound proof which uses results from the hypothesis testing literature. After establishing the lower bounds, we will discuss the well-known UCB strategies which achieve regret close to the lower-bounds.  We will also go over some techniques to establish high probability bounds on regret for such UCB strategies. This merely scratches the surface of the MAB literature, therefore we will have another talk in this series which will delve into more recent developments in the realm of bandit problems.

10.22.2015      "Hardness of low delay network scheduling"                                                               Soumya Basu                     [.pdf]
10.29.2015      "Large-scale collaborative ranking from pairwise comparisons"                               Dohyung Park                   [.pdf]

11.12.2015      "Low-density parity constraints for hashing based discrete integration"                     Megas Asteris                   [.pdf]

11.19.2015      "Accelerating SGD using predictive variance reduction"                                                Louie Wu                          [.pdf]
06.28.2016      "Convex Optimization without Projection Steps"                                                            Erik Lindgren                   [.pdf]

07.05.2016                                                                                                                                                  Abishek Sankararaman
07.12.2016                                                                                                                                                  Shanshan Wu