# Learning Linear Models Using Distributed Iterative Hessian Sketching

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 57 references that are in the map.
- First posted on arXiv 8 Dec 2021.

## Builds on (most cited first, 30 of 30)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [CoCoA: A General Framework for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1611.02189/) (2016)
- [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019)
- [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017)
- [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019)
- [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020)
- [GIANT: Globally Improved Approximate Newton Method for Distributed Optimization](https://mlsanity.com/paper/1709.03528/) (2017)
- [The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint](https://mlsanity.com/paper/1812.03565/) (2018)
- [Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories](https://mlsanity.com/paper/2009.00739/) (2020)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [A Double Residual Compression Algorithm for Efficient Distributed Learning](https://mlsanity.com/paper/1910.07561/) (2019)
- [An Asynchronous Parallel Stochastic Coordinate Descent Algorithm](https://mlsanity.com/paper/1311.1873/) (2013)
- [Randomized Sketches of Convex Programs with Sharp Guarantees](https://mlsanity.com/paper/1404.7203/) (2014)
- [DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization](https://mlsanity.com/paper/1901.05134/) (2019)
- [Sparse sketches with small inversion bias](https://mlsanity.com/paper/2011.10695/) (2020)
- [On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filters](https://mlsanity.com/paper/1809.05870/) (2018)
- [Distributed estimation of the inverse Hessian by determinantal averaging](https://mlsanity.com/paper/1905.11546/) (2019)
- [Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging](https://mlsanity.com/paper/1702.04837/) (2017)
- [Non-asymptotic Closed-Loop System Identification using Autoregressive Processes and Hankel Model Reduction](https://mlsanity.com/paper/1909.02192/) (2019)
- [Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectory](https://mlsanity.com/paper/2102.11822/) (2021)
- [A Parallel SGD method with Strong Convergence](https://mlsanity.com/paper/1311.0636/) (2013)
- [Distributed Averaging Methods for Randomized Second Order Optimization](https://mlsanity.com/paper/2002.06540/) (2020)
- [Large-Scale System Identification Using a Randomized SVD](https://mlsanity.com/paper/2109.02703/) (2021)

## Abstract (arXiv)

This work considers the problem of learning the Markov parameters of a linear system from observed data. Recent non-asymptotic system identification results have characterized the sample complexity of this problem in the single and multi-rollout setting. In both instances, the number of samples required in order to obtain acceptable estimates can produce optimization problems with an intractably large number of decision variables for a second-order algorithm. We show that a randomized and distributed Newton algorithm based on Hessian-sketching can produce ε-optimal solutions and converges geometrically. Moreover, the algorithm is trivially parallelizable. Our results hold for a variety of sketching matrices and we illustrate the theory with numerical examples.