Random Structures Fall 2013

Friday, 2:00PM-3.30PM, RLM 8.136

Organizers: Francois Baccelli and Ngoc Tran

This is a weekly working group at the Department of Mathematics at UT Austin. It is opened to anybody who is interested in topics around the theme of random structures, such as networks, spatial processes, random graphs, random combinatorial objects, with applications in operations research, machine learning and computer science.

DATE SPEAKER TITLE (click for abstract below)
September 13th Mir Omid Mirsadegi Point-Shift and Palm Probabilities
September 27th Ngoc Mai Tran Exponential Robust Binary Storage in Little-Hopfield Networks
October 4th Anup Biswas Control of a queuing system under the moderate deviation scaling
November 1st Mingyuan Zhou Count-Mixture Modeling and Exchangeable Random Partitions
November 8th Rachel Ward Stochastic Gradient Descent with Importance Sampling
November 15th Pradeep Ravikumar Poisson Graphical Models
November 22nd Dhandapani Yogeshwaran Understanding the Topology of the Boolean Model

Title and Abstracts

Point-Shift and Palm Probabilities

Mir Omid Mirsadegi
Department of Mathematics, Sharif University

A point-shift maps, in a translation invariant way, each point of a stationary point process to some point of this process. The problem addressed in this paper is that of the existence of probability measures, defined on the space of counting measures with an atom at the origin, which are left invariant by a given point-shift.
Assume that this point-shift is continuous with respect to the vague topology. Then, when it exists, the point-shift probability of a stationary point-process,which is introduced in the present paper, provides a solution to this problem. The notion of point-shift probability is shown to be a strict generalization of that of Palm probability: if there is no evaporation, i.e. when the image of the point process $\Phi$ by the $n$-th iterate of the point-shift tends to a point process with positive intensity for $n$ tending to infinity, then the point-shift probability of $\Phi$ exists and coincides with the law of $\Phi$ under the Palm probability of some compatible thinning $\Psi$ of $\Phi$; in the case with evaporation, the paper presents examples where the point-shift probability of $\Phi$ exists but cannot be the law of $\Phi$ under the Palm probability of any point process $\Psi$, jointly stationary with $\Phi$.
The paper also gives a criterium of existence of the point-shift probability of a stationary point process and discusses uniqueness issues.
Joint work with F. Baccelli.

Exponential Robust Binary Storage in Little-Hopfield Networks

Ngoc Mai Tran
Department of Mathematics, UT Austin

Hopfield networks are models of neural memory storage and retrieval which can have exponential capacity relative to the number of neurons. However, known algorithms have produced networks with linear capacity, and it has been a long-standing open problem whether robust exponential storage is possible. For a network with $n$ neurons, the problem involves a linear program in $n^2$ variables and exponentially many constraints. We utilized the action of the symmetric group on the neuron labels and successfully reduced the problem to a linear program in three variables and three constraints. We then explicitly constructed simple networks that answer the question affirmatively, with the best possible asymptotic robustness index. This work calls for further research into Hopfield networks and their applications to theoretical neuroscience and computer science.

Joint work with Christopher Hillar and Kilian Koepsell.

Control of a queuing system under the moderate deviation scaling

Anup Biswas
Department of Electrical and Computer Engineering, UT Austin

Abstract: In recent days, exponential type cost structure has become popular in control theory. In this talk we formulate and discuss a risk- sensitive type control problem for a multi-class queuing system under the moderate deviation scaling. It is known that the rate function corresponding to the moderate deviation scaling is of Gaussian type. This property of the rate function is often useful for mathematical analysis. We show that the limiting game corresponding to our control problem is solvable. Also the limiting game has a similarity to the well-studied Brownian control problems. This problem is also related to a conjecture of Damon Wischik (2001). The main difficulty in working with G/G/1 queuing network is that the underlying state dynamics is not Markov. Markov property is proven useful for these type of problems (see e.g., Atar-Goswami-Shwartz(2012)). The standard way to solve these problems is to look at the pde associated with the state dynamics and sandwich the limiting value between the upper and lower value of the game. This technique does not work when the state dynamics is not Markov. We will see that the special structure of the rate function and moderate deviation settings will be helpful to overcome such difficulties. Extension to many- server models will also be discussed.

