From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model

Shinsaku Sakaue; Yuichi Yoshida

arxiv: 2602.09457 · v2 · submitted 2026-02-10 · 📊 stat.ML · cs.DS· cs.LG

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model

Shinsaku Sakaue , Yuichi Yoshida This is my paper

Pith reviewed 2026-05-16 06:06 UTC · model grok-4.3

classification 📊 stat.ML cs.DScs.LG

keywords online learningrandom-order modelaverage sensitivitysmall-loss regretsubmodular minimizationk-means clusteringcut sparsifiers

0 comments

The pith

Offline algorithms with (1+ε) approximation and average sensitivity bounds convert to online algorithms with small-loss regret in the random-order model.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that any offline algorithm satisfying a (1+ε)-approximation guarantee, an average sensitivity bound controlled by some function ϕ(ε), and stability with respect to ε can be turned into an online algorithm whose regret is bounded by roughly the concave conjugate of ϕ applied to the total offline optimum. This refines earlier (1+ε)-approximate regret results and removes the need for linearity or smoothness assumptions on the losses. The result covers online k-means clustering and low-rank approximation directly, and produces a concrete small-loss bound of order Õ(n³ + n^{3/4} OPT_T^{3/4}) for online submodular function minimization via cut sparsifiers.

Core claim

If an offline algorithm enjoys a (1+ε)-approximation guarantee, an average sensitivity bound controlled by a function ϕ(ε), and stability with respect to ε, then the batch-to-online transformation yields a small-loss regret bound of order Õ(ϕ*(OPT_T)) in the random-order model, where ϕ* is the concave conjugate of ϕ and OPT_T is the offline optimum over T rounds.

What carries the argument

The extended batch-to-online transformation that converts average sensitivity bounds into small-loss regret via the concave conjugate ϕ*.

If this is right

Online k-means clustering admits small-loss regret controlled by the offline optimum.
Online low-rank approximation admits small-loss regret controlled by the offline optimum.
Online submodular minimization admits regret Õ(n³ + n^{3/4} OPT_T^{3/4}) using (1±ε) cut sparsifiers.
Online ℓ1 regression admits a small-loss regret bound derived from the same transformation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same template can be applied to any new offline problem once an average-sensitivity bound for its (1+ε) approximation is proved.
Cut sparsifiers become a generic tool for obtaining small-loss online regret rather than merely approximation guarantees.
The dependence on OPT_T rather than T suggests the bounds remain meaningful even when the total loss grows sublinearly.

Load-bearing premise

The offline algorithms for the target problems already possess both the (1+ε) approximation guarantee and the stated average sensitivity bound, and the random order does not destroy the necessary concentration properties.

What would settle it

An explicit construction of an offline (1+ε)-approximation algorithm whose average sensitivity is bounded by ϕ(ε) yet whose online regret in random order exceeds any constant multiple of ϕ*(OPT_T) for large T.

read the original abstract

We study online learning in the random-order model, where the multiset of loss functions is chosen adversarially but revealed in a uniformly random order. By extending the batch-to-online transformation of Dong and Yoshida (2023), we show that if an offline algorithm enjoys a $(1+\varepsilon)$-approximation guarantee, an average sensitivity bound controlled by a function $\varphi(\varepsilon)$, and stability with respect to $\varepsilon$, then we can obtain a small-loss regret bound typically of order $\tilde O(\varphi^{\star}(\mathrm{OPT}_T))$, where $\varphi^{\star}$ is the concave conjugate of $\varphi$, $\mathrm{OPT}_T$ is the offline optimum over $T$ rounds, and $\tilde O$ hides polylogarithmic factors in $T$. Our result refines their original $(1+\varepsilon)$-approximate regret guarantee and applies to a broad class of problems, including online $k$-means clustering and online low-rank approximation. We further apply our approach to online submodular function minimization using $(1\pm\varepsilon)$-cut sparsifiers of submodular hypergraphs, obtaining a small-loss regret bound of $\tilde O(n^3 + n^{3/4}\mathrm{OPT}_T^{3/4})$, where $n$ is the ground-set size; we also demonstrate its applicability to online $\ell_1$ regression. Our work sheds light on the power of sparsification and related algorithmic techniques in achieving small-loss regret bounds in the random-order model, without requiring structural assumptions on loss functions, such as linearity or smoothness.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean reduction from offline (1+ε)-approx plus average sensitivity to small-loss regret in random order, plus a new explicit bound for submodular minimization.

