The IMA Postdoc Seminar meets at 11:15-12:15 every Tuesday during the semester in Keller Hall 3-180, except during IMA workshop weeks. This seminar provides opportunities for postdocs to give talks not necessarily related to the thematic program, and for invited IMA visitors (or U of MN faculty) to give talks on subjects of interest to the IMA postdocs. The Fall semester postdoc seminar is organized by Yulia Hristova < > September 20, 2011
Shiqian Ma (IMA Postdoc)

Alternating Direction Methods for Sparse and Low-Rank Optimization

Abstract: In this talk, we show how alternating direction methods are used recently in sparse and low-rank optimization problems. We also show the iteration complexity bounds for two specific types of alternating direction methods, namely alternating linearizaton and multiple splitting methods. We prove that the basic versions of both methods require $O(1/eps)$ iterations to obtain an eps-optimal solution, and the accelerated versions of these methods require $O(1/\sqrt{eps})$ iterations, while the computational effort needed at each iteration is almost unchanged. To the best of our knowledge, these complexity results are the first ones of this type that have been given for splitting and alternating direction type methods. Numerical results on problems with millions of variables and constraints arising from computer vision, machine learning and image processing are reported to demonstrate the efficiency of the proposed methods.

October 4, 2011
Paolo Codenotti (IMA Postdoc)

On the Group Isomorphism Problem

Abstract: We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The $n^{\log n}$ bound on the time complexity for the general case has not been improved over the past four decades. We demonstrate that the obstacle to efficient algorithms is the presence of abelian normal subgroups; we show this by giving a polynomial-time isomomrphism test for "semisimple groups,'' defined as groups without abelian normal subgroups (joint work L. Babai, Y. Qiao, in preparation). This concludes a project started with with L. Babai, J. A. Grochow, Y. Qiao (SODA 2011). That paper gave an $n^{\log\log n}$ algorithm for this class, and gave polynomial-time algorithms assuming boundedness of certain parameters. The key ingredients for this algorithm are: (a) an algorithm to test permutational isomorphism of permutation groups in time polynomial in the order and simply exponential in the degree; (b) the introduction of the "twisted code equivalence problem," a generalization of the classical code equivalence problem (which asks whether two sets of strings over a finite alphabet are equivalent by permuting the coordinates), by admitting a group action on the alphabet; (c) an algorithm to test twisted code equivalence; (d) a reduction of semisimple group isomorphism to permutational isomorphism of transitive permutation groups under the given time limits via twisted code equivalence.

The twisted code equivalence problem and the problem of permutational isomorphism of permutation groups are of interest in their own right. In this talk I will give the definitions of the problems that make up the overall plan, show how they fit together, and then give some details on the algorithm to test permutational isomorphism of transitive groups.

This talk is based on joint work with: Laszlo Babai (University of Chicago), Joshua A. Grochow (University of Chicago) and Youming Qiao (Tsingua University).

October 11, 2011
Caroline Uhler (IMA Postdoc)

Geometry of maximum likelihood estimation in Gaussian graphical models

Abstract: We study maximum likelihood estimation in Gaussian graphical models from a geometric point of view. In current applications of statistics, we are often faced with problems involving a large number of random variables, but only a small number of observations. An algebraic elimination criterion allows us to find exact lower bounds on the number of observations needed to ensure that the maximum likelihood estimator exists with probability one. This is applied to bipartite graphs and grids, leading to the first instance of a graph for which the maximum likelihood estimator exists with probability one even when the number of observations equals the treewidth of the graph.

October 18, 2011
Divyanshu Vats (IMA Postdoc)

Necessary Conditions for Set-Based Graphical Model Selection

Abstract: Graphical model selection, where the goal is to estimate the graph underlying a distribution, is known to be computationally intractable in general. An important issue is to study theoretical limits on the performance of graphical model selection algorithms. In particular, given parameters of the underlying distribution, we want to find a lower bound on the number of samples required for accurate graph estimation. When deriving these theoretical bounds, it is common to treat the learning problem as a communication problem where the observations correspond to noisy messages and the decoding problem infers the graph from the observations. Current analysis of graphical model selection algorithms is limited to studying graph estimators that output a unique graph. In this paper, we consider graph estimators that output a set of graphs, leading to set-based graphical model selection (SB-GMS). This has connections to list-decoding where a decoder outputs a list of possible codewords instead of a single codeword. Our main contribution is to derive necessary conditions for accurate SB-GMS for various classes of graphical models and show reduction in the number of samples required for consistent estimation. Further, we derive necessary conditions on the cardinality of the set-based estimates given graph parameters.

November 1, 2011
Gabriela Martinez (IMA Postdoc)

Regularization Methods for Probabilistic Optimization

Abstract: We analyze nonlinear stochastic optimization problems with joint probabilistic constraints using the concept of a $p$-efficient point of a probability distribution. If the problem is described by convex functions, we develop two algorithms based on first order optimality conditions and a dual approach to the problem. The algorithms yield an optimal solution for problems involving $\alpha$-concave probability distributions. For arbitrary distributions, the algorithms provide upper and lower bounds for the optimal value and nearly optimal solutions. When the problem is described by continuously differentiable non-convex functions, we describe the tangent and the normal cone to the level set of the underlying probability function. Furthermore, we formulate first order and second order conditions of optimality based on the notion of $p$-efficient points. For the case of discrete distribution functions, we developed an augmented Lagrangian method based on progressive inner approximation of the level set of the probability function by generation of $p$-efficient points. Numerical experience is provided.

November 8, 2011
Brendan Ames (IMA Postdoc)

November 22, 2011
Xin Liu (IMA Postdoc)

November 29, 2011
Arthur Szlam (IMA Postdoc)

December 6, 2011
Teng Zhang (IMA Postdoc)