TITLE: Sparsity Constrained Minimax Optimization with Applications to Game Theory and Machine Learning
Speaker: Bora Çetin
Advisor: Prof. Mustafa Çelebi Pınar
Date & Time: July 7, 2025, Monday at 10:00
Place: EA409
ABSTRACT:
Classical game-theoretic methods often yield dense strategies for a player, which might not be practical in real-world implementations. This thesis studies incorporating the sparsity constraint to the minimax optimization problem to compute sparse strategies in bimatrix games. The theory and algorithms also apply to the equivalent problem of computing sparse classifiers in the margin maximizing boosting problem. Optimality conditions in the sparse optimization literature are extended to nonsmooth functions. A new optimality condition for neighborhood search that covers the existing conditions is proposed. Practical greedy algorithms are developed to find candidate points satisfying optimality conditions. Based on the properties of the Minimax function, connections between the cardinality-constrained problem and the cardinality-regularized problem are established. A new concave penalty for cardinality-regularized optimization problems over the unit simplex is proposed, which offers an alternative to the sparsity-promoting penalties in the literature. The resulting problem is solved efficiently using a faster version of the Difference of Convex (DC) algorithm. The proposed algorithms are tested empirically on random game matrices and real data for binary classification. The performance is compared to well-known regularization techniques and the MILP formulation of the problem.
BIO:
Bora Çetin received his B.S and graduated from the Department of Industrial Engineering at Bilkent University in June 2023. He is currently pursuing an M.S. degree in the Department of Industrial Engineering under the supervision of Prof. Mustafa Çelebi Pınar. His main research interest is sparse optimization, with particular focus on game theory and machine learning applications.