Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation

Harsh Shah 1 , Purna Chandrasekhar 2 , Rahul Vaze 3 · 2025

Read Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation by Harsh Shah 1 , Purna Chandrasekhar 2 , Rahul Vaze 3 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04133.txt.

Introduction

Harsh Shah, Purna Chandrasekhar, and Rahul Vaze study online choices under tight information in a 2025 paper. At each step, a learner must act before seeing the full cost, and changing actions carries a switching cost. In their frugal setting, the learner gets just one function value and one gradient at the last action, for the current or the previous cost. With a linear switching cost, they derive methods whose performance matches the best possible order. With noisy gradients, their method's ratio grows with the square of the noise size.

Catalog record

CREATORHarsh Shah 1 , Purna Chandrasekhar 2 , Rahul Vaze 3
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04133

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation Harsh Shah 1 , Purna Chandrasekhar 2 , Rahul Vaze 3 Abstract Online convex optimization with switching cost is considered under the frugal information setting where at time t t , before action x t x_{t} is taken, only a single function evaluation and a single gradient is available at the previously chosen action x t − 1 x_{t-1} for either the current cost function f t f_{t} or the most recent cost function f t − 1 f_{t-1} . When the switching cost is linear, online algorithms with optimal order-wise competitive ratios are derived for the frugal setting. When the gradient information is noisy, an online algorithm whose competitive ratio grows quadratically with the noise magnitude is derived. I Introduction Online convex optimization with switching cost (OCO-S) problem was introduced in [ 1 ] , where for each discrete time t , a convex cost function is f_{t}:{\mathbb{R}}^{{\mathsf{d}}}\rightarrow{\mathbb{R}}^{+} . The cost of choosing action x_{t} at time t is the sum of the cost f_{t}(x_{t}) , and the switching cost c(x_{t-1},x_{t}) . The goal is to choose x_{t},1\leq t\leq T that solves \min_{x(t)}\sum_{t=1}^{T}f_{t}(x_{t})+c(x_{t-1},x_{t}). (1) Problem ( 1 ) was motivated by capacity provisioning problem [ 1 ] where demand d(t) at time t is revealed causally over time, and to serve demand d(t) , s(t) number of servers are employed. Changing s(t) over time to dynamically serve d(t) keeps the QoS cost f(d(t),s(t)) small but incurs a large switching cost. I-A Prior Work For the OCO-S ( 1 ) with quadratic switching cost, i.e., c(x_{t},x_{t-1})=||x_{t}-x_{t-1}||^{2} , if the functions f_{t} ’s are just convex, then the competitive ratio of any deterministic online algorithm is unbounded [ 2 ] . Thus, starting with [ 3 ] , to solve ( 1 ), f_{t} ’s were assumed to be strongly convex. With \mu -strongly convex f_{t} ’s, online balanced descent (OBD) algorithm that balances the suboptimality and switching cost at each time, has a competitive ratio of at most 3+\mathcal{O}(\frac{1}{\mu}) [ 4 ] . Surprisingly, [ 5 ] showed that the same guarantee can be obtained by a simple algorithm that chooses x_{t} as the local optimizer of f_{t} disregarding the switching cost. This result was improved in [ 2 ] using a modification of OBD to get a competitive ratio \mathcal{O}(\frac{1}{\sqrt{\mu}}) as {\mu\to 0^{+}} , which is also shown to be the best possible (order-wise) competitive ratio for all possible deterministic online algorithms [ 2 ] . OCO-S with linear switching cost, where c(x_{t},x_{t-1})=|x_{t}-x_{t-1}| has also been widely considered. For this case, when {\mathsf{d}}=1 , an optimal offline algorithm was derived in [ 1 ] , while online algorithms have been explored in [ 1 , 6 , 7 , 8 , 9 , 3 , 10 , 11 ] when f_{t} ’s are just convex. For {\mathsf{d}}=1 , the best known online algorithm has the competitive ratio of 2 which matches the lower bound [ 9 ] . For general {\mathsf{d}} , when f_{t} ’s are convex, the competitive ratio of any algorithm has a lower bound \Omega(\sqrt{{\mathsf{d}}}) [ 3 ] . [ 10 ] proposed a constrained online balanced descent (COBD) algorithm with a competitive ratio \mathcal{O}(\sqrt{\kappa}) where \kappa:=L/\mu as the condition number. Recently, [ 12 ] considered the OCO-S with linear switching cost under some long-term constraints. Almost all the prior work except [ 13 ] considered the OCO-S problem under the full-information setting where the action x_{t} is chosen after function f_{t} is revealed completely. The full information setting is quite imposing for many applications and difficult to realize in practice. In [ 13 ] , when f_{t} ’s are strongly convex, the limited information setting was considered, where at time t , multiple stale gradients \nabla f_{t-1}(x_{1}),\dots,\nabla f_{t-1}(x_{n}) are available, where n is a function of the strong convexity parameter and Lipschitz constant. In this paper, we study the OCO-S problem for {\mathsf{d}}=1 when functions f_{t} ’s are convex under the frugal information setting, where at time t , before action x_{t} is chosen, either \{f_{t}(x_{t-1}),\nabla f_{t}(x_{t-1})\} (called fresh ) or \{f_{t-1}(x_{t-1}),\nabla f_{t-1}(x_{t-1})\} (called stale ) is available. Thus, information available is only a single function evaluation and a single gradient at the previously chosen action x_{t-1} for either f_{t} or f_{t-1} . We also consider the noisy gradient setting. We limit ourselves to the linear switching cost, i.e., c(x_{t},x_{t-1})=|x_{t}-x_{t-1}| . In this paper, we consider the worst-case input and the objective is to design online (that have access to only causal information) algorithms for solving Problem ( 1 ) with small competitive ratios that is defined as follows. The competitive ratio for an online algorithm \mathcal{A} is \mu_{\mathcal{A}}=\max_{\sigma}\frac{C_{\mathcal{A}}(\sigma)}{C_{\mathsf{OPT}}(\sigma)}, where \sigma is the input, C_{\mathcal{A}} is the cost ( 1 ) of an online algorithm \mathcal{A} , while C_{\mathsf{OPT}} denotes the cost of the optimal offline algorithm \mathsf{OPT} , that knows the input \sigma ahead of time, non-causally. I-B Our Contributions with linear switching cost We propose a single online algorithm (A-OBD) for all the frugal settings, where only the input parameter changes depending on the particular setting. • For the fresh setting, we show that the \mu_{\text{A-OBD}}=O(M) , where M is the common smoothness parameter of functions f_{t} ’s. We also show that the competitive ratio of any online algorithm is \Omega(M) . • For the stale setting, we show that the \mu_{\text{A-OBD}}=\Theta(M+L) , where L is the common Lipschitz constant for functions f_{t} ’s. We also show that the competitive ratio of any online algorithm is \Omega(\max\{M,L\}) . • With noisy gradients, we show that in the fresh/stale setting, \mu_{\text{A-OBD}}\leq O(M+L+\alpha^{2}) , where \alpha is maximum noise error defined ahead. II System Model We consider Problem ( 1 ) with {\mathsf{d}}=1 . Typically, x_{t} is chosen to minimize ( 1 ) with the full information about f_{t} which can be expensive to obtain. To obviate this, in this paper, we consider frugal information settings. For example, at time t, either \{f_{t}(x_{t-1}),\nabla f_{t}(x_{t-1})\} or \{f_{t-1}(x_{t-1}),\nabla f_{t-1}(x_{t-1})\} or an approximate estimate of \nabla f_{t-1}(x_{t-1}) is available. Under these frugal information settings, we consider the design of online algorithms that minimize the cost ( 1 ) using only causal information. For the rest of this paper, we consider ( 1 ) with linear switching cost, i.e., c(x_{t},x_{t-1})=|x_{t}-x_{t-1}|, . The precise definition of causal frugal information settings that we consider is as follows (a) fresh gradient setting: At time t, to choose x_{t}, \mathcal{A} can use \left\{f_{i}(x_{i-1}),\nabla f_{i}(x_{i-1})\mid i=1,2,\ldots,t\right\}. (b) stale gradient setting: At time t, to choose x_{t}, \mathcal{A} can use \left\{f_{i-1}(x_{i-1}),\nabla f_{i-1}(x_{i-1})\mid i=2,\ldots,t\right\}. (c) noisy gradient setting: Let \nabla f^{\text{rec}}_{t} be the approximate estimate of \nabla f_{t}(x_{t-1}) with error at most \alpha i.e. |\nabla f^{\text{rec}}_{t}-\nabla f_{t}(x_{t-1})|\leq\alpha. At time t, to choose x_{t}, \mathcal{A} can use \left\{f_{i}(x_{i-1}),\nabla f^{\text{rec}}_{i}\mid i=1,2,\ldots,\tau\right\}. We consider this noisy setting for both fresh ( \tau=t ) and stale ( \tau=t-1 ) scenarios. III Algorithm At time t , let t_{\max} be the latest time t^{\prime}\leq t for which information about f_{t^{\prime}}(x_{t-1}) and \nabla f_{t^{\prime}}(x_{t-1}) is available. Thus, in the fresh setting t_{\max}=t , while for the stale setting t_{\max}=t-1 . Define f^{avl}_{t}:={f}_{t_{\max}}(x_{t-1}) and \nabla^{avl}_{t}:=\nabla{f}_{t_{\max}}(x_{t-1}). In the noisy gradient setting, f^{avl}_{t}

Read the complete text