We study the sample complexity of stochastic convex optimization when problem parameters, e.g., the distance to optimality, are unknown. We pursue two strategies. First, we develop a reliable model selection method that avoids overfitting the validation set. This method allows us to generically tune the learning rate of stochastic optimization methods to match the optimal known-parameter sample complexity up to $\log\log$ factors. Second, we develop a regularization-based method that is specialized to the case that only the distance to optimality is unknown. This method provides perfect adaptability to unknown distance to optimality, demonstrating a separation between the sample and computational complexity of parameter-free stochastic convex optimization. Combining these two methods allows us to simultaneously adapt to multiple problem structures.

Experiments performing few-shot learning on CIFAR-10 by fine-tuning CLIP models and prompt engineering Gemini to count shapes indicate that our reliable model selection method can help mitigate overfitting to small validation sets.

Bio: Oliver is an Assistant Professor in the Industrial Engineering Department at the University of Pittsburgh. Before joining the University of Pittsburgh he was a visiting postdoctoral scholar at Google Research. He earned his PhD in 2019 under the supervision of Yinyu Ye. His research develops optimization algorithms for solving large-scale machine learning and operations research problems.

Oliver's work has led to important advances in optimization theory. For instance, his work with Yair Carmon establishing lower bounds on the cost of uncertainty in problem parameters in machine learning received the 2024 Best Paper Award at the Conference on Learning Theory.

Oliver's innovations have also driven real-world impact. At Google, he developed the PDLP solver, a cutting-edge first-order method for solving large-scale linear programs. This work earned him and his collaborators the 2024 Beale-Orchard-Hays Prize for computational excellence. PDLP has been widely adopted in industry including at NVIDIA, COPT, and Gurobi.