Abstract: We consider a repeatedly played generalized Nash equilibrium game. This induces a multi-agent online learning problem with joint constraints. An important challenge in this setting is that the feasible set for each agent depends on the simultaneous moves of the other agents and, therefore, varies over time. As a consequence, the agents face time-varying constraints, which are not adversarial but rather endogenous to the system. Prior work in this setting focused on convergence to a feasible solution in the limit via integrating the constraints in the objective as a penalty function. However, no existing work can guarantee that the constraints are satisfied for all iterations while simultaneously guaranteeing convergence to a generalized Nash equilibrium. This is a problem of fundamental theoretical interest and practical relevance. In this work, we introduce a new online feasible point method. Under the assumption that limited communication between the agents is allowed, this method guarantees feasibility. We identify the class of benign generalized Nash equilibrium problems for which the convergence of our method to the equilibrium is guaranteed. We set this class of benign generalized Nash equilibrium games in context with existing definitions and illustrate our method with examples.

Abstract: Tracking the solution of time-varying variational inequalities is an important problem with ap- plications in game theory, optimization, and machine learning. Existing work considers time-varying games or time-varying optimization problems. For strongly convex optimization problems or strongly monotone games, these results provide tracking guarantees under the assumption that the variation of the time-varying problem is restrained, that is, problems with a sublinear solution path. In this work, we extend existing results in two ways: In our first result, we provide tracking bounds for (1) variational inequalities with a sublinear solution path but not necessarily monotone functions, and (2) for periodic time-varying variational inequalities that do not necessarily have a sublinear solution path-length. Our second main contribution is an extensive study of the convergence behavior and trajectory of discrete dynamical systems of periodic time-varying VI. We show that these systems can exhibit provably chaotic behavior or can converge to the solution. Finally, we illustrate our theoretical results with experiments.

Abstract: Stochastic and adversarial data are two widely studied settings in online learning. But many optimization tasks are neither i.i.d. nor fully adversarial, which makes it of fundamental interest to get a better theoretical understanding of the world between these extremes. In this work we establish novel regret bounds for online convex optimization in a setting that interpolates between stochastic i.i.d. and fully adversarial losses. By exploiting smoothness of the expected losses, these bounds replace a dependence on the maximum gradient length by the variance of the gradients, which was previously known only for linear losses. In addition, they weaken the i.i.d. assumption by allowing, for example, adversarially poisoned rounds, which were previously considered in the related expert and bandit settings. In the fully i.i.d. case, our regret bounds match the rates one would expect from results in stochastic acceleration, and we also recover the optimal stochastically accelerated rates via online-to-batch conversion. In the fully adversarial case our bounds gracefully deteriorate to match the minimax regret. We further provide lower bounds showing that our regret upper bounds are tight for all intermediate regimes in terms of the stochastic variance and the adversarial variation of the loss gradients.

