GL-LowPopArt: A Nearly Instance-Wise Minimax-Optimal Estimator for Generalized Low-Rank Trace Regression

We sincerely thank the reviewer for providing detailed and insightful reviews, and we are especially encouraged by your overall positive evaluation of our paper. Let us respond to each point that you have raised.

Discussions regarding Burer-Monteiro Factorization (BMF) Approach

Thank you for pointing us to the references on the BMF approach. Given that one of our main applications is generalized linear matrix completion under USR, we will include relevant discussions regarding the BMF literature suggested by the reviewer in the revision. Below, we provide a summary of the key points we intend to address:

Different Problem Setting: We note that the setting considered in the BMF literature differs slightly from ours. The reviewer's recommended references all focus on the noiseless matrix recovery problem, where the linear measurement operator $\mathcal{A}$ is deterministic, and the goal is to recover the ground-truth matrix $M^*$ exactly. In contrast, our setting involves noisy matrix recovery, focusing on how quickly the error decays with the sample size rather than exact recovery.

Optimization vs. Statistical Complexity: Our methodology relies solely on convex optimization problems, meaning the optimization complexity associated with non-convex approaches like BMF does not apply here. Upon reviewing the suggested literature, we believe directly comparing the optimization complexity metric (OCM) from Yalçin et al. (2022); Zhang et al. (2024) with our "statistical complexity metric" (SCM) in Theorem 4.1, $\lambda_{\max}(H(\pi; \Theta_\star))$, is ambiguous. The OCM quantifies the non-convexity of the BMF landscape relating to the success of local search methods, while SCM is information-theoretic and relates to the sample size required for any estimator to obtain a desired accuracy with high probability.

Comparison with Bi et al. (2022): As noted earlier, Bi et al. (2022) focus on exact recovery in the noiseless setting using gradient descent and provide only convergence rate results (Theorems 5 and 6). We could not identify a statistical sample complexity bound for 1-bit matrix completion beyond the experimental results presented.

Computational Cost: Our methodology only involves convex optimization subroutines and inverting and computing the SVD of $d^2 \times d^2$ matrices, all of which can be solved using CVXPY and NumPy. While our approach may not scale as efficiently as BMF in high dimensions, its primary contribution lies in the statistical guarantees.

Empirical comparisons: See our response to reviewer pkis

C1. Remark 1

Thank you for pointing out this oversight. Indeed, the bound you provided is correct, and we will correct this in the revision.

C2. Lower bound on $N$ in Theorem 4.1

Thank you for highlighting this. Upon careful review of the proof of Theorem 4.1, we recognized that the previously stated requirement on $N$ was merely an artifact of our original proof strategy. We have since refined our proof, resulting in an improved version of Theorem 4.1 that no longer requires this condition:

Let $\mathcal{A} \subseteq B^{d_1 \times d_2}_F(1)$ and $\pi \in \mathcal{P}(\mathcal{A})$. Let $S\_\* > 0, r \geq 1$ such that $\frac{S\_\*^2}{r} \geq \gamma$ for some $\gamma > 0$. Then, there exist universal constants $C\_1, C\_2 > 0$ and $c \in (0, 1)$ such that for any $\Theta\_\star \in \Theta(r, S\_\*)$ with $\lVert \Theta\_\star \rVert_F^2 \geq \frac{9 \gamma}{8}$, there exists a $\varepsilon = \varepsilon(\Theta\_\star) > 0$ such that the following holds:

$\inf\_{\widehat{\Theta}} \sup\_{\widetilde{\Theta}\_\star \in \mathcal{N}\_\star} \mathbb{P}\_{\pi, \widetilde{\Theta}\_\star}\left( \left\lVert \widehat{\Theta} - \widetilde{\Theta}\_\star \right\rVert\_F^2 \geq \frac{C\_2 \gamma g(\tau) r (d\_1 \vee d\_2)}{N \lambda\_{\max}(H(\pi; \Theta\_\star)) S\_\*^2} \right) \geq c.$

We sincerely appreciate the reviewer’s insightful comment, which enabled us to refine our lower bound result.

C3. Adaptive Estimation at the end of Section 5.1

