Optimal Competitive Ratios for Chasing Convex Functions with Quadratic Growth

Linzhe He; Sifan Yang; Wei Jiang; Lijun Zhang

cs.LGNov 5, 2026

Optimal Competitive Ratios for Chasing Convex Functions with Quadratic Growth

Authors: Linzhe He, Sifan Yang, Wei Jiang, Lijun Zhang

Organizations: State Key Laboratory of Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · School of Computer Science and Engineering, Nanjing University of Science and Technology

Abstract

Chasing convex function has attracted much attention in recent years, which can be formulated as a game between a learner and an adversary. In each round, the adversary reveals a convex function, and the learner selects a decision and incurs a hitting cost and a movement cost for changing its decision. The performance of the learner is measured by the competitive ratio, which compares its cumulative cost with that of an optimal offline decision sequence. For Euclidean movement, existing upper and lower bounds for $κ$ -well-conditioned functions exhibit a polynomial gap. For squared Euclidean movement, dimension-free competitive guarantees have been established under quadratic growth, but the optimal competitive ratio remains unclear. In this paper, we establish optimal dimension-free competitive ratios for convex function chasing under two types of movement costs. For Euclidean movement, we propose Clipped Proximal Descent (CPD), which combines a balanced proximal step with a clipped correction toward the current minimizer. CPD achieves an $O(κ^{1/3})$ competitive ratio for smooth convex functions satisfying quadratic growth, improving the previous $O(\sqrtκ)$ upper bound and matching the existing $Ω(κ^{1/3})$ lower bound. For squared Euclidean movement, we establish the exact optimal dimension-free competitive ratio for convex functions satisfying quadratic growth. Our result is based on a new tight competitive analysis of Regularized Online Balanced Descent (R-OBD) and a matching lower bound against randomized algorithms.

Figures & tables

Figure 1: A balanced round of Algorithm 1 with

\mathcal{X}=\mathbb{R}^{d}

. The proximal step moves

\mathbf{x}_{t-1}

\mathbf{y}_{t}

, and the clipped correction moves

\mathbf{y}_{t}

toward

\mathbf{v}_{t}

Competitive Analysis

Competitive analysis compares online decisions with an offline optimum to measure performance under worst-case inputs and imperfect information.

See all 19 papers

Oct 17, 2026

Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds

We revisit smoothed online learning and develop algorithms with improved competitive ratios, optimal dynamic regret with switching cost, and best-of-both-worlds guarantees. Surprisingly, minimizing the hitting cost alone is

\max(1,\frac{2}α)

-competitive for

α

-polyhedral functions under the

\ell_2

-norm switching cost and

1+\frac{4}λ

-competitive for

λ

-quadratic growth functions under the squared

\ell_2

-norm switching cost, significantly improving existing guarantees. The polyhedral bound is tight for this naive algorithm, and we establish a matching lower bound for

α\geq1

. For convex

λ

-quadratic growth hitting costs, minimizing a suitably weighted sum of hitting and squared

\ell_2

-norm switching costs yields a competitive ratio of

1+\frac{2}{\sqrtλ}

. For dynamic regret with the

\ell_2

-norm switching cost, we develop Smoothed Ader (SAder), which achieves the optimal

O(\sqrt{T(1+P_T)})

rate in the standard online convex optimization setting, where

P_T

is the comparator's path-length. Its lookahead version removes the bounded-gradient assumption, and a matching lower bound establishes optimality in this setting. Finally, for convex hitting costs on a bounded convex domain, we develop UDNP to aggregate any two experts in the lookahead setting under both switching costs. Its additional cumulative cost is at most

O(1)

relative to the first expert and

O(\sqrt{T\log T})

relative to the second, yielding best-of-both-worlds guarantees without bounded gradients.

Lijun Zhang, Linzhe He, Wei Jiang +1

State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China · School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China +1

Competitive Analysis Online Convex Optimization Dynamic Regret Minimization

Ask PDF

Aug 29, 2026

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

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.

Dhruv Sarkar, Aprameyo Chakrabartty

Massachusetts Institute of Technology, Cambridge, MA · Purdue University, West Lafayette, IN

Online Convex Optimization

Ask PDF

May 8, 2026

Convex Optimization with Nested Evolving Feasible Sets

Convex Optimization with Nested Evolving Feasible Sets (CONES)} is considered where the objective function

f

remains fixed but the feasible region evolves over time as a nested sequence

S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T

. The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known nested convex body chasing problem. When the loss function is convex, we propose a lazy-algorithm and show that it achieves

O(T^{1-β}), O(T^β)

simultaneous regret and movement cost for any

β\in (0,1]

, over a time horizon of

T

. When the loss function is strongly convex or

α

-sharp, we propose an algorithm Frugal that simultaneously achieves zero regret and a movement cost of

O(\log T)

. To complement this, we show that any online algorithm with

o(T)

regret has a movement cost of

Ω(\log{T})

for both cases, proving optimality of Frugal.

Karthick Krishna M., Haricharan Balasundaram, Rahul Vaze

Online Convex Optimization Constrained Optimization

Ask PDF

Abstract

Competitive Analysis

Explore similar work

Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds

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

Convex Optimization with Nested Evolving Feasible Sets