Lazy Perturbed Leaders with Resampled Importance Weights for Piecewise Losses

Many tuning problems have a loss that jumps rather than slopes. Examples are choosing the exponent in a greedy knapsack rule, the two penalties of an ElasticNet, or a kernel bandwidth for graph-based semi-supervised learning. A tiny change in the parameter reorders items or changes which features are kept, and validation loss jumps. Online learning handles these landscapes through dispersion, an assumption that the jump locations do not pile up in any small region across rounds. Under dispersion, exponential-weights methods reach square-root-of-$T$ regret, where regret is the gap to the best fixed parameter in hindsight. This theory has two costs that no existing method pays down at once. It either needs the full loss curve every round, or it maintains an explicit density over the parameter space. Maintaining that density is cheap on a line but exponential in dimension.

We propose an online learner that tackles both costs together. It follows a perturbed leader, meaning it plays the minimizer of noise-perturbed past losses, and it holds its choice fixed within epochs. It sees only the region of constant loss around the parameter it actually ran. Its importance weights come from repeatedly calling the same offline minimizer, not from a density we cannot integrate. Because the policy is frozen within an epoch, those repeated calls can be pooled and shared across rounds. That pooling makes a small number of oracle calls do the work of an explicit probability computation. The result is a dimension-scalable learner for discontinuous losses under partial feedback, together with a measured tradeoff curve between oracle calls and regret.

Core Claim

Two lines of work sit on either side of this gap. Semi-bandit Optimization in the Dispersed Setting observes that running a combinatorial algorithm at parameter $\rho_t$ reveals the loss on the whole piece $A_t$ of constant behavior around it. Its Continuous Exp3-SET divides the observed loss by the probability mass the learner puts on that piece. This gives $\tilde{O}(\sqrt{dT}+T^{1-\beta})$ regret, but it requires integrating an explicit piecewise density, which is only practical in one dimension. Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making avoids densities entirely. It uses Lazy Follow-the-Perturbed-Leader, which reaches average regret $\epsilon$ with $O(\epsilon^{-2})$ calls to an offline minimizer, but it needs the full past loss functions and so full information. The obstacle to combining them is concrete. A perturbed leader's action distribution is implicit, so the probability of piece $A_t$, which the estimator divides by, is never available in closed form.

The method we reuse is geometric resampling, the idea in Neu et al. of approximating unknown selection probabilities by repeated simulation of the learner. Applied here, it works as follows. After observing piece $A_t$, draw fresh perturbed-leader outputs from the current policy until one lands in $A_t$, stopping after $M$ draws. Let $K_t$ be the number of draws used. The estimate is

$$\hat{\ell}_t(\rho) = \ell_t(\rho)\, K_t\, \mathbb{I}\{\rho \in A_t\},$$

where $\ell_t(\rho)$ is the loss observed on the piece and $\mathbb{I}$ is the indicator. Since $K_t$ is geometric with success probability $p_t(A_t)$, its mean is close to $1/p_t(A_t)$. The truncation at $M$ adds a downward bias of at most $(1-p_t(A_t))^M$ per round.

Dispersion is what keeps this bias small, because it prevents pieces from shrinking to near-zero mass. Laziness is what keeps it cheap. Within an epoch of length $\tau$ the policy is frozen, so one pool of $M$ draws can serve every round in that epoch. The oracle cost becomes roughly $(T/\tau)\cdot M$ calls instead of $T\cdot M$.

Our main claim is that this pooled estimator, fed back into Lazy FTPL, gives sublinear regret for dispersed piecewise losses under semi-bandit feedback. It does so with oracle calls sublinear in $T$ and per-round work polynomial in dimension. We further claim that the three knobs of epoch length, pool size and perturbation scale trace an explicit efficiency-regret frontier.

The closest prior bandit method, INTERNAL EXP3 in No Internal Regret with Non-convex Loss Functions, discretizes onto a grid of size $(1/\epsilon)^d$ and pays $O(T^{2/3})$ for piecewise-constant losses. We use no grid and exploit the piece structure that grid methods discard.

Research Program

The theoretical work has three parts. The first is to bound the variance of the pooled estimator. Reusing one pool across an epoch makes estimates within that epoch correlated, although each is still correctly centered given the past. We must show that the correlation inflates the stability term of the Block–Simchowitz–Rakhlin analysis by at most a factor controlled by $\tau$ and the dispersion constant. This is the step most likely to fail, and a fallback is available: use fresh draws each round and give up the amortization.

The second part is to turn the truncation bias into a regret term. We expect it to behave like the $T/(eM)$ term familiar from geometric resampling, multiplied by a dispersion-controlled count of pieces with small mass.

The third part concerns adversarial cliffs. The research file notes that freezing a policy lets an adversary trap it on the wrong side of a cliff. We address this through the smoothed-adversary assumption rather than by shortening epochs, and we test whether that assumption is actually needed.

The engineering work is modest. Each problem needs an offline minimizer over weighted piece-losses, and a routine that reports the piece around a queried parameter. Knapsack with multi-parameter scoring and ElasticNet paths both admit these.

