Adaptive sequential optimization with applications to machine learning

The focus of this thesis is on solving a sequence of optimization problems that change over time in a structured manner. This type of problem naturally arises in contexts as diverse as channel estimation, target tracking, sequential machine learning, and repeated games. Due to the time-varying nature of these problems, it is necessary to determine new solutions as the problems change in order to ensure good solution quality. However, since the problems change over time in a structured manner, it is beneficial to exploit solutions to the previous optimization problems in order to efficiently solve the current optimization problem. The first problem considered is sequentially solving minimization problems that change slowly, in the sense that the gap between successive minimizers is bounded in norm. The minimization problems are solved by sequentially applying a selected optimization algorithm, such as stochastic gradient descent (SGD), based on drawing a number of samples in order to carry out a desired number of iterations. Two tracking criteria are introduced to evaluate approximate minimizer quality: one based on being accurate with respect to the mean trajectory, and the other based on being accurate in high probability (IHP). Knowledge of the bound on how the minimizers change, combined with properties of the chosen optimization algorithm, is used to select the number of samples needed to meet the desired tracking criterion. Next, it is not assumed that the bound on how the minimizers change is known. A technique to estimate the change in minimizers is provided along with analysis to show that eventually the estimate upper bounds the change in minimizers. This estimate of the change in minimizers is combined with the previous analysis to provide sample size selection rules to ensure that the mean or IHP tracking criterion is met. Simulations are used to confirm that the estimation approach provides the desired tracking accuracy in practice. An application of this framework to machine learning problems is considered next. A cost-based approach is introduced to select the number of samples with a cost function for taking a number of samples and a cost budget over a fixed horizon. An extension of this framework is developed to apply cross validation for model selection. Finally, experiments with synthetic and real data are used to confirm that this approach performs well for machine learning problems. The next model considered is solving a sequence of minimization problems with the possibility that there can be abrupt jumps in the minimizers mixed in with the normal slow changes. Alternative approaches are introduced to estimate the changes in the minimizers and select the number of samples. A simulation experiment demonstrates the effectiveness of this approach. Finally, a variant of this framework is applied to learning in games. A sequence of repeated games is considered in which the underlying stage games themselves vary slowly over time in the sense that the pure strategy Nash equilibria change slowly. Approximate pure-strategy Nash equilibria are learned for this sequence of zero sum games. A technique is introduced to estimate the change in the Nash equilibiria as for the sequence of minimization problems. Applications to a synthetic game and a game based on a surveillance network problem are introduced to demonstrate the game framework