acceptodds
Under review as a conference paper at ICLR 2027

When Local Geometry Makes Online Learning Easy

Abstract

Convex relaxations make combinatorial online problems tractable, but the relaxed decision space can still have exponentially many vertices. We exploit a finer structure: the space is partitioned into polyhedral cells, where a cell is a region on which every loss is affine and is therefore determined by its values at that region's vertices. Existing global methods ignore these smaller local action sets, while existing cell-based arguments can conflate two different tasks: learning within a known cell and identifying the relevant cell from past observations. We separate these tasks and first study the setting in which the relevant cell and each change of cell are supplied before play. Our key insight is that the best fixed decision within an affine cell is attained at a vertex. Learning during an epoch with an unchanged cell therefore reduces exactly to prediction with a small set of experts. Restarting multiplicative weights at cell changes yields epochwise regret of order over rounds and epochs, where losses are bounded by and each cell has at most vertices. Thus, for fixed loss and geometry parameters, average regret vanishes whenever . In submodular–concave games, each Lov\'asz cell has only chain vertices; combining the reduction with projected ascent gives order .

Primary area:
learning theory
Keywords:
online learning, online convex optimization, regret, polyhedral instability

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_XVgYOpenReview ↗
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 O(METlog⁡Vmax⁡)O(M\sqrt{ET\log V_{\max}}). For submodular--concave games, Lovasz cells have n+1n+1 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 0.447 [0.433,0.464]0.447\,[0.433,0.464] a successful test of 0.5000.500? Is the crossover at 17.717.7 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 n=8n=8.

  • Clarification of model alignment. What convex domain and covering make the supplied faces conv⁡{ei:i∈Aj}\operatorname{conv}\{e_i:i\in A_j\} 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

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 log⁡Vmax⁡\log V_{\max} factor. For Lovász cells, there are only n+1n+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 EE supplied comparator epochs and use ft(S)=Mst(2×1({it∈S})−1)f_t(S)=Ms_t(2\times\mathbf 1(\{i_t\in S\})-1), with it∈[n]i_t\in[n] and st∈{−1,1}s_t\in\{-1,1\}. The n+1n+1 chain vertices correspond to thresholds on [n][n], whose Littlestone dimension is ⌊log⁡2(n+1)⌋\lfloor\log_2(n+1)\rfloor. Applying [Ben-David et al. (2009), Lemma 14] independently across balanced epochs gives expected regret Ω(METlog⁡(n+1))\Omega(M\sqrt{ET\log(n+1)}) when T/E≥log⁡2(n+1)T/E\ge\log_2(n+1). This matches Theorem 4.1's minimizer dependence. Here, EE 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)\alpha\in(0,1) and suppose Algorithm 1's cell query returns the canonical equilibrium label of the previous round's objective: πt=πt−1⋆\pi_t=\pi^\star_{t-1} for t≥2t\ge2. Let Q⋆\mathcal Q^\star partition the rounds into maximal contiguous intervals with a constant canonical equilibrium label. Then, with E=1+SCTE=1+\mathrm{SC}_T, RegTepoch(Q⋆)≤METlog⁡((n+1)/α)+4LyDYET+4ME.\mathrm{Reg}^{\mathrm{epoch}}_T(\mathcal{Q}^\star) \leq M \sqrt{ET \log((n+1)/ \alpha)}+4L_yD_Y \sqrt{ET}+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 2M2M per player. This accounts for both cell errors and epoch boundaries. Since E≤TE\le T, the additional 4ME4ME 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.

  • Acceptance criterion. The reviewer is correct that the interval excludes 0.5, and we appreciate the reviewer for identifying this. While this is consistent with our bound in Theorem 5.6, it does not test the exact exponent. We will update the table in our revision.
  • Crossover at at 17.7. This is extrapolated. We will clarify this in our revision.
  • Bootstrap unit is the seed. Within each configuration we resample its 20 seeds with replacement, keeping paired algorithm runs together. We then recompute each configuration's mean regret and refit the slope. We use 10,000 resamples and report the 2.5–97.5 percentile interval.
  • Nonpositive regrets. Logs are taken only of per-configuration mean regret, so negative runs enter the mean unclipped. If a mean is negative in the data or in a resample, that row is instead fit as Reg = c·x^b on the raw scale and flagged. We will clarify in revision.
  • Rare label experiment at n=8. We consider 100 seeds × 5×10⁶ rounds = 5×10⁸ predictions. We observe 12,502 matches against 12,401 expected. The match rate is 2.50×10⁻⁵.

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{ei:i∈Aje_i : i ∈ A_j} is one of these cells. Under this covering, VmaxV_{max} = N, where VmaxV_{max} 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 RegTepoch(Q⋆)≤METlog⁡((n+1)/α)+4LyDYET+4ME.\mathrm{Reg}^{\mathrm{epoch}}_T(\mathcal{Q}^\star) \leq M \sqrt{ET \log((n+1)/ \alpha)}+4L_yD_Y \sqrt{ET}+4ME. with E=1+SCT.E = 1 + SC_T. The 4ME term covers the one-round delay at each oracle switch. Since E≤TE \leq T, it does not change the rate.

