Convergence and Sample Complexity of Gradient Methods for the Model-Free Linear Quadratic Regulator
summary
Proves exponential stability of gradient flow over the set of stabilizing gains and shows gradient descent with fixed step attains linear convergence; uses a convex reparameterization via change of variables Y=KX to get PL/strong-convexity on sublevel sets. For model-free LQR, a two-point gradient estimate yields sample complexity with iterations O(log(1/ε)) and samples per iteration linear in state dimension, so overall roughly O(d log(1/ε)) samples with high probability (offline, sub-Gaussian initials). Continuous- and discrete-time cases both addressed.
AI-written summary · about
chapters (19)
- 0:00Intro
- 1:08A case study: LQR problem
- 4:58Our contributions GRADIENT FLOW DYNAMICS FOR LOR exponential stability: over the set of stabilizing K
- 6:59Linear convergence of gradient descent
- 7:54Model-free setup
- 8:33Random search for model-free LQR
- 10:41Main result: linear rate; log complexity
- 12:11State-of-the-art for random search LQR
- 14:25Approximate gradient descent
- 15:33An example
- 15:58Occurrence with high probability
- 17:36Challenge: lack of convexity
- 19:21Key known properties
- 22:15Convex re-parameterization
- 24:32Our approach
- 25:25Key property
- 28:52References
- 29:11Acknowledgements
- 30:49Objective
related talks
35mOn the Global Convergence and Approximation Benefits of Policy Gradient Methods
41mCompetitive Algorithms for Online Control
05mNon-monotonic convergence of gradient descent with large stepsize
58mFirst-Order Stochastic Optimization
13mNon-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient Descent
29mImplicit Regularization in Nonconvex Statistical Estimation
01h 18mOptimization I
42mWhat (Doesn't) Make Learning Algorithms Generalize?