[YPNG] YPNG 18 Sept 2015
sekhar.tatikonda at yale.edu
Tue Sep 15 10:51:38 EDT 2015
At the next YPNG Patrick will talk about:
Title: Killed random walks and graph Laplacians: local sensitivity in
network flow problems.
Abstract: Consider the problem of minimizing a strongly convex function
f given the equality constraint Ax=b, where A is a full row rank matrix.
How does the unique solution of this problem x*(b) behave as a function
of the constraint vector b? In textbooks, results on the sensitivity
analysis for optimization procedures are only stated with respect to the
optimal objective function, i.e. f(x*(b)), not with respect to the point
where the optimum is attained, i.e., x*(b). In the context of network
flow problems we show that local perturbations made on b have an impact
on the components of x*(b) that decreases exponentially with an
underlying notion of distance. The rate of convergence is controlled by
the largest eigenvalue of a killed random walk naturally associated to
the problem, and it is connected to graph Laplacians. Our results can be
interpreted as the first manifestation of a decay of correlation
principle for (non-random) optimization procedures. We show how this
principle can be used to develop local algorithms and substantially
reduce the computational complexity of standard optimization procedures.
See you Friday at 11am in the Stat's classroom.
More information about the YPNG