Model Selection, Tuning, and Generalization Questions

Direct answer
Instead of treating the objective (validation loss) as an opaque black box, hypergradient methods differentiate THROUGH the training process itself to get a gradient of validation loss with respect to hyperparameters directly, either by implicit differentiation at a converged solution or by unrolling a finite number of training steps and back-propagating through them; this is feasible mainly for continuous hyperparameters with a differentiable relationship to the training update, and its main cost is memory (for unrolling) or the need to solve an implicit system (for the implicit approach), with truncation being the standard way to make either tractable.

Structured elaboration
Implicit differentiation treats the model's trained parameters as an implicit function of the hyperparameters (defined by the training optimum satisfying a stationarity condition), and uses the implicit function theorem to compute how the validation loss changes as hyperparameters change, without literally re-running training from scratch for each perturbation. This requires solving a linear system involving the Hessian of the training loss (or an approximation to it), which is itself expensive for large models, requiring Hessian-vector-product tricks or approximations rather than forming the full Hessian.
Unrolling instead treats a FIXED, finite number of training steps (say, the last 5 or 10 SGD updates) as a differentiable computation graph, and back-propagates the validation loss's gradient through those unrolled update steps all the way back to the hyperparameters that influenced them (e.g. the learning rate used at each step). This is conceptually simpler than implicit differentiation but its memory cost grows with the number of unrolled steps, since you need to keep the whole unrolled computation graph in memory for the backward pass, exactly the same memory-cost pattern as backpropagation through time in a recurrent network.
Feasibility and truncation: full unrolling through an entire training run (potentially thousands of steps) is generally infeasible memory-wise; truncated unrolling (differentiating through only the LAST K steps, treating earlier steps as fixed) trades exactness for tractability, at the cost of only capturing how the hyperparameter affects the LATE part of training, missing any effect it had on earlier dynamics. This is the same truncation trade-off as truncated backpropagation through time.

Worked example
Tuning a learning-rate SCHEDULE (rather than a single fixed learning rate) via hypergradients: unroll the last 20 training steps as a differentiable graph, compute the gradient of final validation loss with respect to each of those 20 steps' learning rate, and use that gradient to directly update the schedule, rather than treating the whole schedule as a black-box hyperparameter to search over via grid/random/Bayesian methods.

Trade-offs & pitfalls
Hypergradient methods are a genuinely distinct 4th paradigm alongside grid/random/Bayesian/multi-fidelity search (gradient-based rather than derivative-free), but they're considerably more implementation-heavy and less broadly applicable (they need a differentiable relationship between hyperparameter and training update, which rules out purely discrete/categorical or architectural hyperparameters); for most practical tuning problems, they remain a research-adjacent technique rather than a standard default tool.

Direct answer
Sample complexity is driven mainly by the model family's effective capacity relative to the true signal's complexity: linear models need relatively few examples (roughly proportional to the number of features) if the true relationship is close to linear, while flexible non-parametric families (deep trees, large neural networks) need substantially more, since they have to statistically pin down a much richer function; you estimate the practical number empirically via a learning curve and extrapolation rather than relying on a closed-form theoretical answer for most real, non-linear model families.

Structured elaboration
Linear models: sample complexity scales roughly with the number of features (dimensionality), classical statistical theory gives fairly precise guidance here (roughly on the order of a small constant times the number of parameters, for well-behaved data). Decision trees and random forests: need enough examples per region of the input space that gets split off by the tree; a deeper tree implicitly carves the space into many small regions, each needing enough data to estimate reliably, so sample needs grow with tree complexity, though ensembling (random forests) partially mitigates this by averaging over many trees. Gradient boosting: similar story to trees, but boosting's sequential error-correction can extract more signal per example than a single tree, often needing somewhat less data than an equally deep single tree for comparable performance. Neural networks: sample complexity theory here is much less precise in practice (the classical VC-dimension-style bounds are vacuous, as covered elsewhere for this topic); empirically, large networks tend to need substantially more labeled data than simpler families to reliably outperform them, though this varies enormously by architecture and task.
Empirical estimation via learning curves: train the model on increasing subsample sizes of your current data, plot validation error against sample size, and fit a decay curve (commonly a power-law form) to extrapolate how much MORE data would be needed to reach a target error, the same methodology used elsewhere for the "would more data help" question, applied here specifically to compare across model families rather than to decide between more data and more capacity for one fixed family.

Worked example
Comparing a linear model and a random forest on the same task via learning curves at n=1000, 5000, 25000: the linear model's curve might flatten by n=5000 (it's already near its achievable floor, since it can't represent much more relationship complexity regardless of data), while the random forest's curve is still clearly improving at n=25000, suggesting the forest genuinely needs (and can use) substantially more data to reach ITS achievable floor, even though the forest may already be outperforming the linear model at every size tested.

Trade-offs & pitfalls
Extrapolating a fitted decay curve beyond the range of sample sizes you've actually tested is inherently uncertain; treat it as a planning estimate to validate once you've collected an intermediate amount of new data, not a firm prediction, especially for model families (like neural networks) whose sample-complexity behavior is theoretically less well understood.

