ในบันทึกนี้ ฉันจะแบ่งปันความเข้าใจ/คำอธิบายของบทความเรื่อง "Tight Bounds for Approximate Carathéodory and Beyond" [1] เขียนโดย Mirrokni และคณะ

หมายเหตุนี้ส่วนใหญ่ประกอบด้วย 2 ส่วน: ในครึ่งแรก เราใช้ปัญหาจูงใจง่ายๆ เพื่อแสดงอัลกอริทึมที่เสนอโดย Mirrokni และคณะ ในช่วงครึ่งหลัง เราจะศึกษาขั้นตอนสำคัญของการพิสูจน์ขอบเขตของอัลกอริทึมที่เสนอ ในตอนท้ายมีความคิดเห็นสั้นๆ เกี่ยวกับแนวคิดที่น่าสนใจในบทความนี้

ข้อจำกัดความรับผิดชอบ: หมายเหตุนี้ไม่ได้รับการพิจารณาอย่างละเอียดตามปกติซึ่งสงวนไว้สำหรับการเผยแพร่อย่างเป็นทางการ

บทความนี้มี การสนับสนุนหลัก 3 ประการ:

1) ให้อัลกอริธึมที่กำหนดเวลาเกือบเชิงเส้นเป็นครั้งแรกสำหรับปัญหาการาเธโอโดรีโดยประมาณ ซึ่งเมื่อเปรียบเทียบกับอัลกอริธึมการสุ่มตัวอย่างก่อนหน้านี้ จะบันทึกการคำนวณล่วงหน้าของวิธีแก้ปัญหาที่แน่นอนสำหรับปัญหาการาเธโอกลิ่น

2) การใช้อัลกอริธึมที่เสนอเป็นการพิสูจน์เชิงสร้างสรรค์ จะให้ขอบเขตล่างที่แคบสำหรับปัญหาการาเธโอโดรี ซึ่งแสดงให้เห็นว่าจุดใดๆ ภายในโพลีโทปที่มีอยู่ในลูกบอล lp ของ รัศมี D สามารถประมาณได้ภายใน ϵ ใน lp บรรทัดฐานโดยการรวมกันนูนเพียง O(D² p/ϵ²) จุดยอดของโพลีโทปสำหรับ p ≥ 2

3) แสดงส่วนขยายอย่างง่ายของอัลกอริทึมที่นำเสนอที่สามารถนำไปใช้กับแอปพลิเคชันอื่นๆ เช่น ฟังก์ชัน submodular และการฝึกอบรม SVM

คำถามสร้างแรงบันดาลใจ

ทฤษฎีบทการาเทโอโดรีระบุว่าจุดใดๆ u ในโพลีโทป P ⊆ R^n สามารถแสดงเป็นผลรวมนูนของจุดยอด n+1 ของ P. ตัวอย่างเช่น ในรูปด้านบน โพลีโทป P มีจุดยอด 6 v1, v2, v3, v4, v5, v6 และ P ⊆ R² เลือกจุด u โดยพลการ มันสามารถแสดงเป็นผลรวมนูนของจุดยอด 2+1 (เช่น u = 0.25 ⋅ v1 + 0.5 ⋅ v2 + 0 ⋅ v3 + 0 ⋅ v4 + 0 ⋅ v5 + 0.25 ⋅ v6)

อย่างไรก็ตาม การคำนวณเพื่อแก้ไขปัญหา Carathéodory ที่แน่นอนอาจมีค่าใช้จ่ายสูง ความซับซ้อนจะยิ่งสูงขึ้นไปอีกเมื่อโพลีโทปมีจุดยอดหลายจุดแบบทวีคูณ (เช่น โพลีโทปที่ตรงกันหรือโพลีโทปฐานเมทริกซ์) ทีนี้ ถ้าเรายินดีที่จะยอมรับข้อผิดพลาดของ ϵ ใน lp norm; กล่าวคือ เรายอมรับวิธีแก้ปัญหาแบบรวมนูนถ้า

