Two-Way Sparse Reduced-Rank Regression via Scaled Gradient Descent with Hard Thresholding

This paper addresses the problem of two-way sparse reduced-rank regression (TSRRR), which aims to estimate a coefficient matrix that is both low-rank and two-way sparse (sparse in both rows and columns) within a multiple response linear regression model. We formulate TSRRR as a nonconvex optimization problem and propose an efficient, scalable iterative algorithm called Scaled Gradient Descent with Hard Thresholding (ScaledGDT) to solve it. We demonstrate that the iterates obtained by ScaledGDT converge linearly to a region within the statistical error of the ground truth, and this convergence rate is independent of the condition number of the coefficient matrix. Furthermore, we prove that the statistical error rate achieved by ScaledGDT is nearly minimax optimal. Experimental results confirm our theoretical findings and showcase the competitive performance of ScaledGDT.

I. Introduction

We begin by describing the general multiple response linear regression model [1], of which the two-way sparse reduced-rank regression (TSRRR) model is a special case. Let denote the sample size, the number of predictors, and the number of responses. We observe a pair of matrices and X from the linear model:

$$\begin{equation*}\mathrm{Y}=\text{XC}_{*}+\mathrm{E},\tag{1}\end{equation*}$$ where is the response matrix, X is the design matrix, is the unknown coefficient matrix to be estimated, and is an unobserved matrix with i.i.d. noise entries.