Events - 2017

Title: Signal Recovery by Proximal Forward-Backward Splitting

Abstract:

We will be discussing the paper (bearing the same title) of Patrick Combettes and Valérie Wajs.  We show that various inverse problems in signal recovery can be formulated as the generic problem of minimizing the sum of two convex functions with certain regularity properties.

Title: Asymmetric Latin squares, Steiner triple systems, and 1-factorizations

Abstract:

We outline how the Van der Waerden permanent theorem can be used to show that almost all Latin squares, Steiner triple systems, and 1-factorizations of the complete graph admit only trivial automorphisms. 

Title: Efficient First-Order Methods for Linear Programming and Semidefinite Programming 

Abstract:

We will be discussing the paper (bearing the same title) of James Reneger.  We present a simple transformation of any linear program or semidefinite program into an equivalent convex optimization problem whose only constraints are linear equations. The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable.

Title: Ramsey theory for biased graphs

Abstract:

We discuss the unavoidable subgraphs of biased graphs whose underlying graph is a clique.

Title: Sum-of-Squares Proofs in Optimization

Abstract:

The old concept of sum-of-squares found its way into optimization and even machine learning. I will talk about this quickly evolving research area known as convex algebraic geometry.

Title: Recent Advances in Frank-Wolfe Optimization

Abstract:

The Frank-Wolfe (FW) optimization algorithm has lately re-gained popularity thanks in particular to its ability to nicely handle the structured constraints appearing in machine learning and signal processing applications. However, its convergence rate is known to be slow (sublinear) when the solution lies at the boundary.

Title: Convex drawings of complete graphs:  topology meets geometry

Abstract:

A drawing D of the complete graph K(n) is the sphere is characterized by, for each isomorph J of K(5), D[J] is homeomorphic to one of the three rectilinear drawings of K(5).  Every drawing of K(n) in the plane with all edges straight-line segments is obviously convex.  Thus, convex drawings generalize planar point sets that are in general position. 

Title: Coloring (cap even hole)-free graphs

Abstract:

An even cycle of length 4 or more is called an even hole. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this talk we consider (cap, even hole)-free graphs, i.e., graphs that do not contain any even hole or cap as an induced subgraph.

Title: An application of graph "recolouring”

Abstract:

I will prove that for any graph G, if there is an edge e such that G-e has less than (k-1)!/2 cycles of length zero mod k, then the chromatic number of G is less or equal to k.

Title: How we solve linear programs

Abstract:

Linear programming is one of the most fundamental tools in optimization, and its theoretical complexity is well understood. In practice though, things are quite different: Which types of problems can we really solve? What sizes? With what algorithms?

Title: A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

Abstract:

We will be discussing the paper (having the same title) by Roux, Schmidt, and Bach.  The authors propose a new stochastic gradient method for optimizing the sum of
 a finite set of smooth functions, where the sum is strongly convex.