mlsanityData to 7 Oct 2026

Learning Linear Models Using Distributed Iterative Hessian Sketching

arXiv 2112.04101 ↗First posted 8 Dec 2021math.OC cs.LG cs.NAcited by 0

Not on the map. Why?

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.

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

Builds on

30 of 57 references.

References · 30

  1. 2021Convex optimizationcited by 2,479
  2. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  3. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  4. 2018Learning Without Mixing: Towards A Sharp Analysis of Linear System Identificationcited by 158
  5. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 151
  6. 2018Near optimal finite time identification of arbitrary linear dynamical systemscited by 89
  7. 2018Non-asymptotic Identification of LTI Systems from a Single Trajectorycited by 77
  8. 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
  9. 2016CoCoA: A General Framework for Communication-Efficient Distributed Optimizationcited by 69
  10. 2019Finite Sample Analysis of Stochastic System Identificationcited by 67
  11. 2017Finite Time Identification in Unstable Linear Systemscited by 66
  12. 2019Learning Linear Dynamical Systems with Semi-Parametric Least Squarescited by 58
18 more
  1. 2020Logarithmic Regret Bound in Partially Observable Linear Dynamical Systemscited by 46
  2. 2017GIANT: Globally Improved Approximate Newton Method for Distributed Optimizationcited by 43
  3. 2020Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectoriescited by 38
  4. 2018The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpointcited by 36
  5. 2014Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squarescited by 34
  6. 2019A Double Residual Compression Algorithm for Efficient Distributed Learningcited by 31
  7. 2013An Asynchronous Parallel Stochastic Coordinate Descent Algorithmcited by 26
  8. 2014Randomized Sketches of Convex Programs with Sharp Guaranteescited by 25
  9. 2019DINGO: Distributed Newton-Type Method for Gradient-Norm Optimizationcited by 20
  10. 2020Sparse sketches with small inversion biascited by 19
  11. 2018On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filterscited by 16
  12. 2019Distributed estimation of the inverse Hessian by determinantal averagingcited by 16
  13. 2017Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averagingcited by 13
  14. 2019Non-asymptotic Closed-Loop System Identification using Autoregressive Processes and Hankel Model Reductioncited by 9
  15. 2021Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectorycited by 3
  16. 2013A Parallel SGD method with Strong Convergencecited by 2
  17. 2020Distributed Averaging Methods for Randomized Second Order Optimizationcited by 2
  18. 2021Large-Scale System Identification Using a Randomized SVDcited by 2

Built on by

Not cited yet.