Adaptive sequential optimization with applications to machine learning

Wilson, Craig A

Permalink

https://hdl.handle.net/2142/90876 Copy

Description

Title

Adaptive sequential optimization with applications to machine learning

Author(s)

Wilson, Craig A

Issue Date

2016-04-01

Director of Research (if dissertation) or Advisor (if thesis)

Veeravalli, Venugopal V.

Doctoral Committee Chair(s)

Veeravalli, Venugopal V.

Committee Member(s)

• Nedic, Angelia
• Srikant, Rayadurgam
• Başar, Tamer

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• convex optimization
• adaptive algorithms sequential machine learning
• machine learning

Abstract

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.

Graduation Semester

2016-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/90876

Copyright and License Information

Copyright 2016 Craig Wilson

Owning Collections