InfoResearchPeer-reviewed
The Sample Complexity of Parameter-Free Stochastic Convex Optimization
- Published
- Record updated
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.