เส้นทางของ gradient flow บนฟังก์ชันนูนจะยาวได้เท่าใด ภายใต้ข้อจำกัดว่ามันต้องอยู่ใน unit Euclidean ball ในมิติ n?
^ นี่คือคำถามที่ผมใช้มาสองปีแล้วเพื่อทดสอบความก้าวหน้าของ AI คำถามนี้ฟังดูง่ายมากแต่ก็ยากเหลือเกินที่จะแก้ ในเวลา 168 นาทีของการคิด GPT-5.6 สามารถทำผลงานได้ดีกว่า SOTA ที่ตีพิมพ์เผยแพร่ไว้มากอย่างมีนัยสำคัญสำหรับคำถามนี้ ในแบบที่ไม่มีโมเดลอื่นใดทำได้มาก่อน แต่ผมกำลังพูดเร็วไปหน่อย มาคิดเกี่ยวกับคำถามนี้กันก่อน ทบทวนวรรณกรรมที่เกี่ยวข้อง แล้วค่อยพูดถึงว่าความก้าวหน้าจาก o3 ถึง gpt-5.6 เป็นอย่างไรบ้าง
1. SOTA
คนทั่วไปอาจพูดว่า: "gradient descent มีอัตราการลู่เข้าที่ไม่ขึ้นกับมิติ (dimension-free) ซึ่งเป็นเหตุผลว่าทำไมมันถึงน่าตื่นเต้นสำหรับปัญหาที่มีพารามิเตอร์จำนวนมาก ดังนั้นความน่าจะเป็นที่ความยาวของ gradient flow ดังกล่าวก็น่าจะไม่ขึ้นกับมิติด้วย?" เอาล่ะ บางครั้งความคิดแบบคนทั่วไปก็ผิดอย่างมหันต์ได้ เริ่มต้นเลย: เส้นโค้งแบบนี้สามารถวัดความยาวได้ (rectifiable คือมีความยาวจำกัด ยังไม่ต้องพูดถึงการพึ่งพามิติ) หรือไม่??? แม้แต่การพิสูจน์เรื่องนี้ก็ไม่ใช่เรื่องง่าย และที่จริงมันเป็นเท็จสำหรับ Nesterov's accelerated gradient descent (ดู บทความนี้ โดย @ErnestRyu ซึ่งทำทั้งหมดด้วย gpt-5.5)
โอเค แล้วเรารู้อะไรเกี่ยวกับคำถามนี้บ้าง? มีบทความที่สวยงามในปี 1991 โดย Manselli และ Pucci ที่แสดงให้เห็นว่าเส้นโค้งดังกล่าวสามารถวัดความยาวได้จริง และยิ่งไปกว่านั้น ความยาวของมันสูงสุดคือ n^O(n) ใช่ คุณอ่านถูกต้องแล้ว แย่กว่า exponential เมื่อเทียบกับมิติเสียอีก นั่นคือขอบเขตที่ดีที่สุดจากเมื่อ 35 ปีที่แล้ว!! อนึ่ง บทความนี้ยังชี้ให้เห็นว่าเส้นโค้งดังกล่าวเป็นสิ่งที่เรียกว่า "self-contracted" กล่าวคือ มันจะเข้าใกล้จุดในอนาคตของมันเสมอ (หยิบจุดใดๆ บนเส้นโค้งที่เวลา t แล้ว dist(x(s), x(t)) จะไม่เพิ่มขึ้นสำหรับ s<t; ดูภาพประกอบด้านล่าง)
ทีนี้แล้วขอบเขตล่างล่ะ นั่นคือการสร้างเส้นโค้ง self-contracted ที่ยาวจริงๆ? สิ่งมาตรฐานที่เรามักดูในวรรณกรรมการหาค่าเหมาะที่สุดแบบนูน (convex optimization) คือ quadratic ที่มี conditioning ไม่ดี เช่น x_1^2 + large_cst\x_2^2 + even_larger_cst\x_3^2 + ... ประเด็นคือ gradient descent จะเคลื่อนที่เกือบเป็นเส้นตรงในทิศทางที่มี large_cst มากที่สุดก่อน จากนั้นไปในทิศทางที่มี large_cst รองลงมา และต่อไปเรื่อยๆ (ดูภาพประกอบด้านล่าง) ดังนั้นความยาวรวมของเส้นทางจะเป็นประมาณ n และเส้นทางจะอยู่ใน hypercube ซึ่งอยู่ใน ball ที่มีรัศมี sqrt(n) ดังนั้นเมื่อปรับขนาดใหม่ เราจะได้เส้นโค้ง self-contracted ที่มีความยาว sqrt(n)
แค่นั้นแหละ นั่นคือ SOTA ที่ตีพิมพ์เผยแพร่ไว้: ขอบเขตบนเป็น n^O(n) และขอบเขตล่างเป็น sqrt(n) ช่องว่างมหาศาลสำหรับคำถามที่ทั้งเรียบง่ายและเป็นธรรมชาติเช่นนี้!!!
คำจำกัดความของเส้นโค้ง self-contracted
เส้นโค้ง self-contracted ความยาว sqrt(n)
2. งานที่ยังไม่ได้ตีพิมพ์โดยมนุษย์
ผมคิดเกี่ยวกับคำถามนี้เมื่อ 8 ปีที่แล้วร่วมกับผู้ร่วมงานที่ยอดเยี่ยม Omer Angel, Tomas Merchan Rodriguez, และ Fedja Nazarov เราสามารถสร้างความก้าวหน้าได้พอสมควรและพิสูจน์ว่าคำตอบนั้นเป็น exponential ในมิติจริงๆ!! โดยเฉพาะเรามีขอบเขตล่างเป็น sqrt(2)^n และขอบเขตบนเป็น 4^n บทความที่มีการประมาณค่าเหล่านี้เขียนไว้อย่างเรียบร้อยและนั่งอยู่ในโฟลเดอร์ dropbox ของผมมาเกือบสิบปีแล้ว ส่วนหนึ่งเพราะเรารู้ว่าขอบเขตเหล่านี้สามารถปรับปรุงเพิ่มเติมได้ และแน่นอน Tomas กับ Fedja ก็สร้างความก้าวหน้าเพิ่มขึ้น โดยเริ่มจากการผลักดันขอบเขตล่างขึ้นไปถึง 2^n และปรับปรุงขอบเขตบนเป็น 2.29...^n โปรดทราบว่าความเข้าใจของผมเองในปัญหานี้ยังคงอยู่ที่ขอบเขตล่างที่มากกว่า sqrt(2)^n เล็กน้อยและขอบเขตบนที่ 4^n (อันที่จริง ผมลืมเรื่อง 2^n และ 2.29^n ไปแล้ว จนกระทั่ง AI เริ่มสร้างความก้าวหน้าในเรื่องนี้... รายละเอียดเพิ่มเติมด้านล่าง)
3. ความก้าวหน้าของ AI
o3 เป็นโมเดล AI ตัวแรกที่เข้าใจคำถามนี้ด้วยซ้ำ ใช่ คุณอ่านประโยคนั้นถูกต้องแล้ว คุณอาจลืมไป แต่เมื่อสองปีที่แล้วมันยังไม่ชัดเจนด้วยซ้ำว่า AI จะสามารถเข้าใจคำถามที่หลอกให้คิดว่ามันง่ายแบบนี้ได้ ไม่ต้องพูดถึงการแก้มันเลย โดยเฉพาะ o3 สามารถเห็นว่าคำถามนี้จริงๆ แล้วเกี่ยวกับเส้นโค้ง self-contracted และรู้ว่า SOTA สำหรับคำถามนี้คืออะไร ผมประทับใจมากๆ ในตอนนั้น
แต่แล้วทุกอย่างก็เริ่มซับซ้อน และเมื่อซีรีส์โมเดล GPT-5 มาถึง ผมก็ใช้คำถามนี้เป็นเรื่องเตือนใจ: เมื่อเร็วๆ นี้ถึงเดือนกุมภาพันธ์ปีนี้ ผมยังยกคำถามนี้ในการบรรยายเกี่ยวกับความก้าวหน้าของ LLM ในคณิตศาสตร์ เป็นตัวอย่างของคำถามที่คุณไม่ควรถาม LLM เหตุผลก็คือ GPT-5 หรือแม้แต่ GPT-5.2/5.4 จะพยายามให้คำตอบที่ซับซ้อน แต่มันผิดอยู่ที่ไหนสักแห่งเสมอ และเราจะเสียเวลาตรวจสอบคำตอบเหล่านั้นมากมาย ดังนั้นมันจึงเป็นตัวอย่างที่ดีว่าเพื่อไม่ให้เสียเวลากับ LLM ในคณิตศาสตร์ เราควรรู้ว่าระดับของคำถามที่เหมาะสมที่จะถามคืออะไร
สิ่งนี้เปลี่ยนไปกับ GPT-5.5 และทันใดนั้น หลังจากพูดคุยไปมาจำนวนมากและการตั้งคำถามโดยผู้เชี่ยวชาญ Mark Sellke ก็สามารถค้นพบการสร้างขอบเขตล่าง 2^n ได้อีกครั้ง (ซึ่งผมตะลึงมาก ส่วนหนึ่งเพราะผมลืมไปว่า Tomer และ Fedja รู้อยู่แล้ว 😅) ในทางกลับกัน ไม่มีโชคเลยสำหรับขอบเขตบน
และตอนนี้ GPT-5.6 ก็มาถึง และความก้าวหน้าของ AI ก็ปรากฏให้เห็นเต็มที่:
- GPT-5.6-pro ONE SHOT ขอบเขตล่าง 2^n คุณสามารถดู one-shot ได้ที่นี่ (80 นาทีของการคิด): https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
- GPT-5.6-pro ONE SHOT ขอบเขตบน 4^n และที่จริงมันทำได้เร็วมากใน CoT (Chain of Thought) และเมื่อสิ้นสุดการคิด มันก็สร้างขอบเขตบน 2.31...^n ขึ้นมา ถึงแม้จะยังไม่เท่ากับ 2.29...^n ของ Fedja (และที่จริงกลยุทธ์ 2.31...^n ไม่สามารถปรับปรุงเพิ่มเติมได้หากไม่มีแนวคิดใหม่ๆ -- อันที่จริง Fedja เองก็สังเกตไว้ใน โพสต์ MathOverflow เมื่อปี 2018: "[สำหรับ 2.31..] การโต้แย้งเริ่มยุ่งเหยิงและเห็นได้ชัดว่าวิธีนี้จะไม่นำไปสู่การประมาณค่าที่ดีที่สุด") แต่ก็ยังน่าประทับใจมากและเกินกว่าที่ผมเคยเข้าใจเกี่ยวกับปัญหานี้เมื่อตอนที่ผมทำงานอย่างจริงจังกับมัน คุณสามารถดู one-shot ได้ที่นี่ ใช้เวลา 88 นาทีในการคิด: https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64
3. ความท้าทายสำหรับอนาคต
เรื่องราวนี้ในตอนนี้ยังคงมีมนุษย์เป็นผู้ชนะ 2.29 สำหรับมนุษย์เทียบกับ 2.31 สำหรับเครื่องจักร โดยธรรมชาติแล้ว การคาดเดาคือเส้นโค้ง self-contracted ไม่สามารถยาวเกิน 2^n (ซึ่งจะเป็นคำตอบที่ดีที่สุดเมื่อพิจารณาจากขอบเขตล่าง 2^n) สิ่งนี้ดูยากมากที่จะพิสูจน์และเกินความสามารถของ GPT-5.6 ผมจะสามารถใช้คำถามนี้เพื่อติดตามความก้าวหน้าของ AI ได้นานแค่ไหน? ผมสงสัยว่ามันอาจจะน้อยกว่า 6 เดือนก็ได้...
PS: ผมคัดลอกและวางโพสต์ด้านบนลงใน ChatGPT work และขอให้มันสร้างภาพประกอบสำหรับโพสต์นี้ ชุดภาพที่นี่ได้มาจากการร้องขอครั้งเดียว (one-shot) จากคำขอนั้น
