Towards Fully Parameter-Free Stochastic Optimization: Grid Search with Self-Bounding Analysis

Parameter-free stochastic optimization aims to design algorithms that are agnostic to the underlying problem parameters while still achieving convergence rates competitive with optimally tuned methods. While some parameter-free methods do not require the specific values of the problem parameters, they still rely on prior knowledge, such as the lower or upper bounds of them. We refer to such methods as "partially parameter-free". In this work, we target achieving "fully parameter-free" methods, i.e., the algorithmic inputs do not need to satisfy any unverifiable condition related to the true problem parameters. We propose a powerful and general grid search framework, named GRASP, with a novel self-bounding analysis technique that effectively determines the search ranges of parameters, in contrast to previous work. Our method demonstrates generality in: (i) the non-convex case, where we propose a fully parameter-free method that achieves near-optimal convergence rate, up to logarithmic factors; (ii) the convex case, where our parameter-free methods are competitive with strong performance in terms of acceleration and universality. Finally, we contribute a sharper guarantee for the model ensemble, a final step of the grid search framework, under interpolated variance characterization.

Training machine learning models on very large datasets is a common challenge. Many training methods require setting one or more tuning parameters (often called hyperparameters), and both theory and practice show that these choices can strongly affect performance. In principle, optimal hyperparameters depend on data statistics, but for large real-world datasets those properties are usually unknown. A common practical strategy is to choose a candidate range, evaluate several values, and pick the best -- known as "grid search". When the range is chosen by experience, it may miss values that are theoretically optimal and thus lack rigorous assurance. We introduce "self-bounding", a method that derives a principled hyperparameter range from the algorithm's own theoretical guarantees. Rather than assuming knowledge of the data, the method analyzes when the theory would fail and uses that to infer a safe search range. Running grid search inside this self-bounded range yields training results that retain theoretical guarantees without detailed dataset knowledge. The approach is general and extendable; we demonstrate it in two common training settings. We expect self-bounding to narrow the gap between theory and practice for grid search and to provide more reliable, theory-grounded guidance for hyperparameter selection.