read the letter

The main takeaway is a general reduction that converts an offline (1+ε)-approximation algorithm with average sensitivity bounded by ϕ(ε) and ε-stability into a small-loss regret bound of order Õ(ϕ*(OPT_T)) under random order. They also produce a new concrete bound for online submodular function minimization using cut sparsifiers. This refines the earlier (1+ε) regret from Dong and Yoshida by swapping in the concave conjugate of the sensitivity function. The approach covers k-means clustering, low-rank approximation, and submodular minimization without requiring the loss functions to be linear or smooth, which is a practical plus. The submodular bound Õ(n³ + n^{3/4} OPT_T^{3/4}) is explicit and not present in the cited prior work, so that part is genuinely new. The reduction itself is stated cleanly in the abstract and seems to follow directly once the sensitivity and stability conditions hold for the offline algorithm. The soft spots are limited. The central step extends the 2023 batch-to-online transformation, so the proof must confirm that average sensitivity alone controls the concentration under random permutation; if that link is tight, the claim is fine, but it is the part worth checking most carefully. The submodular result also depends on the quality of the cited sparsifiers, which is inherited rather than reproved here. Overall the math looks grounded and the applications are chosen sensibly. This is for researchers working on online algorithms for combinatorial problems or regret bounds that improve with OPT_T. A reader focused on submodular optimization or online clustering would get direct value from the new bound and the general technique. It deserves a serious referee because the reduction is general enough and the submodular application is concrete enough to justify the time.

Referee Report

2 major / 2 minor

Summary. The paper claims that by extending the batch-to-online transformation of Dong and Yoshida (2023), any offline (1+ε)-approximation algorithm equipped with an average sensitivity bound controlled by a function ϕ(ε) and ε-stability yields an online algorithm with small-loss regret Õ(ϕ^*(OPT_T)) in the random-order model, where ϕ^* is the concave conjugate. The framework is applied to online k-means clustering, low-rank approximation, submodular function minimization (producing the concrete bound Õ(n^3 + n^{3/4} OPT_T^{3/4}) via (1±ε)-cut sparsifiers), and ℓ1 regression, without requiring linearity or smoothness of the losses.

Significance. If the reduction is shown to hold under the stated conditions, the result is significant: it supplies a general route from offline approximation-plus-sensitivity properties to refined small-loss regret bounds in the random-order model, thereby clarifying the algorithmic utility of sparsification techniques for online problems. The concrete applications to clustering and submodular minimization illustrate the framework's reach and avoid strong structural assumptions on the loss sequence.

major comments (2)

[Main reduction theorem] The central reduction (extending Dong and Yoshida 2023) asserts that average sensitivity ϕ(ε) together with ε-stability is sufficient for the random-order concentration arguments that produce the conjugate bound Õ(ϕ^*(OPT_T)). The manuscript must supply an explicit self-contained argument showing how ϕ(ε) controls the deviation terms under uniform random permutation; without this, the step from offline sensitivity to online small-loss regret remains unverified and is load-bearing for the main claim.
[Submodular function minimization application] In the submodular minimization application, the stated regret Õ(n^3 + n^{3/4} OPT_T^{3/4}) is obtained by plugging the sensitivity of (1±ε)-cut sparsifiers into the general template. The paper must derive the precise functional form of ϕ(ε) induced by the sparsifier parameters and confirm that the resulting offline algorithm satisfies the required ε-stability condition; otherwise the concrete bound cannot be guaranteed.

