cs.LGSep 4, 2026

Dimension-Adaptive Batched Lipschitz Narrowing Without Knowing the Zooming Dimension

Authors: Yasong Feng

Abstract

The Appropriately Combined Edge-length (ACE) sequence in A-BLiN depends on the zooming dimension dzd_z. 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 dzd_z or the zooming constant CzC_z, yet it attains O~d(T(dz+1)/(dz+2))\widetilde{\mathcal O}_d(T^{(d_z+1)/(d_z+2)}) regret with Od(log⁡log⁡T)\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)Θ_d(\log\log T) when dzd_z is unknown.

Explore similar work

CardsList
  1. Memory--Batch Tradeoffs in Lipschitz Bandits

    Aug 8, 2026Zicheng Lyu, Zengfeng HuangMulti-Armed Bandits

  2. Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

    May 29, 2026Ivan Lau, Daniel McMorrow, Kevin Jamieson +1Multi-Armed BanditsMinimax Regret

  3. Batched Kernelized Bandits: Refinements and Extensions

    Mar 13, 2026Chenkai Ma, Keqin Chen, Jonathan ScarlettBlack-Box OptimizationMulti-Armed Bandits