acceptodds
Under review as a conference paper at ICLR 2027

Decentralized Computation of Tyler's -Estimator

Abstract

We study decentralized computation of Tyler's -estimator over a peer-to-peer network. A central difficulty is that the estimator may exist for the pooled data while being undefined at individual nodes, whose local weighted-scatter matrices can be singular. We propose a decentralized majorization–minimization method (D-MM) that combines local weighted-scatter updates with finitely many rounds of neighbor averaging and requires the Tyler existence condition only for the pooled observations. Relative Loewner-order bounds preserve positive definiteness after finite consensus, while Hilbert's projective metric controls both inter-node disagreement and the error caused by heterogeneous local iterates. Under summable consensus errors, all node estimates converge to the pooled Tyler estimator, with explicit finite-step and communication guarantees for polynomial schedules. We further show that, on the determinant-one manifold, the strict occupancy condition induces positive data-dependent geodesic curvature on the invariant region. This yields an instance-dependent linear convergence rate for the unregularized centralized Tyler iteration, sharpening the recent deterministic objective-gap guarantee without regularization. Under geometrically decaying consensus errors, D-MM inherits this contraction and converges linearly. Experiments confirm the predicted effects of communication, network connectivity, and data geometry, and demonstrate agreement with pooled Tyler estimation in a rolling portfolio application.

Primary area:
optimization
Keywords:
Tyler's M-estimator, decentralized estimation, robust shape estimation, majorization--minimization, Hilbert's projective metric

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_urBNOpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies computation of the pooled, unregularized Tyler shape estimator over a synchronous peer-to-peer network. Its motivating setting is that the pooled observations satisfy the strict subspace-occupancy condition, while individual nodes may have insufficient or rank-deficient data and therefore cannot compute local Tyler estimators. The proposed decentralized majorization–minimization algorithm, D-MM, alternates local weighted-scatter computation, finite-round neighbor averaging, and determinant normalization. The analysis uses relative Loewner-order bounds to preserve positive definiteness and Hilbert’s projective metric to control disagreement and heterogeneous local iterates. The paper claims convergence under summable consensus errors, deterministic instance-dependent linear convergence for centralized Tyler iteration, and linear convergence of D-MM under geometrically decaying consensus errors. Experiments examine communication schedules, data geometry, graph topology, and a rolling portfolio application.

Critical strengths
  1. A meaningful decentralized estimation setting.
  2. The geometric tools fit the problem well.
  3. Several empirical and interpretive choices are careful.
Critical weaknesses
  1. The experiments do not establish the algorithm’s advantage over alternative ways to compute the same pooled estimator
  2. Essential experimental settings—and the motivating locally singular regime—are not sufficiently documented in the main text
  3. The stopping criterion does not reliably certify estimator accuracy
  4. The portfolio study supports numerical agreement, but its reproducibility and practical interpretation are limited
Questions for authors
  1. How do you ensure that the iterate-difference stopping criterion does not terminate prematurely on nearly degenerate datasets? What are the final estimator errors, rather than only step sizes, in the reported runs?
  2. How does D-MM compare with an exact aggregation implementation or accelerated/adaptive consensus at matched pooled-Tyler accuracy? What is included in the round and byte accounting, and how is global termination detected?
2 comments

Thank you for the constructive comments.

Experimental settings and locally singular data. Appendix H.2 details the data allocation, network, and communication schedules. In the default feasibility experiment, d=10d=10, N=50N=50, and m=8m=8. Under the balanced partition, each node receives 6 or 7 samples, fewer than the dimension. In the one-sample-per-node experiment, we instead use N=m=12N=m=12, so each node receives exactly one sample. Consequently, every local weighted-scatter matrix is singular in both settings.

We will highlight these settings and their connection to the locally singular regime in the main text.

Stopping criterion and estimator accuracy. The threshold 10−710^{-7} applies to the maximum successive-iterate difference across nodes. It is a practical stopping criterion and is not claimed to be a 10−710^{-7} bound on the distance to the pooled Tyler estimator. This distinction also arises in centralized Tyler estimation: a small change between successive iterates does not generally imply an equally small distance to the exact solution. Stopping based on iterate changes is common in practice; for example, the centralized Tyler estimator in the R package fitHeavyTail uses a relative tolerance on parameter changes and a maximum iteration limit.

We will report final distances to the pooled Tyler reference separately from the stopping threshold, distinguishing runs that satisfy it from those reaching the iteration limit. For example, in the one-sample-per-node experiment, the maximum-node affine-invariant distance to the pooled reference has a median of 3.88×10−63.88\times10^{-6} and a maximum of 6.37×10−66.37\times10^{-6} across 100 runs.

