acceptodds
Under review as a conference paper at ICLR 2027

Communication-Efficient Distributed Multilinear Multitask Learning

Abstract

In multi-task learning (MTL), the parameter of each task is often multidimensional and exhibits high-order intra-task relatedness. Meanwhile, multiple multidimensional parameters in MTL naturally induce the multi-way inter-task relatedness. This paper proposes a distributed multilinear MTL method that models these two types of relatedness through a shared multilinear representation, which models the parameter of each task through mode-wise factors shared across tasks and a task-specific core tensor. We instantiate our method for the multi-task high-dimensional tensor linear regression (MTTLR) problem. A two-stage communication-efficient distributed method, termed D-AltMin-PGD, is developed to minimize the induced non-convex loss to jointly learn the models. For the Gaussian input and additive noise, we prove that from initialization via the proposed distributed power-iteration, D-AltMin-PGD converges linearly to a statistical neighborhood of truth parameters despite nonconvexity. The resulting statistical error separates into a shared-factor term that benefits from the samples across all tasks and a task-specific core term determined by the per-task samples, thereby establishing a provable multi-task gain. We further propose a preconditioned variant, D-AltMin-P2GD, to accelerate convergence in ill-conditioned regimes with negligible extra communication cost. Finally, we establish minimax lower bound for proposed MTTLR under Gaussian input and noise. Extensive experiments validate our theoretical results and demonstrate the efficiency of the proposed method.

Primary area:
optimization
Keywords:
Tensor Regression, Multi-task Learning, Shared Representation Learning, Communication-Efficient Distributed Learning, Nonconvex Optimization, Statistical Learning Theory

Reviews

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

This paper investigates distributed multi-task tensor linear regression under a shared multilinear representation. The authors assume that the parameter tensors across different tasks admit a shared Tucker decomposition structure, where multiple tasks share low-dimensional factor matrices along each mode while retaining their own task-specific core tensors.

To address the nonconvex optimization problem arising from this parameterization, the authors propose a two-stage algorithm, D-AltMin-PGD, which combines distributed spectral initialization with alternating minimization and projected gradient descent. They further develop a preconditioned variant, D-AltMin-P2GD, to improve convergence under ill-conditioned settings.

On the theoretical side, the authors establish that, under Gaussian designs and noise, appropriate initialization, and sufficient sample sizes, the proposed methods achieve linear convergence to a neighborhood of the true parameters determined by statistical estimation error. They also derive corresponding statistical error upper bounds and a minimax lower bound. These results indicate that the estimation error of the shared factors decreases as the number of tasks increases, whereas the estimation error of each task-specific core tensor remains primarily determined by the sample size of the corresponding task.

Critical strengths

1. The theoretical analysis and algorithmic development are relatively comprehensive.

The paper involves a considerable degree of technical complexity. The authors integrate shared Tucker parameterization, distributed spectral initialization, alternating minimization, and preconditioned gradient descent into a unified distributed optimization framework. They also provide a systematic analysis of initialization accuracy, local linear convergence, statistical estimation error, and communication complexity. In particular, compared with conventional linear shared representations, multilinear representations involve multiple coupled shared factors, which introduce additional technical challenges in the analysis of nonconvex optimization.

2. The theoretical results explicitly characterize the benefits of multi-task learning in terms of sample complexity and statistical accuracy.

According to Theorem 2, under appropriate initialization, SNR, and other technical conditions, when the number of samples used by each task in a single optimization round satisfies $ m\gtrsim \frac{\mu^2\kappa^4Nd_{\max}r_{\max}^2}{K} +\prod_{n=1}^{N}r_n, $ the authors establish linear convergence to a neighborhood determined by statistical estimation error. Furthermore, the minimax lower bound established in Theorem 4 exhibits a similar dependence on problem dimensions and multi-task scaling to the statistical error upper bounds, providing additional theoretical justification for the benefits of multi-task learning.

Critical weaknesses

The SNR and sample complexity requirements for spectral initialization appear restrictive, and their relationship to the intrinsic statistical difficulty of the problem remains unclear. This is my primary concern about the paper.

