--- abstract: 'In the analysis of data sets consisting of $(X, Y)$-pairs, a tacit assumption is that each pair corresponds to the same observation unit. If, however, such pairs are obtained via record linkage of two files, this assumption can be violated as a result of mismatch error rooting, for example, in the lack of reliable identifiers in the two files. Recently, there has been a surge of interest in this setting under the term "Shuffled data" in which the underlying correct pairing of $(X, Y)$-pairs is represented via an unknown index permutation. Explicit modeling of the permutation tends to be associated with substantial overfitting, prompting the need for suitable methods of regularization. In this paper, we propose a flexible exponential family prior on the permutation group for this purpose that can be used to integrate various structures such as sparse and locally constrained shuffling. This prior turns out to be conjugate for canonical shuffled data problems in which the likelihood conditional on a fixed permutation can be expressed as product over the corresponding $(X,Y)$-pairs. Inference is based on the EM algorithm in which the intractable E-step is approximated by the Fisher-Yates algorithm. The M-step is shown to admit a significant reduction from $n^2$ to $n$ terms if the likelihood of $(X,Y)$-pairs has exponential family form as in the case of generalized linear models. Comparisons on synthetic and real data show that the proposed approach compares favorably to competing methods.' bibliography: - 'refs.bib' --- 3.5ex 1.5ex <span>$^{*}$Department of Statistics, George Mason University, Fairfax, VA 22030, USA $\; \; \;$</span>\ \ . 3.5ex Introduction {#sec:intro} ============ Shuffled data problems refer broadly to situations in which the goal is to perform inference for a functional of the joint distribution of a pair of random variables $(\x,\y)$ (such as, e.g., their covariance) based on separate samples $\{ \x_i \}_{i = 1}^n$ and $\{ \y_i \}_{i = 1}^m$ that involve matching pairs $\{ (X_{\pi^*(i)}, Y_i) \}_{i = 1}^{m}$ pertaining to the same statistical unit, where the map $\pi^*: \{1,\ldots,m\} \rightarrow \{1,\ldots,n \}$ may only be observed incompletely. This is a rather common scenario in data integration problems in which different pieces of information about a shared set of entities reside in multiple data sources that need to be combined in order to perform a given data analysis task. The process of identifying matching parts across two or more files is often far from trivial in the absence of unique identifiers, and has thus grown into a vast and active field of research known as *record linkage* (e.g., @Binette2020). The above shuffled data model in terms of the unknown map $\pi^*$ represents a direct approach to account for mismatches in record linkage and their impact on downstream data analysis. Historically, shuffled data problems were first systematically discussed in a series of papers by DeGroot *et al*. @DeGroot1971 [@DeGroot1976; @DeGroot1980; @Goel1975], with little to no progress until only a few years ago given advances in computation @Gutman13. Recently, shuffled data problems have generated much more widespread interest, fueled by novel applications in engineering and computer vision, among others @Unnikrishnan2015 [@Pananjady2016; @Pananjady2017]. Several papers have investigated the statistical limits of signal estimation and permutation recovery in *unlabeled sensing* in which the goal is to recover a signal $\theta^*$ from $n$ noisy linear measurements $y_i = \nscp{\x_{\pi^*(i)}}{\theta^*} + \eps_i$, $1 \leq i \leq n$, where $\pi^*$ is an unknown index permutation @Unnikrishnan2015 [@Pananjady2016; @Hsu2017; @Abid2017; @TsakirisICML19]. Another line of research has studied similar permuted data settings in which $x$ and $y$ are scalar and related by a monotone transformation @Carpentier2016 [@Weed2018; @Balabdoui2020; @Flammarion16; @Ma2020]. A common conclusion from these works is that shuffled data problems are generally plagued by both statistical and computational challenges. First, the combinatorial nature of $\pi^*$ makes it hard to devise computationally tractable approaches with provable guarantees. Existing algorithmic "solutions" involve integer programming @TsakirisICML19 [@Peng2020; @Mazumder2021] and the EM algorithm @Tsakiris2018 [@Abid2018; @Gutman13]. Regardless of the computational challenges, shuffled data problems tend to be highly susceptible to noise and prone to overfitting. In fact, statistical guarantees typically involve unrealistically stringent signal-to-noise requirements @Pananjady2016 [@Hsu2017; @SlawskiBenDavid2017]. Loosely speaking, this issue results from the fact that the set of index permutations grows rapidly in size with $n$. This observation suggests that suitable forms of regularization hinging on prior information on $\pi^*$ are needed to constrain the size of the parameter space under consideration. Several papers consider partial shufflings in which varying fractions of $(\x_i,\y_i)$-pairs are already observed with the correct correspondence @SlawskiBenDavid2017 [@Peng2021; @SlawskiDiaoBenDavid2019; @SlawskiBenDavidLi2019; @SlawskiRahmaniLi2018; @ZhangLi2020], and only the remaining portion of the data is subject to shuffling. Another constraint commonly encountered in record linkage applications is that $\pi^*$ is block-structured with known composition of the blocks based on auxiliary variables that are required to agree for matching records @Chambers2009 [@chambers2019improved; @Zhang2020]. In other applications such as signal processing and computer vision, $\pi^*$ is often constrained to act locally in the sense that indices are shuffled only within small time windows or image regions @Ma2021 [@Abbasi2021]. The goal of the present paper is the development of a regularization framework for shuffled data problems that integrates the aforementioned as well as potential other constraints in a unified fashion. For this purpose, we introduce an exponential family prior on the permutation group that is flexible enough to accommodate any kind of prior information that can be expressed in terms of index pairs $(i,j)$. Conveniently, this prior turns out to be conjugate for canonical shuffled data problems in which the likelihood conditional on a fixed permutation can be expressed as the product over the corresponding $(\x,\y)$-pairs. Inference is performed via the Monte-Carlo EM algorithm considered in earlier works @Wu1998 [@Abid2018; @Gutman13]. We show that for exponential family likelihoods, the resulting M-step is particularly scalable since it only involves $n$ instead of $n^2$ terms. Moreover, computation of the MAP estimator of $\pi^*$ with the remaining parameters fixed is shown to reduce to a linear assignment problem (LAP), and hence remains computationally tractable. Several theoretical results as well as a collection of experiments for various shuffled data settings demonstrate the usefulness of regularization based on the proposed prior in comparison to the unregularized counterpart and several other baselines. 1.5ex <span>**Paper organization**</span>. Section $\S$\[sec:approach\] starts with a detailed motivation of the proposed approach, followed by a discussion of central technical and computational aspects. Section $\S$\[sec:theory\] contains several theoretical results and accompanying discussions. Numerical results on synthetic and real data are presented in $\S$\[sec:experiments\]. Proofs and complementary technical details are relegated to the appendix. 1.5ex <span>**Notations**</span>. For the convenience of the reader, an overview of the most frequently used notation throughout this paper is provided below. ---------------------------------------------- ----------------------------------------------------- -------------------- ------------------------------------ $p(\cdot)$ density of a list of variables $\propto$ equality up to a positive constant $p(\cdot \, | \, \cdot)$ conditional density $I_n$ $n$-by-$n$ identity matrix $u \sim p$ random variable $u$ has density $p$ $\mathbb{I}$ indicator function $(\M{x}, \M{y})$ generic pair $[n]$ $\{1,\ldots,n \}$ $\mc{D} = \{ (\M{x}_i, \M{y}_i)\}_{i = 1}^n$ observed linked data $\pi$ permutation on $[n]$ $\M{X}$ row-wise concatenation of $\{ \M{x}_i \}_{i = 1}^n$ $\Pi = (\pi_{ij})$ corresponding permutation matrix $\M{Y}$ row-wise concatenation of $\{ \M{y}_i \}_{i = 1}^n$ $\mc{P}(n)$ set of permutations on $[n]$ $\E_{\ldots}[]$ expectation w.r.t. $\ldots$ $\theta$ model parameter $\tr$ matrix trace $d_{\textsf{H}}$ Hamming distance on $\mc{P}(n)$ $\nscp{A}{B}$ $\tr(A^{\T} B)$ $|A|$ cardinality of set $A$ $\nnorm{\cdot}_{\text{F}}$ Frobenius norm signal-to-noise ratio ---------------------------------------------- ----------------------------------------------------- -------------------- ------------------------------------ <span>**Conventions**</span>. We often refer to a permutation via the underlying map $\pi$ and the corresponding matrix $\Pi$ in an interchangeable fashion, and accordingly $\mc{P}(n)$ and subsets thereof may refer to both maps and matrices. Asterisked symbols such as $\pi^*$, $\theta^*$, $\sigma_*$ etc. refer to ground truth parameters, whereas non-asterisked symbols such as $\pi$, $\theta$, $\sigma$ etc. refer to generic elements of the associated parameter spaces. Approach {#sec:approach} ======== The following three subsections are dedicated to a detailed account of the approach. We start with a brief motivation before a more formal systematic introduction and subsequent technical details pertaining to computation and model fitting. Motivating examples {#subsec:mot_example} ------------------- Consider the simple linear regression setup $y_i = x_{\pi^*(i)} \beta^* + \sigma_* \eps_i$, where $x_i$ and $\eps_i$ are independent standard normal random variables, $1 \leq i \leq n$, and $\pi^*$ permutes 10% of the indices bridgeslisa@example.com. Suppose that the sign of $\beta^*$ is known to be positive. Then the ML estimator of $\pi^*$ (or equivalently, the MAP estimator under a uniform prior over $\mc{P}(n)$) is given by the permutation $\wh{\pi}_{\text{ML}}$ that matches the corresponding order statistics in $\{ x_i \}_{i = 1}^n$ and $\{ y_i \}_{i = 1}^n$, i.e., $$\label{eq:pihat_ML} \su x_{\wh{\pi}_{\text{ML}}(i)} y_i = \su x_{(i)} y_{(i)}$$ As shown in Figure \[fig:motivation\_sparse\], the estimator $\wh{\pi}_{\text{ML}}$ performs rather poorly. The scatterplot of the matching of corresponding order statistics is far from that of the underlying correct pairing. In fact, $\wh{\pi}_{\text{ML}}$ is associated with massive overfitting as made explicit in the sequel. Let $$\wh{\beta}_{\text{ML}} = \su x_{(i)} y_{(i)} \Big / \sum_{i = 1}^n x_i^2, \qquad \wh{\sigma}_{\text{ML}}^2 = \frac{1}{n} \su (y_i - x_i \wh{\beta}_{\text{ML}})^2$$ denote the resulting ML estimators of $\beta^*$ and $\sigma_*^2$, respectively. It is straightforward to show that $$\label{eq:convergence_overfitting} \wh{\beta}_{\text{ML}} \rightarrow \sqrt{(\beta^*)^2 + \sigma_*^2}, \qquad \wh{\sigma}_{\text{ML}}^2 \rightarrow 0, \qquad \frac{1}{n} \su (x_i \beta^* - x_i \wh{\beta}_{\text{ML}})^2 \rightarrow \sigma_*^2$$ in probability as $n \rightarrow \infty$ (see Appendix \[app:overfitting\_ml\] for a derivation). In particular, the second and third relation in are alarming since they imply that the least squares fit absorbs all the noise. Figure \[fig:motivation\_sparse\] shows that the ML estimator is too aggressive in forming "corrected" pairs $(x_{\wh{\pi}_{\text{ML}}(i)}, y_i)$ given that only 10% of the observations are actually mismatched, and among those 10%, only a similarly small fraction contributes substantial mismatch that visibly exceeds the noise inherent in the problem. Sparsity of $\pi^*$ is often a reasonable assumption in post-linkage data analysis (e.g., @Chambers2009 [@chambers2019improved; @SlawskiBenDavid2017; @SlawskiDiaoBenDavid2019]), where sparsity here refers to the set of mismatches $\{1 \leq i \leq n: \pi^*(i) \neq i \}$ having significantly smaller cardinality than $n$. If an upper bound on the number of mismatches, say $k$, is known, it is appropriate to consider the following constrained ML estimator of $\pi^*$: $$\label{eq:sparsity_constrained} \max_{\pi \in \mc{P}(n)} \su x_{\pi(i)} y_i \quad \text{subject to} \; \dH(\pi, \textsf{id}) \leq k,$$ where $\textsf{id}$ is the identity map on $[n]$ and $\dH(\pi, \pi') = \su \mathbb{I}(\pi(i) \neq \pi'(i))$ denotes the Hamming distance between two elements $\pi, \pi'$ of $\mc{P}(n)$. For $k = n$, the maximizer of the above problem is given by $\wh{\pi}_{\text{ML}}$ and for $k < 2$, the maximizer is given by $\textsf{id}$. For general $k$, to the best of our knowledge, there is no efficient algorithm for computing the maximizer directly. However, there exists a Lagrangian multiplier $\gamma > 0$ such that is equivalent to the optimization problem $$\label{eq:sparsity_LAP} \max_{\pi \in \mc{P}(n)} \left\{ \su x_{\pi(i)} y_i - \gamma \dH(\pi, \textsf{id}) \right \} = \max_{\Pi \in \mc{P}(n)} \left\{ \su \sum_{j = 1}^n \pi_{ij} (x_j y_i - \gamma \mathbb{I}(i \neq j)) \right \},$$ which is a linear assignment problem with cost matrix $C = \big(\gamma \mathbb{I}(i \neq j) - x_j y_i \big)_{i,j}$, which is computationally tractable according to the discussion following below. As elaborated in the next subsection $\S$\[subsec:expfam\], the maximizer of corresponds to the MAP estimator of $\pi^*$ (for fixed model parameter $\beta$) under a specific class of prior distributions over $\mc{P}(n)$. The right panel of Figure \[fig:motivation\_sparse\] highlights the improvement that can be achieved by the resulting estimator which here only performs a small number of re-pairings capturing those pairs that correspond to massive mismatch error in the left panel. This re-pairing is consistent with the underlying regression slope, avoiding both the amplification bias associated with $\wh{\pi}_{\text{ML}}$ depicted in the middle panel as well as the attenuation bias that is incurred when ignoring mismatch error altogether (e.g., @Neter65 [@Scheuren93; @Scheuren97; @WangBenDavidDiaoSlawski2021]) . Figure \[fig:motivation\_local\] illustrates scenarios in which $\pi^*$ is not sparse (with a mismatch rate exceeding 80%), but constrained to be a "local shuffling" in the sense that $\max_{i \in [n]} |\pi^*(i) - i| \leq r$, i.e., the corresponding permutation matrix is a band matrix with bandwidth at most $r$. This scenario is particularly relevant when the data is recorded sequentially (e.g., over different time points) or across a spatial domain endowed with a notion of distance, and it is known that $\pi^*$ can only mix up the order of data inside a specific time window or within a local neighborhood. There are numerous applications in which $\pi^*$ is locally constrained such as genome sequencing @Abid2017, signal processing @Balakrishnan1962 [@Abbasi2021], or computer vision @Ma2021. The illustrative example in Figure \[fig:motivation\_local\] can be thought of as a regression problem in which the signal is a sine with known frequency but unknown (positive) amplitude $\beta^*$, i.e., $y_{t_i} = \beta^* \sin(10 \pi t_i) + 0.1 \eps_i$, $1 \leq i \leq n$ (left panel). However, the observed data is of the form $(y_{t_{\pi^*(i)}})_{i = 1}^n$ for some unknown (local) permutation $\pi^*$ (middle panel). If $\beta^*$ is known to be positive, then the (unconstrained) ML estimator $\wh{\pi}_{\text{ML}}$ of $\pi^*$ matches the order statistics $\{ \mu_{(i)} \}_{i = 1}^n$ and $\{ y_{(i)} \}_{i = 1}^n$, where $\mu_i = \sin(10 \pi t_i)$, $1 \leq i \leq n$. In order to improve over the ML estimator using the prior knowledge of local shuffling, we impose the constraint that the alternative estimator $\wh{\pi}$ does not pair any indices that are more than $r = 3$ apart. This estimator can be obtained as solution of the optimization problem $$\label{eq:local_LAP} \max_{\substack{\pi \in \mc{P}(n) \\ \max_{i \in [n]}|\pi(i) - i| \leq r}} \left\{ \su \mu_i y_{\pi(i)} \right \} = \max_{\Pi \in \mc{P}(n)} \left\{ \su \sum_{j = 1}^n \pi_{ij} (\mu_i y_j - c_{ij}) \right \},$$ where $c_{ij} = 0$ if $|i - j| \leq r$ and $c_{ij} = +\infty$ otherwise. As in , the problem on the right hand side is a linear assignment problem and hence computationally tractable, and corresponds to MAP estimation under the family of priors considered below in detail. The corrected, i.e., repaired data $(t_i, y_{\wh{\pi} \circ \pi^*(i)})_{i = 1}^n$ based on this approach are depicted in the right panel of Figure \[fig:motivation\_local\]. Exponential family prior on $\mc{P}(n)$ {#subsec:expfam} --------------------------------------- In this subsection, we show that the priors discussed in the two examples of the previous subsection can be understood as specific instances of a more general family of prior distributions over $\mc{P}(n)$. Specifically, we consider the family of priors $$\label{eq:prior} p(\pi) \propto \exp(\gamma \, \tr(\Pi^{\T} M)), \quad M \in \R^{n \times n}, \quad \gamma > 0,$$ where $\gamma > 0$ is the concentration parameter, and the matrix $M$ (which is not required to have any specific properties) defines the mode(s) of the distribution, i.e., $\argmax_{\Pi \in \mc{P}(n)} \nscp{\Pi}{M}$, where $\nscp{\cdot}{\cdot}$ here represents the trace inner product on matrices of the same dimension that induces the Frobenius norm $\nnorm{\cdot}_{\textsf{F}}$. In the same vein, the mode(s) of the distribution correspond to the set of matrices closest to $M$ with respect to the same norm. Moreover, the distribution specified by is of exponential family form with respect to the trace inner product (cf., e.g., $\S$3.2 in @wainwright2008graphical). 1ex *Linear Assignment Problems*. Linear Assignment problems (LAPs) are a well-studied class of optimization problems for computing optimal one-to-one matchings of two sets of items @Burkard2009. LAPs are of the form $$\label{eq:LAP} \min_{\Pi \in \mc{P}(n)} \nscp{\Pi}{C},$$ where $C$ is a given cost matrix. By the Birkhoff-von Neumann theorem @Ziegler1995, the vertices of the set of $n$-by-$n$ doubly stochastic matrices $$\mc{D}\mc{S}(n) = \left\{P \in \R^{n \times n}: \; P_{ij} \geq 0, \; 1 \leq i,j \leq n, \; \sum_{j= 1}^n P_{ij} = 1, \; \, 1 \leq i \leq n, \; \sum_{i= 1}^n P_{ij} = 1, \; \, 1 \leq j \leq n \right \}$$ are given by $\mc{P}(n)$. As a result, the minimum over $\mc{P}(n)$ can be replaced by the minimum over $\mc{D}\mc{S}(n)$, hence reduces to a linear program in $n^2$ variables and $n^2 + 2n$ linear constraints. This brief summary entails that computing a mode of reduces to a tractable problem, by setting $C = -M$ in . 1ex *Specific examples*. Below, we consider a few examples of interest that are special cases of . 1ex (I) Hamming prior.\ Consider the choice $M = I_n$. In this case, for any $\Pi \in \mc{P}(n)$, we have $$\nscp{\Pi}{I_n} = \sum_{i = 1}^n \Pi_{ii} = n - \sum_{i = 1}^n \mathbb{I}(\Pi_{ii} \neq 1) = n - \dH(\pi, \textsf{id}),$$ where, as before, $\dH(\pi, \pi') = \sum_{i = 1}^n \mathbb{I}(\pi(i) \neq \pi'(i))$ denotes the Hamming distance on $\mc{P}(n)$. Since $n$ does not depend on $\pi$, this implies that can be expressed equivalently as $$\label{eq:Hammingprior} p(\pi) \propto \exp(-\gamma \, \dH(\pi, \textsf{id})),$$ which appeared in the first example of the preceding subsection $\S$\[subsec:mot\_example\], cf. , in which the goal was to take into account the underlying low rate of mismatches. The distribution is a specific instance of the class of Mallow's priors of the form $p(\pi) \propto \exp(-\gamma d(\pi, \pi_0))$ for a base permutation $\pi_0$ and a metric $d$ on $\mc{P}(n)$ @Mallows1957 [@Diaconis1988; @fligner1986distance; @irurozki2019mallows; @fligner1993probability]. We note, however, that the family of Mallow's priors is not a sub-family of the exponential family prior since the metric $d$ cannot be expressed via a trace inner product in general. 1ex (II) Local shuffling prior.\ As in the second example in $\S$\[subsec:mot\_example\], suppose we want to have the prior $p$ place most of its mass on permutations that move indices within small windows, i.e., $|\pi(i) - i|$ tends to be small. This can be achieved by choosing the entries of the matrix $M$ in of the form $M_{ij} = -\phi(|i - j|)$ for some non-decreasing function $\phi: \R_+ \rightarrow \R_+$. The choice $\phi(u) = 0$ if $u \leq r$ for some positive integer $r$ and $\phi(u) = +\infty$ otherwise yields the approach that underlies the example in Figure \[fig:motivation\_local\] above. 1ex (III) Block prior.\ Under the local shuffling assumption $\max_{i \in [n]} |\pi^*(i) - i| \leq r$, the corresponding permutation matrix $\Pi^*$ is typically block diagonal, i.e., $\Pi^* = \text{bdiag}(\Pi_1^*, \ldots, \Pi^*_B)$, with all $B$ blocks having size proportional to $r$. Note that the composition of the blocks is generally *not* known in advance. On the other hand, in record linkage applications, it is rather common that the composition of the blocks is indeed known given matching variables used during record linkage. For example, suppose that the combination of gender, ethnicity, and age group are used for that purpose and that these three categorical variables are free of errors. In this case, mismatches can only involve pairs $(i,j)$ falling into the same block corresponding to a specific combination of gender, ethnicity, and age. Such known block structure can be encoded via prior by choosing $M_{ij} = -\infty$ if $(i,j)$ is not contained in the same block and $M_{ij} = 0$ otherwise. Note that this corresponds to a uniform prior for each block, i.e., $p(\pi) = \prod_{b = 1}^B p(\pi_b)$ with $p(\pi_b) \propto 1$, $1 \leq b \leq B$. The prior for each block does not have to be necessarily uniform. For example, a Hamming prior as in Example (I) above can be used instead. Moreover, the hard block constraint can be softened by choosing a suitable finite negative number for entries $M_{ij}$ corresponding to pairs $(i,j)$ not contained in the same block. 1ex (IV) Lahiri-Larsen prior.\ In their seminal work on adjusting (generalized) linear regression in the presence of mismatch errors, Lahiri & Larsen @Lahiri05 and Chambers @Chambers2009 assume that $\pi^* \sim p(\pi)$ whose expectation $\E_{p(\pi)}[\Pi^*] = Q$ is known to the (post-linkage) data analyst. Observe that $Q \in \mc{D}\mc{S}(n)$ is a double stochastic matrix. Any distribution over permutations whose expectation equals $Q$ can be used as a potential prior. In fact, it is known that there are distributions supported over only $O(n^2)$ (as opposed to $n!$) permutations satisfying that requirement. Identification of the support via Birkhoff's decomposition @johnson_dulmage_mendelsohn_1960 requires at least $O(n^4)$ runtime, and hence is not scalable. In the framework considered here, it is convenient to use $M = Q$ in the prior . The mode(s) of that prior are then given by the permutation matrices solving the Euclidean projection problem $\min_{\Pi \in \mc{P}(n)} \nnorm{\Pi - Q}_{\textsf{F}}^2$ of $Q$ on $\mc{P}(n)$. A basic example for $Q$ results for the so-called exchangeable linkage model in @Chambers2009 [@Zhang2020] in which $Q = (1 - \alpha) I_n + \frac{\alpha}{n-1} \bm{1}_n \bm{1}_n^{\T}$. Since in this case $\scp{Q}{\Pi} = (1 - \alpha)\scp{I_n}{\Pi} + \alpha \frac{n}{n-1}$ for $\alpha \in [0,1)$, the resulting prior is equivalent to the Hamming prior considered in Example (I). More complex priors are obtained depending on the structure of $Q$. Integration in Shuffled Data Problems {#subsec:dataproblems} ------------------------------------- In this subsection, we outline how the above prior can be integrated into generic shuffled data problems. The proposed Monte-Carlo EM @wei1990monte framework builds upon the classical work @Wu1998 that has been rediscovered in the more recent work @Abid2018. The Monte-Carlo EM scheme in @Wu1998 was further developed based on the concept of data augmentation @TannerWong1987 in Gutman *et al*. @Gutman13. Note that none of @Wu1998 [@Abid2018; @Gutman13] consider informative priors for the permutation. 2ex <span>**Conditional and Integrated Likelihood**</span> 1ex Suppose we are given data $\mc{D} = \{ (\M{x}_i, \M{y}_i)\}_{i = 1}^n$ potentially contaminated by mismatch error. Let $p(\M{x}_j, \M{y}_i;\theta)$ be the likelihood (depending on a parameter $\theta$) for the pairing of $\M{x}_j$ with $\M{y}_i$, $(i,j) \in [n]^2$. The likelihood for $\theta$ resulting from $\mc{D}$ conditional on a specific permutation $\pi \in \mc{P}(n)$ is given by $$\label{eq:conditional_likelihood} L(\theta| \pi) = \prod_{i = 1}^n p(\M{x}_{\pi(i)}, \M{y}_i;\theta) = \prod_{i = 1}^n \prod_{j = 1}^n p(\M{x}_j, \M{y}_i;\theta)^{\pi_{ij}}$$ *Conjugacy*. It is worth noting that under , the posterior $p(\pi|\mc{D}, \theta)$ is a member of the family of distributions specified by $p(\pi)$ of the form , i.e., the latter is a conjugate prior. This follows immediately from the observation that $$\begin{aligned} p(\pi|\mc{D}, \theta) \propto p(\mc{D}|\pi, \theta) \cdot p(\pi) &= L(\theta|\pi) \cdot p(\pi) \notag \\ &= \exp\left(\sum_{i = 1}^n \sum_{j = 1}^n \pi_{ij} \left[ \log\{ p (\M{x}_j, \M{y}_i | \theta) \} + \gamma M_{ij} \right] \right) \notag\\ &= \exp(\tr(\Pi^{\T} M_{\mc{D}, \theta, \gamma})),\label{eq:proof_conjugacy} \end{aligned}$$ with $M_{\mc{D}, \theta, \gamma} = \big( \log(p(\M{x}_j, \M{y}_i | \theta)) + \gamma M_{ij} \big)$. The (conditional) likelihood can be maximized with respect to both $\theta$ and $\pi$ as, e.g., in @Pananjady2016 [@Abid2017; @SlawskiBenDavid2017]. In an alternative view, $\theta$ is considered as the quantity of primary interest, in which case one would rather consider the *integrated likelihood* $$\label{eq:integrated_likelihood} L(\theta) = \E_{\pi} [ L(\theta | \pi)] = \sum_{\pi \in \mc{P}(n)} L(\theta|\pi) p(\pi).$$ As seen in $\S$\[subsec:mot\_example\], maximizing the conditional likelihood tends to be prone to overfitting, prompting a need for regularization. The use of the integrated likelihood mitigates that problem at best slightly, but not substantially as can be seen, e.g., by examining the case of linear regression with i.i.d. Gaussian errors (cf. Appendix \[app:overfitting\_integrated\]), hence regularization remains relevant. 1ex <span>**Monte Carlo EM scheme**</span> 1ex The Expectation-Maximization (EM) algorithm @dempster1977maximum is an established heuristic for (approximately) minimizing the negative log-likelihood corresponding to . Specifically, instead of minimizing $\ell(\theta) = -\log L(\theta)$, a sequence of surrogate functions $\{ \wt{\ell}^{(t)}(\theta; \theta^{(t)}) \}_{t \geq 0}$ are minimized successively: $$\ell(\theta) = -\log \E_{\pi}[L(\theta|\pi)] \; \; \leadsto \; \; \E_{\pi|\mc{D},\theta^{(t)}}[-\log L(\theta|\pi)] \invcoloneq \wt{\ell}^{(t)}(\theta; \theta^{(t)}),$$ where $$\label{eq:expected_complete} \E_{\pi|\mc{D},\theta^{(t)}}[-\log L(\theta|\pi)] = \sum_{i = 1}^n \sum_{j = 1}^n \E[\pi_{ij} | \mc{D}, \theta^{(t)}] \{ -\log p(\M{x}_j, \M{y}_i; \theta) \}$$ is the so-called *expected complete data* negative log-likelihood. The surrogates $\{ \wt{\ell}^{(t)}(\cdot\,;\theta^{(t)}) \}$ tend to be easier to minimize since they are linear combinations of standard likelihood terms as they are encountered for fixed and known $\pi$. Surrogates are updated according to the recursion $$\theta^{(t+1)} \leftarrow \argmin_{\theta} \wt{\ell}^{(t)}(\theta; \theta^{(t)}) \; \; \leadsto \; \; \wt{\ell}^{(t+1)}(\theta;\theta^{(t+1)}).$$ It can be shown @dempster1977maximum that the sequence generated in this fashion exhibits a monotonic descent property with respect to the original objective $\ell$, i.e., $\ell(\theta^{(t+1)}) \leq \ell(\theta^{(t)})$ for all $t$. Here, the main challenge of this scheme is the E-step, i.e, the calculation of the expectation on the right term in . For any entry $\pi_{ij}$ of $\Pi$, we have $$\begin{aligned} \E[\pi_{ij}|\mc{D}, \theta^{(t)}] = \sum_{\pi \in \mc{P}(n)} p(\pi|\mc{D},\theta^{(t)}) \pi_{ij} &\propto \sum_{\pi \in \mc{P}(n)} p(\mc{D}|\pi,\theta^{(t)}) p(\pi) \pi_{ij} \\ &= \sum_{\pi \in \mc{P}(n)} \left\{ \prod_{i = 1}^n p(\M{x}_{\pi(i)}, \M{y}_i;\theta^{(t)}) \right \}p(\pi) \pi_{ij}. \end{aligned}$$ Since the summation over $\mc{P}(n)$ is not computationally tractable, the expectation needs to be approximated, e.g., via Monte Carlo simulation. Since for the same reason, the posterior $p(\pi | \mc{D}, \theta^{(t)})$ is only accessible up to an unknown constant (cf. ), it is appropriate to resort to Markov Chain Monte Carlo (MCMC) sampling techniques @gelman2013bayesian. The Metropolis-Hastings (MH) algorithm can be used to generate a Markov Chain $\{ \pi^{(k)} \}_{k \geq 1}$ whose stationary distribution equals $p(\pi|\mc{D}, \theta^{(t)})$. This yields the approximation $$\label{eq:MC-EM} \wh{\E}[\pi_{ij}|\mc{D}, \theta^{(t)}] = \frac{1}{m - b} \sum_{k = b+1}^m \pi_{ij}^{(k)}, \quad (i,j) \in [n]^2.$$ where $b$ denotes the length of the so-called "burn-in" period after which the Markov Chain is considered to have reached stationarity, and $m$ denotes the total length of the Markov chain. Substituting into then yields what is known as Monte-Carlo EM scheme, summarized in Algorithm \[alg:montecarloEM\]. Conveniently, there is a proposal distribution for the MH algorithm that is, in a sense, canonical and easy to work with. That proposal distribution, known as Fisher-Yates sampling, generates a new permutation from the current one by swapping the assignments of a pair of indices (cf. Algorithm \[alg:MH\] for details). 2ex *Initialization*. It is a well-known fact that the choice of the initial iterate $\theta^{(0)}$ can critically impact the quality of the solution that is returned by EM schemes given that the latter is a local strategy that finds a stationary point of a (in general) non-convex objective near the initial iterate. Several consistent initial estimators of $\theta^*$ are known for regression setups depending on the structure of $\pi$ @SlawskiBenDavid2017 [@SlawskiDiaoBenDavid2019; @Lahiri05; @Chambers2009; @chambers2019improved; @Peng2021], and those naturally lend themselves as initial iterate for the above EM scheme. Careful initialization of the MH subroutine is important as well in order to ensure that $p(\pi|\mc{D}, \theta^{(t)})$ is explored reasonably well given that the domain of interest $\mc{P(n)}$ has $n!$ elements while the number of MCMC iterations $m$ is limited. Fortunately, under the prior , computing the mode $\argmax_{\pi} p(\pi|\mc{D}, \theta^{(t)})$ reduces to an LAP of the form in virtue of . Initialization via the mode has the advantage that the Markov chain is started in a high density region. The hope is that the resulting iterates (which are generated according to a localized proposal distribution) will pick up most of the mass of $p(\pi|\mc{D}, \theta^{(t)})$ so that will well approximate the underlying expectation. 1ex <span>0.63</span> \[H\] <span>**Input**</span>: $\mc{D} = \{\{ \M{x}_i \}_{i = 1}^n$, $\{ \M{y}_i \}_{i = 1}^n \}$, $\gamma$, `EM_iter` **Initialize** $\theta^{(0)} \leftarrow \wh{\theta}_{\text{init}}$. <span>**for**</span> $t=0,\ldots,$`EM_iter` - $\wh{\pi}_{\text{init}} \leftarrow \argmax_{\pi \in \mc{P}(n)} p(\pi | \mc{D}, \theta^{(t)})$. - $\wh{\E}[\pi|\mc{D}, \theta^{(t)}] \leftarrow \texttt{MH}(\mc{D}, \theta^{(t)}, \wh{\pi}_{\text{init}}, \gamma, m)$. - $\theta^{(t+1)} \leftarrow \min_{\theta} \mbox{{\small $\left\{ \sum_{i = 1}^n \sum_{j = 1}^n \wh{\E}[\pi_{ij} | \mc{D}, \theta^{(t)}] \{ -\log p(\M{x}_j, \M{y}_i; \theta) \} \right\}$}}$. - $t \leftarrow t+1$ <span>**end for**</span> <span>0.36</span> \[H\] <span>**Input**</span>: $\mc{D}, \theta, \wh{\pi}_{\text{init}}, \gamma, m$ **Initialize** $\pi^{(0)} \leftarrow \wh{\pi}_{\text{init}}$. <span>**for**</span> $k=0,\ldots,m$ - Sample $(i,j) \in [n]^2$[^1]. - $\wt{\pi}(i) \leftarrow \pi^{(k)}(j)$, $\wt{\pi}(j) = \pi^{(k)}(i)$. - $r(\wt{\pi}, \pi^{(k)}) \leftarrow \min \left\{ \frac{p(\wt{\pi}|\mc{D}, \theta;\gamma)}{p(\pi^{(k)}|\mc{D}, \theta;\gamma)}, 1 \right \}$. - Draw $u \sim U([0,1])$. - <span>**if**</span> $r(\wt{\pi}, \pi^{(k)}) > u$: $\pi^{(k + 1)} \leftarrow \wt{\pi}$. - <span>**else**</span>: $\pi^{(k + 1)} \leftarrow \pi^{(k)}$. - $k \leftarrow k+1$. <span>**end for**</span>\ <span>**return**</span> $\wh{\E}[\pi | \mc{D}, \theta]$ as in 2ex <span>**Reduction under exponential family likelihood**</span> 1ex Interestingly, for a variety of exponential family models, the expected complete data negative log-likelihood involves only $n$ instead of $n^2$ terms, which is a substantial reduction. Specifically, will be of the form $$\sum_{i = 1}^n r\{\M{x}_i, \M{y}_i, (\E[\Pi | \mc{D}, \theta^{(t)}]^{\T} \M{Y})_i; \theta) \}$$ for a function $r$ depending at most on $\{ \M{x}_i, \M{y}_i, (\E[\Pi | \mc{D}, \theta^{(t)}]^{\T} \M{Y})_i \}_{i = 1}^n$. Specific examples of interest are presented in the sequel.1ex *(i) Least squares regression*. Taking $-\log p(\M{x}, y; \beta, \sigma^2) = \frac{1}{2\sigma^2} (y - \M{x}^{\T} \beta)^2$, which corresponds to the negative likelihood of a linear regression model with i.i.d. zero-mean Gaussian errors with variance $\sigma^2$ yields the following expression for the expected complete data negative log-likelihood: $$\begin{aligned} &\frac{1}{2\sigma^2} \sum_{i = 1}^n \sum_{j = 1}^n \E[\pi_{ij} | \mc{D}, \theta^{(t)}] (y_i - \M{x}_j^{\T} \beta)^2 = \frac{1}{\sigma^2} \sum_{i = 1}^n \sum_{j = 1}^n \E[\pi_{ij} | \mc{D}, \theta^{(t)}] \left\{ \frac{1}{2} (\M{x}_j^{\T} \beta)^2 - y_i \M{x}_j^{\T} \beta \right \} + c. \\ &= \frac{1}{2\sigma^2} \sum_{i = 1}^n \E \left[\sum_{j = 1}^n \pi_{ij} (\M{x}_j^{\T} \beta)^2 \Big | \mc{D}, \theta^{(t)} \right] - \frac{1}{\sigma^2} \sum_{j = 1}^n \M{x}_j^{\T} \beta \sum_{i = 1}^n \E[\pi_{ij} | \mc{D}, \theta^{(t)}] y_i + c \\ &= \frac{1}{\sigma^2} \left\{ \frac{1}{2} \sum_{i = 1}^n (\M{x}_i^{\T} \beta)^2 - \sum_{i = 1}^n \left \{ \E[\Pi | \mc{D}, \theta^{(t)}]^{\T} \M{Y} \right\}_i (\M{x}_i^{\T} \beta) \right\} + c \\ &=\frac{1}{\sigma^2} \left\{ \frac{1}{2} \nnorm{\M{X} \beta}_2^2 - \nscp{\E[\Pi | \mc{D}, \theta^{(t)}]^{\T} \M{Y}}{\M{X} \beta} \right\} + c\end{aligned}$$ which is identical to a standard least squares objective with design matrix $\M{X}$ and response vector $\E[\Pi^{\T} | \mc{D}, \theta^{(t)}] \M{Y}$. 1ex *(ii) Generalized linear models*. In this case, we have $-\log p(\M{x}, y;\beta, \phi) = \frac{\psi(\M{x}^{\T} \beta) - y \M{x}^{\T} \beta}{a(\phi)} + c(y, \phi)$, where $a$, $\psi$ and $c$ denote scale function, cumulant, and partition function, respectively. Using a reasoning similar to above, one shows that $$\begin{aligned} &\frac{1}{a(\phi)}\sum_{i = 1}^n \sum_{j = 1}^n \E[\pi_{ij} | \mc{D}, \theta^{(t)}] \{ \psi(\M{x}_j^{\T} \beta) - y_i \M{x}_j^{\T} \beta \} + \sum_{i = 1}^n c(y_i, \phi) \\ =&\frac{1}{a(\phi)} \su \{ \psi(\M{x}_i^{\T} \beta) - ( \E[\Pi | \mc{D}, \theta^{(t)}]^{\T} \M{Y})_i \, \M{x}_i^{\T} \beta \} + \sum_{i = 1}^n c(y_i, \phi). \end{aligned}$$ While in the above calculation, the canonical link is assumed for simplicity, this assumption is not necessary to achieve the aforementioned reduction from $n^2$ to $n$ terms. 1ex *(iii) Multivariate Normal data and precision matrix estimation*. Suppose that $(\M{x}, \M{y}) \sim N(\mu_*, \Omega_*^{-1})$, where $\Omega_*$ is referred to as precision matrix. Since estimation of $\mu_*$ is not affected by the presence of an unknown permutation, let us assume that $\mu_* = 0$ for simplicity. We have $-\log p(\M{x}, \M{y}; \Omega) = -\log \det \Omega + \tr(\Omega \M{z} \M{z}^{\T})$ up to additive constants, where $\M{z} = [\M{x}^{\T} \; \M{y}^{\T}]^{\T}$ denotes the horizontal concatenation of $\M{x}$ and $\M{y}$. Note that $\M{z} \M{z}^{\T}$ consists of diagonal blocks $\M{x} \M{x}^{\T}$ and $\M{y} \M{y}^{\T}$ and off-diagonal blocks $\M{x} \M{y}^{\T}$ and $\M{y} \M{x}^{\T}$. Accordingly, we have $\tr(\Omega \M{z} \M{z}^{\T}) = \tr(\Omega_{\M{x}\M{x}} \M{x} \M{x}^{\T}) + \tr(\Omega_{\M{y}\M{y}} \M{y} \M{y}^{\T}) + 2 \tr(\Omega_{\M{y} \M{x}} \M{x} \M{y}^{\T})$, where $\Omega_{\M{x} \M{x}}$, $\Omega_{\M{y} \M{y}}$ etc. denote the corresponding sub-matrices of $\Omega$. Consequently, we have (up to constants) $$\begin{aligned} &\su \sum_{j = 1}^n \E[\pi_{ij} | \mc{D}, \Omega^{(t)}] \{-\log p(\M{x}_j, \M{y}_i; \Omega) \} \\\ &= -n \log \det \Omega + \tr\left(\Omega_{\M{x} \M{x}} \su \M{x}_i \M{x}_i^{\T} \right) + \tr\left(\Omega_{\M{y} \M{y}} \su \M{y}_i \M{y}_i^{\T} \right) + \tr \left(\Omega_{\M{y} \M{x}} \su \sum_{j = 1}^n \E[\pi_{ij} | \mc{D}, \Omega^{(t)}] \M{x}_j \M{y}_i^{\T} \right) \\ &= -n \log \det \Omega + \tr(\Omega_{\M{x} \M{x}} \M{X}^{\T} \M{X}) + \tr(\Omega_{\M{y} \M{y}} \M{Y}^{\T} \M{Y}) + \tr(\Omega_{\M{y} \M{x}} \M{X}^{\T} \E[\Pi|\mc{D}, \Omega^{(t)}]^{\T} \M{Y})\\ &= -n ( \log \det \Omega + \tr(\Omega \M{S}_{ \E[\Pi|\mc{D}, \Omega^{(t)}]}),\end{aligned}$$ where $\M{S}_{ \E[\Pi|\mc{D}, \Omega^{(t)}]}$ consists of blocks <span>$\M{X}^{\T} \M{X} / n$, $\M{Y}^{\T} \M{Y} / n$, $\M{X}^{\T} \E[\Pi|\mc{D}, \Omega^{(t)}]^{\T} \M{Y}/n$ and $\M{Y}^{\T} \E[\Pi|\mc{D}, \Omega^{(t)}] \M{X}/n$</span>. 2ex <span>**Computational complexity**</span> 1ex We here discuss the computational complexity of Algorithm \[alg:montecarloEM\]. For exponential family models benefiting from the above reduction, the M-step, i.e., the update of $\theta$ only involves $n$ terms, and is hence computationally equivalent to a standard estimation problem. Apart from the initialization of the Markov chain, the approximate E-step has complexity $O(m)$, where $m$ denotes the length of the Markov chain. Computing the acceptance probability, updating $\pi^{(k)}$, and keeping tracking of $\wh{\E}[\Pi | \mc{D}, \theta^{(t)}]^{\T} \M{Y}$ within Algorithm \[alg:MH\] can be done in time $O(1)$ given that the proposal distribution only changes $\pi^{(k)}$ at two positions. However, $m$ is recommended to be at least of the order $\Omega(n)$, heuristically justified by the fact that in the worst case a permutation is the product of $n-1$ transpositions. Obtaining the initial permutation $\wh{\pi}_{\text{init}}$ generally involves the solution of a linear assignment problem, which is costly with a complexity of $O(n^3)$, while approximate solutions via Sinkhorn iterations can be obtained in complexity $O(n^2)$ @COT2019. Alternatively, since computing $\wh{\pi}_{\text{init}}$ based on an LAP is expensive, $\wh{\pi}_{\text{init}}$ can be initialized as the last state of the Markov chain returned by Algorithm \[alg:MH\] in the previous EM iteration $t$, for all EM iterations beyond the first. 2ex <span>**Data augmentation**</span> 1ex Following @TannerWong1987 and @Gutman13, the Monte-Carlo EM approach can be converted into a Bayesian inference procedure targeting the posterior $p(\theta | \mc{D})$, and along the way also $p(\pi | \mc{D})$. Since Monte-Carlo EM already involves sampling from the distribution of $p(\pi | \mc{D}, \theta)$, one can as well sample from $p(\theta | \mc{D}, \pi)$ in an alternating fashion, which can be understood as a specific Gibbs sampler for the joint posterior $p(\theta, \pi | \mc{D})$. Such sampling scheme is particularly attractive whenever it is easy to sample from $p(\theta | \mc{D}, \pi)$. This is the case, e.g., for the Gaussian linear regression setting with conjugate priors for the regression parameter $\beta$ and the error variance $\sigma^2$, as well as for the precision matrix estimation problem for multivariate Normal data described above with an inverse Wishart prior for $\Omega$. Compared to the Monte-Carlo EM approach, sampling from $p(\theta | \mc{D}, \pi)$ has potential advantages from the standpoint of inference (approximate standard errors and construction of credibility intervals). An illustrative example is presented in $\S$\[sec:experiments\]. 2ex <span>**Beyond permutations**</span> 1ex We would like to point out that the framework presented herein does not require $\pi$ to be a permutation. Specifically, we may be given two separate files $\mc{D}_{\M{x}} = \{ \M{x}_i \}_{i = 1}^N$ and $\mc{D}_{\M{y}} = \{ \M{y}_i \}_{i = 1}^n$, $N > n$ (without loss of generality), and the consider maps $\pi: \{1,\ldots,n \} \rightarrow \{1,\ldots,N\}$ with corresponding matrix $\Pi \in \{0,1\}^{n \times N}$ with row sums equal to one. Letting $\mc{P}(n,N)$ denote the set of all such matrices/maps, we can define a prior of the form given a mode $M \in \R^{n \times N}$. Conditional and integrated likelihoods can be defined analogously to and , and the conjugacy property continues to hold. The proposed computational Monte-Carlo EM scheme remains applicable with minor modifications in Algorithm \[alg:MH\], inclusive the reduction for exponential family likelihoods. Theoretical Insights {#sec:theory} ==================== In this section, we present some analysis on the proposed prior from the perspective of regularization. The main purpose of the analysis is to provide additional guidance on the choice of the concentration parameter $\gamma$ in regression problems. 1ex <span>**Hamming prior**</span>. Our first results concerns the MAP estimator of $\Pi^*$ under the Hamming prior . Specifically, we consider the linear regression setup $$\label{eq:gaussianlinear} y_i = \mu_{\pi^*(i)}(\M{x}) + \sigma_* \eps_i, \quad \mu_i(\M{x}) = \M{x}_i^{\T} \beta^*, \quad \M{x}_i \sim N(0, I_d), 1 \leq i \leq n, \quad \{ \eps_i \}_{i = 1}^n \overset{\text{i.i.d.}}{\sim} N(0, 1),$$ as considered in a series of prior works on shuffled linear regression @Pananjady2016 [@Abid2017; @Hsu2017; @SlawskiBenDavid2017]. The statement below considers the sparse setting with the underlying permutation $\pi^*$ satisfying the constraint $\dH(\pi^*, \textsf{id}) \leq k$ for $k$ "small enough" as made precise below. Moreover, it is assumed for simplicity that $\beta^*$ and $\sigma_*^2$ are known; a variety of estimators for the regression parameter in this scenario have been proposed in the literature @SlawskiDiaoBenDavid2019 [@ZhangLi2020; @SlawskiBenDavid2017; @Peng2021]. We recall from $\S$\[subsec:mot\_example\] that = $\nnorm{\beta^*}_2^2 / \sigma_*^2$ denotes the signal-to-noise ratio. \[theo:hamming\] Suppose the setting holds true. Let $\wh{\Pi}$ denote the resulting MAP estimator of $\Pi^*$ with $d_{\emph{\textsf{H}}}(\Pi^*, I_n) \leq k$. Then, if $\gamma \geq 3 \gamma_0$, where $\gamma_0 = 72 \sqrt{\emph{\textsf{SNR}}} \log(en/k)$, the following holds: $$d_{\emph{\textsf{H}}}(\wh{\Pi}, I_n) \leq 2k, \qquad \nnorm{(\wh{\Pi} - \Pi^*)\bm{\mu}}_2 \leq \sigma_* \left(17 \sqrt{k \log(e n / 3k)} + \sqrt{2 \gamma} \right).$$ with probability at least $1-2/n$ and $1 -3/n$, respectively, where $\bm{\mu} = (\mu_i(\M{x}))_{i = 1}^n$. Let us briefly comment on the implications of Theorem \[theo:hamming\]. First, if $\gamma$ is chosen larger than the threshold $\gamma_0$, the MAP estimator $\wh{\Pi}$ will be $2k$-sparse, which matches the sparsity of $\Pi^*$ up to the factor $2$. In particular, the triangle inequality implies that $\dH(\Pi^*, \wh{\Pi}) \leq 3k$, i.e., $\wh{\Pi}$ and $\Pi^*$ will be close with respect to the Hamming distance. Moreover, for values $\gamma$ such that $3\gamma_0 \leq \gamma \leq C \gamma_0$ for some constant $C > 3$, we obtain that $$\nnorm{(\wh{\Pi} - \Pi^*)\bm{\mu}}_2 \lesssim \sigma_* (\sqrt{k \log(en/k)} + \textsf{SNR}^{1/4} \sqrt{k \log(en/k)}),$$ where $\lesssim$ is short for $\leq$ up to constant factors. The dependence on the signal-to-noise ratio is improved compared to the naive estimator $\wh{\Pi}_0 = I_n$, which will scale as $\sigma_* \sqrt{k \log(en/k)} \textsf{SNR}^{1/2}$; note that for small , one cannot hope for improvements over $\wh{\Pi}_0$ in general. On the other hand, in light of the discussion in $\S$\[subsec:mot\_example\], the improvement over the maximum likelihood estimator $\wh{\Pi}_{\text{ML}}$ whose corresponding error scales as $\sigma_* \sqrt{n}$, is rather substantial as long as $k$ is small relative to $n$. 1ex Theorem \[theo:hamming\] provides guidance on the choice of $\gamma$ for a specific setup. To an extent, the next result yields a lower bound on $\gamma$ in order to ensure a pre-scribed level of sparsity $k$. \[prop:conc\_inequality\] Suppose that $\pi$ follows the Hamming prior $p$ with parameter $\gamma$. Then for all $2 \leq k < n$ $$\p_{\pi \sim p}\big(\text{\emph{$\dH$}}(\pi, \textsf{\emph{id}}) \geq k \big) \begin{cases} \leq \exp(-k \delta \log n) \quad & \text{if} \; \gamma \geq (1 + \delta) \log n, \; \delta > 0, \\[1ex] \geq c(k,n) \quad & \text{if} \; \gamma \leq \log (n-k), \end{cases}$$ where $c(k,n) \rightarrow \frac{1}{4} \frac{!k}{k!}$ as $n \rightarrow \infty$, with $!k$ denoting the number of derangements of $k$ elements (i.e., the number of permutations without fixed point). Suppose it is known that $\dH(\pi^*, \textsf{id}) \leq k$. Then Proposition \[prop:conc\_inequality\] asserts that the concentration parameter $\gamma$ of the Hamming prior should be chosen proportional to $\log(n - k) \sim \log n$ as $n$ gets large in order to ensure that the prior places essentially no mass outside the Hamming ball $\{\pi: \, \dH(\pi, \textsf{id}) \leq k \}$. The threshold $\gamma \sim \log n$ is sharp in the sense that if $\gamma \leq \log(n - k)$, the prior will place at least constant mass $\frac{1}{4} !k/k! \sim \frac{1}{4e}$ for not too small $k$ outside that Hamming ball. The likelihood $p(\mc{D}|\pi)$ will favor permutations giving best fit to the observed data, so that the posterior mass $\p_{\pi|\mc{D}}(\{\pi: \, \dH(\pi, \textsf{id}) \leq k \}) $ will generally be less than the prior mass. Consequently, it is natural to consider the lower bound $\gamma \sim \log n$ as a starting point when setting this parameter. 1ex <span>**Local shuffling prior**</span>. The next proposition addresses scenarios similar to that depicted in Figure \[fig:motivation\_local\] when the underlying function is Lipschitz continuous. Specifically, the level of penalty that is needed for the MAP solution to satisfy the bandwidth condition $|\wh{\pi}(i) - i| \leq r$ for all $1 \leq i \leq n$ is provided. \[prop:banded\] Suppose that $y_i = \mu_{\pi^*(i)} + \sigma_* \eps_i$, $1 \leq i \leq n$, with $\{ \eps_i \}_{i = 1}^n \overset{\text{i.i.d.}}{\sim} N(0, 1)$, where $\mu_i = f^*(i/n)$, $1 \leq i \leq n$ for a function $f^*: [0,1] \rightarrow \R$ that is $L$-Lipschitz. Let further the matrix $M$ in the prior have entries $M_{ij} = I(|i - j| \leq r)$, $1 \leq i,j \leq n$, for a given bandwidth $r = \max_{1 \leq i \leq n} |\pi^*(i) - i|$. If $\gamma > \frac{2L}{\sigma^*} \left(\sqrt{\log n} + \sqrt{2} r \right)$, the resulting MAP estimator $\wh{\pi}$ satisfies $|\wh{\pi}(i) - i| \leq r$, $1 \leq i \leq n$, with probability at least $1 - \exp(-(\sqrt{2} - 1)^2/2) - 2/n$. In particular, under the same event, $\max_{1 \leq i \leq n} |\mu_{\wh{\pi}(i)} - \mu_{\pi^*(i)}| \leq 2L \cdot r / n$. Note that while in theory, the assertion of the above proposition can always be achieved by setting $\gamma = \infty$, established solvers of linear assignment problems require the entries of the cost matrix to be finite. In addition, solver accuracy can degrade with the magnitude of the entries @Bernhard2021. Experiments {#sec:experiments} =========== In this section, we present the results of experiments conducted with synthetic and real data. At the end of the section, we also show an example demonstrating the use of the data augmentation approach discussed at the end of $\S$\[subsec:dataproblems\] as an alternative to the Monte-Carlo EM scheme. The `MATLAB` code underlying the results shown herein can be accessed from <https://github.com/bruce1edward/exp_prior_shuffled_data>. 2ex <span>**Synthetic data**</span>. We consider data generation according to the following three models:\ ---------------------------------------- --------------------------------------------------------------------------------------------------------------- Linear Regression (`LR`): $y_{i}|\M{x_{\pi^*(i)}} \sim N(\x^{\T}_{\pi^*(i)}\beta^*, \sigma_*^2)$, $1 \leq i \leq n$, \[1.3ex\] Poisson Regression (`GLM`): $y_{i}|\M{x_{\pi^*(i)}} \sim \text{Poisson}(\exp(\x^{\T}_{\pi^*(i)}\beta^* + \beta_0^*))$, $1 \leq i \leq n$, \[1.3ex\] Multivariate Normal (`MVN`): $\M{z}_{i} = (\M{x}_{\pi^*(i)}, \M{y}_{i}) \sim N(\mu_*, \Omega_*^{-1})$, $1 \leq i \leq n$. ---------------------------------------- --------------------------------------------------------------------------------------------------------------- \ The $\{\x_{i}\}^{n}_{i=1}$ and $\{\epsilon_{i}\}^{n}_{i=1}$ are i.i.d random samples from the $N(0, I_{d})$ and $N(0, 1)$ distributions, respectively. The regression parameter $\beta^*$ is sampled uniformly from the sphere of radius $3$, i.e., the set $\{\beta \in \R^d: \, \nnorm{\beta}_2 = 3\}$, and $\beta_0^* \sim N(0,1)$. For `MVN`, we let $\mu_* = 0$ and $\Omega_*^{-1} = (\tau_* - \rho_*)I_{p+q} + \rho_*\M{1}_{p+q}\M{1}^{\T}_{p+q}$. Finally, $\pi^*$ is a permutation selected uniformly at random from one of the following three constraint sets: $$\begin{aligned} &\text{(i)}\;k\text{-\textbf{Sparse}:}\, \left\{\pi \in \mc{P}(n) : \sum^{n}_{i=1}\mathbb{I}(\pi(i) \neq i) \leq k \right\}, \;\text{(ii)}\;r\text{-\textbf{Banded}:}\, \Big\{ \pi \in \mc{P}(n): \; \max_{1 \leq i \leq n} |\pi(i) - i| \leq r \Big\}, \notag \\ &\text{(iii)}\;k\text{-\textbf{SparseBlock}:}\, \left\{\pi \in \mc{P}(B) : \sum^{n}_{i=1}\mathbb{I}(\pi(i) \neq i) \leq k \cdot B\right\}, \label{eq:experiments_constraints}\end{aligned}$$ where $\mc{P}(B)$ denotes the set of block-structured permutations corresponding to $B$ blocks of uniform size $n/B$, i.e., $\{1,\ldots,n/B \}$, $\{n/B + 1, \ldots, 2\cdot n/B\}, \ldots, \{(B-1) (n/B) +1,\ldots, n \}$. Note that in (i), the number $k$ refers to the number total of mismatches, whereas in (iii) the number $k$ refers to the number of mismatches per block. We fix $n = 1,000$, $d = 20$, $\sigma_* = 1$, $\rho_* = 0.8$, $p = q = 5$, $B = 50$. The mismatch rates $k/n$ and $k \cdot B / n$ in (i) and (iii), respectively, are varied between $0.2$ and $0.5$ in steps of $0.05$, and the bandwidth $r$ in (ii) is varied between $3$ and $10$. For each setup and each value of $k$ and $r$, 100 independent replications are performed. 1ex The following approaches are compared: \(I) . Standard maximum likelihood estimation as used for parameter estimation in the absence of mismatches, which corresponds to fixing $\pi = \textsf{id}$ as the identity permutation. 1ex (II) . The unknown permutation $\pi^*$ is considered as known, and standard maximum likelihood estimation is used for parameter estimation after fixing $\pi = \pi^*$. 1ex (III) \[for setting $k$-<span>**Sparse**</span> only\]. For setup `LR`, the regression parameter is estimated on the `robustfit` function in `MATLAB` @MATLAB:2019. For setup `GLM`, the regression parameter is estimated based on the robust GLM estimation method @wang2020estimation that uses observation-specific dummy variables and penalization. For setup `MVN`, $\Omega_*^{-1}$ is estimated according to the `robustcov` function in `MATLAB` @MATLAB:2019 which implements the minimum covariance determinant estimator in @rousseeuw1999fast. 1ex (IV) , , , . Algorithm \[alg:montecarloEM\] using uniform, Hamming, local shuffling, and block-Hamming prior, respectively, where the latter three reflect the constraint sets (i) to (iii) in . The EM iterations are initialized by setting $\pi = \textsf{id}$, and the number of EM iterations is limited to 400. The number of MCMC iterations per EM iteration is set to 8k, half of which are counted towards the "burn-in period". We note that a modified MH algorithm is used for (cf. Appendix \[app:MH\_local\]); for , the MH scheme in Algorithm \[alg:MH\] is applied block by block. For the <span>**Sparse**</span> and <span>**SparseBlock**</span> settings, the hyperparameter $\gamma$ is chosen based on Proposition \[prop:conc\_inequality\], which suggests $\gamma \propto \log(n)$. For the <span>**Banded**</span> setting, the choice $\gamma = 1$ was found to yield good performance. 1ex (V) , \[for setting $k$ only\]. The approaches described in @Chambers2009 and @Lahiri05 with the choice $Q = \E[\Pi^*] = I_B \otimes Q_{0}$, where $Q_{0} = (1 - \alpha_*) I_{n/B} + \alpha_* \M{1}_{n/B}\M{1}_{n/B}^{\T}$, $\alpha_* = (k \cdot B)/n$. For setup `MVN`, the LL approach amounts to estimation of $\Omega_*$ by the inverse of the modified sample covariance matrix $\wt{S}$ with blocks $\wt{S}_{\M{x}\M{x}} = \M{X}^{\T}\M{X} / n$, $\wt{S}_{\M{x}\M{y}} = \M{X}^{\T}Q^{\T}\M{Y} / n$, and $\wt{S}_{\M{y}\M{y}} =\M{Y}^{\T}\M{Y} / n$. 1ex (VI) \[for setting $r$-<span>**Banded**</span> only\]. We compute (componentwise) running averages of the $\{ \x_i \}_{i = 1}^n$ and $\{ \M{y}_i \}_{i = 1}^n$ within sliding windows of size $r$, and estimate the parameters $\beta^*$ and $\Omega_*$ from these local averages in the usual way (i.e., if these were the original and uncontaminated data). 1ex <span>ccc</span> Hamming **LR** & Hamming **GLM** & Hamming **MVN**\ & & 3ex <span>ccc</span> SparseBlock **LR** & SparseBlock **GLM** & SparseBlock **MVN**\ & & 3ex <span>ccc</span> Local **LR** & Local **GLM** & Local **MVN**\ & & For better comparison across different experimental configurations, we visualize the relative estimation error (REE) $\nnorm{\beta^{\text{est}} - \beta^*}_{2}/\nnorm{\beta^*}_{2}$ and $\nnorm{\text{Corr}^{\text{est}} - \text{Corr}^*}_{\textsf{F}}$ , where $\beta^{\text{est}}$ and $\text{Corr}^{\text{est}}$ are a placeholder for the aforementioned estimators; $\text{Corr}$ refers to the correlation matrix corresponding to $\Omega_*^{-1}$. Selected results are shown in Figure \[fig:sim\], which displays averages of the REE over 100 replications for each model and each permutation. Overall, it can be seen that , , achieve significant improvements over their unregularized counterpart and the other baseline methods under consideration. .5ex <span>lllllll</span> data(abbreviation) & $n$ & $d/p$ & $q$ & model & setting of $\pi$ & $\text{MCMC steps}$\ @SlawskiDiaoBenDavid2019 & 2011 & 2 & & `LR` & $k$ & 2k\ @SlawskiDiaoBenDavid2019 & 93935 & 5 & & `LR` & $k$ & 1.5k\ @SlawskiDiaoBenDavid2019 & 534 & 11 & & `LR` & $k$ & 2k\ @wang2020estimation & 731 & 16 & & `GLM` & $k$ & 1.5k\ @SlawskiBenDavidLi2019 & 335 & 30 & 6 & `MVN` & $k$ & 2k\ @SlawskiBenDavidLi2019 & 8966 & 35 & 16 & `MVN` & $k$ & 4k\ @SlawskiBenDavidLi2019 & 9762 & 5 & 5 & `MVN` & $r$ & 2k\ <span>**Real data**</span>. We consider seven benchmark data sets for shuffled data problems as tabulated in Table \[table:1\]. The data sets are preprocessed versions of their original counterparts. The details of data processing can be found in the corresponding reference provided in Table \[table:1\]. Even though the data sets themselves are real, the permutations that scramble the given matching pairs $\{ (\M{x}_i, \M{y}_i) \}_{i = 1}^n$ are synthetic. Specifically, for each data set, we consider 100 independent random permutations depending on the underlying setting. We consider the same list of competitors and associated configurations as for the synthetic data experiments. Asterisked ground truth parameters here refer to oracle estimates based on knowledge of $\pi^*$, and relative estimation error (REE) is defined accordingly in terms of those (pseudo)-ground truth parameters. <span>ccc</span>\[fig:real\_data\] Hamming ISD & SparseBlock END & Hamming FTP\ & & \ Hamming CPS & SparseBlock BSD & Hamming SCM\ & & <span>**Hamming and Block prior**</span>. As can be seen from Figure \[fig:real\_data\], the proposed approach consistently improves over naive least squares once the fraction of mismatches exceeds 0.2, and yields significant improvements as that fraction increases. The regularized EM approach with specific prior (i.e. , , ) noticeable reduces error induced by shuffling. 1ex <span>**Local shuffling prior.**</span> As shown in the Table \[table: 2\], the EM approach with local shuffling prior achieves significant error reductions compared to the naive approach and the EM approach without regularization. <span>cccc</span> **Methods** & **naive** & **EM** & **EML**\ \ $\nnorm{\text{Corr}^{\text{est}} - \text{Corr}^*}_{F}$ & 0.76 & 1.97 & 0.34\ standard error & 0.0012 & 0.0111 & 0.0010 Data Augmentation {#data-augmentation .unnumbered} ----------------- In this paragraph we present a brief illustration of the proposed approach when used in conjunction with data augmentation, i.e., both the parameter and the permutation are sampled in an alternating fashion (cf. discussion at the end of $\S$\[subsec:dataproblems\]). For this purpose, we consider the Italian household survey discussed in @Tancredi15, see also Table \[table:1\]. This data set involves a simple linear regression problem in which the household income (in 1k Euros) in 2010 is is regressed on the same quantity in 2008, including an intercept term. The process of file linkage subject to mismatch error involving the income data from the two years under consideration is simulated by generating a permutation $\pi^*$ uniformly at random from the Hamming ball of radius $k$ around the identity permutation, where $k/n = 0.4$. Following the paradigm of data augmentation in @TannerWong1987 in which $\pi^*$ is considered as missing data yields the following scheme that alternates between sampling of a permutation $\pi$ and sampling of regression parameters $\beta = (\beta_0, \beta_1)$ and $\sigma^2$ given responses $\M{Y} = (y_i)_{i = 1}^n$ (income from 2010) and design matrix $\M{X} = [\bm{1}_n \; (x_i)_{i = 1}^n]$ (intercept and income from 2008). $$\begin{aligned} {2} &\text{(I) Augmentation Step:} \;\;\, && \text{Sample} \; \pi^{(j)} \text{ from } p(\pi|\M{Y},\M{X}, \beta^{(k-1)}, {\sigma^2}^{(k-1)}), \; \, j = 1, \ldots, m,\\ &\text{(II) Posterior Step:}\;\;\, && \text{(a) Sample } \beta^{(k)} \; \text{from} \; \, \frac{1}{m}\sum_{j=1}^{m}p(\beta|{\sigma^2}^{(k-1)}, \pi^{(j)}, \M{Y},\M{X}), \\ & && \text{(b) Sample} \; {\sigma^2}^{(k)} \text{ from } \;\, \frac{1}{m}\sum_{j=1}^{m}p(\sigma^2|\beta^{(k)}, \pi^{(j)}, \M{Y},\M{X}),\end{aligned}$$ where $m$ denotes the number of samples in the augmentation step, and $k$ denotes the iteration counter for the parameters $(\beta, \sigma^2)$. Sampling in step (I) is
{'source': 'arXiv_out/2111'}