Comparison with alternative communication methods. Our objective is to study whether and how the pooled Tyler estimator can be computed through finite-round neighbor consensus when individual nodes may not have enough data to form local Tyler estimators. The contribution is the D-MM construction and its convergence analysis under controlled consensus errors; we do not claim that D-MM is more communication-efficient than all alternative approaches.

Exact tree aggregation is a useful comparator for the same estimation task, but it follows a different communication architecture: it collects and broadcasts aggregated quantities over a designated spanning tree, whereas D-MM uses a prescribed neighbor-mixing matrix without an aggregation root. Tree aggregation requires the selection and construction of a spanning tree, which may also need to be maintained or repaired as the network changes. D-MM avoids maintaining such a tree. More broadly, gossip-based aggregation has been studied as a decentralized approach for dynamic distributed systems; see, for example, Kempe, Dobra, and Gehrke (2003).

The neighbor-consensus framework also provides a natural basis for extensions to randomized neighbor selection and asynchronous communication, as studied in the gossip literature. Accelerated or adaptive consensus is another direction for extending the consensus step. By establishing convergence for D-MM with standard consensus, our work provides a foundation for adapting the algorithm and analysis to such variants. We expect these to be natural follow-up extensions, with the precise conditions depending on the chosen protocol. A matched-accuracy comparison with these variants is beyond the current experiments.

Communication accounting and termination. The reported D-MM communication rounds count neighbor-averaging rounds. In each round, every directed edge transmits one symmetric d×dd\times d matrix, corresponding to d(d+1)/2d(d+1)/2 scalars. The global stopping condition is evaluated in the simulation by taking the maximum iterate change over all nodes.

Portfolio experiment. Appendix G documents the data and experiment setting. We use publicly available value-weighted monthly returns from the Fama–French 49-industry dataset, specifying the 202607 CRSP data vintage and download date. We select the first 30 industries with complete observations from January 1970, use a 120-month rolling training window, center each window by its training mean, and evaluate the resulting portfolios over the 559 months from January 1980 to July 2026. The appendix also specifies the network, communication schedule, stopping criteria, and no-short-sales portfolio construction.

The purpose of this experiment is to assess whether the numerical agreement between D-MM and pooled Tyler carries over to a downstream portfolio task. It is not intended to establish superior investment performance. We will make this purpose and the location of the reproducibility details clearer in the main text.

Dear Reviewer urBN,

Thank you again for your detailed comments. In our response above, we distinguished the stopping threshold from estimator accuracy, provided final errors for the one-sample-per-node experiment, and clarified the communication accounting and the scope of our experimental comparisons. We would appreciate your feedback on these points, particularly whether any concerns about the stopping criterion or accuracy assessment remain. We would welcome your perspective on the remaining limitations.

Reviewer_EdHtOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to compute Tyler’s M-estimator across a network using only communication between neighboring nodes. Each node computes a partial matrix from its own observations and exchanges it with its neighbors, and importan point is that some nodes can have few samples to compute a local estimator, and all nodes still converge to the pooled estimate as long as the combined data satisfy Tyler’s existence condition. The authors also prove an instance-dependent linear convergence rate for the unregularized Tyler iteration and show that the decentralized method converges linearly when communication errors decrease geometrically.

Critical strengths
  • The paper studies an interesting and theoretically meaningful problem.
  • The paper provides a consistentt connection between data geometry, centralized contraction, and communication errors.
  • nodes do not need enough samples to compute their local estimator. Some can even have no samples, and all nodes still converge to the pooled estimate as long as the combined data satisfy Tyler’s existence condition. This is useful when data are unevenly distributed across the network.
Critical weaknesses
  • The introduction is currently hard to follow because key terms are used before they are defined. Improving the clarity and introducing definitions earlier would make the paper much easier to understand.
  • Franks and Moitra used a related approach to prove the convergence and the theorems. Since this is a theoretical paper and authors main claim rests on that theory, Please clearly show how analysis differs from theirs. This distinction is crucial since central theorem is the paper's main point. -The comparison with Cederberg (2026) is a bit vague. Explanation of what new argument boosts the unregularized rate from O(1/k)O(1/k) to an instance-dependent linear rate could be useful.
Questions for authors
  • What is the main technical novelty beyond Franks and Moitra’s work?
3 comments

We thank the reviewer for the thoughtful evaluation and constructive suggestions. We appreciate the reviewer’s comments on the clarity of the introduction and the connection between data geometry, centralized convergence, and communication. The questions about Franks and Moitra (2020) and Cederberg (2026) also help us identify where the manuscript should explain our technical contribution more clearly.