Reviewer_UJr6OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper shows how local geometry can simplify online learning when losses are affine within polyhedral cells. Given the active cell and its changes before play, the learner can run multiplicative weights over local vertices, achieving epochwise regret O(METlog⁡Vmax⁡)O(M\sqrt{ET\log V_{\max}}) across TT rounds and EE epochs. For submodular-concave games, each Lovász cell has only n+1n+1 vertices; combining this reduction with projected ascent adds an O(LyDYET)O(L_yD_Y\sqrt{ET}) term. Crucially, the paper separates learning within supplied cells from identifying equilibrium cells causally: the causal algorithm’s guarantee concerns its own selected cells. Lower bounds establish unavoidable T\sqrt T dependence even without cell switches, while synthetic experiments support the predicted scaling and show that warm-start gains depend on persistent useful weights and restart schedules.

Critical strengths
  1. An exact reduction from local geometry to expert learning. Affinity within a cell ensures that the played loss is a weighted average of vertex losses and that the best fixed comparator is a vertex. This yields O(METlog⁡Vmax⁡)O(M\sqrt{ET\log V_{\max}}) regret through restarted multiplicative weights, without knowing epoch lengths. For Lovász cells, only n+1n+1 vertices are needed. The reduction also extends beyond submodularity and does not require global convexity.
  2. A mathematically substantiated separation between learning and cell identification. The paper provides constructions showing that perfect maximizer tracking can still select the wrong equilibrium cell and that independent equilibrium labels can defeat causal prediction. These results justify treating supplied-cell access as a substantive assumption and explain why regret on causally selected cells does not automatically transfer to the oracle benchmark.
Critical weaknesses
  1. The main guarantee assumes access to the difficult cell-identification information. The active cell and its changes must be supplied before play; equilibrium-based labels therefore reveal information about the unseen objective. The causal alternative only guarantees regret against its own selected cells, without a bound relating that benchmark to the oracle’s. Consequently, the paper leaves unresolved whether its local-complexity advantage can be achieved under ordinary causal feedback.
  2. The lower bounds do not establish optimality in the motivating structural model. The full Ω(Mmin⁡{T,ETlog⁡K})\Omega(M\min\{T,\sqrt{ET\log K}\}) lower bound permits arbitrary expert losses, which need not satisfy global submodularity, affine compatibility, or prescribed equilibrium-cell switches. The actual in-class construction establishes only Ω(MT)\Omega(M\sqrt T) at zero switches. Thus, although explicitly acknowledged, the necessity of the upper bound’s joint switch-count and local-vertex dependence remains unproved.
Questions for authors
  1. Under what stability or margin assumptions could the causal selector obtain a quantitative regret guarantee against the oracle’s cell sequence? Controlling label errors alone would also require accounting for differences in comparator cells and epoch boundaries.
  2. Can the joint dependence on equilibrium-cell switches and log⁡(n+1)\log(n+1) be established through a lower bound using bounded, globally submodular losses? Alternatively, might these structural constraints permit better rates than the unrestricted expert surrogate?
  3. Can an anytime algorithm avoid internal doubling restarts and exploit the comparator-specific initialization KL from Lemma B.2? The experiments suggest that preserving learned weights matters substantially, but the current guarantee uses the worst-case probability floor.
1 comment

We thank the reviewer for detailed feedback.

When does the causal selector achieve regret against the oracle’s cells?

The required condition is that the best-response query identify the previous round’s canonical equilibrium cell. We derive the following result.

