Research map / Learning theory and algorithms / Kernels and regression theory
Regression Learning with Limited Observations of Multivariate Outcomes and Features
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.
Develops online/stochastic gradient algorithms for multivariate linear regression when only a few outcome and feature coordinates can be observed, with L2 (ridge-like and Lasso-type) and L1 (ridge-like and Lasso-type) losses, and proves excess risk bounds, showing PAC learning for L2 but not L1 under missing features.
Problem
Multivariate linear regression when both outcomes and features are only partially observed (limited observations per sample), which is common in real data with missing or costly measurements.
Approach
Extends the univariate limited-attribute-observation algorithms (AERR, Hazan & Koren 2012; Bullins et al. 2016) to multivariate outcomes by unbiased sampling of observed outcome and feature coordinates for the gradient, combined with ridge-like constraints or proximal (FOBOS-style) sparse group Lasso penalties, with closed-form proximal updates.
Key results
- On synthetic data (T=1e4 to 5e4, sigma^2=5), LSR achieved mean prediction error 25.08 vs 37.41 for multivariate AERR with p0=10, outperforming the naive per-coordinate approach.
- With 20% Cauchy outliers, LADR (Algorithm 3) had prediction error 12.70 at p0=20 vs 51.25 for LSR at T=1e4, showing robustness of the L1 loss.
- Theory: the L2 algorithm achieves excess risk O(sqrt(pq/(T(p0-1)q0))), giving PAC learning, whereas the L1 algorithm retains a constant gap of 2 sqrt(q) B Bx sqrt(1-p0/p) when p0<p.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use multivariate LSR instead of multivariate AERR | Synthetic multivariate regression · Synthetic data, σ²ε=5 and 10 | mean prediction error | Helped |
| Use multivariate AERR with p0 redefined as 12 instead of p0=10 | Multivariate AERR · Synthetic data | mean prediction error | Helped |
| Use L1 loss rather than L2 loss | Regression with limited observations and outliers · Synthetic data with 20% outliers | mean prediction error | Helped |
| Increase the number of observed features p0 | LADR, LSR, and LSR0 · Synthetic data with 20% outliers | mean prediction error | Helped |
| Increase the sample size T | LSR and LSR0 · Synthetic data with 20% outliers | mean prediction error | Helped |
| Add the Lasso-type penalty | Least squares regression (Algorithm 2) · Synthetic sparse regression | mean prediction error | Helped |
| Use L1 loss and Lasso-type penalty rather than L2 loss and its penalized counterpart | Penalized regression with limited observations · Synthetic data with outliers | mean prediction error | Helped |
Surprising findings
- For L1 loss with missing features (p0<p), no PAC algorithm exists, so a constant gap remains even as T goes to infinity.
Limitations
- Assumes i.i.d. samples; departures from iid may affect guarantees.
- L1 loss with limited features cannot reach arbitrary accuracy (no PAC guarantee).
- Experiments are mostly on synthetic data and two real datasets; the work is online and not evaluated against deep or nonlinear models.
Experimental setup
Datasets: yeast cell cycle data (spls R package) children activity data (accelerometer, Goldsmith)
Benchmarks: synthetic linear regression data yeast cell cycle data children activity data
Metrics: mean prediction error squared prediction error absolute prediction error
Baselines: multivariate AERR Imp1 (mice imputation after LSR sampling) Imp2 (mean imputation plus mice) LADR
Builds on: AERR (Hazan & Koren 2012) FOBOS (Duchi & Singer 2009) Bullins et al. 2016 LAD limited observation
Closest papers by meaning
- The Limits of Learning with Missing Data (NeurIPS 2016 · similarity 0.87)
- A convex optimization formulation for multivariate regression (NeurIPS 2020 · similarity 0.87)
- A theory of high dimensional regression with arbitrary correlations between input features and target functions: sample complexity, multiple descent curves and a hierarchy of phase transitions (ICML 2021 · similarity 0.86)
- Random features models: a way to study the success of naive imputation (ICML 2024 · similarity 0.85)
- Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterization (ICML 2025 · similarity 0.84)
- Transfer Learning Meets Functional Linear Regression: No Negative Transfer Under Posterior Drift (AAAI 2025 · similarity 0.84)
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.