Georgia Institute of Technology College of Sciences

We consider the problem of estimating the factors of a rank-1 matrix with i.i.d. Gaussian, rank-1 measurements that are nonlinearly transformed and corrupted by noise. Considering two prototypical choices for the nonlinearity, we study the convergence properties of a natural alternating update rule for this nonconvex optimization problem starting from a random initialization. We show sharp convergence guarantees for a sample-split version of the algorithm by deriving a deterministic recursion that is accurate even in high-dimensional problems. Our sharp, non-asymptotic analysis also exposes several other fine-grained properties of this problem, including how the nonlinearity and noise level affect convergence behavior.

On a technical level, our results are enabled by showing that the empirical error recursion can be predicted by our deterministic sequence within fluctuations of the order n−1/2 when each iteration is run with n observations. Our technique leverages leave-one-out tools originating in the literature on high-dimensional M–estimation and provides an avenue for sharply analyzing higher-order iterative algorithms from a random initialization in other high-dimensional optimization problems with random data.

We give a polynomial-time algorithm for online covering IPs with a competitive ratio of O(\log mn) when the constraints are revealed in random order, essentially matching the best possible offline bound of \Omega(\log n) and circumventing the \Omega(\log m \log n) lower bound known in adversarial order. We then leverage this O(\log mn)-competitive algorithm to solve this problem in the prophet setting, where constraints are sampled from a sequence of known distributions. Our reduction in fact relies only on samples from these distributions, in a manner evocative of prior work on single-sample prophet inequalities for online packing problems. We present sample guarantees in the prophet setting, as well as in the setting where random samples from an adversarial instance are revealed at the outset.

This talk is based on joint work with Anupam Gupta and Roie Levin, part of which appeared at FOCS 2021. 

Assemblies are subsets of neurons whose coordinated excitation is hypothesized to represent the subject's thinking of an object, idea, episode, or word. Consequently, they provide a promising basis for a theory of how neurons and synapses give rise to higher-level cognitive phenomena. The existence (and pivotal role) of assemblies was first proposed by Hebb, and has since been experimentally confirmed, as well as rigorously proven to emerge in the model of computation in the brain recently developed by Papadimitriou & Vempala. In light of contemporary studies which have documented the creation and activation of sequences of assemblies of neurons following training on tasks with sequential decisions, we study here the brain's mechanisms for working with sequences in the assemblies model of Papadimitriou & Vempala.  We show that (1) repeated presentation of a sequence of stimuli leads to the creation of a sequence of corresponding assemblies -- upon future presentation of any contiguous sub-sequence of stimuli, the corresponding assemblies are activated and continue until the end of the sequence; (2) when the stimulus sequence is projected to two brain areas in a "scaffold", both memorization and recall are more efficient, giving rigorous backing to the cognitive phenomenon that memorization and recall are easier with scaffolded memories; and (3) existing assemblies can be quite easily linked to simulate an arbitrary finite state machine (FSM), thereby capturing the brain's ability to memorize algorithms. This also makes the assemblies model capable of arbitrary computation simply in response to presentation of a suitable stimulus sequence, without explicit control commands. These findings provide a rigorous, theoretical explanation at the neuronal level of complex phenomena such as sequence memorization in rats and algorithm learning in humans, as well as a concrete hypothesis as to how the brain's remarkable computing and learning abilities could be realized.

Joint work with Christos Papadimitriou and Santosh Vempala.

We consider a service system where incoming tasks are instantaneously assigned to one out of many heterogeneous server pools. All the tasks sharing a server pool are executed in parallel and the execution times do not depend on the class of the server pool or the number of tasks currently contending for service. However, associated with each server pool is a utility function that does depend on the class of the server pool and the number of tasks currently sharing it. These features are characteristic of streaming and online gaming services, where the duration of tasks is mainly determined by the application but congestion can have a strong impact on the quality-of-service (e.g., video resolution and smoothness). We derive an upper bound for the mean overall utility in steady-state and introduce two load balancing policies that achieve this upper bound in a large-scale regime. Also, the transient and stationary behavior of these asymptotically optimal load balancing policies is characterized in the same large-scale regime.