Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets

Dhruv Sarkar; Aprameyo Chakrabartty

Source-linked AI summary

Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets

Dhruv Sarkar, Aprameyo Chakrabartty

arXiv:2608.29074v1Aug 29, 2026cs.AI

TL;DR

The paper addresses online optimization with nested shrinking feasible regions in CONES and COCO, where loss control and geometric movement must be handled together. It combines constrained minimizers, cumulative-loss tests, reset rules, and nested convex-body chasing to obtain nonpositive-prefix or sublinear regret with controlled movement and constraint violation. The resulting horizon dependence is optimal in strongly convex CONES, while stronger growth yields T-independent movement and COCO inherits polynomial dimension dependence.

Problem
Online optimization with evolving nested feasible regions requires controlling both objective performance and movement through shrinking sets.
Method
The algorithms separate loss control through constrained minimizers and cumulative-loss resets from movement control through a deterministic nested convex-body chaser.
Results
The paper obtains optimal Ω(√log T) movement dependence for sublinear-regret strongly convex CONES, T-independent movement under linear growth, and polynomial-dimension COCO guarantees with logarithmic rates for strongly convex losses.
Takeaways & Limitations
Nested-body chasing provides a common geometric mechanism for controlling movement while preserving regret and cumulative constraint-violation guarantees across CONES and COCO.
Takeaways & Limitations
The results use exact constrained optimization, exact Steiner points, and tentative deterministic-chaser evaluation; comparable guarantees under standard oracle access remain open.

Abstract

from arXiv · show

We study online optimization with nested shrinking feasible regions in two settings: convex optimization with nested evolving feasible sets (CONES) and adversarial constrained online convex optimization (COCO). Our algorithms separate loss control from geometric movement: constrained minimizers and cumulative-loss tests preserve regret guarantees, while a deterministic resettable nested convex-body chaser limits movement. For CONES with a $G$-Lipschitz, $μ$-strongly convex objective on a diameter-$D$ domain, we chase intersections of the current feasible set with adaptive objective sublevel sets. Using the Euclidean chasing ratio $O(\sqrt{d\log(1+d)})$, we obtain nonpositive regret at every prefix and movement $O(\sqrt{d\log(1+d)\,GD\log(eT)/μ})$. The bound adapts to the increase in the constrained optimum value. In dimension two, with all other parameters fixed, every randomized algorithm with terminal expected regret $O(T^β)$, $β<1$, suffers $Ω(\sqrt{\log T})$ expected movement on some deterministic nested sequence, proving optimal horizon dependence. Under linear growth away from the constrained minimizer set, Steiner-point tracking yields movement independent of $T$. For general convex COCO, one-step-delayed chasing with regularized-leader resets gives regret $O(G_fD\sqrt{d\log(1+d)T})$ and cumulative constraint violation $O(G_gD\sqrt{d\log(1+d)T})$. For strongly convex losses, both are $O(d\log(1+d)\log(eT))$ when other parameters are fixed. These reductions replace the $O(d^{d/2})$ projection-path factor in prior analyses by the polynomial dimension dependence of Euclidean nested convex-body chasing.

1 Introduction

The paper studies online optimization when feasible regions shrink as nested convex sets, separating objective control from geometric movement. It develops chasing-based guarantees for CONES and COCO, including optimal or logarithmic horizon dependence in key regimes.

Motivation: Nested feasible regions create a geometric movement problem in addition to competing with the best feasible decision.The learner must move through a shrinking sequence of convex sets while controlling movement and loss.
Models: CONES reveals feasible sets before acting, whereas COCO learns the nested constraint sequence with one-round delay.Both models compare against an action feasible for all constraints while controlling cumulative losses and violations.
Method: The framework separates loss control from movement control using constrained minimizers, cumulative-loss tests, reset rules, and nested-body chasing.A chaser proposes feasible points, while budget tests determine whether to retain proposals or reset to an optimizer.
CONES: Strongly convex CONES achieves nonpositive prefix regret with movement O(√(d log(1 + d) GD log(eT)/μ)), using adaptive sublevel-set epochs.Geometrically increasing scales and strong convexity produce the square-root dependence on the constrained optimum increase and O(√log T) horizon dependence.
COCO and stronger growth: Under uniform linear growth, Steiner-point tracking gives movement independent of T, while COCO obtains polynomial dimension dependence and logarithmic strongly convex rates.General convex COCO uses regularized-leader resets; strongly convex COCO has logarithmic regret and cumulative constraint violation, and the displayed dimension factor is polynomial.
CONES: In dimension two, every randomized algorithm with terminal expected regret O(T^β), β < 1, incurs Ω(√log T) expected movement on some deterministic nested sequence.This matches the upper-bound horizon dependence for the stated sublinear terminal-regret regime.

