pith. sign in

arxiv: 2506.03074 · v5 · submitted 2025-06-03 · 📊 stat.ML · cs.LG

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

Junghyun Lee , Kyoungseok Jang , Kwang-Sung Jun , Milan Vojnovi\'c , Se-Young Yun This is my paper

Pith reviewed 2026-05-19 10:46 UTC · model grok-4.3

classification 📊 stat.ML cs.LG
keywords generalized low-rank trace regressionminimax optimalitynuclear norm regularizationCatoni estimationmatrix completiondueling banditslocal minimax lower bound
0
0 comments X

The pith

A two-stage nuclear norm and Catoni estimator achieves nearly instance-wise minimax optimality for generalized low-rank trace regression up to the ground-truth Hessian condition number.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces GL-LowPopArt as a Catoni-style estimator for generalized low-rank trace regression that uses a two-stage procedure of nuclear norm regularization followed by matrix Catoni estimation. This approach controls bias from the nonlinear inverse link function and yields improved estimation error bounds over prior methods. A sympathetic reader would care because the work also proves a local minimax lower bound for instance-wise optimality and demonstrates gains in generalized linear matrix completion and a new bilinear dueling bandits setting.

Core claim

GL-LowPopArt employs a two-stage approach of nuclear norm regularization followed by matrix Catoni estimation to control bias from the nonlinear inverse link function in generalized low-rank trace regression. The paper establishes state-of-the-art estimation error bounds that surpass existing guarantees and proves a local minimax lower bound showing instance-wise optimality up to the condition number of the ground-truth Hessian. It further provides an improved Frobenius error guarantee for generalized linear matrix completion and introduces bilinear dueling bandits with an improved Borda regret bound via an explore-then-commit strategy.

What carries the argument

The two-stage nuclear-norm-plus-Catoni procedure that controls bias induced by the nonlinear inverse link function while delivering the claimed rates.

If this is right

  • Improved Frobenius error guarantee for generalized linear matrix completion compared to prior approaches.
  • Introduction of bilinear dueling bandits as a contextualized dueling bandits problem with a general preference model.
  • Improved Borda regret bound for bilinear dueling bandits using an explore-then-commit strategy with GL-LowPopArt.
  • Revelation of a novel experimental design objective denoted GL(π).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The local minimax optimality result could guide estimator design in other low-rank generalized linear models where instance-specific rates matter.
  • The GL(π) objective might suggest new ways to choose sampling distributions in related trace regression or matrix sensing problems.
  • Practitioners in recommendation systems or preference learning could test whether the two-stage bias control translates to better downstream performance in high-dimensional data.

Load-bearing premise

The two-stage nuclear-norm-plus-Catoni procedure sufficiently controls the bias induced by the nonlinear inverse link function without introducing new dominant error terms that would invalidate the claimed rates.

What would settle it

An empirical study in which the observed estimation error of GL-LowPopArt exceeds the local minimax lower bound by more than a factor equal to the condition number of the ground-truth Hessian across multiple instances would falsify the near instance-wise optimality claim.

Figures

Figures reproduced from arXiv: 2506.03074 by Junghyun Lee, Kwang-Sung Jun, Kyoungseok Jang, Milan Vojnovi\'c, Se-Young Yun.

Figure 1
Figure 1. Figure 1: Plots of the nuclear norm errors for N ∈ {104 , 2 · 104 , 3 · 104 , 4 · 104 , 5 · 104}. J.2 Results & Discussion We report 95% studentized bootstrapped confidence intervals with bias correction (DiCiccio and Efron, 1996; Hall, 1992) for each (algorithm, N) pair, using 1000 outer bootstrap samples and 500 inner samples. When the empirical variation is too small for reliable studentization, we fall back to t… view at source ↗
Figure 2
Figure 2. Figure 2: Ablation plots of the nuclear norm errors for [PITH_FULL_IMAGE:figures/full_fig_p064_2.png] view at source ↗
read the original abstract

