Main navigation | Main content
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, 2011On 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).
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)
Connect With Us: |