Thank you for bringing this ambiguity to our attention. To explicitly clarify, our Stage I estimation procedure (nuclear-norm regularized MLE) assumes knowledge of all GLM parameters except $\Theta_\star$. For example, in the Gaussian noise case, knowledge (or an accurate upper bound) of the true variance is needed, as it informs the choice of regularization parameter in Stage I (Theorem 3.1 and Lemma B.4). When mentioning adaptive estimation at the end of Section 5.1, we intended to suggest alternative approaches that could be employed for Stage I when such knowledge is unavailable or uncertain. For instance, Section 4 of Klopp (2014) addresses adaptive estimation for matrix completion problems with unknown noise variance. We also note that our previous reference to Klopp et al. (2015) was inaccurate, as their method similarly assumes knowledge of the GLM. We will clarify these points in the revision.

We sincerely thank the reviewer for providing detailed and insightful reviews, and we are especially encouraged by your overall positive evaluation of our paper. Let us respond to each point that you have raised.

W1. Lack of empirical evaluation

Thank you for your suggestion. We provide preliminary experimental results in this link. We assure the reviewer that we will expand upon the numerical experiments in the revision.

We consider 1-bit recovery of a rank-1 symmetric matrix and compare the nuclear norm error of Stage I vs. Stage I+II vs. BMF w.r.t. the number of samples. For fair comparison, we ensured that Stage I+II uses the same number of samples as the others. Detailed implementation can be found in the link. Fig1.png shows the result, where it is clear that our Stage I+II outperforms the other baselines.

W2. No complexity analysis or runtime comparison with existing methods

Thank you for raising this important point. As correctly noted by the reviewer, our primary goal has been to obtain tight statistical and sample complexity guarantees, and thus, we did not explicitly provide computational complexity or runtime comparisons. However, we emphasize that our algorithm is computationally tractable since it relies solely on convex optimization subproblems (MLE, optimal experimental design) that are efficiently solvable via available tools such as CVXPY. We also note that prior works focusing primarily on statistical guarantees, such as Jang et al. (2024), similarly do not provide computational complexity comparisons.

To rigorously analyze computational complexity, one would need to introduce optimization errors ($\varepsilon$) and examine two key aspects: (1) how these optimization errors impact the statistical guarantees, and (2) the complexity of solving each convex optimization subproblem to $\varepsilon$-accuracy. Such analysis has been conducted, for instance, in Faury et al. (2022) within the context of logistic bandits. We recognize this as an important avenue for future work and will include relevant discussions in our revised manuscript.

Typos

Thank you for pointing them out. We will make sure to fix all typos for the revision.

Q1. How sensitive is the method to misspecification of the GLM, and could it be extended to handle uncertainty in the GLM itself?

Thank you for your interesting question. We begin by emphasizing that all the discussions in our paper assume a well-specified GLM, which is a common assumption in the bandit and statistical literature (e.g., Chapter 24.4 of Lattimore & Szepesvari, 2020). Indeed, addressing misspecifications typically requires separate theoretical and algorithmic techniques, as misspecification can introduce challenges such as biased estimates and reduced efficiency. There are established works in the literature (White, 1982; see Fortunati et al. (2017) for a survey) that explore such issues in the context of misspecified models, but handling them is often beyond the scope of our current focus.

With this clarification, we can elaborate on why our current methodology isn’t expected to be robust to gross misspecification, such as a misspecified distribution. It is well known that misspecified MLE estimates converge not to the true $\Theta_\star$, but rather to the KL projection of the misspecified distribution onto the ground-truth distribution (White, 1982). This results in the initialization in Stage I of our GL-LowPopArt (Algorithm 1) potentially being too far from the true $\Theta_\star$, which can lead to a constant, non-vanishing bias during the Catoni estimation in Stage II.

However, if the misspecification is "minor," such as an overestimation of variance in the Gaussian case (where the true variance is $\sigma$ but the learner assumes $\bar{\sigma} > \sigma$), our methodology is expected to be somewhat robust. In such cases, the estimates would still be reasonably close to the true $\Theta_\star$.

We also acknowledge that the issue of uncertainty in the GLM is a critical and promising direction for future research. While our current work is not focused on modeling uncertainty in the GLM, such extensions—whether through Bayesian methods or robust statistical techniques (Walker, 2013)—could certainly enhance the generalizability of our approach. We will discuss these possibilities in more detail in the revision. Thank you for your valuable question.