minor comments (2)

[Abstract and introduction] The definition and properties of the concave conjugate ϕ^* should be recalled explicitly when first introduced, including its relation to the Legendre transform or Fenchel conjugate.
[Preliminaries] Ensure that the stability notion with respect to ε is stated with a precise mathematical definition (e.g., Lipschitz or continuity modulus) rather than left implicit.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The two major comments identify places where the presentation of the central reduction and the submodular application can be strengthened. We will revise the manuscript to address both points explicitly.

read point-by-point responses

Referee: [Main reduction theorem] The central reduction (extending Dong and Yoshida 2023) asserts that average sensitivity ϕ(ε) together with ε-stability is sufficient for the random-order concentration arguments that produce the conjugate bound Õ(ϕ^*(OPT_T)). The manuscript must supply an explicit self-contained argument showing how ϕ(ε) controls the deviation terms under uniform random permutation; without this, the step from offline sensitivity to online small-loss regret remains unverified and is load-bearing for the main claim.

Authors: We agree that a fully self-contained derivation is desirable. In the revised manuscript we will add a dedicated subsection that derives the concentration bounds step-by-step, showing precisely how the average-sensitivity function ϕ(ε) enters the deviation terms under a uniform random permutation and how the ε-stability assumption closes the argument. This will make the reduction from offline sensitivity to the small-loss regret bound Õ(ϕ^*(OPT_T)) explicit and verifiable without reference to the prior work. revision: yes
Referee: [Submodular function minimization application] In the submodular minimization application, the stated regret Õ(n^3 + n^{3/4} OPT_T^{3/4}) is obtained by plugging the sensitivity of (1±ε)-cut sparsifiers into the general template. The paper must derive the precise functional form of ϕ(ε) induced by the sparsifier parameters and confirm that the resulting offline algorithm satisfies the required ε-stability condition; otherwise the concrete bound cannot be guaranteed.

Authors: We will expand the submodular section to include the explicit functional form of ϕ(ε) obtained from the (1±ε)-cut sparsifier construction (with the concrete dependence on the sparsification parameter ε and the ground-set size n). We will also verify that the resulting offline (1+ε)-approximation algorithm satisfies the ε-stability condition required by the general framework, thereby confirming that the stated regret bound follows directly from the main theorem. revision: yes

Circularity Check

0 steps flagged

No circularity: central result is an explicit extension of the 2023 transformation under new sensitivity conditions

full rationale

The paper derives its small-loss regret bound by extending the batch-to-online transformation of Dong and Yoshida (2023) once an offline (1+ε)-approximation algorithm is assumed to satisfy average sensitivity ϕ(ε) and ε-stability. This extension is presented as the paper's technical contribution and does not reduce any claimed prediction to a fitted parameter, self-definition, or unverified self-citation by construction. The new modeling conditions (average sensitivity and stability) are independent inputs, and the resulting Õ(ϕ^*(OPT_T)) bound follows from the extended reduction rather than from renaming or smuggling an ansatz. The derivation chain remains self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the prior batch-to-online transformation and on the existence of offline algorithms satisfying the stated approximation, sensitivity, and stability properties; no new free parameters or invented entities are introduced.

axioms (2)

domain assumption The batch-to-online transformation of Dong and Yoshida (2023) extends to algorithms possessing average sensitivity bounds controlled by ϕ(ε) and stability with respect to ε.
This is the load-bearing step that converts offline guarantees into online regret bounds.
domain assumption Offline (1+ε)-approximation algorithms with the required average sensitivity exist for the problems considered (k-means, low-rank approximation, submodular minimization).
The paper invokes this existence to obtain concrete regret bounds.

pith-pipeline@v0.9.0 · 5594 in / 1675 out tokens · 79673 ms · 2026-05-16T06:06:19.319539+00:00 · methodology

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)