- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies online learning when the decision domain has polyhedral cells on which every loss is affine. When the active cell and its changes are supplied before play, multiplicative weights over its vertices gives epochwise regret . For submodular--concave games, Lovasz cells have chain vertices; combining this reduction with restarted projected ascent leads to $O( M\sqrt{ET\log(n+1)}+4L_yD_Y\sqrt{ET})$. The benchmark sums both players' external regrets against fixed comparators within each declared epoch. The paper distinguishes a current-equilibrium-cell oracle from a causal selector, whose guarantee concerns its own selected cells. Section 6 reports synthetic experiments with exact epoch comparators, scaling tests, and restart/transfer ablations.
Critical strengths
-
The paper correctly identifies that the cumulative loss within an affine cell is minimized at a vertex and obtains a logarithmic local-vertex factor. The proof is short, transparent, and applies beyond Lovasz simplices.
-
The zero-switch lower bound is interesting, as well as the arbitrary-expert lower bound as a surrogate result. The counterexamples concerning dynamic regret, tie conventions, and maximizer tracking show why cell stability alone is not sufficient. These provide useful guidance for future work on causal cell identification.
Critical weaknesses
-
Limited technical novelty and central causal difficulty remains unresolved: The main rate follows from familiar expert/OCO bounds and a restart-and-sum argument. Theorem 4.5 competes only with the algorithm's own cells and holds for any causal permutation rule: fixing an arbitrary cell forever already gives a one-epoch guarantee against that restricted cell. Thus it does not seem to establish useful global performance or performance against the oracle benchmark. Exact past-objective best-response and lexicographic selection also have no aasociated quantified costs.
-
The empirical evidence does not seem to significantly back up the stronger interpretations: A one-sided bound on signed regret establishes a vanishing positive part, not necessarily convergence of signed average regret to zero. An upper bound also does not predict an exact experimental scaling exponent or an actual crossover between algorithms.
Questions for authors
-
Clarification of experimental claims. What prespecified acceptance criterion makes a successful test of ? Is the crossover at measured or extrapolated? Please specify the bootstrap resampling unit, handling of nonpositive regrets in log fits, and the trial counts and uncertainty for the rare-label experiment at .
-
Clarification of model alignment. What convex domain and covering make the supplied faces an instance of Section 5.2? Alternatively, should those experiments be described as tests of the broader supplied-action-set reduction?
-
Clarification of substantive contribution. Is there an existing result or experiment showing that the proposed causal selector yields a useful external benchmark or a computational advantage after selection costs are included? If so, please identify it.
2 comments
Model alignment.
For domain and covering, take X = Δ_N, with all of its nonempty faces as cells. The faces cover Δ_N, their relative interiors are disjoint, and a linear loss is affine on each face. Each supplied face conv{} is one of these cells. Under this covering, = N, where is the maximum over supplied cells. We agree with the reviewer's alternative. We will describe these experiments as tests of the supplied-action-set reduction.
Substantive contribution.
Our new theorem yields a new external benchmark. It shows that if Algorithm 1's cell query returns the previous round's canonical equilibrium label, then with The 4ME term covers the one-round delay at each oracle switch. Since , it does not change the rate.
We thank the reviewer for detailed feedback.
Technical novelty and the causal guarantee
We study online learning with losses that are affine within cells of a fixed polyhedral partition. The question is how regret depends on the number of vertices in the active cells and the number of epochs over which the comparator is allowed to change. A main instance is submodular–concave games whose minimizer chooses a set and maximizer chooses a continuous action, and the set loss's Lovász extension is affine within each cell. We study both supplied cells and cells selected causally from past objectives.
Affinity within a cell gives an exact reduction to learning over its vertices. Both the learner's loss and the best fixed comparator can be represented using those vertices, giving the logVmax factor. For Lovász cells, there are only n+1 vertices. The regret analysis then uses standard expert and online convex optimization bounds. The paper also establishes when cell information is sufficient and why equilibrium labels can be difficult to identify causally.
We further derive a lower bound using bounded, globally modular losses, which are submodular. Declare the same cell in all E supplied comparator epochs and use ft(S)=Mst(2×1({it∈S})−1), with it∈[n] and st∈{−1,1}. The n+1 chain vertices correspond to thresholds on [n], whose Littlestone dimension is ⌊log2(n+1)⌋. Applying [Ben-David et al. (2009), Lemma 14] independently across balanced epochs gives expected regret Ω(METlog(n+1)) when T/E≥log2(n+1). This matches Theorem 4.1's minimizer dependence. Here, E counts comparator epochs, which can begin without a cell change.
For the causal difficulty, we distinguish learning within a selected cell from competing with the oracle's cells. Theorem 4.5 provides the first guarantee. We derive the latter under a mild assumption below.
Theorem. Under Assumption 3.1, let α∈(0,1) and suppose Algorithm 1's cell query returns the canonical equilibrium label of the previous round's objective: πt=πt−1⋆ for t≥2. Let Q⋆ partition the rounds into maximal contiguous intervals with a constant canonical equilibrium label. Then, with E=1+SCT, RegTepoch(Q⋆)≤METlog((n+1)/α)+4LyDYET+4ME.
Under this condition, the selected cell is correct after the first round of each oracle epoch. At a label change, Algorithm 1 starts a new cell run one round later. The within-cell bounds apply to the remaining rounds, and the first round costs at most 2M per player. This accounts for both cell errors and epoch boundaries. Since E≤T, the additional 4ME term does not change the regret rate.
The condition holds if the query solves the previous round's minimax problem and selects its canonical equilibrium label. This gives a causal way to retain the oracle regret rate using an already revealed objective. We will include this result and clarify Theorem 4.5 in the revision.
What the empirical evidence supports.
The reviewer is correct on signed regret and that how upper bounds predict regrets. We will clarify them in our revision.
Clarification of experiments.