An applied course on first-order methods in control

An applied course on first-order methods in control Gradient methods Pablo Krupa IMT School for Advanced Studies, Lucca, Italy. [email protected] December 2025 Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 1 / 34 First-order methods First-order methods are iterative optimization algorithms for solving optimization problems that only require knowledge of the gradientaof the objective function. aOr subgradient, but we will focus on differentiable functions in this course Why first-order methods? Simple to implement (when compared to other optimization algorithms). Inexpensive online computations; matrix-vector linear algebra, but no matrix inversions. Scale very well with problem dimension; applicable to large-scale optimization problems. Can solve a wide class of constrained optimization problems. Many proven convergence rates for different families of optimization problems. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 2 / 34 In this part of the course x∗= arg min xf(x) s.t. x ∈ C. Recursion xk+1 =A(xk), starting from some x0∈Rn, such that xk+1 →x∗as k→ ∞. They are designed so that a fixed-point iterate of the algorithm, i.e., an iterate xk satisfying xk=A(xk), satisfies xk=x∗. We will present two first-order methods: ▶Gradient descent ▶Proximal gradient method We will discuss convergence rates, stopping criteria, etc. We will also present accelerated first-order methods and restart schemes. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 3 / 34 Gradient descent min x∈Rnf(x) Assumption Function f:Rn→Ris convex and L-smooth (∥∇f(x)−∇f(y)∥2≤L∥x−y∥2,∀x, y ∈Rn). Gradient descent Require: x0∈Rn 1For each k= 0,1,2, . . . repeat 2xk+1 ←xk−αk∇f(xk) Gradient descent takes steps in the direction given by the negative of the gradient. The size of the step depends on the value of the gradient and choice of the step-size αk. If the step-size αk∈R>0is selected appropriately, the sequence {xk}converges to x∗. Under the above assumption, the easiest choice is αk≤2 L. Under this choice, the gradient descent method provides a O(1/k)convergence rate in terms of function value. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 4 / 34 Convergence rates How many iterations are required to guarantee that f(xk)−f∗≤ϵ, for ϵ > 0. •Convergence rates allow us to compare the theoretical speed of convergence. •Let {ek}∞ k=0 be a sequence where ek≥0. Two common convergence rates are:1 Linear convergence There exist constants q∈(0,1) and C > 0such that ek≤Cqk,∀k= 0,1, . . . ek≤ϵachieved in Olog 1 ϵiters. Sublinear convergence If it is slower than linear convergence. Several alternatives: ek≤C √k+ 1, ek≤C k+ 1, ek≤C (k+ 1)2,∀k= 0,1, . . . ek≤ϵin O1 √ϵ,O1 ϵ,O1 ϵ2. 1In optimization, we will take ek=f(xk)−f∗or ek=∥xk−x∗∥2. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 5 / 34 Convergence rate of gradient descent Convergence of gradient descent for convex f Let fbe convex and L-smooth, and take αk=1 L. Then, the iterates {xk}of the gradient descent method satisfy f(xk)−f∗≤2L∥x0−x∗∥2 2 k+ 4 ,∀k > 0. •Similar O(1/k)convergence results can be obtained if we take αk≡α, with 0< α ≤2 L. However, the step-size α=1 Lprovides the optimal convergence guarantee. The strongly convex case If fis µ-strongly convex, then, taking α=2 µ+L, the above convergence result is improved to f(xk)−f∗≤L 2κ−1−1 κ−1+ 12k ∥x0−x∗∥2 2, where κ=µ Lis the condition number of f. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 6 / 34 What if we don’t know L?2 Then, the step-size αkcan be adapted online using a backtracking method: 1We take αk=1 Lk, where Lk∈R>0is used to estimate the value of the Lipschitz constant Lof function f. 2We start by taking an initial guess L−1>0. 3At each iteration k≥0, we first take Lk←Lk−1. Then, while f(xk+1)> f(xk) + ⟨∇f(xk), xk+1 −xk⟩+Lk 2∥xk+1 −xk∥2 2, we set Lk←ηLk, with η > 1, and then recompute xk+1. Step 3 is checking if the descent lemma is satisfied (for Lk≥Lit will be). Property: will eventually reach an Lkthat always satisfied the descent lemma. Disadvantage: xk+1 is discarded if it does not satisfy the descent lemma. Convergence: similar to fixed αk≡α(the O(1/k)rate is maintained). 2Or we don’t want to compute it. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 7 / 34 What about constraints? What if my objective function is not smooth? Many problems of interest include constraints, which are not considered in gradient descent, or non-smooth terms in the objective function. Consider a constraint x∈ C, where C ⊂ Rnis a non-empty closed convex set: min x∈C f(x). Consider an optimization problem min x∈Rn{f(x)≡h(x) + g(x)}, where h:Rn→Ris L-smooth and g:Rn→R∪{∞} is PCC. Function gcould be non-smooth, or even non-differentiable. •We will now see how to solve these problems using the proximal gradient method (PGM). Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 8 / 34 Proximal mapping Definition (Proximal mapping) Given g:Rn→R∪{∞}, the proximal mappingaof gfor x∈Rnis given by proxg(x) = arg min y∈Rng(y) + 1 2∥y−x∥2 2. aAlso referred to as the “proximal operator”, “prox mapping” or “prox operator”. Intuitively, proxg(x)is a compromise between minimizing gand staying close to x. Theorem: if gis PCC, then proxg(x)is a singleton for any x∈Rn. We often encounter the use of the prox operator of a scaled function λg, with λ > 0, i.e., proxλg(x) = arg min y∈Rng(y) + 1 2λ∥y−x∥2 2. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 9 / 34 Some more examples of the solutions of prox operators Quadratic function: g(x) = 1 2x⊤Hx +q⊤x+c, proxλg(x)=(In+λH)−1(x−λq) Logarithmic barrier: g(x) = − n P j=1 log x(j), [proxλg(x)]j=1 2x(j)+qx2 (j)+ 4λ •Many more examples can be fount in Chapter 6 of 6 Beck, A. (2017). First-order methods in optimization. Society for Industrial and Applied Mathematics (SIAM). 6See Section 6.9 for a summary of prox computations. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 16 / 34 We cal also leverage some prox calculus rules Separable sum: g(x) = n P j=1 gj(x(j)), then [proxλg(x)](j)= proxλgj(x(j)). Post-composition: g(x) = αϕ(x) + b, with α > 0, then proxλg(x) = proxαλϕ(x). Pre-composition: g(x) = ϕ(αx +b),α= 0, then proxλg(x) = 1 α(proxα2λϕ(αx +b)−b). Affine addition: g(x) = ϕ(x) + a⊤x+b, then proxλg(x) = proxλϕ(x−λa). Regularization: g(x) = ϕ(x) + ρ 2∥x−a∥2 2, then proxλg(x) = prox˜ λϕ ˜ λ λx+ρ˜ λa,˜ λ=λ 1+ρλ . •More calculus rules can also be found in Chapter 6 of Beck, A. (2017). First-order methods in optimization. Society for Industrial and Applied Mathematics (SIAM). Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 17 / 34 When should we stop the algorithm? If you need a specific sub-optimality threshold f(xk)−f∗≤ϵ, with ϵ > 0, you can use the convergence rates to determine the number of iterations that guarantee this condition.7 •Issue: Convergence rates are an upper-bound ⇒large number of iterations. In a practical setting, we include a termination criterion. For PGM, we can take: Stop the algorithm if L∥xk−xk+1∥2 2≤ϵ. ▶Reason: xkin an optimal solution of the problem if and only if ∥xk−xk+1∥2 2= 0. ▶Since we asymptotically converge to x∗, we take some small ϵinstead. ▶Note: suboptimality will depend on L, so ϵshould take the Lypschitz constant into account. ▶One can also check variations on |f(xk)−f(xk+1)|as an additional stopping criterion. ▶Advantage: very computationally cheap exit condition. ▶Disadvantage: the suboptimality that can be guaranteed is conservative (may require very small ϵto guarantee small suboptimality). 7This can also be done to guarantee that ∥xk−x∗∥ ≤ ϵ, for some ϵ > 0. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 18 / 34 Introduction to accelerated first-order methods Y. Nesterov, “A method of solving a convex programming problem with convergence rate O(1/k2),” Sov. Math. Dokl., vol. 27, no. 2, pp. 372–376, 1983. Accelerated gradient descent The iterations of the accelerated gradient descent method are given by xk+1 =yk−αk∇f(yk), tk+1 =1 21 + q1+4t2 k, yk+1 =xk+1 +tk−1 tk+1 (xk+1 −xk), starting at an initial point x0=y0∈Rnand taking t0= 1. Intuitively, acceleration can be seen as adding momentum to the optimization method. Gradient descent is a static method, but the accelerated method is dynamic! Convergence rate in convex case improves: O(1/k)→ O(1/k2). Also faster in practice! Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 19 / 34 The accelerated PGM: FISTA8 FISTA Require: Initial guess r∈Rn 1y0←r,x0←r,t0←1 2For each k= 0,1,2, . . . repeat 3Pick Lk>0 4xk+1 ←prox 1 Lkgyk−1 Lk∇h(yk) 5tk+1 ←1 21 + q1+4t2 k 6yk+1 =xk+1 +tk−1 tk+1 (xk+1 −xk) •Assumes that his L-smooth and convex, and gis PCC. Beck, A., Teboulle, M. (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1), 183-202. 8Fast Iteratire Shrinkage-Thresholding Algorithm. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 20 / 34 Convergence rate of FISTA Backtracking procedure for FISTA Same procedure as PGM, but the check is: h(xk+1)> h(yk) + ⟨∇h(yk), xk+1 −yk⟩+Lk 2∥xk+1 −yk∥2 2, which you check after Step 4 of FISTA. Set Lk←ηLkuntil the condition is not satisfied. •Let α=Lkif Lk≡ˆ L,9and α=Lmax{η, L−1 L}if backtracking is used. Convergence rate for convex and L-smooth function h f(xk)−f∗≤2α∥x0−x∗∥2 2 (k+ 1)2,∀k > 0. 9Here we are also assuming that the descent lemma is satisfied, e.g., if ˆ L≥L. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 21 / 34 What about the µ-strongly convex case? We have two options Use a restart scheme with linear convergence guarantees.10 Implement V-FISTA. Requires knowing µand L. Denote κ=µ L. V-FISTA Require: Initial guess r∈Rn 1y0←r,x0←r,β←√κ−1−1 √κ−1+1 2For each k= 0,1,2, . . . repeat 3xk+1 ←prox 1 Lgyk−1 L∇h(yk) 4yk+1 =xk+1 +β(xk+1 −xk) Convergence rate of V-FISTA f(xk)−f∗≤1−rµ Lkf(x0)−f∗+µ 2∥x0−x∗∥2 2,∀k≥0. 10Some require knowing µand L, but others provide linear convergence without knowing these parameters. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 22 / 34 An illustrative example Example on a two-dimensional QP problem min x∈R2 1 2x⊤Hx +q⊤x, where H=diag(0.5,1) and q=−(0.1,1). Assume we don’t know L, so we take Lk= 100.a aThe Lypschitz constant is L= 1. We take a conservative Lkto highlight the difference between PGM and FISTA. -0.5 0 0.5 1 0 0.5 1 1.5 2 0 500 1000 1500 2000 10 -12 10 -10 10 -8 10 -6 10 -4 10 -2 10 0 •PGM in dashed-black, FISTA in solid-blue. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 23 / 34 Restart schemes for accelerated first-order methods General restart procedure for algorithm A Require: r0∈Rn,Ec,Et 1k←0,j←1 2repeat 3[rj, kj]← A(rj−1,Ec) 4k←k+kj,j←j+ 1 5Evaluate Et 6until Et= true Output: rout ←rj,jout ←j,kout ←k Restart condition: Ec=(true if certain condition is met false otherwise •Etis the overall exit condition, which should be a measure of suboptimality of rj. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 24 / 34 Restart schemes from the literature Heuristic restart schemes B. O’Donoghue and E. Candes, “Adaptive restart for accelerated gradient schemes,” Foundations of computational mathematics, vol. 15, no. 3, pp. 715–732, 2015. Simple to implement, good performance. They mostly lack theoretical guarantees. Fixed-rate restart schemes I. Necoara, Y. Nesterov, and F. Glineur, “Linear convergence of first order methods for non-strongly convex optimization,” Mathematical Programming, pp. 1–39, 2018. Recovers optimal iteration complexity. Requires difficult to obtain parameters. Adaptive restart schemes (see bibliography in final slides) Theoretical guarantees, good performance. More complex and computational cost. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 25 / 34 Use of SGD for non-convex problems Even though SGD only has guaranteed convergence for L-smooth convex problems, it is often used to solve non-linear problems (mainly for training deep neural networks). In this case, the common choice is to use variants of SGD that add momentum and an adaptive learning rate αk. Popular choices include: Adam, AdaGrad, Adamax, etc. Why? They provide good results, even though they have no convergence guarantee.11 Interested in implementing these methods? My suggestion is to use Python and the packages: jax (https://docs.jax.dev): similar to numpy but with automatic differentiation and JIT compilation. Great for machine learning. jaxopt (https://jaxopt.github.io) and optax (https://optax.readthedocs.io) for solving the learning problem (includes implementation of Adam). 11The very popular Adam algorithm does not even guarantee convergence for L-smooth convex problems. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 32 / 34 General bibliography on gradient methods Parikh, N., Boyd, S. (2014). Proximal algorithms. Foundations and trends®in Optimization, 1(3), 127-239. Light introduction to the proximal operator and PGM. Beck, A. (2017). First-order methods in optimization. Society for Industrial and Applied Mathematics (SIAM). Very good reference for first-order methods. Focus on PGM. Includes FISTA and variants. Nesterov, Y. (2013). Introductory lectures on convex optimization: A basic course (Vol. 87). Springer Science Business Media. Contains many results on first-order methods. Beck, A., Teboulle, M. (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1), 183-202. The article that presented FISTA. Garrigos, G., Gower, R. M. (2023). Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235. Approachable tutorial article on convergence of SGD (and other gradient and SGD-like methods). Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 33 / 34 Some bibliography adaptive restart schemes Estimate µusing “backtracking”: O. Fercoq, and Zheng Qu. ”Adaptive restart of accelerated gradient methods under local quadratic growth condition.” IMA Journal of Numerical Analysis 39.4 (2019): 2069-2095. Lin, Q., Xiao, L. An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization. Comput Optim Appl 60, 633–674 (2015) Estimate µimplicitly: T. Alamo, P. Krupa, and D. Limon, “Restart FISTA with global linear convergence,” in Proceedings of the European Control Conference (ECC), pp. 1969–1974, IEEE, 2019. J. Aujol, et al. ”FISTA restart using an automatic estimation of the growth parameter” (2021). Based on other performance metrics: T. Alamo, P. Krupa, and D. Limon, “Gradient based restart FISTA,” in Proceedings of the Conference on Decision and Control (CDC), pp. 3936–3941, IEEE, Nice, France, 2019. D. Applegate, et al. ”Faster first-order primal-dual methods for linear programming using restarts and sharpness.” Mathematical Programming (2022): 1-52. Pablo Krupa (IMT) An applied course on first-order methods in control December 2025 34 / 34