Abstract:  In the first-order query model for zero-sum K × K matrix games, players observe the expected pay-offs for all their possible actions under the randomized action played by their opponent. This is a classical model, which has received renewed interest after the discovery by Rakhlin and Sridharan that ε-approximate Nash equilibria can be computed efficiently from O( ln K/ε ) instead of O( ln K/ε^2 )  queries. Surprisingly, the optimal number of such queries, as a function of both ε and k, is not known. We make progress on this question on two fronts. First, we fully characterize the query complexity of learning exact equilibria (ε = 0), by showing that they require a number of queries that is linear in K, which means that it is essentially as hard as querying the whole matrix, which can also be done with K queries. Second, for ε > 0, the current query complexity upper bound stands at O(min(ln(K)/ε,K)). We argue that, unfortunately, obtaining matching lower bound is not possible with existing techniques: we prove that no lower bound can be derived by constructing hard matrices whose entries take values in a known countable set, because such matrices can be fully identified by a single query. This rules out, for instance, reducing to a submodular optimization problem over the hypercube by encoding it as a binary matrix. We then introduce a new technique for lower bounds, which allows us to obtain lower bounds of order Ω ̃(log( 1/(Kε) ) for any ε <= 1/(cK^4), where c is a constant independent of K. We further discuss possible future directions to improve on our techniques in order to close the gap with the upper bounds.

Abstract: Algorithm- and data-dependent generalization bounds are required to explain the generalization behavior of modern machine learning algorithms. In this context, there exist information theoretic generalization bounds that involve (various forms of) mutual information, as well as bounds based on hypothesis set stability. We propose a conceptually related, but technically distinct complexity measure to control generalization error, which is the empirical Rademacher complexity of an algorithm- and data-dependent hypothesis class. Combining standard properties of Rademacher complexity with the convenient structure of this class, we are able to (i) obtain novel bounds based on the finite fractal dimension, which (a) extend previous fractal dimension-type bounds from continuous to finite hypothesis classes, and (b) avoid a mutual information term that was required in prior work; (ii) we greatly simplify the proof of a recent dimension-independent generalization bound for stochastic gradient descent; and (iii) we easily recover results for VC classes and compression schemes, similar to approaches based on conditional mutual information.

Abstract: Stochastic and adversarial data are two widely studied settings in online learning. But many optimization tasks are neither i.i.d. nor fully adversarial, which makes it of fundamental interest to get a better theoretical understanding of the world between these extremes. In this work we establish novel regret bounds for online convex optimization in a setting that interpolates between stochastic i.i.d. and fully adversarial losses. By exploiting smoothness of the expected losses, these bounds replace a dependence on the maximum gradient length by the variance of the gradients, which was previously known only for linear losses. In addition, they weaken the i.i.d. assumption by allowing, for example, adversarially poisoned rounds, which were previously considered in the expert and bandit setting. Our results extend this to the online convex optimization framework. In the fully i.i.d. case, our bounds match the rates one would expect from results in stochastic acceleration, and in the fully adversarial case they gracefully deteriorate to match the minimax regret. We further provide lower bounds showing that our regret upper bounds are tight for all intermediate regimes in terms of the stochastic variance and the adversarial variation of the loss gradients.

Abstract: We consider online convex optimization when a number k of data points are outliers that may be corrupted. We model this by introducing the notion of robust regret, which measures the regret only on rounds that are not outliers. The aim for the learner is to achieve small robust regret, without knowing where the outliers are. If the outliers are chosen adversarially, we show that a simple filtering strategy on extreme gradients incurs O(k) additive overhead compared to the usual regret bounds, and that this is unimprovable, which means that k needs to be sublinear in the number of rounds. We further ask which additional assumptions would allow for a linear number of outliers. It turns out that the usual benign cases of independently, identically distributed (i.i.d.) observations or strongly convex losses are not sufficient. However, combining i.i.d. observations with the assumption that outliers are those observations that are in an extreme quantile of the distribution, does lead to sublinear robust regret, even though the expected number of outliers is linear. 

Abstract: This thesis is about various aspects of theoretical machine learning. In particular, about optimization, game theory, and generalization bounds. Therefore, this thesis is structured in three parts: Part I is about optimization in machine learning. More specifically, we show new regret bounds for online convex optimization problems which fall between stochastic and adversarial learning problems. Furthermore, we provide new insights into the behavior of various first-order algorithms on time-varying variational inequalities. These results relate to dynamic regret bounds for strongly convex optimization problems and equilibrium tracking guarantees for time-varying games. Hence, these results are also related to Part III, which is about the game-theoretical aspects of machine learning. In this part, we show the first non-trivial lower bound on the query complexity for the computation of Nash equilibria in zero-sum games. Furthermore, we introduce an online feasible point method for generalized Nash-equilibrium problems. For a subclass of generalized games, we show that the convergence to the generalized Nash equilibrium is guaranteed while preserving feasibility for all iterates. In Part II we show algorithm and data-dependent generalization guarantees. This is done via a new definition of an algorithm-dependent Rademacher complexity. Furthermore, we derive geometrically interpretable bounds in terms of the fractal dimension of the output set of an algorithm.