# Quickly Finding the Best Linear Model in High Dimensions

arXiv: https://arxiv.org/abs/1907.01728 · HTML: https://mlsanity.com/paper/1907.01728/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2019.

## Built on by (most cited first, 1 of 1)

- [MPC-Inspired Reinforcement Learning for Verifiable Model-Free Control](https://mlsanity.com/paper/2312.05332/) (2023)

## Abstract (arXiv)

We study the problem of finding the best linear model that can minimize least-squares loss given a data-set. While this problem is trivial in the low dimensional regime, it becomes more interesting in high dimensions where the population minimizer is assumed to lie on a manifold such as sparse vectors. We propose projected gradient descent (PGD) algorithm to estimate the population minimizer in the finite sample regime. We establish linear convergence rate and data dependent estimation error bounds for PGD. Our contributions include: 1) The results are established for heavier tailed sub-exponential distributions besides sub-gaussian. 2) We directly analyze the empirical risk minimization and do not require a realizable model that connects input data and labels. 3) Our PGD algorithm is augmented to learn the bias terms which boosts the performance. The numerical experiments validate our theoretical results.