On Online Nonconvex Nonstationary Optimization And Game Theory

On Online Nonconvex Nonstationary Optimization and Game Theory

Sequential decision making in a nonstationary environment has always been an important research area in various fields. The landscapes of optimization and game theory are replete with problems based on Sequential Decision Making. On the other hand, in modern day machine learning non-convex optimization is becoming increasingly common. The most popular examples include matrix completion, phase retrieval,and the last but not the least, deep learning. Complexity in non-convex optimization arises from the fact that finding global minima even for simple non-convex functions are NP-hard. So efficient algorithms designed for convex optimization either fails or are inefficient for non-convex optimization. The literature is even more inadequate for non-convex optimization under online learning paradigm. Online learning is sequential decision making setting where a decision maker observes the outcome only after taking the decision. Most prominent examples of online learning are recommendation system, online portfolio selection, and online convex optimization with knapsack. In this the second chapter we design and analyze algorithms for online nonstationary nonconvex optimization. Here nonstationarity implies that we measure the optimality of the solution with respect to a dynamic oracle which is provably more difficult than the static setting. In traditional nonconvex optimization, one tries to converge to a local minima avoiding the saddle point. But in many applications, saddle points are the points of interest, e.g., in zero-sum game Nash equilibrium turns out to be the saddle point of a strongly-convex strongly-concave function. In the third chapter, we study and analyze algorithms on how to perform saddle-point optimization in an online nonstationary environment. This problem setup can be used to compute the Nash equilibrium in various repeated/sequential games. Furthermore, game theory is itself a powerful tool to study different strategic problems. On that note, in the last chapter, we study the group dynamics among attackers in the context of cybersecurity through a coalition-formation game.

Index to IEEE Publications

Issues for 1973- cover the entire IEEE technical literature.

Mathematical Reviews