Main navigation | Main content

HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program

PROGRAMS/ACTIVITIES

Annual Thematic Program »Postdoctoral Fellowships »Hot Topics and Special »Public Lectures »New Directions »PI Programs »Industrial Programs »Seminars »Be an Organizer »Annual »Hot Topics »PI Summer »PI Conference »Applying to Participate »

IMA Postdoc Seminar 2011-2012

11:15am – 12:15pm, Keller Hall 3-180

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

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.

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).

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 ﬁnd 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 ﬁrst 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)