zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Sự hội tụ của hàm lồi mạnh và hàm trơn

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:7

Báo xấu

12
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết "Sự hội tụ của hàm lồi mạnh và hàm trơn" tìm hiểu các hàm trơn, hàm lồi, hàm lồi mạnh và các tính chất của chúng. Sau đó, chứng minh các bước lặp của thuật toán Gradient Descent là hội tụ sau một số vòng lặp...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sự hội tụ của hàm lồi mạnh và hàm trơn

TẠP CHÍ KHOA HỌC TÀI CHÍNH KẾ TOÁN SỰ HỘI TỤ CỦA HÀM LỒI MẠNH VÀ HÀM TRƠN CONVERGENCE FOR STRONGLY CONVEX AND SMOOTH FUNCTIONS Ngày nhận bài : 13.3.2023 ThS. Nguyễn Tấn Bình Ngày nhận kết quả phản biện : 11.4.2023 Trường Đại học Tài chính - Kế toán Ngày duyệt đăng : 28.4.2023 TÓM TẮT Trong bài viết này, chúng tôi tìm hiểu các hàm trơn, hàm lồi, hàm lồi mạnh và các tính chất của chúng. Sau đó, chúng tôi chứng minh các bước lặp của thuật toán GD là hội tụ sau một số vòng lặp. Trong Định lý 1, chúng tôi chứng minh hội tụ tuyến tính phụ với giả thuyết f là hàm lồi. Trong Định lý 2, chúng tôi chứng minh sự hội tụ tuyến tính (một dạng hội tụ nhanh hơn) với giả thuyết mạnh rằng f là µ -lồi mạnh. Cuối cùng, chúng tôi trình bày kết quả hội tụ của các hàm không lồi thỏa mãn điều kiện Polyak- Lojasiewicz trong Định lý 3. Từ khóa: hàm lồi, hàm lồi mạnh, hàm trơn, Polyak - Lojasiewicz, Gradient Descent ABSTRACT In this article, the author learns about smooth functions, convex functions, strongly convex functions and their properties. Then, we prove that the iterations of the GD algorithm converge after a number of iterations. In Theorem 1, we prove sub-linear convergence in the case that f is a convex function.. In Theorem 2, we prove linear convergence (a faster form of convergence) with the strong hypothesis that is strong µ -convex. Finally, we also present the convergence results of non-convex functions satisfying the condition Polyak- Lojasiewicz in Theorem 3. Keywords: convex function, strong convex function, smooth function, Polyak- Lojasiewicz, Gradient Descent 1. Đặt vấn đề Trong các bài toán machine learning hoặc các bài toán tối ưu nói chung, chúng ta thường phải làm việc với những điểm cực trị (thường là điểm cực tiểu) của một hàm số. Hay trong chương trình phổ ' thông, muốn tìm cực trị một hàm số y = f ( x) chúng ta sẽ giải phương trình y = f ( x) . Tuy nhiên, phương trình trên không phải lúc nào cũng giải được, có những trường hợp việc giải phương trình trên là bất khả thi. Nguyên nhân có thể đến từ sự phức tạp của dạng của đạo hàm. Hướng tiếp cận phổ biến nhất là xuất phát từ một điểm mà chúng ta coi là gần với nghiệm của bài toán, sau đó dùng một phép toán lặp để tiến dần đến điểm cần tìm, tức đến khi đạo hàm gần với 0. Khi đó, thuật toán Gradient Descent cho chúng ta cách thức tìm các điểm cực tiểu cục bộ này một cách xấp xỉ sau một số vòng lặp. 2. Các khái niệm và định lý 2.1. Hàm lồi Định nghĩa 1. Cho f :  d →   {+∞} , f được gọi là hàm lồi nếu ∀x, y ∈  d ; ∀t ∈ [ 0,1] : f (tx + (1 − t ) y ) ≤ tf ( x) + (1 − t ) f ( y ) (1) . Bổ đề 1.[1]. Nếu f :  d →  là lồi và khả vi thì ∀x, y ∈  d , f ( x) ≥ f ( y ) + ∇f ( y ), x − y (2) 102
ĐẠI HỌC TÀI CHÍNH - KẾ TOÁN Chứng minh. Từ (1) ta suy ra f ( y + t ( x − y )) − f ( y ) ≤ tf ( x) − tf ( y ) f ( y + t ( x − y )) − f ( y ) Chia hai vế cho t, ta được f ≤ f ( x) − f ( y ) t Khi t → 0 , ∇f ( y ), x − y ≤ f ( x) − f ( y ) hay ∇f ( y ), x − y + f ( y ) ≤ f ( x) Bổ đề 2.[1] Nếu f :  d →  là lồi và khả vi đến cấp 2, ∀x ∈  d , thì ≥ với mọi giá trị riêng λ của ∇ 2 f ( x) . Chứng minh. Vì f là lồi nên chúng ta có thể sử dụng (2) hai lần và hoán vị vai trò của x và y cho nhau. Sau đó, cộng hai bất đẳng thứ này với nhau ta được f ( x) ≥ f ( y ) + ∇f ( y ), x − y f ( y ) ≥ f ( x) + ∇f ( x), y − x ⇒ 0 ≥ ∇f ( x), y − x + ∇f ( y ), x − y hay ∇f ( y ) − ∇f ( y ), y − x ≥ 0 (3) Với x, v ∈  d . Ta có : ∇f ( x + tv) − ∇f ( x) 1 ∇ 2 f ( x)v, = lim v ,v = lim 2 ∇f ( x + tv) − ∇f ( x), ( x + tv) − x ≥ 0 t →0 t t →0 t (vì theo bất đẳng thứ (3) khi thay y= x + tv ) Khi λ là giá trị riêng của ∇ f ( x) , lấy bất kì vecto riêng v ∈  d , ta viết 2 2 λ v = λ v, v = ∇ 2 f ( x )v, v ≥ 0 ⇒ λ ≥ 0 2.2. Hàm lồi mạnh Định nghĩa 2. Cho f :  d →   {+∞} và µ > 0 . ta nói rằng f là µ -lồi mạnh nếu ∀x, y ∈  d ; ∀t ∈ [ 0,1] , ta có: t (1 − t ) 2 µ x − y + f (tx + (1 − t ) y ) ≤ tf ( x) + (1 − t ) f ( y ) 2 Ta nói, µ là hằng số lồi mạnh của f . Bổ đề 3. Cho f :  d →  và µ > 0 . Hàm f là µ -lồi mạnh khi và chỉ khi tồn tại một hàm lồi µ 2 g :  d →  sao cho f= g ( x) + x ( x) 2 Chứng minh. Đặt zt = tx + (1 − t ) y µ 2 f là µ -lồi mạnh ⇔ f ( zt ) + t (1 − t ) x − y ≤ (1 − t ) f ( x) + tf ( y ) 2 Do đó, với mọi t, x, y ta có µ 2 µ 2 µ 2 µ 2 g ( zt ) + zt + t (1 − t ) x − y ≤ (1 − t ) g ( x) + tg ( y ) + (1 − t ) x + t y 2 2 2 2 Nhóm các số hạng chứa µ ta được: 1 2 1 2 1 2 1 2 µ zt + t (1 − t ) x − y − (1 − t ) x − t y  2 2 2 2  ( 2 2 2 2 = µ (1 − t ) 2 x + t 2 y + 2t (1 − t ) x, y + t (1 − t ) x + t (1 − t ) y − 2t (1 − t ) x, y − (1 − t ) x − t y 2 2 ) 103
TẠP CHÍ KHOA HỌC TÀI CHÍNH KẾ TOÁN = µ  x ((1 − t ) 2 + t (1 − t ) − (1 − t )) + y (t 2 + t (1 − t= µ .0. ) − t ) 2 2   Như vậy, tất cả các số hạng chứa µ bị triệt tiêu, phần còn lại theo định nghĩa là hàm g lồi. 2 Nhận xét: Chỉ cần cộng thêm bội của . vào hàm lồi thì ta được hàm lồi mạnh. Bổ đề 4.[1]. Nếu f :  d →  là µ -lồi mạnh và khả vi thì µ 2 ∀x, y ∈  d , f ( y ) ≥ f ( x) + ∇f ( x), y − x + y−x (4) 2 Chứng minh. µ 2 Vì f là µ -lồi mạnh nên theo bổ đề 3, tồn tại g sao cho: f= g ( x) + x , trong đó g là lồi. ( x) Theo quy tắc tính tổng, ta có ∇f ( x) = x) + µ x . 2 ∇g ( µ 2 µ 2 µ 2 Do đó, f ( y ) − f ( x) − ∇f ( x), y − x ≥ y − x − µ x, y − =x y−x 2 2 2 2.3. Polyak- Lojasiewicz Định nghĩa 3. Cho f :  d →  khả vi và µ > 0 . Ta nói rằng f là µ - Polyak- Lojasiewicz nếu 1 2 f bị chặn dưới và ∀x ∈  d , f ( x) − inf f ≤ ∇f ( x ) (5) . 2µ Ta nói f là Polyak- Lojasiewicz (hay PL) nếu tồn tại µ > 0 sao cho f là µ - Polyak- Lojasiewicz. Kết quả dưới đây cho ta thấy tính Polyak- Lojasiewicz yếu hơn tính lồi mạnh Bổ đề 5[1]. Giả sử f :  d →  là khả vi và µ > 0 . Nếu f là µ -lồi mạnh thì f là µ - Polyak- Lojasiewicz. Chứng minh. Đặt x* là cực tiểu của f sao cho f ( x* ) = inf f . Nhân (4) với -1 và thay y bởi x* . Ta được: µ 2 f ( x) − f ( x* ) ≤ ∇f ( x), x − x* − ∇f ( x) 2 2 1 1 1 2 1 2 = µ (x − x ) − * ∇f ( x ) + ∇f ( x ) ≤ ∇f ( x ) 2 µ 2µ 2µ Bổ đề 6[1]. Cho f :  d →  là hàm PL khả vi . x* ∈ arg min f ⇔ ∇f ( x* ) =0 Bổ đề được chứng minh bằng cách thay x bởi x* vào (5) 2.4. Hàm trơn Định nghĩa 4. Cho F :  d →  p và L > 0 . Ta nói rằng F là L -Lipschitz nếu ∀x, y ∈  d , F ( y ) − F ( x) ≤ L y − x . . Định nghĩa 5. Cho f :  d →  và L > 0 . Ta nói rằng f là L -trơn nếu f khả vi và ∇f :  d →  d là L -Lipschitz: ∀x, y ∈  d , ∇f ( x) − ∇f ( y ) ≤ L x − y (6) 2.4.1. Tính chất hàm trơn và không lồi Bổ đề 7.[1]. Nếu f :  d →  là L -trơn thì L 2 ∀x, y ∈  d , f ( y ) ≤ f ( x) + ∇f ( x), y − x + y−x (7) 2 104
ĐẠI HỌC TÀI CHÍNH - KẾ TOÁN Bổ đề 8.[1]. Nếu f :  d →  là L -trơn và λ > 0 thì  λL  2 ∀x, y ∈  d , f ( x − λ∇f ( x)) − f ( x) ≤ −λ 1 −  ∇f ( x ) (8)  2  Bổ đề 9.[1]. Nếu f là L -trơn và có đạo hàm đến cấp 2 thì ∀x ∈  d , với mỗi giá trị riêng λ của ∇ 2 f ( x) , chúng ta có λ ≤ L 2.4.2. Tính chất hàm trơn và lồi Bổ đề 10.[1]. Nếu f :  d →  là L -trơn và lồi thì ∀x, y ∈  d , chúng ta có 1 2 i. ∇f ( y ) − ∇f ( x) ≤ f ( y ) − f ( x) − ∇f ( x), y − x (9) 2L 1 2 ii. ∇f ( y ) − ∇f ( x) ≤ ∇f ( y ) − ∇f ( x), y − x (10) L Chứng minh. i, áp dụng (2) và (7), ∀z ∈  d , cố định x, y ∈  d . Ta có: f ( x) − f ( y ) = f ( x) − f ( z ) + f ( z ) − f ( y ) L 2 ≤ ∇f ( x), x − z + ∇f ( y ), z − y + z−y 2 1 Cực tiểu hóa vế phải đối với z, ta được z= y − ( ∇f ( y ) − ∇f ( x ) ) L Từ đó suy ra, L 2 f ( x) − f ( y ) ≤ ∇f ( x), x − z + ∇f ( y ), z − y + z−y 2 1 2 1 2 ≤ ∇f ( x), x − z − ∇f ( y ) − ∇f ( x) + ∇f ( y ) − ∇f ( x ) L 2L 1 2 ≤ ∇f ( x), x − y − ∇f ( y ) − ∇f ( x ) 2L ii, Áp dụng (9) hai lần và thay đổi vai trò x và y cho nhau ta được 1 2 ∇f ( y ) − ∇f ( x) ≤ f ( y ) − f ( x) − ∇f ( x), y − x 2L 1 2 ∇f ( x) − ∇f ( y ) ≤ f ( x) − f ( y ) − ∇f ( y ), x − y 2L Cộng vế theo vế 2 bất phương trình trên ta có (10) 3. Giảm dần độ dốc Bài toán đặt ra: Chúng ta muốn cực tiểu hóa một hàm khả vi f :  d →  với điều kiện bài toán thỏa mãn arg min f ≠ ∅ . Thuật toán Gradient Descent (GD): Cho x 0 ∈  d và γ > 0 là tốc độ học. Thuật toán GD xác định 1 dãy ( xt )t∈N thỏa mãn xt +1 = xt − γ∇f ( xt ) (*) . Dưới đây chúng ta sẽ chứng minh các bước lặp của thuật toán GD hội tụ 3.1. Sự hội tụ của hàm lồi và hàm trơn Định lý 1. [1]. Cho hàm khả vi f :  d →  là lồi và L -trơn. Đặt ( xt )t∈N là một dãy phép lặp của 2 L * x 0 − x* thuật toán GD, với 0 < γ < , x ∈ arg min f , t ∈ N . Ta có f ( x ) − inf f ≤ t . 2 2γ t 105
TẠP CHÍ KHOA HỌC TÀI CHÍNH KẾ TOÁN Chứng minh. Đầu tiên, chúng ta kiểm tra f ( xt ) là giảm. Thật vậy, với x* ∈ arg min f , từ (8) với giả thiết γ L ≤ 1 .  γL t 2 Ta có f ( xt +1 ) − f ( xt ) ≤ −γ 1 −  ∇f ( x ) ≤ 0 (11)  2  2 Tiếp theo, ta chứng minh xt − x* giảm dần. 1 t +1 * 2 1 t 2 −1 t +1 t 2 x −x − x − x* = x − x − ∇f ( xt ), xt +1 − x* 2γ 2γ 2γ −1 t +1 t 2 = x − x − ∇f ( x t ), x t +1 − x t + ∇f ( xt ), x* − xt (12) 2γ Áp dụng tính lồi của f và (2), ta có ∇f ( x t ), x* − x t ≤ f ( x* ) − f ( x t )= inf f − f ( x t ) Theo (7) và tính chất L- trơn của hàm f thì L 2 − ∇f ( xt ), xt +1 − xt ≤ xt +1 − xt + f ( xt ) − f ( xt +1 ) 2 Từ (12) và 2 bất đẳng trên, ta suy ra 1 t +1 * 2 1 t 2 −1 t +1 2 x −x − x − x* ≤ x − x t − ( f ( x t +1 ) − inf f ) ≤ −( f ( x t +1 ) − inf f ) (13) 2γ 2γ 2γ 1 t 2 Kết hợp hai đại lượng giảm dương f ( x t ) − inf f , x − x* và hàm năng lượng Lyapunov cho bởi: 2γ 1 t 2 =Et x − x* + t ( f ( x t ) − inf f ) , ∀t ∈  2γ Ta sẽ chứng minh hàm năng lượng này là hàm giảm. Thật vậy, 1 t +1 * 2 1 t Et +1 − Et = t + 1) ( f ( x t +1 ) − f ( x t ) ) − t ( f ( x t ) − inf f ) + 2 ( x −x − x − x* 2γ 2γ 1 t +1 * 2 1 t = f ( x t +1 ) − inf f + t ( f ( x t +1 ) − f ( x t ) ) + 2 x −x − x − x* (14) 2γ 2γ Từ (11), (13), (14) ta thu được kết quả sau: 1 t +1 * 2 1 t Et +1 − Et ≤ f ( x t +1 ) − inf f + t ( f ( x t +1 ) − f ( x t ) ) + 2 x −x − x − x* 2γ 2γ ≤ f ( x t +1 ) − inf f − ( f ( x t +1 ) − inf f ) ≤0 Vậy Et là hàm giảm. Do đó, ta suy ra được 1 0 t ( f ( x t ) − inf f ) ≤ Et ≤ E0 2 = x − x* 2γ 1 0 2 ⇒ f ( x t ) − inf f ≤ x − x* 2tγ 3.2. Sự hội tụ của hàm lồi mạnh và hàm trơn Định lý 2.[1] Cho hàm khả vi f :  d →  là µ -lồi mạnh và L -trơn. Với L ≥ µ > 0 , đặt 106
ĐẠI HỌC TÀI CHÍNH - KẾ TOÁN L * (x ) t t∈N là một dãy dãy phép lặp của thuật toán GD, với 0 < γ < 2 , x ∈ arg min f , t ∈ N . Ta có 2 2 xt +1 − x* ≤ (1 − γµ )t +1 x 0 − x* . Chứng minh. Từ thuật toán GD ta có, 2 2 2 2 x t +1 − x* = x t − x * − γ∇f ( x t ) = x t − x* − 2γ ∇f ( x t ), x t − x* + γ 2 ∇f ( x t ) (4) 2 2 ≤ (1 − γµ ) x t − x* − 2γ ( f ( x t ) − inf f ) + γ 2 ∇f ( x t ) (8) 2 ≤ (1 − γµ ) x t − x* − 2γ ( f ( x t ) − inf f ) + 2γ 2 L( f ( x t ) − inf f ) 2 = − γµ ) x t − x* − 2γ (1 − γ L)( f ( x t ) − inf f ) (1 1 2 2 Vì γ ≤ nên −2γ (1 − γ ) < 0 . Do đó, xt +1 − x* ≤ (1 − γµ ) xt − x* L 3.3. Sự hội tụ của Polyak- Lojasiewicz và các hàm trơn Định lý 3. [1]. Cho hàm khả vi f :  d →  là µ -Polyak-Lojasiewicz và L -trơn. Với L L ≥ µ > 0 . Xét ( x )t∈N là một dãy dãy phép lặp của thuật toán GD, với 0 < γ < , . Ta có t 2 f ( x t ) − in f f ≤ (1 − γµ )t ( f ( x 0 ) − in f f ) . Chứng minh. Từ (7) ta có: L t +1 t 2 f ( xt +1 ) ≤ f ( xt ) + ∇f ( xt ), xt +1 − xt + x −x 2 2 L 2 2 = f ( x t ) − γ ∇f ( x t ) + γ ∇f ( x t ) 2 γ 2 γ 2 = f ( xt ) − (2 − Lγ ) ∇f ( xt ) ≤ f ( xt ) − ∇f ( xt ) 2 2 với γ L ≤ 1 . Theo tính chất Polyak-Lojasiewicz, ta viết lại f ( x t +1 ) ≤ f ( x t ) − γµ ( f ( x t ) − inf f ) . Trừ cả 2 vế của bất đẳng thức cho inf f và quy nạp thì ta được kết quả cần chứng minh. TÀI LIỆU THAM KHẢO 1. Guillaume Garrigos, Robert M.Gower (1/2023), Handbook of Convergence Theorems for (Stochastic) Gradient Methods, Center of Computational Mathematics Flatiron Institute, New York. 2. Mark Schmid, Nicolas Le Roux, Francis Bath (2011), Convergence Rates of Inexact Proximal- Gradient Method for Convex Optimization, France. 3. http://www.benfrederickson.com/numerical-optimization/ 107
TẠP CHÍ KHOA HỌC TÀI CHÍNH KẾ TOÁN THỂ LỆ VIẾT BÀI, GỬI BÀI ĐĂNG TRÊN TẠP CHÍ KHOA HỌC TÀI CHÍNH KẾ TOÁN 1. Bài nhận đăng là các công trình mới có ý nghĩa khoa học và thực tiễn trong các lĩnh vực khoa học cơ bản, khoa học xã hội - nhân văn, kỹ thuật, kinh tế, tài chính, kế toán, v.v..., chưa công bố ở bất kỳ tạp chí nào. Tác giả tự chịu trách nhiệm về nội dung, tính minh bạch, tính khoa học độc lập của bài viết. Nếu muốn ngừng đăng hoặc chuyển sang tạp chí khác, tác giả phải thông báo ngay cho Ban Biên tập. 2. Bài báo khoa học phải bao gồm các phần: 2.1. Tựa bài: Phản ảnh nội dung chính của bài viết. 2.2. Tóm tắt: Bằng tiếng Việt và tiếng Anh (in nghiêng), nêu ý tưởng và nội dung chính bài viết, không quá 200 từ. 2.3. Phần nội dung bài viết: Nêu lên được kết quả nghiên cứu của tác giả, với các phần: Đặt vấn đề, giải quyết vấn đề, kết luận. 2.4. Phần tài liệu tham khảo: Tài liệu tham khảo ghi theo trình tự: Tên tác giả, năm xuất bản, tên sách (hoặc tạp chí), nhà xuất bản, nơi xuất bản (tập, số, năm xuất bản đối với tạp chí). Tất cả đều viết bằng tiếng của nước đã xuất bản ấn phẩm, không phiên âm, chuyển ngữ hoặc dịch. 3. Bài gửi đăng được soạn thảo theo font chữ Times New Roman, bảng mã Unicode, cỡ chữ 12, định dạng lề trên 2.5 cm, lề dưới 2 cm, lề trái 3 cm, lề phải 2 cm, khoảng cách dòng: single, khoảng cách đoạn: 3pt. Công thức toán học dùng MS Equation hoặc phần mềm gõ công thức toán học (Mathtypes). Bài viết dài tối đa không quá 6 trang A4, kể cả tài liệu tham khảo. 4. Cuối bài viết, tác giả ghi rõ họ tên, học hàm, học vị, tên cơ quan và địa chỉ, điện thoại và email để tiện liên lạc. 5. Hình thức gửi bài: Bài gửi về Ban Biên tập bằng cả 2 hình thức: Bản in trên giấy A4 và file dữ liệu. 6. Thời gian gửi bài: Ban Biên tập thường xuyên nhận bài gửi đăng từ các tác giả trong và ngoài trường, tổ chức thẩm định và xét duyệt theo quy định của Tạp chí. Các bài gửi đăng đạt yêu cầu sẽ được đăng trên số Tạp chí định kỳ phát hành gần nhất. Bài không đăng sẽ được thông báo cho tác giả, tòa soạn không trả lại bản thảo. 7. Địa chỉ gửi bài: Tạp chí Khoa học Tài chính Kế toán, Trường Đại học Tài chính - Kế toán; Thị trấn La Hà, Huyện Tư Nghĩa, Tỉnh Quảng Ngãi; điện thoại: (0255) 3912482; email: tapchidhtckt@tckt.edu.vn In 200 bản, khổ 19 x 27cm tại Trung tâm xuất bản Giao thông vận tải miền Trung - 132 Nguyễn Thị Minh Khai TP. Đà Nẵng. Xong và nộp lưu chiểu 5. 2023 108

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.