Clarity of the introduction. We will revise the introduction so that the motivation leads more naturally to the problem formulation and the main contributions. We will define key terms when they first appear and explain how the centralized result enters the decentralized convergence analysis.

Comparison of our result with Franks and Moitra (2020). Franks and Moitra identify the strict subspace-occupancy condition (Assumption 1 in our paper) as the criterion for existence and uniqueness up to scale in their Theorem 2.1. Their high-probability linear convergence in Theorem 1.3 requires more than Assumption 1 alone: they assume elliptical sampling and impose the additional sample-size requirement N≥Cdlog⁡2dN\geq C d\log^2 d.

Our deterministic linear convergence guarantee applies to every fixed dataset satisfying Assumption 1, with no distributional assumption or additional sample-size requirement. For example, under the same elliptical sampling model, Assumption 1 holds almost surely as soon as N>dN>d, so our result applies even at N=d+1N=d+1.

Main technical novelty beyond previous work. Franks and Moitra (2020) use quantum expansion to obtain the geometry needed for fast convergence and show that the required expansion holds with high probability under their sampling model. This sampling assumption limits the scope, since real data may come from non-elliptical distributions. Our analysis derives a positive curvature bound directly from Assumption 1 for the observed dataset. In this respect, our approach is closer to the optimization analysis of Cederberg (2026), whose Theorem 1 combines geodesic convexity and descent to obtain a deterministic O(1/k)O(1/k) objective-gap bound for the unregularized iteration.

A difficulty in obtaining a linear rate is that the objective is constant along every ray: G(cΣ)=G(Σ)G(c\Sigma)=G(\Sigma) for all c>0c>0. Its curvature therefore vanishes in the scale direction, precluding a positive curvature lower bound on the full positive definite cone. We exploit the fact that determinant normalization confines our iterates to the determinant-one manifold and removes this flat direction. The additional step is to show that the strict subspace-occupancy condition (Assumption 1) rules out zero curvature in every remaining tangent direction. Compactness then yields a uniform positive curvature lower bound μR0>0\mu_{R_0}>0 on the region containing the iterates. Combined with the descent bound for the Tyler update, this gives Δk+1≤(1−μR0/d2)Δk\Delta_{k+1}\leq(1-\mu_{R_0}/d^2)\Delta_k, where Δk\Delta_k denotes the objective gap. Thus, under the same data condition as in Cederberg (2026), we strengthen the sublinear bound to an linear rate.

Dear Reviewer EdHt,

Thank you again for your constructive comments. In our response above, we clarified how our deterministic, linear convergence result differs from the results of Franks and Moitra and Cederberg. We would appreciate knowing whether this addresses your question about the main technical novelty, or whether any part of the distinction remains unclear. We would be happy to provide further clarification.

This clarification resolves my main concern about the paper’s technical contribution, and I am raising my recommendation to weak accept. I encourage the authors to include this comparison in the revised introduction.

Reviewer_WiMSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

In "Decentralized computation of Tyler's M-estimator" the authors provide an algorithm to compute the estimator over a peer-to-peer network where the pooled observations satisfy the conditions required for the existence and uniqueness of the estimator but local data sets need not satisfy these conditions.

The proposed method D-MM (decentralized majorization-minimization) has agents compute local weighted-scatter matrices and perform multiple rounds of consensus to approximate the centralized Tyler update. The analysis uses relative Loewner-order perturbation bounds and Hilber'ts projective metric to establish positive definiteness and convergence.

The paper establishes convergence to the pooled estimator under summable consensus errors. Under geometrically decreasing errors, the decentralized method converges linearly. Numerical experiments illustrate the performance of the method.

Critical strengths
  1. No local identifiability requirement: The proposed method requires the pooled observations to satisfy the strict subspace-occupancy condition but does not require it to hold at each agent. Other works have dealt with decentralized problems under similar assumptions: namely for high-dimensional sparse regression and matrix sensing. Some additional references could be added in that regard.
  2. Convergence analysis for the centralized estimator: the instance dependent linear convergence result for the centralized Tyler iteration is potentially useful compared to the existing sub-linear convergence result.
Critical weaknesses
  1. Limited algorithmic novelty: the proposed decentralized method follows a relatively standard strategy. The resulting algorithmic design does not appear to introduce a fundamentally new decentralized optimization principle.
  2. Communication requirements weaken the significance of linear convergence: in many cases communication is a principal resource in decentralized computation, therefore, requiring an increasing number of communication rounds substantially limits the practical significance of the linear rate claim.
  3. Theoretical contribution is specialized: Much of the analysis is devoted to controlling the perturbation introduced by approximate consensus and transferring convergence properties of the centralized algorithm to the distributed setting. The broader methdological significance of these results is not sufficiently clear.