Baselines

The naive reference is uniform discretization with standard Exp3 from Bubeck et al.. We will run it with grid width tuned over the same budget as our method. It shows what ignoring the piece structure costs, and in $d\ge 3$ it shows the per-round cost of an explicit grid.

The strongest competitor in one dimension is Continuous Exp3-SET Semi-bandit Optimization in the Dispersed Setting. It uses the same feedback and computes piece probabilities exactly. That paper reports a bound improvement for greedy knapsack from $\tilde{O}(n^2\sqrt{T})$ to $\tilde{O}(n\sqrt{T})$ at $O(n\log n)$ per round. No reported empirical regret number was found on Lacuna for Continuous Exp3-SET. We will run it on identical instance streams with its learning rate tuned on the same held-out streams used to tune ours.

In one dimension, "beating" it means matching its cumulative regret to within 10% while using comparable wall-clock time. In $d\ge 2$ it can only run on a coarse grid of pieces, and beating it means lower regret at equal wall-clock time.

The full-information ceiling is Lazy FTPL given complete loss curves Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making. It uses the same oracle and the same epochs. We will report how much of its regret we recover and at what ratio of oracle calls.

We also include INTERNAL EXP3 No Internal Regret with Non-convex Loss Functions, run for external regret, as the existing bandit method for dispersed losses.

Two ablations isolate our key ingredient. The first replaces pooled resampling with fresh per-round resampling at equal $M$, which isolates amortization. The second replaces resampling with a known uniform-exploration floor, in which the learner explores uniformly with probability $\gamma$ and updates only on exploration rounds. This isolates whether resampled weights are needed at all.

Why not just…?

Why not just discretize and run Exp3? A grid of width $\epsilon$ has $(1/\epsilon)^d$ arms. A shift of $\epsilon$ across a jump can change the loss by a constant amount, so the grid does not recover the Lipschitz approximation argument. Sharma's grid-based bandit analysis lands at $O(T^{2/3})$ for piecewise-constant losses No Internal Regret with Non-convex Loss Functions. The grid baseline above measures both the regret gap and the per-round cost as $d$ grows from 1 to 5.

Why not just use Continuous Exp3-SET, which already solves this? In one dimension this is a real threat, because the piece masses there are exact and cheap. We therefore do not claim a one-dimensional win and treat parity as the success criterion. The case for our method rests on $d\ge 2$, where integrating the density over pieces bounded by nonlinear surfaces is the unaddressed bottleneck named in that paper. If the multidimensional knapsack and ElasticNet runs show no advantage at equal wall-clock, the claim fails.

Why not just compute the full loss curve and run full-information Lazy FTPL? This is fine when the full curve is cheap, as for one-dimensional knapsack. Tracing every piece of a two-parameter ElasticNet path or a multi-parameter scoring rule on each round is costly, however. Provably tuning the ElasticNet across instances establishes $O(p^2)$ pseudo-dimension, which says nothing about how cheap enumeration is. We will measure the time to compute the full curve against the time for a piece query, and report regret per unit of wall-clock rather than per round.

Why not just add $\gamma$-uniform exploration so probabilities are known? Knowing the probability of a piece under uniform exploration still requires the piece's volume, which is equally hard to compute in $d\ge 2$. Updating only on exploration rounds also typically costs a $T^{2/3}$ rate, the same pattern the first-order Banditron shows in Efficient Online Bandit Multiclass Learning with Õ(√T) Regret. This is the second ablation in the Baselines section, and we will estimate its regret slope directly.

Proposed Experiments

We use four testbeds. The first is greedy knapsack with scoring $v_i/s_i^\rho$, as in Semi-bandit Optimization in the Dispersed Setting, extended to multi-exponent scorings with $d=2$ to $5$. The file reports only a meta-learning figure here: 84.74% versus 85.66% of offline optimum in Learning-to-learn non-convex piecewise-Lipschitz functions. That is a different protocol, so we report fraction-of-optimum as well to allow a loose comparison. The second testbed is ElasticNet $(\lambda_1,\lambda_2)$ tuning across regression instances. The third is Gaussian-kernel graph semi-supervised learning on the MNIST, Omniglot and CIFAR-10 subsets of Data driven semi-supervised learning, which reports no exact accuracy numbers. The fourth is a synthetic adversary that places cliffs near the current leader, run with and without smoothing noise.

The metrics are cumulative regret against the best fixed parameter in hindsight, oracle calls, and wall-clock time. Every method is run over 20 seeds.

The decisive checks are as follows. First, as we sweep $\tau$ and $M$, regret against oracle calls should form a frontier that dominates both baselines in $d\ge 2$. Second, pooled resampling should match fresh resampling in regret at roughly $1/\tau$ of the oracle cost. Third, measured truncation bias should shrink as $M$ grows, at the rate predicted from the dispersion constant. Fourth, without smoothing, the cliff adversary should force near-linear regret on lazy epochs; if it does not, the smoothing assumption is stronger than needed.