[1] White, H. (1982). Maximum Likelihood Estimation of Misspecified Models. Econometrica, 50(1), 1-25.

[2] Fortunati, S., Gini, F., Greco, M. S., and Richmond, C. D. (2017). Performance Bounds for Parameter Estimation under Misspecified Models: Fundamental Findings and Applications. IEEE Signal Processing Magazine, 34(6), 142-157.

[3] Walker, S. G. (2013). Bayesian inference with misspecified models. Journal of Statistical Planning and Inference, 143(10), 1621-1633.

We sincerely thank the reviewer for providing detailed and insightful reviews, and we are especially encouraged by your overall positive evaluation of our paper. Let us respond to each point that you have raised.

W1. First stage, which essentially serves to linearize the problem effectively. Although it may be crucial for establishing the theoretical results, I would be curious to see if it can be skipped in practice and, if so, at what cost.

Thank you for your interesting question. Indeed, as the reviewer correctly pointed out, the first stage essentially linearizes the problem by outputting an asymptotically consistent initial estimator $\Theta_0$, which is crucial in obtaining the correct guarantee for the second stage (Catoni estimation). We also show that this is the case empirically, i.e., the first stage is necessary to obtain a good error at the end. We test the effect of the initial (pilot) estimator for Stage II (matrix Catoni) in 1-bit recovery of a symmetric rank-1 matrix with three initial estimators: zero, random, and MLE obtained from $N = 3 \cdot 10^4$ samples. In Fig2.png of this link, it can be seen that there is a clear gap between {zero, random} and {MLE}, showing that indeed, skipping Stage I leads to much larger bias in practice as well. Still, one can also observe that the matrix Catoni results in a decaying error up to a certain point.

Thank you again for the interesting question, which helps us further emphasize our contribution. In the revision, we will expand upon the experiments, including the one you suggested.

Typos and Writing Suggestions

Thank you for pointing out these typos. We will carefully address and correct all typos in the revision. Specifically, regarding line 157, you are correct—it should indeed be written as $\kappa_\star V(\pi) \preceq H(\pi; \Theta_\star)$.

Q1. Discrepancy between line 080 and line 370

Thank you for highlighting this discrepancy. You are correct that both our guarantee and prior guarantees depend on $\dot{\mu}$. The distinction we intended to make in line 080 is that previous results rely on a "worst-case" $\dot{\mu}$, specifically $\min_{|z| \leq \gamma} \dot{\mu}(z)$, whereas our guarantee depends explicitly on the instance-specific quantity $\min_{i,j} \dot{\mu}((\Theta_\star)_{i,j})$. We will clarify this explicitly in line 080 in the revision.

Q2. Eqn. (4) is the Hessian?

You are correct; using the relation $\langle X_t, \Theta \rangle = \mathrm{vec}(X_t)^\top \mathrm{vec}(\Theta)$ combined with (1), (4) indeed corresponds (up to a constant factor) to the Hessian of the expected negative log-likelihood loss. We acknowledge that this relationship might not have been immediately clear, so in the revised version, we will explicitly state this connection by clearly defining the negative log-likelihood loss just above (4).

Q3. Are there any algorithms with $o(T^{2/3})$ Borda regret?

Thank you for your insightful question. Due to space constraints, we addressed most of the discussions on bilinear dueling bandits in Appendix H of our submission (specifically, see the last paragraph on pg. 48). Among the deferred discussions, we especially highlight the lower bound part. Wu et al. (2024) established a $\Omega(d^{2/3} T^{2/3})$ Borda regret lower bound for generalized linear dueling bandits, attributing the $T^{2/3}$ rate to the inherent difficulty of mixing exploration and exploitation (see the paragraph following their Theorem 4.1). Although Wu et al. (2024)'s setting slightly differs, it is very similar in spirit, and we believe that a $T^{2/3}$ horizon dependence is generally unavoidable for Borda regret. Furthermore, as our estimation guarantee is not sequential (not anytime-valid), we believe ETC is an ideal integration choice for our estimation procedure within the bandit framework. We will clearly discuss this comparison and rationale in the revised manuscript.

Q4. Notation table

Thank you for your valuable suggestion. In the revised version, we will include an Appendix section dedicated to clearly defining and summarizing all notations used throughout the manuscript.