This decommissioned ERA site remains active temporarily to support our final migration steps to https://ualberta.scholaris.ca, ERA's new home. All new collections and items, including Spring 2025 theses, are at that site. For assistance, please contact erahelp@ualberta.ca.
- 85 views
- 83 downloads
Adapting to Non-stationarity in Online Learning
-
- Author / Creator
- Jacobsen, Andrew
-
Over the last decade, machine learning (ML) has lead to advances in many fields, such as computer vision, online decision-making, robotics, natural language processing, and many others. The algorithms driving these successes typically have one or more user-specified free variables called hyperparameters, or simply parameters, which must be set prior to running the algorithm. These parameters can have a significant effect on an algorithm's performance in practice, and setting them optimally requires problem-dependent knowledge that the practitioner does not typically have access to, such as statistics of the underlying data-generating process. Common practice is to empirically "tune" the hyperparameters for a specific problem setting by repeatedly guessing values, observing the resulting performance, and adjusting the hyperparameter values accordingly. However, this practice is ultimately heuristic in nature and generally fails to provide meaningful performance guarantees, especially if the problem may change or drift over time.
The aim of this thesis is to develop learning algorithms which make meaningful performance guarantees in the absence prior knowledge, obviating the need to tune hyperparameters entirely. We focus in particular on developing algorithms which are suitable for non-stationary problem settings, in which the unknown problem solution may change arbitrarily over time. We study this problem through the lens of online learning, a framework used to model learning from a stream of data. We present the first online learning algorithms that achieve optimal performance guarantees in the complete absence of prior knowledge about the problem solution, even if it changes over time. We achieve this feat in the standard setting of Lipschitz losses, as well as under a relaxation of the Lipschitz condition which allows for unbounded losses, leading to novel results for stationary problem settings and saddle-point optimization as well. Our efforts culminate in a universal algorithm for online linear regression, which requires no prior knowledge of any kind to make optimal performance guarantees, even in the face of non-stationary data.
-
- Graduation date
- Fall 2024
-
- Type of Item
- Thesis
-
- Degree
- Doctor of Philosophy
-
- License
- This thesis is made available by the University of Alberta Library with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.