Dalam catatan ini, saya akan berbagi pemahaman/eksposisi saya terhadap makalah Tight Bounds for Approximate Carathéodory and Beyond [1] yang ditulis oleh Mirrokni et al.
Catatan ini terutama berisi 2 bagian: di babak pertama, kami menggunakan masalah motivasi sederhana untuk mengilustrasikan algoritma yang diusulkan oleh Mirrokni dkk. Di babak kedua, kita mempelajari langkah-langkah kunci pembuktian batasan algoritma yang diusulkan. Di bagian akhir terdapat komentar singkat mengenai ide-ide menarik dalam tulisan ini.
Penafian: Catatan ini belum menjalani pemeriksaan yang biasa dilakukan untuk publikasi formal.
Makalah ini memiliki 3 kontribusi utama:
1) Mereka memberikan algoritme deterministik waktu hampir linier pertama untuk perkiraan masalah Carathéodory, yang, dibandingkan dengan algoritme pengambilan sampel sebelumnya, menghemat pra-perhitungan solusi eksak untuk masalah Carathéodory.
2) Dengan menggunakan algoritma yang diusulkan sebagai bukti konstruktif, mereka memberikan batas bawah yang ketat untuk masalah Carathéodory, yang menunjukkan bahwa setiap titik di dalam polytope yang terdapat dalam bola lp radius D dapat diperkirakan dalam ϵ dalam normalp dengan kombinasi cembung hanya O(D² p/ϵ²) simpul polytope untuk p ≥ 2.
3) Mereka menunjukkan perluasan sederhana dari algoritma yang diusulkan dapat diterapkan pada aplikasi lain seperti fungsi submodular dan pelatihan SVM.
Pertanyaan yang Memotivasi
Teorema Carathéodory menyatakan bahwa setiap titik u dalam politope P ⊆ R^n dapat dinyatakan sebagai kombinasi cembung dari n+1 simpul dari P. Misalnya, pada gambar di atas, polytope P mempunyai 6 simpul v1, v2, v3, v4, v5, v6, dan P ⊆ R². Ambil titik u secara sembarangan, dapat dinyatakan sebagai kombinasi cembung dari simpul 2+1 (misalnya u = 0.25 ⋅ v1 + 0,5 ⋅ v2 + 0 ⋅ v3 + 0 ⋅ v4 + 0 ⋅ v5 + 0,25 ⋅ v6).
Namun, menghitung solusi yang tepat untuk masalah Carathéodory bisa memakan biaya yang besar. Kompleksitasnya menjadi lebih tinggi ketika politop memiliki banyak simpul secara eksponensial (misalnya politop yang cocok atau politop dasar matroid). Sekarang, jika kita bersedia menoleransi kesalahan ϵ dalam norma lp; artinya, kita menerima solusi kombinasi cembung jika
Lalu bisakah kita menggunakan lebih sedikit simpul (kombinasi cembung yang lebih jarang) untuk memperkirakan u? Bagaimana kita dapat memperoleh kombinasi cembung yang jarang?
Algoritma Pendekatan Mirrokni et al.
Konten yang akan ditambahkan…
Terikat untuk Iterasi Mirror Descent dan Ketersebaran Solusi
Konten yang akan ditambahkan…
Komentar
Ada 2 ide inspiratif dan patut dicatat dalam makalah ini Batasan Ketat untuk Perkiraan Carathéodory and Beyond [1] yang ditulis oleh Mirrokni et al.
Pertama adalah perumusan masalah sebagai masalah titik pelana dan penggunaan mirror descending yang menghasilkan fungsi ganda yang indah dan menjamin sifat ketersebaran yang diinginkan untuk solusi. Penulis menyebutkan bahwa ide ini terinspirasi oleh pemecah pemrograman linier positif yang ada seperti karya Serge et al. [2] dan karya Young [3].
Ide menarik kedua adalah strategi probabilistik untuk membuktikan bahwa ikatan tersebut ketat, yang membuat jalan memutar dari hambatan dalam membangun contoh solid dari situasi yang diinginkan. Sebaliknya, makalah ini membuktikan probabilitas bahwa contoh masalah yang diinginkan ada. Untuk mendapatkan ide ini, penulis terinspirasi oleh karya Klein dan Young [4].
Meskipun catatan ini tidak mencakup gagasan kedua, kami merujuk pembaca ke bagian 4.2 dari makalah asli (versi arxiv) untuk bacaan lebih lanjut.
Referensi
[1] Mirrokni, Vahab, dkk. “Batas ketat untuk perkiraan Carathéodory dan seterusnya.” Konferensi Internasional tentang Pembelajaran Mesin. PMLR, 2017.
[2] Plotkin, Serge A., David B. Shmoys, dan Éva Tardos. “Algoritma perkiraan cepat untuk pengepakan pecahan dan masalah penutup.” Matematika Riset Operasi 20.2 (1995): 257–301.
[3] Young, Neal E. “Algoritme berurutan dan paralel untuk pengemasan dan penutup campuran.” Prosiding simposium IEEE ke-42 tentang dasar-dasar ilmu komputer. IEEE, 2001.
[4] Klein, Philip, dan Neal E. Young. “Tentang Jumlah Iterasi untuk Dantzig - Optimasi Wolfe dan Algoritma Pendekatan Penutupan Pengepakan.” Jurnal SIAM tentang Komputasi 44.4 (2015): 1154–1172.