ถ้าอย่างนั้น เราสามารถใช้จุดยอดน้อยลง (การรวมแบบกระจายที่นูนขึ้น) เพื่อประมาณ u ได้หรือไม่ เราจะได้ชุดค่าผสมนูนเบาบางเช่นนี้ได้อย่างไร?

อัลกอริทึมการประมาณของ Mirrokni และคณะ

เนื้อหาที่จะเพิ่ม...

มุ่งสู่ Mirror Descent Iteration และการกระจายตัวของโซลูชัน

เนื้อหาที่จะเพิ่ม...

ความคิดเห็น

มีแนวคิดที่สร้างแรงบันดาลใจและน่าสังเกต 2 แนวคิดในบทความนี้ Tight Bounds for Approximate Carathéodory and Beyond [1] เขียนโดย Mirrokni และคณะ

ประการแรกคือการกำหนดปัญหาให้เป็นปัญหาจุดอานและการใช้กระจกเงาซึ่งส่งผลให้เกิดฟังก์ชันคู่ที่สวยงามและรับประกันคุณสมบัติความกระจัดกระจายที่ต้องการสำหรับการแก้ปัญหา ผู้เขียนกล่าวว่าแนวคิดนี้ได้รับแรงบันดาลใจจากตัวแก้ปัญหาการเขียนโปรแกรมเชิงเส้นเชิงบวกที่มีอยู่ เช่น งานของ Serge และคณะ [2] และผลงานของหนุ่ม [3]

แนวคิดที่น่าสนใจประการที่สองคือกลยุทธ์ความน่าจะเป็นในการพิสูจน์ขอบเขตที่แน่นหนา ซึ่งทำให้หลีกเลี่ยงอุปสรรคในการสร้างตัวอย่างที่มั่นคงของสถานการณ์ที่ต้องการ แต่บทความนี้พิสูจน์ให้เห็นถึงความน่าจะเป็นไปได้ว่ามีตัวอย่างปัญหาที่ต้องการอยู่ เพื่อให้ได้แนวคิดนี้ ผู้เขียนได้รับแรงบันดาลใจจากผลงานของ Klein and Young [4]

แม้ว่าหมายเหตุนี้จะไม่ครอบคลุมแนวคิดที่สอง แต่เราแนะนำให้ผู้อ่านอ่านส่วนที่ 4.2 ของ "เอกสารต้นฉบับ (เวอร์ชัน arxiv)" เพื่ออ่านเพิ่มเติม

ข้อมูลอ้างอิง

[1] มีโรคนี, วาฮับ, และคณะ “ขอบเขตที่จำกัดสำหรับ Carathéodory โดยประมาณและอื่นๆ” การประชุมนานาชาติเรื่องการเรียนรู้ของเครื่อง PMLR, 2017.

(2) Plotkin, Serge A., David B. Shmoys และ Éva Tardos “อัลกอริธึมการประมาณที่รวดเร็วสำหรับการบรรจุแบบเศษส่วนและการครอบคลุมปัญหา” คณิตศาสตร์ของการวิจัยปฏิบัติการ 20.2 (1995): 257–301

[3] หนุ่ม นีล อี. “อัลกอริธึมแบบลำดับและแบบขนานสำหรับการบรรจุและการหุ้มแบบผสม” การประชุมสัมมนา IEEE ครั้งที่ 42 เกี่ยวกับรากฐานของวิทยาการคอมพิวเตอร์ อีอีอี, 2001.

[4] ไคลน์, ฟิลิป และนีล อี. ยัง “เกี่ยวกับจำนวนวนซ้ำสำหรับ Dantzig — อัลกอริทึมการเพิ่มประสิทธิภาพของ Wolfe และอัลกอริทึมการประมาณการครอบคลุมการบรรจุ” วารสารสยามคอมพิวเตอร์ 44.4 (2015): 1154–1172.