Sparsity constrained minimax optimization with applications to game theory and machine learning

Klasik oyun teorisi yöntemleri bir oyuncu için çoğunlukla yoğun stratejiler üretmektedir; ancak bu durum, gerçek dünya uygulamalarında pratik olmayabilir. Bu tez, iki oyunculu oyunlarda seyrek stratejileri hesaplamak için minimum-maksimum eniyileme problemine seyreklik kısıtını dahil etmeyi incelemektedir. Teori ve algoritmalar, bu probleme eşdeğer olan sınırı maksimize eden artırma probleminde seyrek sınıflandırıcıların hesaplanmasında da uygulanabilmektedir. Öncelikle, seyrek optimizasyon literatüründeki en iyilik koşulları türevi olmayan fonksiyonlar için genişletildi. Ayrıca, hâlihazırda bulunan bu koşulları kapsayan ve komşu araması yapmayı sağlayan yeni bir koşul geliştirildi. Bu koşulları sağlayan en iyiliğe aday noktaları bulma amacıyla pratik açgözlü algoritmalar geliştirildi. Minimum-maksimum fonksiyonunun özellikleri kullanılarak, seyreklik kısıtlı problem ve seyreklik düzenleyicili problemin bağlantıları oluşturuldu. Literatürdeki seyreklik artırıcı cezalara bir alternatif olarak, birim simpleks üzerinde seyreklik-düzenleyicili eniyileme problemleri için yeni bir içbükey ceza önerildi. Elde edilen problem Dışbükey Farkı (DC) Algoritması'nın hızlandırılmış bir versiyonu ile çözülebilmektedir. Önerilen algoritmalar oyun teorisi için rastgele oluşturulmuş matrisler ve ikili sınıflandırma için gerçek veriler üzerinde deneysel olarak test edildi. Algoritmaların performansı, iyi bilinen düzenleme teknikleri ve problemin MILP formülasyonuyla karşılaştırıldı.