Skip to content
InfoResearchPeer-reviewed

The Sample Complexity of Parameter-Free Stochastic Convex Optimization

Published
Record updated
View JSON

Summary

The authors study the sample complexity of stochastic convex optimization when parameters such as the distance to optimality and the Lipschitz constant are unknown. They propose a reliable model selection method that tunes learning rates to match known-parameter sample complexity up to $\log\log$ factors, and a regularization-based method using norm-regularized empirical risk minimization that estimates the distance to optimality within a constant factor. Few-shot experiments on CIFAR-10 with fine-tuned CLIP models and prompt-engineered Gemini shape counting indicate the model selection method can help mitigate overfitting to small validation sets.