Theorem. Suppose Assumption 3.1 holds. Let α∈(0,1)\alpha\in (0,1) and vtv_t be the maximizer state used in its cell query before round tt. Let πt⋆\pi_t^\star be the canonical equilibrium label of ftf_t. Suppose that, along the realized trajectory, πt−1BR(vt)=πt−1⋆for every t=2,…,T.\pi_{t-1}^{\mathrm{BR}}(v_t)=\pi_{t-1}^\star\quad\text{for every }t=2,\ldots,T.

Let Q⋆=((Ij,Pj))j=1E\mathcal{Q}^\star=((I_j,P_j))_{j=1}^{E} partition the rounds into maximal contiguous intervals on which the canonical equilibrium label is constant, with PjP_j denoting the corresponding cell and E=1+SCTE=1+\mathrm{SC}_T. Then Algorithm 1 satisfies RegTepoch(Q⋆)≤METlog⁡((n+1)/α)+4LyDYET+4ME.\mathrm{Reg}^{\mathrm{epoch}}_T(\mathcal{Q}^\star) \leq M \sqrt{ET \log((n+1)/ \alpha)}+4L_yD_Y \sqrt{ET}+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 guarantees apply to the remaining rounds; the first round costs at most 2M2M per player. Thus, the bound accounts for both cell errors and epoch boundaries. Since E≤TE\leq T, the additional 4ME4ME term does not change the regret rate.

We will revise the paper to include this new result.

Can the lower bound include both switches and local vertices?

We establish a lower bound for supplied comparator epochs using globally modular losses, which are also submodular. Specifically, we obtain expected regret Ω(METlog⁡(n+1))\Omega(M\sqrt{ET\log(n+1)}) for EE supplied epochs when T/E≥log⁡2(n+1)T/E\geq\log_2(n+1). This matches Theorem 4.1’s minimizer dependence. Here, a new comparator epoch can begin while the supplied cell remains unchanged, allowing the comparator to choose a different best fixed decision. Thus, EE counts supplied comparator epochs.

To obtain the bound, declare the same cell PidP_{\rm id} in every epoch and use bounded modular losses ft(S)=Mst(21{it∈S}−1)f_t(S)=Ms_t(2\mathbf1\{i_t\in S\}-1), with it∈[n]i_t\in[n], st∈{−1,1}s_t\in\{-1,1\}, and singleton Y\mathcal Y. The n+1n+1 chain vertices correspond to thresholds on [n][n]. Their Littlestone dimension is ⌊log⁡2(n+1)⌋\lfloor\log_2(n+1)\rfloor, so [Ben-David et al. Lemma 14] applied independently across epochs, gives the stated bound.

Whether equilibrium-switch structure permits better rates remains open and is subject to future work.

Can an anytime algorithm preserve the initialization KL without internal restarts?

Yes for the within-epoch minimizer bound. Use entropic follow-the-regularized-leader (FTRL) with prior qq and ηt=A/(M2t)\eta_t=\sqrt{A/(M^2t)}. Its regret to vertex ii is at most MTj(KL(ei∥q)A+A).M\sqrt{T_j}\left(\frac{\mathrm{KL}(e_i\|q)}{\sqrt A}+\sqrt A\right). With A=log⁡((n+1)/α)A=\log((n+1)/\alpha), this retains the comparator’s initialization KL from Lemma B.2 and preserves Theorem 4.5’s minimizer rate. FTRL reweights cumulative losses at the current rate, so the update must also change. The maximizer can retain its existing schedule. We will add this bound to our revision.

[Ben-David et al], Agnostic Online Learning, COLT 2009

Reviewer_UcGVOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This is a method for online mixed linear online optimization, with regret guarantees.

Critical strengths

The paper presents many results with respect to the problem

Critical weaknesses

The work implicitly circumscribes the contribution to mixed integer-linear online optimization, instead of the announced combinatorial online problems. This should be stated in the abstract, and the title should be changed accordingly. There are important scoping problems.

When minimizing over cells the paper changes the comparator. The restricted comparator can be locally worse than the global optimum. So, the regret value of the overall problem is not really studied.

The paper provides results for given known cells. How will the regret guarantees fare for the paper claims of online determined cells?

The writing is difficult to parse for meaning. There is a lot of hollow language and text distractors. There is no example of a good application of this method.

Questions for authors

See weaknesses.

What guarantees that restricting the comparator to the active cell preserves the quality of the global solution?

Without a bound on the gap between the cell restricted and unrestricted comparators, why should the resulting regret guarantees be considered meaningful for the original online combinatorial optimization problem?

2 comments

