
This paper investigates the behavior of the MinSum message passing scheme to
solve systems of linear equations in the Laplacian matrices of graphs and to
compute electric flows. Voltage and flow problems involve the minimization of
quadratic functions and are fundamental primitives that arise in several
domains. Algorithms that have been proposed are typically centralized and
involve multiple graphtheoretic constructions or sampling mechanisms that make
them difficult to implement and analyze. On the other hand, message passing
routines are distributed, simple, and easy to implement. In this paper we
establish a framework to analyze MinSum to solve voltage and flow problems. We
characterize the error committed by the algorithm on general weighted graphs in
terms of hitting times of random walks defined on the computation trees that
support the operations of the algorithms with time. For $d$regular graphs with
equal weights, we show that the convergence of the algorithms is controlled by
the total variation distance between the distributions of nonbacktracking
random walks defined on the original graph that start from neighboring nodes.
The framework that we introduce extends the analysis of MinSum to settings
where the contraction arguments previously considered in the literature (based
on the assumption of walk summability or scaled diagonal dominance) can not be
used, possibly in the presence of constraints.

In probability theory and statistics notions of correlation among random
variables, decay of correlation, and biasvariance tradeoff 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 mincost 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 warmstart
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
biasvariance tradeoff 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.

We apply the MinSum messagepassing protocol to solve the consensus problem
in distributed optimization. We show that while the ordinary MinSum algorithm
does not converge, a modified version of it known as Splitting yields
convergence to the problem solution. We prove that a proper choice of the
tuning parameters allows MinSum Splitting to yield subdiffusive accelerated
convergence rates, matching the rates obtained by shiftregister methods. The
acceleration scheme embodied by MinSum Splitting for the consensus problem
bears similarities with lifted Markov chains techniques and with multistep
first order methods in convex optimization.

We investigate the fundamental principles that drive the development of
scalable algorithms for network optimization. Despite the significant amount of
work on parallel and decentralized algorithms in the optimization community,
the methods that have been proposed typically rely on strict separability
assumptions for objective function and constraints. Beside sparsity, these
methods typically do not exploit the strength of the interaction between
variables in the system. We propose a notion of correlation in constrained
optimization that is based on the sensitivity of the optimal solution upon
perturbations of the constraints. We develop a general theory of sensitivity of
optimizers the extends beyond the infinitesimal setting. We present instances
in network optimization where the correlation decays exponentially fast with
respect to the natural distance in the network, and we design algorithms that
can exploit this decay to yield dimensionfree optimization. Our results are
the first of their kind, and open new possibilities in the theory of local
algorithms.

The discovery of particle filtering methods has enabled the use of nonlinear
filtering in a wide array of applications. Unfortunately, the approximation
error of particle filters typically grows exponentially in the dimension of the
underlying model. This phenomenon has rendered particle filters of limited use
in complex data assimilation problems. In this paper, we argue that it is often
possible, at least in principle, to develop local particle filtering algorithms
whose approximation error is dimensionfree. The key to such developments is
the decay of correlations property, which is a spatial counterpart of the much
better understood stability property of nonlinear filters. For the simplest
possible algorithm of this type, our results provide under suitable assumptions
an approximation error bound that is uniform both in time and in the model
dimension. More broadly, our results provide a framework for the investigation
of filtering problems and algorithms in high dimension.

We investigate the systematic mechanism for designing fast mixing Markov
chain Monte Carlo algorithms to sample from discrete point processes under the
Dobrushin uniqueness condition for Gibbs measures. Discrete point processes are
defined as probability distributions $\mu(S)\propto \exp(\beta f(S))$ over all
subsets $S\in 2^V$ of a finite set $V$ through a bounded set function
$f:2^V\rightarrow \mathbb{R}$ and a parameter $\beta>0$. A subclass of discrete
point processes characterized by submodular functions (which include
logsubmodular distributions, submodular point processes, and determinantal
point processes) has recently gained a lot of interest in machine learning and
shown to be effective for modeling diversity and coverage. We show that if the
set function (not necessarily submodular) displays a natural notion of decay of
correlation, then, for $\beta$ small enough, it is possible to design fast
mixing Markov chain Monte Carlo methods that yield error bounds on marginal
approximations that do not depend on the size of the set $V$. The sufficient
conditions that we derive involve a control on the (discrete) Hessian of set
functions, a quantity that has not been previously considered in the
literature. We specialize our results for submodular functions, and we discuss
canonical examples where the Hessian can be easily controlled.

It has been established under very general conditions that the ergodic
properties of Markov processes are inherited by their conditional distributions
given partial information. While the existing theory provides a rather complete
picture of classical filtering models, many infinitedimensional problems are
outside its scope. Far from being a technical issue, the infinitedimensional
setting gives rise to surprising phenomena and new questions in filtering
theory. The aim of this paper is to discuss some elementary examples,
conjectures, and general theory that arise in this setting, and to highlight
connections with problems in statistical mechanics and ergodic theory. In
particular, we exhibit a simple example of a uniformly ergodic model in which
ergodicity of the filter undergoes a phase transition, and we develop some
qualitative understanding as to when such phenomena can and cannot occur. We
also discuss closely related problems in the setting of conditional Markov
random fields.

The Dobrushin comparison theorem is a powerful tool to bound the difference
between the marginals of highdimensional probability distributions in terms of
their local specifications. Originally introduced to prove uniqueness and decay
of correlations of Gibbs measures, it has been widely used in statistical
mechanics as well as in the analysis of algorithms on random fields and
interacting Markov chains. However, the classical comparison theorem requires
validity of the Dobrushin uniqueness criterion, essentially restricting its
applicability in most models to a small subset of the natural parameter space.
In this paper we develop generalized Dobrushin comparison theorems in terms of
influences between blocks of sites, in the spirit of DobrushinShlosman and
Weitz, that substantially extend the range of applicability of the classical
comparison theorem. Our proofs are based on the analysis of an associated
family of Markov chains. We develop in detail an application of our main
results to the analysis of sequential Monte Carlo algorithms for filtering in
high dimension.