April 8, 2014, 4:00pm
Rishabh Iyer, Department of Electrical Engineering, UW.
Submodular Combinatorial Problems in Machine Learning: Algorithms and Applications
Abstract: Having long been recognized in combinatorics, the concept of submodularity is becoming increasingly important in machine learning, since it can capture intuitive and yet nontrivial interactions between variables. This expressiveness has found many applications in machine learning, particularly in understanding structured data like text, vision and speech. Submodular functions naturally capture aspects of information, coverage and diversity in maximization problems, while also modeling notions of cooperation, sparsity, complexity and economies of scale in minimization problems. In this talk, we shall consider a large class of submodular optimization problems and motivate them with several real world applications, particularly in machine learning. We shall then provide a unifying algorithmic framework for solving several of these optimization problems, and highlight the scalability and practicality of this approach. We shall also highlight novel theoretical characterizations, which provide better connections between theory and practice. We shall ground this entire talk with a large number of applications in machine learning, including image segmentation, image correspondence, image collection summarization, feature selection, and data subset selection. This talk should be self contained and shall not require prior knowledge of submodular functions and optimization.
This is based on joint work with Jeff Bilmes, Stefanie Jegelka, Sebastian Tschiatschek and Kai Wei.
February 25, 2014, 4:00pm
Marina Meila, Department of Statistics, UW.
Optimization for Ordered Data
This talk is concerned with summarizing — by means of statistical models — of data that expresses preferences. This data is typically a set of rankings of n items by a panel of experts; the simplest summary is the “consensus ranking”, or the “centroid” of the set of rankings.
I will describe how combinatorics, algorithms and statistics come together in this endeavor. At the center of the results is the _code_ of a permutation. This natural mathematical way to represent a permutation is key both to fast computing and to better understanding the models we create. The models have permutations _as parameters_ and fitting them to data leads to combinatorial optimization problems which are often NP-hard. The talk will introduce a class of algorithms to attack these problems, that are exact but intractable in the worst case, and will demonstrate that they are effective on real-world examples.
Joint work with Alnur Ali, Raman Arora, Le Bao, Jeff Bilmes, Harr Chen, Bhushan Mandhani, Chris Meek, Brendan Murphy, Kapil Phadnis, Arthur Patterson.
February 11, 2014, 4:00pm
Mario Micheli, Department of Mathematics, UW.
An Optimization Approach for Image Recovery Through Optical Turbulence
Abstract: The phenomenon that is commonly referred to as optical “turbulence” in imaging is caused by the time and space-varying refraction index of the air which is due, among other factors, to temperature, air pressure, humidity, and wind conditions between the acquired scene and the image-capturing device. The above described distortion may be modeled, at least to a first approximation, as the combination of a blurring effect and a time-dependent deformation of the image domain. After briefly introducing the mathematical modeling of images and video, in this talk I shall describe an algorithm that corrects for the geometric deformation and the blur that affect the images. Both the estimation of the image deformations and the deblurring algorithm are formulated as optimization problems, to be solved with variational techniques. Results from several experiments will be shown.
January 21, 2014, 4:00pm
Mary Beth Hribar, Microsoft.
Adventures in the Unknown; My Career in Industry after an Optimization Dissertation
Abstract: Like most everyone else I knew in graduate school at Northwestern University, I had planned to have a career in academia after receiving a Ph.D. My advisor had prepared me for a career in research and in teaching. After graduation, I completed a post doc position at Rice University. I then had an offer to join a computer science department at a college in Michigan. Life was going as I had planned, but I found that I no longer wanted that plan. So, I rejected the offer from the small college and began an unknown career path in industry which has suited me well. Through the years, I have worked on a varied set of challenging projects spanning parallel linear algebra libraries, a new parallel programming language, user interfaces and data science. In this informal talk and discussion, I will share my experiences and learning what it takes to succeed in industry with a computational mathematics background.
Biosketch: Mary Beth Hribar received her Ph.D. from Northwestern University, completing a dissertation on an interior point algorithm for nonlinear programming. The KNITRO optimization software is based on this algorithm. She has spent most of her career developing numerical software and currently works as a data scientist at Microsoft.
March 18, 2014, 4:00pm
Dvijotham Krishnamurthy, Department of Computer Science and Engineering, UW.
Convex Formulations of Controller Synthesis
Abstract: Control of dynamical systems is a hard and nonconvex problem in general. I will discuss alternate but reasonable formulations of general control problems that lead to convex optimization problems. The formulations we work with are fairly general and cover problems ranging from training neural networks to decentralized control. I’ll also present numerical examples validating our approach and comparing it to alternate (nonconvex) approaches for controller synthesis.
January 28, 2014, 4:00pm
Samet Oymak, Department of Electrical Engineering, Caltech.
A general theory of noisy linear inverse problems
Abstract: We consider the problem of estimating an unknown signal x_0 from noisy linear observations y = Ax_0 + z. In many practical instances of this problem, x_0 has a low-dimensional representation that can be captured by a structure inducing function f(). For example, L1 norm can be used to encourage a sparse solution. To estimate x_0 with the aid of a convex f(), we consider variations of the widely used Lasso estimator and provide sharp characterizations of their performances. Our study falls under a generic framework, where the entries of the measurement (design) matrix A are i.i.d. Gaussian. For the Lasso estimator x*, we ask: “What is the precise estimation error as a function of the noise level, the number of available observations and the structure of the signal?”. We show that, the structure of the signal x_0 and choice of the function f() enter the error formulae through parameters arising from the convex geometry of the problem, in particular, the subdifferential of f() at x_0. We also find explicit formulae for the optimal estimation performance and the optimal penalty parameters. Our results can be seen as a generalization of the classically known results for the least-squares method.
Joint work with Christos Thrampoulidis and Babak Hassibi