We thank the reviewer for detailed feedback.

Scope of the problem.

The model considered in this paper is broader than mixed integer-linear online optimization. We consider online learning with losses that are affine within cells of a fixed polyhedral partition. One instance is submodular–concave games whose set cost is submodular and Lovász extension is affine within each cell. The set cost need not be linear. We will revise the paper to make the models explicit.

Restricted comparator can differ from global optimum.

The reviewer is correct that restricting the comparator to a supplied cell can change the result. Theorem 4.1 shows that, once a cell is supplied, we can learn to perform nearly as well as the best fixed decision inside it. If that cell also contains a best decision for the whole epoch, then the guarantee extends to the full problem. Thus, the theorem gives a full-domain guarantee when the supplied cells capture epoch-optimal decisions; otherwise, its guarantee is limited to those cells.

Regret guarantee for online determined cells

Theorem 4.5 guarantees regret against the learner’s selected cells. We derive the guarantee against the oracle’s cells as follows.

Theorem. Suppose Assumption 3.1 holds. Let α∈(0,1)\alpha\in (0,1) and vtv_t be the maximizer state used in its cell query before round tt. Let πt⋆\pi_t^\star be the canonical equilibrium label of ftf_t. Suppose that, along the realized trajectory, πt−1BR(vt)=πt−1⋆for every t=2,…,T.\pi_{t-1}^{\mathrm{BR}}(v_t)=\pi_{t-1}^\star\quad\text{for every }t=2,\ldots,T. Let Q⋆=((Ij,Pj))j=1E\mathcal{Q}^\star=((I_j,P_j))_{j=1}^{E} partition the rounds into maximal contiguous intervals on which the canonical equilibrium label is constant, with PjP_j denoting the corresponding cell and E=1+SCTE=1+\mathrm{SC}_T. Then Algorithm 1 satisfies RegTepoch(Q⋆)≤METlog⁡((n+1)/α)+4LyDYET+4ME.\mathrm{Reg}^{\mathrm{epoch}}_T(\mathcal{Q}^\star) \leq M \sqrt{ET \log((n+1)/ \alpha)}+4L_yD_Y \sqrt{ET}+4ME.

This result shows that Algorithm 1 can learn its cells online and retain the regret rate available when the correct cells are supplied in advance if its best-response queries correctly identify the previous round’s equilibrium cell.

Presentation and application.

We will improve presentation in our revision. Applications of the studied method include:

  • Edge–cloud service placement: Decide which services run on nearby edge servers and which run in the cloud, balancing execution costs against communication costs as workloads change.
  • Video foreground prediction: Predict which regions of the next frame belong to a moving object, balancing visual evidence against the need for neighboring regions to form a consistent object.
  • Sensor-network fault detection: Identify potentially faulty sensors over time, combining each sensor’s measurements with evidence that related sensors may experience the same fault.

We will revise the manuscript to include these applications.

What guarantees that the restriction preserves global solution quality?

The required condition is that each cell contain a best fixed set for that epoch under the realized maximizer actions. In this case, Theorem 4.1 extends to the full problem domain.

Why is the guarantee meaningful without a bound on the gap?

The guarantee is meaningful when the supplied cells define the allowed decisions. For unrestricted combinatorial optimization, it applies when each epoch’s best unrestricted comparator lies in the supplied cell.

Thank you for the detailed response. I acknowledge that the proposed framework is broader than mixed integer-linear optimization and that the additional results clarify the scope of the theoretical guarantees.

However, my main concern about the comparator is still to be solved. The regret guarantees are relative to the best fixed decision within each supplied cell. The response correctly acknowledges that these guarantees extend to the unrestricted domain only when the supplied cell contains an optimal fixed decision for the corresponding epoch.

Importantly, selecting the cell containing the equilibrium of each individual round does not, in general, guarantee that it contains an optimal fixed decision for the entire epoch. Therefore, even perfect identification of the roundwise equilibrium-cell labels does not automatically control the gap between restricted and unrestricted regret.

The new causal theorem is also conditional on correctly identifying the previous round's equilibrium-cell label, potentially requiring an exact minimax computation for each previously observed objective. Its computational implications remain unclear.

I therefore recognize the validity of the conditional learning reduction to a local domain, but I am unconvinced that the paper establishes a relevant online method for the original unrestricted optimization problem. The paper seems to shift the main difficulty from online learning to identifying appropriate cells and controlling the comparator restriction.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.