Stanford Theory Seminar (formerly known as Stanford Algorithms Seminar/AFLB) is usually held in Gates 498 or Theory Lounge(Gates 463A)

Faculty Contact: Mary Wootters

Student Contact: Shashwat Silas

Click here for directions.

We study the A-optimal design problem, in which we are given n rank-1 d-by-d positive semidefinite (PSD) matrices, and an integer k, and our goal is to find a set S of k matrices, so that the trace of the inverse of the sum of the matrices in S is minimized. This problem is one variant of the optimal experimental design problem in statistics, where each rank-1 matrix corresponds to a noisy linear measurement of an unknown vector, and the goal is to pick k measurements to take, so as to minimize the average variance of the error of the maximum likelihood estimator of the unknown vector. The problem also finds applications in sensor placement in wireless networks, sparse least squares regression, feature selection for k-means clustering, and low-rank matrix approximation. We introduce proportional volume sampling to obtain improved approximation algorithms for A-optimal design.

In traditional volume sampling we pick a subset of k (rank-1 PSD) matrices with probability proportional to the determinant of their sum. In proportional volume sampling this probability distribution is modified by multiplying the probability of each size k subset S by the probability mu(S) assigned to S by another probability distribution mu. In order to obtain improved approximation algorithms for the A-optimal design problem, we appeal to hard-core distributions mu based on the solution of a convex relaxation of the problem. Our results include a d-approximation when k=d, and a (1+epsilon)-approximation when k is on the order of (d/epsilon) + log(1/epsilon)/epsilon^2. When we are allowed repetitions of the selected rank-1 matrices, we achieve a k/(k-d+1)-approximation, which matches the integrality gap of the natural convex relaxation of the problem. We also show that our results cannot be extended to the related E-optimal design problem in which we maximize the minimum eigenvalue of the sum of selected matrices. In particular, we show that for E-optimal design the integrality gap of the natural convex relaxation is at least 1-epsilon for k as large as d/epsilon^2. We also derive generalizations of the problem to selecting fewer than d matrices, and consider an application to restricted invertibility principles.

Joint work with Mohit Singh and Uthaipon Tao Tantipongpipat

Traditional multi-armed bandit models posit that the payoff distribution of each action (or "arm") is stationary over time, and hence that the goal of learning is to identify the arm with the highest expected payoff and choose that one forever after. However, in many applications the efficacy of an action depends on the amount of time that has elapsed since it was last performed. Examples arise in precision agriculture, online education, and music recommendations. In this talk we introduce a generalization of the multi-armed bandit problem that models such applications. In the course of analyzing algorithms for this problem, we will encounter some interesting combinatorial questions about coloring the integers subject to bounds on the sizes of subintervals that exclude a given color.

This talk is based on joint work with Nicole Immorlica.

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem. This is joint work with Ola Svensson and László Végh.

Dimensionality reduction in Euclidean space, as attainable by the Johnson-Lindenstrauss lemma, has been a fundamental tool in algorithm design and machine learning. The JL lemma states that any n point subset of l_2 can be mapped to l_2^m with distortion 1+epsilon, where m = O((log n) / epsilon^2). In this talk, I discuss our recent proof that the JL lemma is optimal, in the sense that for any n, d, epsilon, where epsilon is not too small, there is a point set X in l_2^d such that any f:X->l_2^m with 1+epsilon must have m = Omega(epsilon^{-2} log n). I will also discuss some subsequent work and future directions.

Joint work with Kasper Green Larsen (Aarhus University).

No theory seminar today, instead go to the...

Thanks to major advances in neuroscience, we are on the brink of a scientific understanding of how the brain achieves consciousness. This talk will describe neuroscientist Bernard Baars's Global Workspace Model (GWM) of the brain and propose a formal Turing-Machine-like computational model inspired by it for understanding consciousness. One of several consequences of this Model is the possibility of free will in a completely deterministic world. Another deals with the possibility of building machines that are conscious.

More info about the Motwani Colloquium is available here

We study the general problem of testing whether an unknown discrete probability distribution belongs to a specified family of distributions. More specifically, given a distribution family $\mathcal{P}$ and sample access to an unknown discrete distribution $p$, we want to distinguish (with high probability) between the case that $p$ is in $\mathcal{P}$ and the case that $p$ is eps-far, in total variation distance, from every distribution in $\mathcal{P}$. This is the archetypal hypothesis testing problem that has received significant attention in statistics and, over the past decade and roughly a half, in theoretical computer science.

Of course, the sample complexity of this general inference task depends on the underlying family $\mathcal{P}$. The gold standard in distribution testing is to design sample-optimal and computationally efficient algorithms for this task, as a function of $\mathcal{P}$. The main contribution of this work is a simple and general testing technique that is applicable to /all/ distribution families, and is particularly suited to those whose /Fourier spectrum/ satisfies a certain approximate /sparsity/ property. To the best of our knowledge, ours is the first use of the Fourier transform in the context of distribution testing.

We apply our Fourier-based framework to obtain near sample-optimal and computationally efficient testers for the following fundamental distribution families: Sums of Independent Integer Random Variables (SIIRVs), Poisson Multinomial Distributions (PMDs), and Discrete Log-Concave Distributions. For the first two, ours are the first non-trivial testers in the literature, vastly generalizing previous work on testing Poisson Binomial Distributions. For the third, our tester improves on prior work in both sample and time complexity.

Joint work with Ilias Diakonikolas (USC) and Alistair Stwart (USC).

A de-Morgan formula over Boolean variables x_1, ..., x_n is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that some explicit function (in P or NP) requires large formulas is a central open question in computational complexity.

In this work, we introduce a size-amplification hardness reduction for de-Morgan formulas. We show that average-case hardness implies worst-case hardness for a larger size. More precisely, if a function f cannot be computed correctly on more than 1/2 + eps of the inputs by any formula of size s, then computing f correctly on all inputs requires size ~s*log(1/eps). The tradeoff is essentially tight. Quite surprisingly, the proof relies on a result from quantum query complexity by Reichardt [SODA, 2011].

As an application, we improve the best known formula size lower bounds for explicit functions by logarithmic factors to ~n^3/log(n). In addition, we propose candidates for explicit functions that we believe have formula size ~n^4, and prove non trivial super-quadratic formula size lower bounds for them using our reduction. Learning discrete Markov Random Fields with nearly optimal runtime and sample complexity.

Our approach is new and uses a multiplicative-weight update algorithm. Our algorithm-- Sparsitron-- is easy to implement (has only one parameter) and holds in the online setting. It also gives the first provably efficient solution to the problem of learning sparse Generalized Linear Models (GLMs).

Joint work with Adam Klivans.

Joint work with Sushant Sachdeva.

The crucial techniques are about expanders: 1) an algorithm for decomposing a graph into a collection of expanders in near-linear time, and 2) an algorithm for "repairing" the expansion property of an expander after deleting some edges of it. These techniques can be of independent interest.

This talk is based on results by [Nanongkai, Saranurak and Wulff-Nilsen, FOCS'17], [Nanongkai and Saranurak, STOC'17] and [Wulff-Nilsen, STOC'17].

This talk is based on a joint-work with Shaddin Dughmi, Jason Hartline, and Bobby Kleinberg.