We present `GL-LowPopArt`, a novel Catoni-style estimator for generalized low-rank trace regression. Building on `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, $\mathrm{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 *local minimax lower bound*, showing that our `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 **bilinear dueling bandits**, a contextualized version of dueling bandits with a general preference model. Using an explore-then-commit approach with `GL-LowPopArt', we show an improved Borda regret bound over na\"ive vectorization (Wu et al., 2024).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces GL-LowPopArt, a two-stage estimator for generalized low-rank trace regression that first applies nuclear-norm regularization and then performs matrix Catoni estimation. It claims state-of-the-art Frobenius-norm error bounds that improve on Fan et al. (2019) and Kang et al. (2022), introduces a novel experimental design objective GL(π), proves a local minimax lower bound establishing near instance-wise optimality up to the condition number of the ground-truth Hessian, and derives improved guarantees for generalized linear matrix completion as well as an explore-then-commit algorithm for bilinear dueling bandits with better Borda regret than naive vectorization.

Significance. If the two-stage bias control succeeds without introducing dominant remainder terms beyond the claimed cond(H) factor, the result would constitute a meaningful advance toward instance-optimal rates in generalized low-rank problems, with concrete payoffs for matrix completion and contextual preference learning.

major comments (2)
  1. [Abstract and §4] Abstract and §4 (bias-control analysis): the headline claim of instance-wise optimality up to cond(H) requires that the Taylor remainder after linearizing the inverse link around the first-stage nuclear-norm estimate is absorbed into the cond(H) factor. The manuscript must explicitly bound this remainder in terms of the link-function derivatives and the operator norm of the design; if the bound retains an extra polynomial factor in dimension or rank, the local-minimax statement does not hold as stated.
  2. [Local-minimax lower-bound section] Local-minimax lower-bound section: the lower bound is asserted to be derived independently of the estimator. The proof sketch should clarify whether the construction of the least-favorable instance already incorporates the curvature of the link function or whether an additional assumption on the link (e.g., bounded third derivative) is implicitly used; otherwise the “up to cond(H)” qualifier may understate the gap between upper and lower bounds.
minor comments (2)
  1. [Notation] Notation: the definition of the design objective GL(π) should be stated once in a dedicated subsection and then referenced consistently; currently it appears only in the abstract and introduction.
  2. [Application section] Application section: the bilinear-dueling-bandit regret analysis invokes an explore-then-commit strategy; a short paragraph comparing the resulting Borda regret to the vectorized baseline of Wu et al. (2024) would help readers assess the improvement.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments highlight important points for rigor in the bias analysis and the lower-bound construction. We address each major comment below and indicate the revisions planned for the next version of the manuscript.

read point-by-point responses

  1. Referee: [Abstract and §4] Abstract and §4 (bias-control analysis): the headline claim of instance-wise optimality up to cond(H) requires that the Taylor remainder after linearizing the inverse link around the first-stage nuclear-norm estimate is absorbed into the cond(H) factor. The manuscript must explicitly bound this remainder in terms of the link-function derivatives and the operator norm of the design; if the bound retains an extra polynomial factor in dimension or rank, the local-minimax statement does not hold as stated.

    Authors: We agree that an explicit bound on the Taylor remainder is required to fully substantiate the claim. In the revised manuscript we will insert a new lemma in Section 4 that bounds the remainder explicitly in terms of the first three derivatives of the link function and the operator norm of the design matrix. Under the paper’s standing assumptions (bounded derivatives and the first-stage nuclear-norm error rate), this remainder is absorbed into the cond(H) factor without introducing additional polynomial factors in dimension or rank. The revised analysis will therefore preserve the stated instance-wise optimality result. revision: yes

  2. Referee: [Local-minimax lower-bound section] Local-minimax lower-bound section: the lower bound is asserted to be derived independently of the estimator. The proof sketch should clarify whether the construction of the least-favorable instance already incorporates the curvature of the link function or whether an additional assumption on the link (e.g., bounded third derivative) is implicitly used; otherwise the “up to cond(H)” qualifier may understate the gap between upper and lower bounds.

    Authors: The lower bound is constructed in an estimator-independent manner by perturbing the true parameter along the least-favorable direction defined by the local Hessian of the link function. The curvature of the link is therefore built into the definition of the local neighborhood and into the resulting cond(H) factor; the same bounded-derivative assumptions already stated for the upper bound (including the third derivative for concentration) are used. We will expand the proof sketch to make this dependence explicit and to confirm that no further assumptions are required. The “up to cond(H)” qualifier will remain accurate. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper introduces GL-LowPopArt via a two-stage nuclear-norm plus Catoni procedure that builds on LowPopArt (Jang et al., 2024) to control bias from the nonlinear inverse link function. It separately proves a local minimax lower bound establishing instance-wise optimality up to the condition number of the ground-truth Hessian. This lower bound and the absorption of remainder terms into the cond(H) factor constitute independent technical content rather than a reduction to fitted parameters, self-definitions, or prior self-citations by construction. The central claims remain self-contained against external benchmarks with no evident load-bearing circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only abstract available; ledger populated with minimal domain assumptions typical for generalized trace regression.

axioms (1)
  • domain assumption The link function is known and sufficiently smooth; the parameter matrix is low-rank.
    Standard modeling assumption invoked for generalized low-rank regression.

pith-pipeline@v0.9.0 · 5777 in / 1194 out tokens · 30297 ms · 2026-05-19T10:46:04.390922+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · 2 internal anchors

  1. [1]

    Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro

    doi:10.1007/978-1-4612-0653-8. Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global Optimality of Local Search for Low Rank Matrix Recovery. In Advances in Neural Information Processing Systems , volume 29, pages 3880–

    work page doi:10.1007/978-1-4612-0653-8

  2. [2]

    URL https://proceedings.neurips.cc/paper_files/paper/2016/ file/b139e104214a08ae3f2ebcce149cdf6e-Paper.pdf

    Curran Associates, Inc., 2016. URL https://proceedings.neurips.cc/paper_files/paper/2016/ file/b139e104214a08ae3f2ebcce149cdf6e-Paper.pdf. Yingjie Bi, Haixiang Zhang, and Javad Lavaei. Local and Global Linear Convergence of General Low- Rank Matrix Recovery Problems. Proceedings of the AAAI Conference on Artificial Intelligence , 36(9): 10129–10137, Jun. ...

    work page doi:10.1609/aaai.v36i9.21252 2016

  3. [3]

    Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury

    URL https://homes.cs.washington.edu/~sham/papers/ml/bandit_linear_long.pdf. Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Active Preference Optimization for Sample Efficient RLHF. arXiv preprint arXiv:2402.10500 , 2024. URL https: //arxiv.org/abs/2402.10500. Mark A. Davenport and Justin Romberg. An Overview of Low-Rank Matrix...

    work page doi:10.1109/jstsp.2016.2539100 2024

  4. [4]

    Jianqing Fan, Han Liu, Qiang Sun, and Tong Zhang

    doi:10.1214/ss/1032280214. Jianqing Fan, Han Liu, Qiang Sun, and Tong Zhang. I-LAMM for sparse learning: Simultaneous control of algorithmic complexity and statistical error. The Annals of Statistics , 46(2):814 – 841, 2018. doi:10.1214/17- AOS1568. Jianqing Fan, Wenyan Gong, and Ziwei Zhu. Generalized high-dimensional trace regression via nuclear norm re...

    work page doi:10.1214/ss/1032280214 2018

  5. [5]

    A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm

    URL https://proceedings.mlr.press/v139/jang21a.html. Kyoungseok Jang, Chicheng Zhang, and Kwang-Sung Jun. PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits. In Advances in Neural Information Processing Systems, volume 35, pages 2102–2114. Curran Associates, Inc., 2022. URL https://openreview.net/ forum?id=GWcdXz...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s10107-010-0419-x 2022

  6. [6]

    A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm

    URL https://arxiv.org/abs/1902.03736. Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable Generalized Linear Bandits: Online Computation and Hashing. In Advances in Neural Information Processing Systems , volume 30, pages 98–108. Curran Associates, Inc., 2017. URL https://proceedings.neurips.cc/paper_ files/paper/2017/file/28dd...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.24963/ijcai.2017/278 1902

  7. [7]

    Buchbinder and Ilya Shapiro.Introduction to Quantum Field Theory with Applica- tions to Quantum Gravity

    doi:10.1093/oso/9780198536932.001.0001. Olga Klopp. Noisy low-rank matrix completion with general sampling distribution. Bernoulli, 20(1):282 – 303, 2014. doi:10.3150/12-BEJ486. Olga Klopp, Jean Lafond, ´Eric Moulines, and Joseph Salmon. Adaptive multinomial matrix completion. Electronic Journal of Statistics , 9(2):2950 – 2975, 2015. doi:10.1214/15-EJS10...

    work page doi:10.1093/oso/9780198536932.001.0001 2014

  8. [8]

    doi: https: //doi.org/10.1007/978-1-4419-9982-5

    Curran Associates, Inc., 2014. URL https://papers.nips.cc/paper_files/paper/2014/hash/ 17ac4eb332d6ac6956ea2e835464e03b-Abstract.html. Tor Lattimore and Botao Hao. Bandit Phase Retrieval. In Advances in Neural Information Processing Systems, volume 34, pages 18801–18811. Curran Associates, Inc., 2021. URL https://openreview.net/ forum?id=fThfMoV7Ri. 19 To...

    work page doi:10.1007/978-1-4419-9982-5 2014

  9. [9]

    doi:10.1038/s41467-017-00680-8

    ISSN 2041-1723. doi:10.1038/s41467-017-00680-8. Jianhao Ma and Salar Fattahi. Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery? arXiv preprint arXiv:2302.10963 , 2023. URL https://arxiv.org/abs/2302.10963. 20 Blake Mason, Kwang-Sung Jun, and Lalit Jain. An Experimental Design Approach for Regret Minimization in Logistic Ban...

    work page doi:10.1038/s41467-017-00680-8 2041

  10. [10]

    URL https://arxiv.org/abs/2202.02407

    doi:10.1609/aaai.v36i7.20741. URL https://arxiv.org/abs/2202.02407. Kenneth O. May. Intransitivity, Utility, and the Aggregation of Preference Patterns. Econometrica, 22(1): 1–13, 1954. doi:10.2307/1909827. Peter McCullagh and John A. Nelder. Generalized Linear Models. Monographs on Statistics and Applied Probability. Chapman & Hall/CRC, 2 edition, 1989. ...

    work page doi:10.1609/aaai.v36i7.20741 1954

  11. [11]

    URL https://proceedings.mlr.press/v235/munos24a.html. F. D. Murnaghan and A. Wintner. A Canonical Form for Real Matrices under Orthogonal Transformations. Proceedings of the National Academy of Sciences , 17(7):417–420, 1931. doi:10.1073/pnas.17.7.417. Mojmir Mutn´ y and Andreas Krause. No-regret Algorithms for Capturing Events in Poisson Point Processes....

    work page doi:10.1073/pnas.17.7.417 1931

  12. [12]

    Aadirupa Saha

    URL https://proceedings.mlr.press/v130/russac21a.html. Aadirupa Saha. Optimal Algorithms for Stochastic Contextual Preference Bandits. In Advances in Neural Information Processing Systems , volume 34, pages 30050–30062. Curran Associates, Inc., 2021. URL https://openreview.net/forum?id=1lCZrXJBpM. Aadirupa Saha, Tomer Koren, and Yishay Mansour. Adversaria...

    work page 2021

  13. [13]

    Flore Sentenac, Jialin Yi, Clement Calauzenes, Vianney Perchet, and Milan Vojnovic

    URL https://arxiv.org/abs/2404.06831. Flore Sentenac, Jialin Yi, Clement Calauzenes, Vianney Perchet, and Milan Vojnovic. Pure Exploration and Regret Minimization in Matching Bandits. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9434–9442. PMLR, 18–24 Jul

    work page arXiv

  14. [14]

    Burr Settles

    URL https://proceedings.mlr.press/v139/sentenac21a.html. Burr Settles. Active Learning. Number 1 in Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2012. doi:10.2200/S00429ED1V01Y201207AIM018. Shinichiro Shirota and Alan E. Gelfand. Space and circular time log Gaussian Cox processes with application to cri...

    work page doi:10.2200/s00429ed1v01y201207aim018 2012

  15. [15]

    Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang

    URL https://proceedings.mlr.press/v235/wu24m.html. Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint. In Proceedings of the 41st International Conference on Machine Learning , volume 235 of Proceedings of M...

    work page 2024

  16. [16]

    users are more active than others and popular items are rated more frequently

    URL https://proceedings.mlr.press/v151/yalcin22a.html. Eunho Yang and Pradeep K Ravikumar. Dirty Statistical Models. In Advances in Neural Information Processing Systems, volume 26, pages 611–619. Curran Associates, Inc., 2013. URL https://papers.nips. cc/paper_files/paper/2013/hash/8bf1211fd4b7b94528899de0a43b9fb3-Abstract.html. Wei Hong Yang, Lei-Hong Z...

    work page doi:10.1214/aos/1017939142 2013

  17. [17]

    the convex hull of a subset of arms to contain a ball with radius R ≤ 1 that does not scale with d1 or d2

    For a clear and fair comparison, we also write the upper bound on GLmin(A) as proved in Proposition 3.2. F.2 Their Theorem 4.1 – Stein’s Lemma-based Estimator (row 1) Their first estimator achieves the following error bound (Kang et al., 2022, Theorem 4.1) bΘKang,1 − Θ⋆ 2 F ≲ M(π)(d1 ∨ d2)r κ(π)2N , (57) given that π has a continuously differentiable dens...

    work page 2022

  18. [18]

    H.4 Proof of Proposition H.3 The proof utilizes some tools from topology, Lie group theory and matrix theory

    and PAP ⊤ A (x ⊗ y) = x ∧ y. H.4 Proof of Proposition H.3 The proof utilizes some tools from topology, Lie group theory and matrix theory. Our main references are Munkres (2018), Chapter 21 of Lee (2012) and Horn and Johnson (2012). Consider the generalized linear group GLd(R) := {X ∈ Rd×d : det(X) ̸= 0}, which is a Lie group of dimension d2. We then defi...

    work page 2018

  19. [19]

    Remark 13

    and low-rank bandits (Jang et al., 2024; Kang et al., 2022; Lu et al., 2021). Remark 13. Surprisingly, our regret bound is independent of the rank r of the matrix Θ⋆, which is also the case for bilinear bandits (Jang et al., 2021, Theorem 4.6) albeit for a different reason. We believe 60 that this showcases how GL-LowPopArt is adaptive to the arm-set geom...

    work page 2024

  20. [20]

    E-opt” and “GL-opt

    to demonstrate the effectiveness of GL-LowPopArt; for results in the Gaussian (i.e., linear) setting, we refer readers to the experiments in Jang et al. (2024). The code is publicly available on our GitHub repository.14 J.1 Experimental Setting Dataset. We largely follow the setup in Jang et al. (2024). We set d = d1 = d2 = 3 and rank r = 1. To observe av...

    work page 2024