- 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 also contains a term proportional to . When the tensor order and the mode dimensions are large, this dimensional dependence may substantially restrict the applicability of the theoretical guarantees. For example, when , this term scales as , whereas the intrinsic degrees of freedom of the shared Tucker model are primarily determined by and .
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 , 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?
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:
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.