2 Related work

The paper situates its CONES and COCO results among online constrained optimization and nested-body chasing, replacing projection-based geometric factors with polynomial dimension dependence while improving CONES horizon dependence.

COCO extends online convex optimization to adversarial losses and constraints that may be violated short-term but controlled cumulatively.
Projection-based COCO analyses obtain the relevant horizon orders but can incur finite-length constants with superpolynomial dimension dependence.
The paper recovers these COCO horizon orders through nested-body chasing and makes the dimension factor ρd explicit.
The lower bound becomes Ω(√log T), applies to randomized algorithms, and requires only terminal expected-regret guarantees on deterministic sequences fixed independently of random seeds.
Under uniform linear growth, Steiner-point tracking gives T-independent movement, so horizon-growing lower bounds do not apply under that condition.

3 Preliminaries

The preliminaries define the CONES and COCO models, their regularity assumptions, and the resettable deterministic nested-body chaser used as the paper’s geometric primitive.

3.1 The CONES model: CONES uses a known fixed convex objective and gradually revealed nested feasible sets, with regret measured against the final constrained optimum.
3.2 The COCO model: COCO reveals each loss and scalar constraint after the learner acts, with pathwise guarantees under common feasibility.
3.2 The COCO model: General convex COCO assumes a compact diameter-D domain, Gf-Lipschitz convex losses, Gg-Lipschitz convex constraints, and nonempty cumulative feasible sets.
3.2 The COCO model: Strongly convex COCO additionally assumes every loss is μ-strongly convex on the decision set.
3.3 Nested convex-body chasing: Nested-body chasing selects points from successive nested convex sets while minimizing total movement relative to the best offline path.
3.3 Nested convex-body chasing: The algorithms use a resettable deterministic chaser, allowing fresh phases from prescribed reset points and tentative proposal evaluation from retained request histories.
3.3 Nested convex-body chasing: Theorem 3.4 supplies a Euclidean competitive-ratio chaser for arbitrary nonempty compact convex requests, including lower-dimensional sets and singletons.
Access assumptions and computational scope: The results are information-theoretic and assume exact access to constrained minimizers, minimizer sets, Steiner points, and tentative chaser outputs.

4 Endpoint control for nested-body chasing

Singleton augmentation appends a future singleton request to control a chaser’s endpoint without changing earlier online outputs.

A future feasible point b can be appended as a singleton request for endpoint analysis.The augmented sequence remains nested because b belongs to the final request and therefore every earlier request.
The deterministic online chaser’s outputs on the original requests remain unchanged after augmentation.This permits analysis using information unavailable to the online algorithm.
∥y_j − b∥ ≤ ρ_d∥a − b∥ bounds every intermediate output’s distance from the distinguished endpoint.The bound follows by applying competitiveness to each prefix and dropping nonnegative movement terms.

5 Applications to CONES

The CONES algorithms combine adaptive sublevel-set chasing with cumulative-loss resets to control movement and preserve prefix regret under nested feasible sets.

Strongly convex CONES: Adaptive sublevel epochs use scales that more than double, yielding O(√log T) phase and movement control.The procedure starts a new epoch when the constrained optimum increase exceeds twice the current scale.
Strongly convex CONES: Cumulative-loss tests accept chaser proposals only while the budget remains valid; otherwise the algorithm resets to the current constrained minimizer.This separates objective control from geometric movement control.
Strongly convex CONES: The movement bound adapts to the increase in the constrained optimum value across phases.Strong convexity bounds phase movement through the square root of the increase in constrained optimum values.
Strongly convex CONES: Nonpositive prefix regret is achieved for strongly convex CONES on compact convex domains.The guarantee assumes a G-Lipschitz, μ-strongly convex objective and a diameter bound D.
Lower bound and alternatives: An Ω(√log T) lower bound holds in dimension two for randomized algorithms with sublinear terminal regret.The hard deterministic nested sequence forces visits to neighborhoods of logarithmically many alternating constrained minimizers.
Lower bound and alternatives: Steiner-point tracking gives movement independent of T under uniform set-relative sharpness.The algorithm plays the Steiner point of the current constrained minimizer set.

6 One-step-delayed chasing for COCO

