Apple giới thiệu thuật toán LIPPAX: Đột phá tốc độ hội tụ cho bất đẳng thức biến phân liên kết

Tác giả: Guanghui Wang†**, Satyen Kale

Trong bài báo này, chúng tôi nghiên cứu tối ưu hóa liên kết (federated optimization) để giải quyết các bất đẳng thức biến phân (VIs) ngẫu nhiên, một vấn đề đang thu hút sự quan tâm ngày càng lớn trong những năm gần đây. Mặc dù đã có những tiến bộ đáng kể, vẫn tồn tại một khoảng cách lớn giữa tốc độ hội tụ hiện có và các giới hạn tiên tiến nhất (state-of-the-art) đã biết trong tối ưu hóa lồi liên kết. Trong công trình này, chúng tôi giải quyết hạn chế đó bằng cách thiết lập một loạt các tốc độ hội tụ cải tiến. Đầu tiên, chúng tôi chỉ ra rằng, đối với các bất đẳng thức biến phân trơn và đơn điệu tổng quát, thuật toán Local Extra SGD cổ điển có các đảm bảo chặt chẽ hơn dưới một phân tích tinh chỉnh. Tiếp theo, chúng tôi xác định một hạn chế cố hữu của Local Extra SGD, vốn có thể dẫn đến hiện tượng trôi dạt máy khách (client drift) quá mức. Từ quan sát này, chúng tôi đề xuất một thuật toán mới, Local Inexact Proximal Point Algorithm with Extra Step (LIPPAX), và chứng minh rằng nó giúp giảm thiểu hiện tượng trôi dạt máy khách và đạt được các đảm bảo cải tiến trong một số chế độ, bao gồm các thiết lập Hessian bị chặn, toán tử bị chặn và phương sai thấp. Cuối cùng, chúng tôi mở rộng kết quả của mình cho các bất đẳng thức biến phân hỗn hợp liên kết và thiết lập các đảm bảo hội tụ cải tiến.

• † Viện Công nghệ Georgia
• ** Công trình được thực hiện khi đang làm việc tại Apple

Các bài đọc liên quan và cập nhật.

Trong bài báo này, chúng tôi nghiên cứu tối ưu hóa liên kết để giải quyết các bất đẳng thức biến phân (VIs) ngẫu nhiên, một vấn đề đang thu hút sự quan tâm ngày càng lớn trong những năm gần đây. Mặc dù đã có những tiến bộ đáng kể, vẫn tồn tại một khoảng cách lớn giữa tốc độ hội tụ hiện có và các giới hạn tiên tiến nhất đã biết trong tối ưu hóa lồi liên kết. Trong công trình này, chúng tôi giải quyết hạn chế đó bằng cách thiết lập một loạt các tốc độ hội tụ cải tiến. Đầu tiên, chúng tôi chỉ ra rằng,…

Đọc thêm

Trong thực tế, việc huấn luyện sử dụng học liên kết (federated learning) có thể chậm hơn hàng chục lần so với huấn luyện tập trung tiêu chuẩn. Điều này hạn chế nghiêm trọng số lượng thử nghiệm và tinh chỉnh có thể thực hiện, gây khó khăn cho việc đạt được hiệu suất tốt trên một tác vụ nhất định. Dữ liệu proxy phía máy chủ có thể được sử dụng để chạy các mô phỏng huấn luyện, ví dụ như để tinh chỉnh siêu tham số. Điều này có thể tăng tốc đáng kể quy trình huấn luyện bằng cách giảm số lượng tinh chỉnh…

Đọc thêm