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

Junghyun Lee, Kyoungseok Jang, Kwang-Sung Jun, Milan Vojnovic, Se-Young Yun
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:2872-2880, 2026.

Abstract

We present \textbf{GL-LowPopArt}, a novel Catoni-style estimator for generalized low-rank trace regression. Building on \emph{LowPopArt} (Jang et al., 2024), it employs a two-stage approach: nuclear norm regularization followed by matrix Catoni estimation. We establish state-of-the-art estimation error bounds, surpassing existing guarantees (Fan et al., 2019; Kang et al., 2022), and reveal a novel experimental design objective, \textbf{GL($\pi$)}. The key technical challenge is controlling bias from the nonlinear inverse link function, which we address with our two-stage approach. We prove a \emph{local minimax lower bound}, showing that \textbf{GL-LowPopArt} enjoys instance-wise optimality up to the condition number of the ground-truth Hessian. Our method immediately achieves an improved Frobenius error guarantee for generalized linear matrix completion. We also introduce a new problem setting called \textbf{bilinear dueling bandits}, a contextualized version of dueling bandits with a general preference model. Using an explore-then-commit approach with \textbf{GL-LowPopArt}, we show an improved Borda regret bound over naïve vectorization (Wu et al., 2024).

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-lee26d, title = { GL-LowPopArt: A Nearly Instance-Wise Minimax-Optimal Estimator for Generalized Low-Rank Trace Regression }, author = {Lee, Junghyun and Jang, Kyoungseok and Jun, Kwang-Sung and Vojnovic, Milan and Yun, Se-Young}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {2872--2880}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/lee26d/lee26d.pdf}, url = {https://proceedings.mlr.press/v300/lee26d.html}, abstract = { We present \textbf{GL-LowPopArt}, a novel Catoni-style estimator for generalized low-rank trace regression. Building on \emph{LowPopArt} (Jang et al., 2024), it employs a two-stage approach: nuclear norm regularization followed by matrix Catoni estimation. We establish state-of-the-art estimation error bounds, surpassing existing guarantees (Fan et al., 2019; Kang et al., 2022), and reveal a novel experimental design objective, \textbf{GL($\pi$)}. The key technical challenge is controlling bias from the nonlinear inverse link function, which we address with our two-stage approach. We prove a \emph{local minimax lower bound}, showing that \textbf{GL-LowPopArt} enjoys instance-wise optimality up to the condition number of the ground-truth Hessian. Our method immediately achieves an improved Frobenius error guarantee for generalized linear matrix completion. We also introduce a new problem setting called \textbf{bilinear dueling bandits}, a contextualized version of dueling bandits with a general preference model. Using an explore-then-commit approach with \textbf{GL-LowPopArt}, we show an improved Borda regret bound over naïve vectorization (Wu et al., 2024). } }
Endnote
%0 Conference Paper %T GL-LowPopArt: A Nearly Instance-Wise Minimax-Optimal Estimator for Generalized Low-Rank Trace Regression %A Junghyun Lee %A Kyoungseok Jang %A Kwang-Sung Jun %A Milan Vojnovic %A Se-Young Yun %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-lee26d %I PMLR %P 2872--2880 %U https://proceedings.mlr.press/v300/lee26d.html %V 300 %X We present \textbf{GL-LowPopArt}, a novel Catoni-style estimator for generalized low-rank trace regression. Building on \emph{LowPopArt} (Jang et al., 2024), it employs a two-stage approach: nuclear norm regularization followed by matrix Catoni estimation. We establish state-of-the-art estimation error bounds, surpassing existing guarantees (Fan et al., 2019; Kang et al., 2022), and reveal a novel experimental design objective, \textbf{GL($\pi$)}. The key technical challenge is controlling bias from the nonlinear inverse link function, which we address with our two-stage approach. We prove a \emph{local minimax lower bound}, showing that \textbf{GL-LowPopArt} enjoys instance-wise optimality up to the condition number of the ground-truth Hessian. Our method immediately achieves an improved Frobenius error guarantee for generalized linear matrix completion. We also introduce a new problem setting called \textbf{bilinear dueling bandits}, a contextualized version of dueling bandits with a general preference model. Using an explore-then-commit approach with \textbf{GL-LowPopArt}, we show an improved Borda regret bound over naïve vectorization (Wu et al., 2024).
APA
Lee, J., Jang, K., Jun, K., Vojnovic, M. & Yun, S.. (2026). GL-LowPopArt: A Nearly Instance-Wise Minimax-Optimal Estimator for Generalized Low-Rank Trace Regression . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:2872-2880 Available from https://proceedings.mlr.press/v300/lee26d.html.

Related Material