Độ dài của đường đi gradient flow trên một hàm lồi có thể là bao nhiêu, với ràng buộc rằng nó phải nằm trong hình cầu Euclid đơn vị trong không gian n chiều?
^ đây là câu hỏi tôi đã dùng suốt 2 năm nay để kiểm tra sự tiến bộ của AI. Diễn đạt thì đơn giản đến kỳ lạ, nhưng giải quyết lại khó đến mức khủng khiếp. Sau 168 phút suy nghĩ, GPT-5.6 đã có thể vượt trội hơn hẳn so với SOTA đã công bố cho câu hỏi này, theo một cách mà chưa có mô hình nào khác làm được. Nhưng tôi đang đi hơi xa, hãy cùng suy nghĩ một chút về câu hỏi này, xem lại các tài liệu nghiên cứu, và sau đó thảo luận về sự tiến bộ từ o3 lên gpt-5.6 đã diễn ra như thế nào.
1. SOTA
Một cách ngây thơ, người ta có thể nói: "ồ, gradient descent có tốc độ hội tụ không phụ thuộc vào số chiều -- đó là lý do tại sao nó thú vị cho các bài toán nhiều tham số!-- vậy thì có lẽ độ dài của một đường đi như vậy cũng không phụ thuộc vào số chiều?". Vâng, đôi khi những suy nghĩ ngây thơ có thể sai hoàn toàn. Trước hết: những đường cong như vậy có thể đo được (tức là có độ dài hữu hạn, chưa nói đến sự phụ thuộc vào số chiều) hay không??? Ngay cả điều đó cũng không dễ chứng minh, và thực tế nó SAI đối với Nesterov's accelerated gradient descent (xem bài báo này của @ErnestRyu, tất cả đều được thực hiện với gpt-5.5).
Vậy chính xác thì chúng ta biết gì về câu hỏi này? Có một bài báo tuyệt vời năm 1991 của Manselli và Pucci đã chỉ ra rằng những đường cong như vậy thực sự có thể đo được, và hơn nữa chiều dài của chúng nhiều nhất là n^O(n). Vâng, bạn đọc đúng rồi đấy, thậm chí còn tệ hơn hàm mũ trong số chiều, đó là chặn tốt nhất từ 35 năm trước!! Nhân tiện, bài báo này cũng chỉ ra rằng những đường cong như vậy được gọi là "self-contracted" (tự co lại), tức là chúng luôn tiến gần hơn đến tương lai của chúng (lấy bất kỳ điểm nào trên đường cong tại thời điểm t, thì dist(x(s), x(t)) là không tăng đối với s<t; xem hình minh họa bên dưới).
Còn về chặn dưới, tức là xây dựng một đường cong self-contracted thực sự dài? Một điều tiêu chuẩn để xem xét từ tài liệu về tối ưu hóa lồi sẽ là một quadratic có điều kiện xấu, một cái gì đó như x_1^2 + large_cst\x_2^2 + even_larger_cst\x_3^2 + ... Vấn đề là gradient descent sẽ đầu tiên đi gần như thẳng dọc theo hướng có large_cst lớn nhất, sau đó đi theo hướng có cst lớn thứ hai, và cứ tiếp tục như vậy (xem hình minh họa bên dưới). Vậy tổng chiều dài của đường đi sẽ xấp xỉ n, và đường đi được chứa trong hypercube nằm trong một hình cầu bán kính sqrt(n), do đó bằng cách co giãn lại, chúng ta có được một đường cong self-contracted có độ dài sqrt(n).
Đó là tất cả. Đó là SOTA đã được công bố: chặn trên là n^O(n) và chặn dưới là sqrt(n). Một khoảng cách khá lớn cho một câu hỏi đơn giản và tự nhiên như vậy!!!
Định nghĩa của một đường cong self-contracted
Một đường cong self-contracted có độ dài sqrt(n)
2. Công trình chưa công bố của con người
Tôi đã suy nghĩ về câu hỏi này 8 năm trước cùng với các cộng tác viên tuyệt vời Omer Angel, Tomas Merchan Rodriguez và Fedja Nazarov. Chúng tôi đã đạt được một số tiến bộ đáng kể và xác định rằng câu trả lời thực sự là hàm mũ trong số chiều!! Cụ thể, chúng tôi có chặn dưới là sqrt(2)^n và chặn trên là 4^n. Bài báo với các ước lượng này được viết rất gọn gàng và đã nằm trong thư mục Dropbox của tôi gần một thập kỷ nay, một phần vì chúng tôi biết rằng những chặn này có thể được cải thiện thêm. Và thực sự Tomas và Fedja đã tiến bộ hơn nữa, đầu tiên là đẩy chặn dưới lên 2^n và cũng cải thiện chặn trên lên 2.29...^n. Lưu ý rằng sự hiểu biết của riêng tôi về vấn đề này vẫn dừng lại ở chặn dưới tốt hơn một chút so với sqrt(2)^n và chặn trên 4^n (thực tế, tôi đã quên mất các chặn 2^n và 2.29^n cho đến khi AI bắt đầu có tiến bộ trong vấn đề này ... sẽ nói thêm bên dưới).
3. Tiến bộ của AI
o3 là mô hình AI đầu tiên thậm chí còn hiểu được câu hỏi. Vâng, bạn đọc đúng câu đó. Có thể bạn đã quên, nhưng hai năm trước, thậm chí còn chưa rõ liệu AI có thể HIỂU được những câu hỏi đơn giản một cách lừa dối như vậy hay không, chứ đừng nói đến việc giải quyết chúng. Cụ thể, o3 có thể thấy rằng câu hỏi thực ra là về các đường cong tự co lại, và biết SOTA cho câu hỏi này là gì. Tôi đã vô cùng ấn tượng vào thời điểm đó.
Nhưng sau đó mọi thứ trở nên phức tạp, và với sự xuất hiện của dòng mô hình GPT-5, tôi đã dùng câu hỏi này như một câu chuyện cảnh báo: gần đây nhất là vào tháng Hai năm nay, tôi đã đưa câu hỏi này trong các bài nói về sự tiến bộ của LLM trong toán học như một ví dụ về câu hỏi bạn KHÔNG NÊN hỏi LLM. Lý do là GPT-5 hay thậm chí GPT-5.2/5.4 sẽ CỐ GẮNG đưa ra những câu trả lời phức tạp, nhưng chúng luôn có sai sót ở đâu đó, và người ta sẽ mất rất nhiều thời gian để kiểm tra chúng. Vì vậy, đó là một ví dụ tốt rằng để không lãng phí thời gian với LLM trong toán học, người ta nên biết cấp độ câu hỏi thích hợp để hỏi.
Điều này đã thay đổi với GPT-5.5, và đột nhiên, với rất nhiều trao đổi qua lại và chuyên gia prompting, Mark Sellke đã có thể tái khám phá ra cấu trúc chặn dưới 2^n (điều mà tôi đã BỊ SỐC, một phần vì tôi đã quên rằng Tomer và Fedja đã biết nó 😅). Mặt khác, không có may mắn nào với chặn trên.
Và bây giờ đến GPT-5.6, và sự tiến bộ của AI hiện ra đầy đủ:
- GPT-5.6-pro CHỈ MỘT LẦN đã tìm ra chặn dưới 2^n. Bạn có thể xem lần chạy một lần này tại đây (80 phút suy nghĩ): https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
- GPT-5.6-pro CHỈ MỘT LẦN đã tìm ra chặn trên 4^n, và thực tế là nó làm điều đó rất nhanh trong chuỗi suy nghĩ (CoT), và vào cuối quá trình suy nghĩ, nó tạo ra chặn trên 2.31...^n. Không hoàn toàn bằng với chặn dưới 2.29...^n của Fedja (và thực tế chiến lược 2.31...^n không thể cải thiện thêm nếu không có những ý tưởng mới -- thực tế Fedja đã tự nhận xét điều đó trong một bài đăng trên MathOverflow vào năm 2018: "[đối với 2.31..] lập luận trở nên khá lộn xộn và rõ ràng là hướng này sẽ không dẫn đến ước lượng tối ưu"). Nhưng vẫn khá ấn tượng và vượt xa những gì tôi đã hiểu về vấn đề này khi tôi còn làm việc nghiêm túc với nó. Bạn có thể xem lần chạy một lần này tại đây, được thực hiện trong 88 phút suy nghĩ: https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64
3. Một thử thách cho tương lai
Câu chuyện này hiện tại vẫn có con người là người chiến thắng. 2.29 cho con người so với 2.31 cho máy móc. Một cách tự nhiên, giả thuyết là các đường cong tự co lại không thể dài hơn 2^n (do đó sẽ là câu trả lời tối ưu với chặn dưới 2^n). Điều này có vẻ rất khó chứng minh và vượt quá khả năng của GPT-5.6. Tôi sẽ còn có thể sử dụng câu hỏi này để theo dõi sự tiến bộ của AI trong bao lâu? Tôi nghi ngờ có thể là ít hơn 6 tháng ...
PS: Tôi đã copy-paste bài viết trên vào ChatGPT work và yêu cầu nó tạo ra các hình minh họa cho nó. Bộ sưu tập hình ảnh ở đây được lấy từ một lần truy vấn đó.
