Jonathan C. Mattingly

Daryl R. DeFord, Gregory Herschlag, Jonathan C. Mattingly

We introduce the Cycle Walk, a new Markov chain Monte Carlo method for sampling distributions on balanced graph partitions, motivated by applications in political redistricting. The method operates on spanning forests and combines two types of updates: local "cycle" moves within districts and global moves that exchange population between adjacent districts while preserving balance constraints. This construction enables efficient Metropolis--Hastings correction while allowing proposals at multiple spatial scales. We show that the Cycle Walk naturally interpolates between existing approaches based on local updates and a class of global update methods derived from recombination (RECOM). Through a range of numerical experiments on synthetic graphs and real-world precinct data, we demonstrate that the Cycle Walk exhibits improved empirical convergence diagnostics for distributions that place weaker weight on spanning-tree counts, a regime that is challenging for existing methods. In particular, the algorithm remains effective when incorporating alternative compactness measures that more closely reflect policy-relevant criteria. These results suggest that the Cycle Walk provides a flexible and computationally efficient framework for sampling from a broader class of redistricting distributions than previously accessible with MCMC techniques.

Gabriel Chuang, Gregory Herschlag, Jonathan C. Mattingly

When auditing a redistricting plan, a persuasive method is to compare the plan with an ensemble of neutrally drawn redistricting plans. Ensembles are generated via algorithms that sample distributions on balanced graph partitions. To audit the partisan difference between the ensemble and a given plan, one must ensure that the non-partisan criteria are matched so that we may conclude that partisan differences come from bias rather than, for example, levels of compactness or differences in community preservation. Certain sampling algorithms allow one to explicitly state the policy-based probability distribution on plans, however, these algorithms have shown poor mixing times for large graphs (i.e. redistricting spaces) for all but a few specialized measures. In this work, we generate a multiscale parallel tempering approach that makes local moves at each scale. The local moves allow us to adopt a wide variety of policy-based measures. We examine our method in the state of Connecticut and succeed at achieving fast mixing on a policy-based distribution that has never before been sampled at this scale. Our algorithm shows promise to expand to a significantly wider class of measures that will (i) allow for more principled and situation-based comparisons and (ii) probe for the typical partisan impact that policy can have on redistricting.

Chuang Wang, Jonathan Mattingly, Yue M. Lu

We present a framework for analyzing the exact dynamics of a class of online learning algorithms in the high-dimensional scaling limit. Our results are applied to two concrete examples: online regularized linear regression and principal component analysis. As the ambient dimension tends to infinity, and with proper time scaling, we show that the time-varying joint empirical measures of the target feature vector and its estimates provided by the algorithms will converge weakly to a deterministic measured-valued process that can be characterized as the unique solution of a nonlinear PDE. Numerical solutions of this PDE can be efficiently obtained. These solutions lead to precise predictions of the performance of the algorithms, as many practical performance metrics are linear functionals of the joint empirical measures. In addition to characterizing the dynamic performance of online learning algorithms, our asymptotic analysis also provides useful insights. In particular, in the high-dimensional limit, and due to exchangeability, the original coupled dynamics associated with the algorithms will be asymptotically "decoupled", with each coordinate independently solving a 1-D effective minimization problem via stochastic gradient descent. Exploiting this insight for nonconvex optimization problems may prove an interesting line of future research.

David F. Anderson, Jonathan C. Mattingly

We present a numerical method for the approximation of solutions for the class of stochastic differential equations driven by Brownian motions which induce stochastic variation in fixed directions. This class of equations arises naturally in the study of population processes and chemical reaction kinetics. We show that the method constructs paths that are second order accurate in the weak sense. The method is simpler than many second order methods in that it neither requires the construction of iterated Ito integrals nor the evaluation of any derivatives. The method consists of two steps. In the first an explicit Euler step is used to take a fractional step. This fractional point is then combined with the initial point to obtain a higher order, trapezoidal like, approximation. The higher order of accuracy stems from the fact that both the drift and the quadratic variation of the underlying SDE are approximated to second order.

H. Lamba, J. C. Mattingly, A. M. Stuart

The understanding of adaptive algorithms for SDEs is an open area where many issues related to both convergence and stability (long time behaviour) of algorithms are unresolved. This paper considers a very simple adaptive algorithm, based on controlling only the drift component of a time-step. Both convergence and stability are studied. The primary issue in the convergence analysis is that the adaptive method does not necessarily drive the time-steps to zero with the user-input tolerance. This possibility must be quantified and shown to have low probability. The primary issue in the stability analysis is ergodicity. It is assumed that the noise is non-degenerate, so that the diffusion process is elliptic, and the drift is assumed to satisfy a coercivity condition. The SDE is then geometrically ergodic (converges to statistical equilibrium exponentially quickly). If the drift is not linearly bounded then explicit fixed time-step approximations, such as the Euler-Maruyama scheme, may fail to be ergodic. In this work, it is shown that the simple adaptive time-stepping strategy cures this problem. In addition to proving ergodicity, an exponential moment bound is also proved, generalizing a result known to hold for the SDE itself.