The Sample Complexity of Parameter-Free Stochastic Convex Optimization

Jared Lawrence, Ari Kalinsky, Hannah Bradfield, Yair Carmon, Oliver HinderarXiv 2025 · DOI · arXiv

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}$).

The Reliable Model Selection (RMS) algorithm and visual intuition. RMS uses confidence intervals to define a safe set $\mathcal{F}$ relative to a reference model $x_0$, selecting the best performer within that set ($k_{rely}$) rather than the global validation minimum ($k_{std}$).

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:

  1. 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.
  2. 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

Abstract

We study the sample complexity of stochastic convex optimization when problem parameters such as the distance to optimality and the Lipschitz constant are unknown. We pursue two strategies. First, we develop a reliable model selection method that avoids overfitting to 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. More specifically, it uses norm-regularized empirical risk minimization to estimate the distance to optimality to within a constant factor, allowing known-parameter stochastic optimization methods to achieve optimal sample complexity. 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.
BibTeX
@misc{lawrence2025sample,
  author = {Jared Lawrence and Ari Kalinsky and Hannah Bradfield and Yair Carmon and Oliver Hinder},
  title = {{The Sample Complexity of Parameter-Free Stochastic Convex Optimization}},
  year = {2025},
  eprint = {2506.11336},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.11336},
}
Figure