Introduction
Stochastic convex optimization (SCO) is a cornerstone of modern machine learning. Standard algorithms, such as Stochastic Gradient Descent (SGD), typically require precise knowledge of problem parameters—specifically the Lipschitz constant ($L$) and the distance to the optimum ($R^*$)—to achieve optimal performance. In many practical scenarios, these parameters are unknown, leading to the study of "parameter-free" optimization. While the computational complexity of these methods is well-documented, their sample complexity—the amount of data required to reach a target error—has remained less clear.
A common heuristic to handle unknown parameters is hyperparameter tuning via a validation set. However, this approach is prone to "catastrophic overfitting," particularly when the validation set is small and the objective function lacks strong convexity. This paper addresses this gap by introducing a robust framework for model selection.
Reliable Model Selection (RMS)
The authors propose Reliable Model Selection (RMS) to mitigate the risks of standard model selection. Instead of naively selecting the model with the lowest validation error, which may be a statistical outlier, RMS identifies a "safe set" of candidate models ($\mathcal{F}$).
As illustrated in the algorithm above, RMS utilizes statistical confidence intervals ($\tau_k$) to ensure that every model in $\mathcal{F}$ has a population risk likely close to a designated "reference model" ($x_0$). By selecting the minimum validation error within this restricted set, the method avoids picking "lucky" models that perform well on validation data but poorly on the true population.
Theoretical Contributions and Methods
Beyond RMS, the paper introduces Regularization-based Localization for settings where only the distance to the optimum ($R^*$) is unknown. This two-stage approach first estimates a radius $R$ containing the optimum using non-squared norm regularization, then performs constrained optimization within that radius.
To support these methods, the authors derive new concentration inequalities for sums of i.i.d. vectors and dependent random variables. These theoretical tools allow them to prove that RMS matches the optimal known-parameter sample complexity up to negligible $\log \log$ factors, effectively bridging the gap between parameter-aware and parameter-free SCO.
Experimental Evaluation
The effectiveness of RMS was validated across two distinct domains:
- Few-Shot CLIP Fine-tuning: On CIFAR-10, RMS was used to tune learning rates for fine-tuning the last layer of a CLIP (ViT-L/14) model. In low-data regimes (32 shots or fewer), RMS consistently outperformed standard model selection. As the number of samples increased (64+ shots), RMS performance converged with standard methods, demonstrating its safety across data scales.
- Prompt Engineering for Vision-Language Models: Using Gemini-1.5-flash-002, the authors tested prompt selection for a complex shape-counting task. RMS successfully identified robust prompts, whereas standard selection often chose prompts that overfit to the small validation set but failed on a larger 5,000-image test set.
Key Insights
- Overfitting Fragility: Without strong convexity, tuning hyperparameters on small validation sets can lead to significant performance degradation on the population.
- Complexity Separation: The research highlights a theoretical separation: optimal sample complexity can be achieved without knowing $R^*$, though it may necessitate higher gradient oracle complexity.
- The Power of a Baseline: The success of RMS hinges on the "Power of a Baseline." By remaining skeptical of models that drastically outperform a reliable reference on minimal data, the algorithm ensures stability.
Conclusion and Limitations
While RMS provides a robust path for parameter-free optimization, it does have dependencies. Its performance is tied to the quality of the reference model; an extremely poor baseline may lead to overly conservative selections. Additionally, the method requires some structural knowledge to bound differences between models. Future work may focus on relaxing these requirements and exploring RMS in even larger-scale deep learning regimes where validation sets are traditionally considered "sufficiently large."
Summary updated