NSF-BSF: AF: Small: Parameter-Free Stochastic Optimization via Trajectory Cues

Machine learning has been extremely successful at enabling computers to learn from data to perform image annotation, speech recognition, and language translation. Despite this success, many potential applications remain untapped. One major barrier to more widespread adoption of machine learning is that machine learning methods must be manually tuned to each new learning task. This tuning requires high levels of both computational resources and user skill, which excludes many potential machine learning users. Furthermore, even leading machine learning practitioners make costly tuning mistakes. This project aims to make the tuning process simpler and more computationally efficient. This project focuses on eliminating parameter tuning from the stochastic optimization algorithms that power machine learning. Toward this goal, two novel strategies will be employed. First, instead of using online-to-batch conversion, a standard technique in stochastic optimization, this project will develop algorithms for noiseless optimization and then lift them to the stochastic setting via powerful time-uniform concentration of measure results. Second, the project will develop algorithms based on trajectory cues: quantities directly observable from the optimization trajectory (such as the distance between iterates and the initial point) that serve as stand-ins for unknown problem parameters. These two new strategies will enable this project to tackle outstanding theoretical problems in parameter-free optimization and design practical algorithms that reduce the burden of parameter tuning. The project will also examine parameter-free methods for particular problem classes such as deep learning. All software resulting from this research will be open source. Algorithms from this project will be integrated into optimization and machine learning curricula at both the undergraduate and graduate level. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.