[YPNG] YPNG 18 Sept 2015

[sekhar]

Hi Everyone,
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.

Regards,
sekhar