Dimension-Adaptive Batched Lipschitz Narrowing Without Knowing the Zooming Dimension
Yasong Feng
cs.LG
Abstract
The Appropriately Combined Edge-length (ACE) sequence in A-BLiN depends on the zooming dimension dz. This note removes that dependence. The next edge length is selected from the number of cubes that survive the preceding elimination. The resulting Count-Adaptive BLiN algorithm does not use dz or the zooming constant Cz, yet it attains $\widetilde{\mathcal O}_d(T^{(d_z+1)/(d_z+2)})$ regret with $\mathcal O_d(\log\log T)$ batches. Together with the adaptive-grid lower bound in Theorem 10 of the original paper, the optimal batch complexity remains $Θ_d(\log\log T)$ when dz is unknown.
Topics
Classified with taxonomy v2 on Mon, 7 Sept 2026.