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
| CREATOR | Harsh Shah 1 , Purna Chandrasekhar 2 , Rahul Vaze 3 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
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}