Questions for authors

I encourage the authors to address the weaknesses identified above, particularly those concerning the limited algorithmic novelty and the communication efficiency of the proposed method.

2 comments

Thank you for your careful review and for highlighting the value of computing the pooled Tyler estimator when local estimates may not exist. We appreciate your questions about the algorithmic contribution, the communication cost of the linear rate, and the broader applicability of our analysis.

Novelty. We agree with the reviewer that local updates and neighbor averaging are standard ingredients in decentralized optimization. We deliberately chose this simple architecture for computing the pooled Tyler estimator. Applying the centralized fixed-point iteration locally, however, is not straightforward. The pooled data may satisfy the strict subspace-occupancy condition even when an individual node’s data do not, in which case a positive definite local Tyler fixed point need not exist. D-MM therefore aggregates the local weighted scatters through neighbor averaging before normalization. Starting from a common positive definite estimate, we prove that finitely many consensus rounds satisfying the relative mixing condition yield a positive definite update at every node.

Our main contribution is a convergence guarantee for this setting, without requiring local Tyler estimators to exist. Theorem 4.1 uses relative Loewner bounds and Hilbert’s projective metric to establish positive definiteness and control the deviation of each node’s update from a centralized Tyler step. Under summable consensus errors, all node iterates remain in a common compact region bounded away from singularity. Combined with the descent property of the centralized Tyler iteration, these bounds yield convergence of every node to the pooled estimator.

A further contribution is a deterministic linear convergence guarantee for the unregularized centralized Tyler iteration. We discuss this result and its implications below.

Linear convergence and communication cost. We first establish a linear convergence rate for the unregularized centralized Tyler iteration, providing a direct theoretical improvement over the previously established deterministic rate. Under the strict subspace-occupancy condition, Cederberg (2026, Theorem 1) proves an O(1/k)O(1/k) objective-gap bound. Under the same data condition, we strengthen this guarantee to an linear contraction of the objective gap. Our analysis shows that, after determinant normalization removes the scale direction, the objective has a positive curvature lower bound on a compact region containing the iterates.

We then analyze how this centralized contraction carries over to D-MM under geometrically decreasing consensus errors. We agree with the reviewer that the practical significance of the decentralized linear rate depends on communication cost. For a fixed problem instance, the geometric schedule reaches an objective gap of ε\varepsilon within O(log⁡(1/ε))O(\log(1/\varepsilon)) outer iterations, with an O(log⁡2(1/ε))O(\log^2(1/\varepsilon)) upper bound on the total number of communication rounds.

We do not claim that the geometric schedule with its linear guarantee is practically superior to the polynomial schedule with its sublinear guarantee. We include both schedules in the paper because each has advantages in different accuracy regimes. Consistent with the reviewer’s concern, our experiment shows that the polynomial schedule can reach moderate accuracy with fewer communication rounds, while the geometric schedule attains a smaller residual in the high-accuracy regime. We will emphasize this accuracy–communication trade-off more clearly in the revised paper.

Broader applicability. Although our paper focuses on Tyler’s estimator, our analysis can be extend to a broader class of Maronna-type scatter MM-estimators. These estimators satisfy a weighted-scatter fixed-point equation of the form

Σ=1N∑s=1Nu(xs⊤Σ−1xs)xsxs⊤.\Sigma=\frac{1}{N}\sum_{s=1}^{N}u\left(x_s^\top\Sigma^{-1}x_s\right)x_sx_s^\top.

Tyler’s estimator uses u(t)=d/tu(t)=d/t. Other examples include the Student-tt estimator with u(t)=(ν+d)/(ν+t)u(t)=(\nu+d)/(\nu+t) for ν>0\nu>0, and Huber-type estimators with u(t)=min⁡a,b/tu(t)=\min \\{a,b/t\\} for suitable a,b>0a,b>0.

These updates share the property that each observation contributes a positive multiple of xsxs⊤x_sx_s^\top. Thus, whenever the pooled observations span Rd\mathbb{R}^d, the contributions sum to a positive definite matrix even if each node’s contribution is singular. Under the same relative mixing condition, our argument then guarantees a positive definite update at every node after finitely many consensus rounds. This extends the feasibility result to the broader family. Convergence rates depend additionally on the chosen weight function and the associated centralized iteration.

Dear Reviewer WiMS,

Thank you again for your careful review. We would appreciate your feedback on our response above, particularly our clarification of the contribution beyond standard consensus methods and the distinction between the linear convergence rate and the total communication cost. Could you let us know whether these clarifications address your concerns, or which points would benefit from further explanation? We would be happy to discuss any remaining questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.