Theorem 1 provides sufficient SNR conditions for the proposed distributed spectral initialization algorithm. One of the main terms takes the form $ \mathrm{SNR} \gtrsim \frac{ N\kappa^2\sqrt{r_{\max}} \left(\sqrt{\prod_{n=1}^{N}d_n}+d_{\max}\right) }{ m_0\sqrt K }. $ In addition, the sufficient condition on the initialization sample size m0m_0 also contains a term proportional to ∏n=1Ndn\sqrt{\prod_{n=1}^{N}d_n}. When the tensor order N≥3N\geq 3 and the mode dimensions are large, this dimensional dependence may substantially restrict the applicability of the theoretical guarantees. For example, when d1=⋯=dN=dd_1=\cdots=d_N=d, this term scales as dN/2d^{N/2}, whereas the intrinsic degrees of freedom of the shared Tucker model are primarily determined by ∑ndnrn\sum_n d_nr_n and K∏nrnK\prod_n r_n.

On the other hand, the dimensional structure of the minimax lower bound in Theorem 4 is mainly characterized by the degrees of freedom associated with the shared factors and task-specific core tensors, and its SNR assumptions differ substantially from those required in Theorem 1.

Although Theorem 4 does not directly establish the existence of a computationally efficient estimator under weaker SNR conditions, this discrepancy raises an important question: Is the relatively strong dimensional dependence in Theorem 1 an inherent limitation of the proposed second-moment-based spectral initialization method, or does it arise from looseness in the current concentration analysis?

I believe the authors should discuss this issue more thoroughly to clarify the applicability and limitations of the spectral initialization method in high-dimensional, low-SNR regimes.

Questions for authors

1. On the SNR and initialization sample complexity requirements in Theorem 1.

Both the SNR and sample complexity conditions in Theorem 1 involve terms related to ∏n=1Ndn\sqrt{\prod_{n=1}^{N}d_n}, whereas the minimax lower bound in Theorem 4 primarily reflects the intrinsic degrees of freedom of the shared Tucker model. Could the authors further clarify the main technical difficulties responsible for this discrepancy? In particular, is it related to the construction of the second-moment estimation matrix and the spectral-norm concentration analysis used in the current proof?

Would it be possible to reduce this dependence on the ambient dimensions by employing more refined statistical estimation techniques or alternative spectral initialization strategies?

Furthermore, do the authors believe that this discrepancy suggests a potential statistical-computational gap, or does it primarily reflect the fact that the current analysis has not yet achieved sharper sufficient conditions?

2. On the total sample complexity of the entire optimization procedure.

The convergence guarantees in Theorems 2 and 3 rely on the use of fresh samples. Could the authors further clarify the total sample complexity of the proposed algorithms when accounting for both the initialization stage and the data consumed across all subsequent optimization iterations, given the number of iterations required to reach the final statistical error level?

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

The paper studies distributed multi-task tensor linear regression with a Tucker parameterization: each task tensor shares mode-wise factor matrices and has a task-specific core, preserving intra-task multi-way structure and inter-task subspaces. It proposes distributed spectral initialization, alternating minimization with projected gradient descent, and a preconditioned variant, and proves linear convergence, statistical recovery, a multi-task sample-complexity gain, and a minimax lower bound. Experiments cover synthetic data, HSI/MRI compressed sensing, and CelebA classification.

Critical strengths

1 The Tucker-based formulation is well motivated and non-trivial: shared mode-wise factors plus task-specific cores preserve high-order intra-task structure while enabling inter-task sharing. This is consequential because it makes the multi-task gain a genuine multilinear effect rather than a vectorized add-on, and it underpins the paper's main theoretical claims.

2 The paper provides an unusually complete theoretical package—distributed spectral initialization, non-convex convergence, statistical recovery, communication cost, and a minimax lower bound—and the preconditioned variant removes the condition-number dependence at limited communication cost. This is consequential because it turns a natural but non-convex multi-task model into an end-to-end analyzable method.

Critical weaknesses

1 Assumption 1 imposes (\max_{k} |\mathcal{X}k^\star|F \le \mu \sigma{\max}^\star \sqrt{r{\max}/K}). With (\sigma_{\max}^\star) constant, each task's signal decays as (1/\sqrt{K})—the same normalization that produces the (1/\sqrt{mK}) shared-factor rate and the claimed sample-complexity gain. The paper does not clarify how (\sigma_{\max}^\star) scales with (K) when each task has constant signal magnitude; if the gain disappears under that scaling, the central theoretical claim is weakened.

2 The empirical comparisons do not isolate the benefit of the multilinear structure: HSI uses (r_1=r_2=50) vs (r\in{2,3}) for the baselines, MRI uses (r_1=r_2=19) vs (r\in{4,16}), and CelebA trains a Tucker head end-to-end rather than the proposed optimization algorithms. Larger capacity and a different training protocol can explain the gains, so parameter-matched comparisons, rank-tuning protocols, error bars, and wall-clock measurements are needed.

