Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function

Data-driven algorithm design automates hyperparameter tuning, but its statistical foundations remain limited because model performance can depend on hyperparameters in implicit and highly non-smooth ways. Existing guarantees focus on the simple case of a one-dimensional (scalar) hyperparameter. This leaves the practically important, multi-dimensional hyperparameter tuning setting unresolved. We address this open question by establishing the first general framework for establishing generalization guarantees for tuning multi-dimensional hyperparameters in data-driven settings. Our approach strengthens the generalization guarantee framework for semi-algebraic function classes by exploiting tools from real algebraic geometry, yielding sharper, more broadly applicable guarantees. We then extend the analysis to hyperparameter tuning using the validation loss under minimal assumptions, and derive improved bounds when additional structure is available. Finally, we demonstrate the scope of the framework with new learnability results, including data-driven weighted group lasso and weighted fused lasso.

Machine learning models often depend strongly on hyperparameters. For example, user-chosen settings such as regularization weights that control how a model is trained. In practice, these settings are usually selected by trial and error, grid search, or other heuristic procedures. Although these methods can work well empirically, it is often unclear how much data is needed to choose hyperparameters that will also perform well on future, unseen problems. This paper develops a theoretical framework for understanding when data-driven hyperparameter tuning can be trusted. Unlike prior guarantees, which mainly applied to a single hyperparameter or to simplified training objectives, our results cover multiple interacting hyperparameters and the common practice of tuning them using a separate validation objective. The key idea is to use the algebraic structure present in many machine learning objectives to bound the complexity of the tuning problem. These bounds imply sample-complexity guarantees: how many problem instances are sufficient to learn good hyperparameters. We also prove lower bounds and show applications to sparse learning methods such as weighted group lasso and weighted fused lasso.