Research map / Learning theory and algorithms / Matrix and tensor methods
GL-LowPopArt: A Nearly Instance-Wise Minimax-Optimal Estimator for Generalized Low-Rank Trace Regression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GL-LowPopArt, a two-stage nuclear-norm-regularized MLE plus matrix Catoni estimator for generalized low-rank trace regression, with an instance-wise error bound via a new GL-design objective, a local minimax lower bound, and an application to bilinear dueling bandits.
Problem
Estimating a low-rank matrix parameter from nonlinear (GLM) observations with matrix-valued covariates, where existing guarantees depend on worst-case curvature of the inverse link function rather than instance-specific curvature.
Approach
Two-stage estimator: nuclear-norm penalized MLE for a warm start, then a generalized linear matrix Catoni estimator using one-sample estimators debiased with the Hessian at the initial estimate, followed by singular value thresholding. Introduces the GL-Design objective, whose optimization yields instance-dependent error bounds and near-optimal lower bounds.
Key results
- Instance-wise error bound for GL-LowPopArt scaling with the GL-design objective, improving over worst-case curvature bounds in generalized linear matrix completion (1/min_ij mu-dot((Theta*)_ij) instead of 1/min over |z|<=gamma).
- A local minimax lower bound scaling with lambda_max of the Hessian, making GL-LowPopArt nearly instance-wise optimal up to the Hessian condition number for single-switch policies.
- Bilinear dueling bandit explore-then-commit algorithm attains Borda regret of order (GL_min)^{1/3}(kappa T)^{2/3} up to logs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GL-LowPopArt with optimal GL-design instead of the nuclear penalized MLE | Generalized low-rank trace regression · Frobenius and operator-norm unit balls | squared Frobenius error bound: \kappa_\star^{-2} d_1 d_2 (d_1 \wedge d_2) \gE(N) -> \kappa_\star^{-1} (d_1 \wedge d_2) \gE(N); \kappa_\star^{-2} (d_1 \ | Helped |
| Use GL-LowPopArt with optimal GL-design instead of the Stein estimator | Generalized low-rank trace regression · Frobenius and operator-norm unit balls | squared Frobenius error bound: \kappa_\star^{-2} (d_1 \wedge d_2) \gE(N) -> \kappa_\star^{-1} (d_1 \wedge d_2) \gE(N); \kappa_\star^{-2} (d_1 \vee d_2) | Helped |
| Adapt the curvature factor to the instance rather than the worst-case entrywise domain | GL-LowPopArt for 1-bit matrix completion · 1-bit matrix completion, uniform sampling | squared Frobenius error bound: \frac{1}{\min_{i,j} \dot{\mu}((\bm\Theta_\star)_{ij})} \frac{r d_1 d_2 (d_1 \vee d_2)}{N} | Helped |
| Use optimal GL-design instead of uniform sampling | GL-LowPopArt for 1-bit matrix completion · 1-bit matrix completion | squared Frobenius error bound: \mathrm{Harm}(\bm\Theta_\star)^{-1} \frac{r d_1 d_2 (d_1 \vee d_2)}{N} | Helped |
| Use GL-LowPopArt for the exploration phase and commit to the estimated Borda winner | BETC-GLM-LR · Bilinear dueling bandits | Borda regret: \left( \mathrm{GL}_{\min}(\gX) \log\frac{d}{\delta} \right)^{1/3} \left( \kappa_\star^B T \right)^{2/3} | Helped |
Limitations
- Analysis relies on covariates being bounded in operator norm (unbounded case left for future work).
- Requires the initial estimate to be sufficiently accurate, with a sample-size condition on Stage I.
- Lower bound is local and holds for single-switch policies only up to condition number; not matched for entrywise-constrained neighborhoods in matrix completion.
Experimental setup
Metrics: squared Frobenius error operator norm error Borda regret
Baselines: nuclear penalized MLE Stein estimator Dav14 1-bit matrix completion bound Klo15 bound Warm-LowPopArt
Builds on: LowPopArt Catoni estimator self-concordant generalized linear bandits
Closest papers by meaning
- Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits (ICML 2024 · similarity 0.89)
- Flat Minima in Linear Estimation and an Extended Gauss Markov Theorem (ICLR 2024 · similarity 0.84)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.84)
- Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery (ICML 2024 · similarity 0.83)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.83)
- A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.