3 Overall, the paper is theoretically solid, but these issues currently place it below the acceptance threshold; I would reconsider if the scaling and matched comparisons are addressed.

Questions for authors

1 How does (\sigma_{\max}^\star) scale with (K) in Assumption 1? If each task has a constant signal norm independent of (K), how do Theorem 2 and the lower bound in Theorem 4 change?

2 Does Table 1's sample complexity include the (\log(1/\epsilon)) factor from sample splitting over (T_1) iterations, and is it reported per iteration or as a total per-task budget?

3 Can you provide parameter- or rank-matched HSI and MRI comparisons, with (m_0), (m), (T), and error bars over multiple trials?

4 How stable is the matrix inversion in the preconditioned update when the true cores are severely ill-conditioned or the noise level is high?

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

This paper studies multi-task tensor linear regression (MTTLR) in a distributed setting, where K tasks each have an order-N tensor parameter observed through Gaussian linear measurements, with each task's data held at a separate location. To capture both intra-task (mode-wise) structure and inter-task relatedness, the authors model all task parameters with a shared Tucker representation: common mode-wise factor matrices across tasks and a task-specific core tensor per task. They propose D-AltMin-PGD, a two-stage communication-efficient algorithm — distributed power iteration on an aggregated second-moment matrix for spectral initialization, followed by alternating exact local updates of the cores and server-side projected gradient updates of the shared factors — and a preconditioned variant, D-AltMin-P2GD, intended to remove the condition-number dependence of the convergence rate at negligible extra communication. Theoretically, under Gaussian designs and noise, the authors prove linear convergence to a statistical neighbourhood whose error separates into a shared-factor term improving as 1/sqrt(mK) and a task-specific core term scaling as 1/sqrt(m), and they establish a minimax lower bound with the same two terms, arguing near-optimality of the proposed methods.

Validation is mainly on synthetic data, showing linear convergence, the predicted benefit of preconditioning under larger condition numbers, decreasing estimation error with more tasks (with saturation, as predicted), and phase transitions for exact recovery in the noiseless setting. The appendix adds comparisons with MTLR and MTTPR on synthetic data, hyperspectral (CAVE) and MRI compressed-sensing recovery, robustness checks for sample reuse and model misspecification, and a CelebA multi-task classification experiment using the shared Tucker representation as the classification head.

Critical strengths
  1. A complete and coherent theory for shared-Tucker multi-task learning. The paper does not stop at an algorithm: for the same model it provides a guaranteed distributed spectral initialization (Theorem 1), linear convergence to a statistical neighbourhood for D-AltMin-PGD (Theorem 2), a preconditioned variant (Theorem 3), and a minimax lower bound with the same two-term structure (Theorem 4). The resulting decomposition — a shared-factor error term that improves as 1/sqrt(mK) and a task-specific core term that scales only as 1/sqrt(m) — is consequential because it precisely characterizes when joint learning helps and when the gain must saturate, rather than merely asserting a multi-task benefit; the experiments show exactly this saturation as K grows (Fig. 3).

  2. The algorithm is genuinely designed around communication cost, not just analysed for it. Initialization uses distributed power iteration on the aggregated moment matrix, communicating O(sum_n d_n r_n) entries per round instead of the O(sum_n d_n^2) that a centralized eigendecomposition would require, and each alternating-minimization round communicates only factor gradients and the updated factors. The preconditioned variant D-AltMin-P2GD is a concrete payoff of this design: preconditioning by (S_(n) S_(n)^T)^{-1} costs only O(sum_n r_n^2) extra entries per round, yet removes the condition number from the convergence rate, which the experiments support across kappa in {1,2,4} (Figs. 1 and 5). This matters because ill-conditioning and communication are the two practical bottlenecks for distributed tensor methods, and the paper addresses both within one method.

