Technical Summary: The Sample Complexity of Parameter-Free Stochastic Convex Optimization

Problem Statement

This paper addresses the sample complexity of stochastic convex optimization (SCO) when key problem parameters are unknown. Specifically, it considers the setting where the Lipschitz constant ($L$) is known, but the distance to optimality ($R^\star$, the distance from the initial point to the optimal solution set) is unknown.

Classical theory establishes that when both $L$ and $R^\star$ are known, Stochastic Gradient Descent (SGD) achieves optimal dimension-free worst-case bounds for sample, gradient oracle, and computational complexity. However, in the parameter-free setting, while computational complexity is well-understood, the sample complexity remains an open challenge. A natural approach to handling unknown parameters is hyperparameter search (e.g., tuning the learning rate or radius) via model selection (minimizing validation loss). The paper identifies a critical gap: standard model selection can catastrophically overfit to small validation sets when the loss is unbounded (e.g., cross-entropy) and strong convexity is absent, leading to suboptimal sample complexity.

Methodology

The authors propose two distinct strategies to achieve optimal sample complexity without prior knowledge of $R^\star$:

1. Reliable Model Selection

The first strategy improves upon standard model selection to prevent overfitting on small validation sets.

• Mechanism: The method, termed ReliableModelSelection, introduces a "safe set" of candidate models. Instead of simply picking the model with the lowest validation error, it constructs confidence intervals around the validation error relative to a reference model (typically the origin).
• Algorithm: It defines a threshold $\theta$ based on the minimum of the extended upper bounds (validation error + scaled confidence width). It then selects the model with the lowest validation error only among those candidates whose validation error plus the confidence width falls below this threshold.
• Adaptation: This approach is designed to work generically for tuning hyperparameters (like learning rates) in a grid search. It provides strong guarantees when the population risk is strongly convex and avoids the catastrophic failure modes of standard selection in non-strongly convex settings.

2. Regularization-Based Localization

The second strategy, OptimalAdaptiveMethod, aims for "perfect adaptivity" to the unknown distance $R^\star$, removing the logarithmic factors present in the first strategy.

• Two-Stage Process:
  1. Localization (Stage 1): Using half the sample, the method solves a norm-regularized Empirical Risk Minimization (ERM) problem: $\min_x \bar{F}(x) + \lambda_n \|x\|$. The key insight is that for an appropriately chosen regularization parameter $\lambda_n$ (derived from empirical gradient variance), the solution $\hat{x}_{\lambda_n}$ provides an estimate of the distance to optimality within a constant factor (i.e., $\|x^\star\| \leq O(\|\hat{x}_{\lambda_n}\|)$).
  2. Constrained Optimization (Stage 2): Using the remaining half of the sample, a standard, known-parameter stochastic optimization algorithm (e.g., AdaSGD, AdaGrad, or Entropic Mirror Descent) is run within a ball of radius $R = 2\|\hat{x}_{\lambda_n}\|$.
• Novel Concentration Bounds: To support this, the authors derive new concentration inequalities for sums of i.i.d. vectors and dependent random variables, allowing them to bound the gradient variance empirically without knowing the true Lipschitz constant (provided an upper bound exists).

3. Simultaneous Adaptation

The authors combine these methods to simultaneously adapt to multiple problem structures (Euclidean, $\ell_1$, and $\ell_\infty$ norms). They run the regularization-based method for each norm and use ReliableModelSelection to choose the best output among them.

Key Contributions

1. Characterization of Standard Model Selection Failure: The paper demonstrates that standard model selection (minimizing validation loss) can perform poorly when tuning learning rates for adaptive SGD in the absence of strong convexity and with unbounded losses. It provides a lower bound showing that standard selection can be a factor of $\Omega(\rho)$ worse than optimal, where $\rho$ is the uncertainty in $R^\star$.
2. Reliable Model Selection Algorithm: A generic method that mitigates overfitting on small validation sets. When used to tune learning rates, it achieves sample complexity matching the optimal known-parameter bounds up to $\log \log$ factors in the uncertainty of $R^\star$.
3. Perfect Adaptivity via Regularization: A novel method that achieves sample complexity matching the optimal known-parameter bounds exactly (removing the $\log \log$ factors) when only $R^\star$ is unknown. This is achieved by using norm-regularized ERM to estimate $R^\star$ within a constant factor.
4. Separation of Complexity Measures: The results imply a separation between gradient oracle complexity and sample complexity for parameter-free SCO. While lower bounds exist for oracle complexity (preventing $O(1)$ Price of Adaptivity), the paper shows that $O(1)$ Price of Adaptivity is achievable for sample complexity.
5. Multi-Norm Adaptation: A unified framework that adapts to Euclidean, Manhattan, and Infinity norms simultaneously.

Results

• Theoretical Bounds:

  • Reliable Model Selection: Achieves suboptimality $O\left(\frac{LR^\star}{\sqrt{n}} \sqrt{\ln \ln \rho} + \frac{\hat{L}R^\star}{n} \ln \ln \rho\right)$, matching known-parameter bounds up to $\log \log$ factors.
  • Regularization-Based Method: Achieves suboptimality $O\left(\frac{LR^\star}{\sqrt{n}}\right)$ (and corresponding bounds for $\ell_1$ and $\ell_\infty$ norms) with high probability, matching the optimal known-parameter sample complexity without logarithmic penalties in $\rho$.
  • Simultaneous Adaptation: The combined method achieves the minimum of the optimal bounds across the three norms, up to constant factors.

• Experimental Findings:

  • Few-Shot Learning (CIFAR-10): Fine-tuning CLIP models with small validation sets (32 shots or fewer). Standard model selection (minimizing validation loss) performed worse than the zero-shot baseline due to overfitting. The ReliableModelSelection method successfully improved performance over the baseline.
  • Prompt Engineering (Gemini): Selecting prompts to count shapes in images. With small validation sets, ReliableModelSelection outperformed standard selection when paired with a high-quality reference model.

Significance and Claims

The paper claims to resolve the characterization of sample complexity for parameter-free stochastic convex optimization. Its primary significance lies in demonstrating that perfect adaptivity to the unknown distance to optimality is possible for sample complexity, a result that contrasts with existing lower bounds for gradient oracle complexity.

The authors emphasize that their regularization-based method provides a theoretical separation between the computational/oracle cost and the sample cost of parameter-free optimization. While the method requires an estimate of the Lipschitz constant (within a factor of $\tilde{O}(\sqrt{n})$), it removes the need for knowing the distance to optimality entirely.

The paper also highlights the practical relevance of their "Reliable Model Selection" method, showing through experiments that it can mitigate overfitting in few-shot learning scenarios where validation sets are small and losses are unbounded. However, the authors note limitations: the theoretical guarantees for the regularization method require an upper bound on the Lipschitz constant, and the practical application of ReliableModelSelection depends on the availability of a reasonable reference model and knowledge of the problem structure to compute confidence bounds.