Part of this talk is a joint work with Prof. Rami Atar, Technion.

Count-Mixture Modeling and Exchangeable Random Partitions

Mingyuan Zhou
IROM, McComb School of Business, UT Austin

Abstract: The construction of exchangeable partition probability functions (EPPFs) is an important research topic in both combinatorics and Bayesian nonparametrics. Previous research usually follows Kingman's theory of partition structures to impose sampling consistency, requiring the probability distribution of exchangeable random partitions of a subset of the sample to be independent of the sample size. In this talk, I will use completely random measures to construct a family of EPPFs under the count-mixture modeling framework. An EPPF constructed in this way is not necessarily consistent, but still maintains a simple prediction rule that can be used to develop collapsed Gibbs sampling. I will introduce the generalized Chinese restaurant process as an example, and for the first time demonstrate how to sequentially construct exchangeable random partitions that violate sampling consistency.

Stochastic Gradient Descent with Importance Sampling

Rachel Ward
Department of Mathematics, UT Austin

Stochastic Gradient Descent is a method for minimizing a convex objective based on access to unbiased stochastic gradient estimates. It has recently received renewed attention for confronting very large scale problems, especially in the context of machine learning. In this talk we consider SGD with importance sampling, and show that by perturbing the uniform row selection rule in the direction of sampling estimates proportionally to the Lipschitz constant of their gradients, the convergence rate of SG can be improved dramatically from depending on the average squared condition number to depending on the average (unsquared) condition number of the system.

Poisson Graphical Models

Pradeep Ravikumar
Department of Computer Science, UT Austin

Abstract: Undirected graphical models, such as Gaussian graphical models, Ising, and multinomial/categorical graphical models, are widely used in a variety of applications for modeling distributions over a large number of variables. These standard instances, however, are ill-suited to modeling count data, which are increasingly ubiquitous in big-data settings such as genomic sequencing data, user-ratings data, spatial incidence data, climate studies, and site visits. Existing classes of Poisson graphical models, which arise as the joint distributions that correspond to Poisson distributed node-conditional distributions, have a major drawback: they can only model negative conditional dependencies for reasons of normalizability given its infinite domain.

We consider the task of modifying the Poisson graphical model distribution so that it can capture a rich dependence structure between count-valued variables. We begin by discussing two strategies for truncating the Poisson distribution and show that only one of these leads to a valid joint distribution; even this model, however, has limitations on the types of variables and dependencies that may be modeled. To address this, we propose two novel variants of the Poisson distribution and their corresponding joint graphical model distributions. These models provide a class of Poisson graphical models that can capture both positive and negative conditional dependencies between count-valued variables. One can learn the graph structure of our model via penalized neighborhood selection, and we demonstrate the performance of our methods by learning simulated networks as well as a network from microRNA-Sequencing data.

Joint work with Eunho Yang, Genevera Allen, Zhandong Liu.

Understanding the Topology of the Boolean Model

Dhandapani Yogeshwaran
Technion Israel Institute of Technology

In this talk, we shall look at the well-known Boolean model of stochastic geometry but from a algebraic topological perspective. The Boolean model is nothing but the union of balls centred at random points. In particular, i shall describe results about the growth of Betti numbers in the Boolean model for various point processes. The Betti numbers count the number of components, voids, cavities and so on and hence are useful quantitative descriptors of the topology. We shall focus on the dependence of the phase transitions for Betti numbers on the point process. Also, we shall see some examples where these differences can be quantified explicitly. Time permitting, we shall look into limit theorems for Betti numbers in various regimes as well as the proof techniques. For most of the talk, I shall not assume any knowledge of advanced topology or probability.