D-Adaptation (Learning-Rate-Free Optimization by Distance Lower Bounding)

A hyperparameter-free (learning-rate-free) optimization framework (Algorithms 1-5) for minimizing convex G-Lipschitz and deep learning objectives that automatically calibrates the base step size without backtracking line searches or extra function/gradient evaluations by maintaining a monotonically non-decreasing empirical lower bound d_k <= D on the unknown initial distance to a minimizer D = ||x_0 - x_*||. In Dual Averaging with D-Adaptation (Algorithm 1), at each step k the algorithm accumulates the distance-weighted dual gradient sum s_{k+1} = s_k + d_k g_k, updates the AdaGrad-Norm scale gamma_{k+1} = 1 / sqrt{sum_{i=0}^k ||g_i||^2}, computes the empirical lower bound hat{d}_{k+1} = (gamma_{k+1} ||s_{k+1}||^2 - sum_{i=0}^k gamma_i d_i^2 ||g_i||^2) / (2 ||s_{k+1}||) (Option I) or hat{d}_{k+1} = (sum_{i=0}^k d_i gamma_i langle g_i, s_i rangle) / ||s_{k+1}|| (Option II), sets d_{k+1} = max(d_k, hat{d}_{k+1}), updates x_{k+1} = x_0 - gamma_{k+1} s_{k+1}, and returns the weighted average hat{x}_n = (sum_{k=0}^n d_k x_k) / (sum_{k=0}^n d_k).