Locality in network optimization

Journal article

In probability theory and statistics notions of correlation among random variables, decay of correlation, and biasvariance trade-off are fundamental. In this work we introduce analogous notions in optimization, and we show their usefulness in a concrete setting. We propose a general notion of correlation among variables in optimization procedures that is based on the sensitivity of optimal points upon (possibly finite) perturbations. We present a canonical instance in network optimization (the min-cost network flow problem) that exhibits locality, i.e., a setting where the correlation decays as a function of the graphtheoretical distance in the network. In the case of warm-start reoptimization, we develop a general approach to localize a given optimization routine in order to exploit locality. We show that the localization mechanism is responsible for introducing a bias in the original algorithm, and that the bias-variance trade-off that emerges can be exploited to minimize the computational complexity required to reach a prescribed level of error accuracy. We provide numerical evidence to support our claims.

Authors: Rebeschini, P; Tatikonda, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: IEEE
• Journal: IEEE Transactions on Control of Network Systems
• Volume: 6
• Issue: 2
• Pages: 487-500
• Publication date: 2018-06-01
• Acceptance date: 2018-05-05
• DOI: 10.1109/TCNS.2018.2843164
• ISSN: 2325-5870
• Keywords: Green’s function; decay of correlation; sensitivity of optimal points; Laplacian; network flow; bias-variance