COCO reduces delayed loss and constraint control to movement of a post-update feasible sequence, using resettable nested-body chasing with curvature supplied by losses or regularization.

Common reduction: One-step-delayed play converts both regret and current constraint violation into bounds involving post-update movement.The learner plays the previous post-update feasible point because the current constraint is revealed after action selection.
Strongly convex losses: Strongly convex losses yield logarithmic regret and cumulative constraint violation through constrained-leader resets.Cumulative-loss curvature controls displacement between successive reset points.
General convex losses: The general convex bounds have no additional log T factor.The explicit dimension dependence comes from substituting the Euclidean nested-body chaser.
General convex losses: Regularized-leader resets provide square-root regret and cumulative constraint violation for general convex losses.A fixed quadratic regularizer supplies curvature absent from merely convex losses.
Scope: The bounds require exact constrained optimization, exact Steiner points, and tentative evaluation of a deterministic chaser.These information-theoretic requirements delimit the current results’ computational and oracle scope.

7 Conclusion

The paper presents a movement-based framework for nested feasible regions, establishes CONES and COCO guarantees, and identifies unresolved oracle, joint-dependence, and dimension-gap questions.

The framework separates loss control from geometric movement control across CONES and COCO.CONES uses adaptive sublevel-set chasing, while COCO uses one-step-delayed feasible sequences and reset rules.
CONES achieves nonpositive prefix regret, an Ω(√log T) lower bound under sublinear terminal regret, and T-independent movement under uniform linear growth.The lower bound applies in dimension two with fixed geometric and objective parameters.
COCO obtains square-root guarantees for general convex losses and logarithmic guarantees for strongly convex losses, with polynomial dimension dependence.Euclidean nested-chasing replaces the prior superpolynomial projection-path factor in the stated comparison.
Open limitations: The results assume exact constrained optimization, exact Steiner points, and tentative deterministic-chaser evaluation.Comparable guarantees under standard projection, separation, or first-order oracle access remain undeveloped.
Open limitations: The optimal joint dependence on dimension, regret, and cumulative constraint violation remains open, as does the dimension-dependent gap in strongly convex CONES.These are identified as unresolved questions rather than failures of the presented guarantees.

A.3 Version 2 and comparison with the present results

The paper contrasts its upper and lower bounds with Version 2, while extending the nested-body chaser to arbitrary compact convex requests. Its strongly convex CONES analysis uses adaptive sublevel-set epochs to control loss and movement.

Version 2: K = Θ(log T / log log T) balances phase growth in the repaired strongly convex construction.The construction chooses parameters so B2/(4δ) is independent of K.
Comparison with Version 2: O(√(d log(1 + d))) replaces the prior projection-path dimension factor in the upper bound and removes smoothness.The comparison identifies polynomial Euclidean chasing dependence as the key improvement.
Comparison with Version 2: Ω(√log T) is the improved lower-bound rate, applying to randomized algorithms under only a terminal expected-regret guarantee.The adversarial sequence is deterministic after fixing the algorithm and independent of its realized random seed.
Chaser extension: The lower-dimensional chaser is obtained by enlarging requests, taking cluster points, and selecting lexicographically to preserve prefix consistency.Compactness places limiting outputs in the original requests, while the extension remains resettable and deterministic.
Strongly convex CONES construction: Adaptive sublevel-set epochs feed nested intersections to a resettable chaser, with scales more than doubling when constrained-optimum values increase.Strong convexity supplies movement and loss bounds within each epoch; summing epoch bounds proves the overall movement bound.

C.2 Proof of the strongly convex CONES upper bound

The strongly convex CONES proof combines cumulative-loss acceptance tests with resettable chasing. The invariant yields nonpositive prefix regret, while phase and epoch arguments bound movement by the chasing ratio and increases in constrained optima.

Loss control: RegCONES_T ≤ 0, and the same argument gives nonpositive regret at every prefix.The cumulative-loss invariant is maintained whether tentative proposals are accepted or rejected.
Phase structure: At most 1 + log2 T completed phases occur because reset times more than double.A rejected proposal and the phase loss inequalities imply each reset time exceeds twice the preceding phase start.
Movement bound: (1 + log2 T)(vT − v1) bounds the summed phase contribution to movement before the initial-point adjustment.The constrained-optimum increments telescope across completed and final phases.
Randomization reduction: The mean-policy reduction preserves feasibility and does not increase expected loss or movement on any fixed deterministic nested sequence.Convexity of feasible sets and Jensen’s inequality establish the deterministic feasible policy and both inequalities.

