Source-linked AI summary
Dimension-Adaptive Batched Lipschitz Narrowing Without Knowing the Zooming Dimension
Yasong Feng
TL;DR
The method uses an adaptive batch grid whose edge lengths are measurable from observations rather than requiring zooming parameters as inputs. It attains the optimal regret exponent and Θ_d(log log T) batch-complexity order.
Problem
The algorithm must operate without taking the zooming dimension d_z or zooming constant C_z as inputs.
Method
Count-Adaptive BLiN selects data-dependent edge lengths and batch grids from quantities measurable using observations available at the preceding batch.
Results
The algorithm attains the optimal T-regret exponent with at most O_d(log log T) batches.
Takeaways & Limitations
The optimal Θ_d(log log T) batch-complexity order remains achievable without knowing d_z or C_z.
Abstract
from arXiv · showhide
The Appropriately Combined Edge-length (ACE) sequence in A-BLiN depends on the zooming dimension $d_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 $d_z$ or the zooming constant $C_z$, 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 $d_z$ is unknown.
1 Setup and relation to the original results
CA-BLiN retains the original arm-space model while replacing the zooming-dimension-dependent ACE schedule with data-dependent, dyadic edge lengths. Its adaptive batches use observations from preceding eliminations to determine the next refinement.
- CA-BLiN operates on A = [0, 1]^d with the infinity norm, retaining the model and notation of the original work.
- Each batch maintains active standard cubes Am with common edge length rm, while A+_m records cubes surviving elimination.
- The method replaces the dz-dependent ACE sequence with edge lengths chosen data-dependently and dyadically from the preceding elimination.The original results used ACE to reduce batches from O(log T) to O(log log T).
- The algorithm plays every surviving cube nm times, collects rewards, computes empirical means, and then performs elimination before the next refinement.The batch length is Lm = |Am|nm, and Cleanup handles the remaining rounds without an intermediate feedback round.
- Neither dz nor Cz is required as input, and rm, Am, and tm are measurable from observations available at time tm−1.Thus the resulting batch grid is adaptive in the sense used in the original work.
2 Regret and batch complexity
Count-Adaptive BLiN selects data-dependent edge lengths from surviving cubes, avoiding dependence on d_z and C_z while preserving the optimal regret exponent and logarithmic-logarithmic batch complexity. Its proof extends concentration and elimination guarantees to adaptive scales, bounds refinement and cleanup regret, and establishes the final theorem.
- Theorem scope: The theorem analyzes a dimension-adaptive policy under fixed ambient dimension d, with d_z and C_z appearing only in the analysis.The algorithm itself does not require these instance parameters.
- Proof strategy: The proof preserves concentration and elimination properties for data-dependent edge lengths before bounding refinement-batch and Cleanup regret.The argument proceeds through adaptive-scale concentration, survivor elimination, batch bounds, and cleanup analysis.
- Elimination: Every surviving cube has gap at most 8r_m, so survivors lie in a high-reward region and their centers form an r_m/2-packing.This survivor characterization supports the subsequent count and regret bounds.
- Refinement regret: Every completed refinement batch satisfies the common regret bound in (4), covering both r_m ≥ ρ and r_m < ρ cases.The case split is resolved by a single bound after combining the batch-length inequalities.
- Final guarantees: At most B_0 + 1 = O_d(log log T) batches are used, and the resulting policy attains the optimal T-regret exponent without knowing d_z or C_z.The total expected regret bound follows by summing completed refinements and the final Cleanup batch; Theorem 10 supplies the matching batch-complexity conclusion.