Direct answer
Narrow the field using cheap, offline criteria first (license/usage terms, known benchmark performance on tasks similar to yours, size versus your latency/cost budget, and training-data provenance concerns relevant to your use case), then validate the top 2-3 candidates with a small, targeted evaluation on YOUR actual data and task before committing.

Structured elaboration
Narrowing criteria: licensing (can you legally use and modify it for your product), size relative to your inference budget (a much larger model than your latency/cost constraints allow is disqualified regardless of quality), reported benchmark performance on tasks genuinely similar to yours (not just aggregate leaderboard rank, which can be dominated by tasks irrelevant to your use case), and training-data provenance where it matters (a customer-facing product with sensitivity to certain content or bias concerns may need to rule out models with known problematic training data).
Validation before committing: run the shortlisted 2-3 candidates on a small, representative slice of YOUR actual task and data (not just their published benchmark numbers, which may not transfer to your specific distribution), measuring both quality and the practical serving cost/latency you'd actually see. This step exists because published benchmarks are notoriously poor predictors of performance on a specific downstream task with its own data distribution.

Worked example
Narrowing 8 candidate foundation models to 3 based on license compatibility and inference-cost budget, then running all 3 on a 500-example held-out sample of your actual product's task, measuring both task-specific accuracy and real inference latency on your target hardware; the model that wins on YOUR data, not the one that tops a general leaderboard, is the one to commit to.

Trade-offs & pitfalls
Relying purely on published leaderboard rank without a task-specific validation step is a common and costly mistake; a model's aggregate benchmark superiority doesn't guarantee it's better for your specific narrow task, and the validation step is cheap insurance against committing to the wrong one.

Direct answer
Nested cross-validation wraps an inner CV loop (which searches for the best hyperparameters) inside an outer CV loop (which evaluates that whole tuning procedure on data it never touched); this produces an unbiased generalization estimate because the outer test folds never influence which hyperparameters were chosen, unlike reporting the inner loop's own best CV score, which is optimistic because it's the very quantity that was searched over to pick the winner.

Structured elaboration
The outer loop splits data into K outer folds. For each outer fold, the corresponding outer-training data is handed to an INNER cross-validation procedure (its own set of folds), which performs a hyperparameter search (grid, random, whatever) and returns the single best configuration according to inner-CV score. That configuration is then refit on the full outer-training data and evaluated ONCE on the outer-test fold, a slice of data the entire inner search never saw. Averaging that outer-test score across all K outer folds gives the nested CV estimate.
What goes wrong if you skip the outer loop: if you just report the inner loop's best CV score directly as your generalization estimate, you're reporting the score of the configuration that was SELECTED because it looked best on exactly that data; you've implicitly done a search over many configurations and reported the winner's score without any penalty for having searched, which is systematically optimistic (the more configurations you tried, the more this optimism grows, since you're effectively taking a max over noisy estimates and reporting it as if it were a single unbiased estimate).

Worked example (executed)
Nested 5-fold CV over a ridge-regression alpha grid on a synthetic regression dataset gave outer-fold MSEs of [132.1, 81.4, 96.8, 90.0, 129.0], averaging to 105.9, the honest generalization estimate. A separate simulation comparing this to a naive single train/val split tuning approach measured the naive method's reported validation MSE as noticeably lower than its OWN true held-out test MSE (computed against a genuinely independent large test set from the same generative process), a concrete demonstration of the optimism the naive approach carries; the nested CV estimate tracked the true held-out MSE far more closely in the same experiment.

Trade-offs & pitfalls
Nested CV multiplies your compute cost by roughly (inner folds x outer folds) versus a single tune-and-evaluate pass; it's the right tool when you need an honest generalization NUMBER to report (a paper, a go/no-go decision), but for day-to-day iteration where you just want to pick a reasonable model quickly, a simpler held-out validation approach is often a pragmatic compromise.

Direct answer
When validation scores are close, the deciding factors are usually interpretability, inference latency and cost, training/maintenance complexity, and robustness to future data shifts, not the metric itself.

Structured elaboration
Logistic regression wins on interpretability (coefficients have a direct, explainable meaning), inference speed (a dot product versus a full forward pass), training simplicity, and often on robustness when the true relationship is close to linear or there isn't enough data to reliably fit a much more flexible model. A deep neural network wins if there's genuine, complex non-linear structure the data supports learning, if you expect to keep improving it with more data/features over time, or if it's part of a broader system (e.g. shared embeddings) that benefits from the same architecture family.
Beyond those two big axes: maintenance cost (a neural network typically needs more careful monitoring and retraining discipline), regulatory/compliance requirements (some domains effectively require an explainable model), and how the model will be consumed downstream (a real-time low-latency service favors the cheaper model).

Worked example
For a credit-approval decision where regulation requires explaining individual denials and a millisecond-level latency budget exists, logistic regression is very likely the right call even if the neural network scores half a point higher on validation AUC. For an internal ranking model with no explainability requirement and a generous latency budget, the marginal edge might justify the added complexity of the neural network.

Trade-offs & pitfalls
Don't let "the fancier model is probably better long-term" become the deciding factor by default; if the simpler model is genuinely competitive today, the burden of proof is on the more complex model to show it earns its added cost, not the other way around.