Critical weaknesses
  1. The efficiency claims are not established under total-cost accounting, and the analysed algorithm is not the one implemented. The theory requires fresh samples at every iteration (Remark 1; Algorithm 2), handled in Sec. 5.4 by sample splitting, which reduces the per-iteration batch to m/m_2 — so the stated rates are not simultaneously achievable at the stated total sample size and iteration count. The experiments instead reuse the same samples throughout (Sec. 6), and the paper's own comparison (Appendix B.1.2, Table 2) shows reuse is materially worse: it fails to reach the target accuracy within 2500 rounds at m=30 and m=32 where fresh sampling succeeds, and needs roughly 6–10x more rounds when both succeed (535 vs. 51 rounds at m=35). In addition, the initialization cost is substantial — m_0 contains a term proportional to kappa^8 (Theorem 1, Eq. (10)), and m_0=400 in the experiments is 4x the per-iteration m=100 — yet Table 1's comparison excludes it, and "communication efficiency" is reported per round while the method uses hundreds to thousands of synchronous rounds. This is consequential because communication/sample efficiency is the paper's headline claim: as presented, it rests on per-iteration, per-round accounting rather than the total cost of reaching a target accuracy.

  2. The empirical validation does not isolate the proposed method, and the theory's scope is narrower than the claims suggest. All main-text experiments are small synthetic settings (N=3, d=20, r=2, K=50) with no baseline method; baselines appear only in the appendix. There, the real-data comparisons appear capacity-confounded: on the hyperspectral data the proposed method uses core dimensions r_1=r_2=50 while the baselines' rank is tuned over r=2,3 (Appendix B.2.3), so the large PSNR gaps (e.g. 41.92 vs. 31.72 on Balloons) may reflect model capacity rather than the algorithm; the MRI comparison has the same issue in milder form (r=19 vs. r=4,16, with only two frames shown), and the CelebA experiment tests the Tucker head trained with AdamW, not the distributed algorithm. At the same time, the guarantees require exactly shared mode-wise subspaces, known ranks, Gaussian designs and noise, and cross-task balancedness (Assumption 1), with near-optimality shown only for kappa, mu = O(1) (Sec. 5.4) — so none of the guarantees cover the misspecified real-data settings used for validation. This is consequential because, without parameter-matched comparisons and at least one larger-scale controlled experiment, the reader cannot tell how much of the reported gain comes from the method versus the model class and its capacity.

Questions for authors

Clarification requests (answers could materially affect my assessment):

  1. Total cost accounting. For one representative synthetic setting, can you report the total samples consumed (including the initialization samples m_0 and, for the theory version, all fresh per-iteration batches) and the total communicated bytes (rounds x bytes per round, for both stages) needed for D-AltMin-PGD / D-AltMin-P2GD to reach a fixed target accuracy (e.g. Err <= 1e-3), with MTLR and MTTPR measured under the same accounting? Does the ordering in Table 1 survive under total rather than per-iteration / per-round accounting?

  2. Sample reuse. The guarantees require fresh samples at every iteration, while the experiments reuse samples. Is any guarantee available for the reused-sample version actually implemented, or, failing that, at the (m_0, m) used in Figs. 1–3, what are the success/failure rates of the reuse version across random seeds (cf. Table 2, where reuse fails at m=30, 32 within 2500 rounds)?

  3. Real-data comparisons. What are the parameter counts of each method in the hyperspectral and MRI experiments, and how do the results change if the baselines are given rank budgets matching the proposed method in parameter count (r_1=r_2=50 for HSI; r_1=r_2=19 for MRI)? This determines whether the reported gains reflect the algorithm or model capacity.

  4. Preconditioner in practice. Is (S_(n) S_(n)^T)^{-1} in D-AltMin-P2GD ever regularized or pseudo-inverted in the implementation, and what is its condition number along the trajectory (e.g. for the kappa=4 runs)? Algorithm 2 applies it from the first iteration, when the stacked cores may be ill-conditioned.

Suggestions for future work (would not change my assessment of this submission):

  1. Rank selection and heterogeneity: a data-driven way to choose or validate the ranks {r_n}, sensitivity to rank misspecification, and experiments with unequal per-task sample sizes m_k or unequal noise levels would broaden the practical relevance beyond the exactly-shared, known-rank, homogeneous setting analysed here.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Our Rebuttal and Discussion

Dear Reviewers and Area Chairs,

As the author–reviewer discussion period comes to an end, we sincerely thank all reviewers and Area Chairs for their time and constructive feedback.

During the rebuttal, we have made substantial efforts to address the reviewers' concerns. Specifically, we have:

  1. Clarified Assumption 1 and the theoretical multi-task gains.
  2. Provided total sample and communication costs, including initialization and optimization.
  3. Conducted additional parameter-matched experiments, reporting error bars over 10 trials and wall-clock times.
  4. Clarified the initialization requirements, sample reuse limitations, and numerical stability of the preconditioner.

We appreciate Reviewer 4vVx's confirmation that our responses addressed their main concerns, and Reviewer VcbT's acknowledgment that most concerns were satisfactorily addressed.

We have also provided detailed responses to Reviewer sDuL's concerns regarding scaling and matched comparisons. We understand the considerable time and effort involved in reviewing and hope our clarifications and additional results will be helpful in the final assessment.

The corresponding revisions are highlighted in blue in our updated manuscript. Thank you again for your time and consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.