C.4 Proof of the terminal-regret lower bound

The terminal-regret lower bound constructs a deterministic sequence of nested halfspace-constrained sets that forces a policy with sublinear terminal regret to reach successive minimizer neighborhoods. The resulting trajectory yields the movement lower bound, including for randomized algorithms through mean-policy derandomization.

Derandomization: A deterministic sequence can be constructed from the randomized algorithm’s distributional rule, not its realized random seed.Mean-policy derandomization reduces the randomized guarantee to a deterministic feasible policy with no larger movement.
Geometric construction: The construction uses unique constrained minimizers with a fixed excess-loss gap outside ε-neighborhoods.This gap converts failure to enter a target neighborhood into a quantifiable regret penalty.
Horizon control: All K target neighborhoods are reached within the horizon, after which the adversary keeps the final feasible set fixed.The phase deadlines leave room for subsequent phases and the final filler rounds.
Phase forcing: Every phase target must be reached by its deadline, or freezing the feasible set creates terminal regret exceeding the assumed guarantee.The contradiction combines earlier-phase benchmark credit with the phase’s excess loss.
Movement lower bound: The ordered entries into successive minimizer neighborhoods produce disjoint trajectory segments whose total length proves the deterministic and randomized movement lower bounds.Consecutive minimizers and the entry times connect phase progress to movement.

D.1 Proof of the convex COCO theorem

The convex COCO proof regularizes cumulative losses, uses resettable nested-body chasing between rejected proposals, and controls both movement and constraint violation. Strong convexity of the regularized leaders supplies the reset-displacement bound even when individual losses are only convex.

Budget invariant: Bt := vt − At ≥ 0 is the regularized budget invariant maintained by Algorithm 4.The invariant follows from the constrained minimizer inequality and the acceptance or rejection update.
Movement control: ρd bounds the chaser movement contribution for each completed phase through the reset displacement δk.Singleton augmentation converts each phase’s offline comparison path into a ρd-scaled movement bound.
Regularization: Ht is λ-strongly convex on X, even though the losses fs are only convex.The quadratic regularizer transfers strong convexity to the cumulative objective used for constrained minimization.
Final phase: The unfinished final phase contributes at most ρdD because a common feasible point provides an offline path of cost at most D.Combining completed-phase and final-phase estimates yields the overall movement bound.
Constraint violation: [gt(zt−1)]+ ≤ Gg ∥zt − zt−1∥ converts movement into cumulative constraint violation.Summing this one-step bound gives the violation estimate used in the theorem.
Dimension dependence: ρd = O(√(d log(1 + d))) supplies the polynomial dimension dependence in the resulting COCO bounds.The theorem substitutes the Euclidean nested-body chasing ratio into the regret and violation estimates.

D.5 Reset inequality and movement bound

The section establishes a reset inequality for completed phases and uses it to control the chaser’s cumulative movement. Reset displacements are bounded through phase-wise loss comparisons and logarithmic growth across reset times.

Reset inequality: The reset displacement is defined as δ_k = ||a_{k+1} − a_k||, where a_k is the chaser state at reset time r_k.The reset states satisfy a_k := z_{r_k} = u_{r_k}, with r_0 = 1.
Reset inequality: Lemma D.6 gives a reset inequality for every completed phase, relating the phase displacement to the phase endpoint quantities.The proof compares the rejected tentative proposal with accepted chaser outputs and uses the reset-point relation B_r = v_r − A_r.
Reset inequality: For nonzero displacements, dividing the reset inequality yields a multiplicative growth factor involving 1 + μδ_k/(2G_fρ_d).Zero displacement contributes nothing, while the case G_f = 0 is handled separately because strong convexity then forces the domain to be a singleton.
Movement bound: Since each displacement is at most D, logarithmic lower bounds convert the product over completed phases into a bound involving the number of rounds and the reset displacements.The argument uses δ_k ≤ D and log(1 + x) ≥ x/(1 + M) for 0 ≤ x ≤ M.
Movement bound: The total movement is bounded phase by phase using the Euclidean chaser ratio, with the unfinished final phase contributing at most ρ_dD.Completed-phase movement, including reset jumps, is bounded by ρ_dδ_k; the initial movement is at most D.
Movement bound: The resulting theorem follows by summing completed-phase movement bounds and accounting for the initial and final-phase contributions.The proof explicitly includes reset jumps and appends a point in the final feasible set to close the unfinished phase.