{'fraction_non_alphanumeric': 0.04417448923246825, 'fraction_numerical': 0.01413583655438984, 'mean_word_length': 4.217207605146918, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Online Convex Optimization with Binary Constraints

We consider online optimization with binary decision variables and convex loss functions. We design a new algorithm, binary online gradient descent (bOGD) and bound its expected dynamic regret. We provide a regret bound that holds for any time horizon and a specialized bound for finite time horizons. First, we present the regret as the sum of the relaxed, continuous round optimum tracking error and the rounding error of our update in which the former asymptomatically decreases with time under certain conditions. Then, we derive a finite-time bound that is sublinear in time and linear in the cumulative variation of the relaxed, continuous round optima. We apply bOGD to demand response with thermostatically controlled loads, in which binary constraints model discrete on/off settings. We also model uncertainty and varying load availability, which depend on temperature deadbands, lockout of cooling units and manual overrides. We test the performance of bOGD in several simulations based on demand response. The simulations corroborate that the use of randomization in bOGD does not significantly degrade performance while making the problem more tractable.

In this work, we formulate an algorithm for online convex optimization with binary constraints, which we refer to as the binary online gradient descent (bOGD). The challenge is to design an algorithm: (i) in line with OCO's simple and computationally efficient updates so that binary decisions can be provided in real-time, and (ii) which has theoretically guaranteed performance. The guarantee we are after takes the form of a sublinear regret in the problem's time horizon. We use bOGD for setpoint tracking with TCLs with discrete on/off settings and lockout constraints, as well as the standard deadband temperature constraint. The lockout constraint ensures that, after being turned off, a 5-minute period must pass before a cooling unit can be turned on again. Lockout is a significant physical limitation of TCLs for fast demand response applications, and is rarely accounted for in the literature.
Several decision-making and resource allocation problems have binary constraints, e.g., scheduling [10] or turning off or on a residential load's cooling unit for demand response [5], [6]. In this work, we focus on functions which, without the binary constraint, are convex over the set [0, 1] n , n ∈ N. In our work, we show that bOGD, an OCO algorithm with an additional randomization step, provides sequential binary decisions with a provable finite-time performance guarantee [11]. We show that, for a finite time horizon, bOGD has an expected dynamic regret bound that is sublinear in the number of rounds and linear in the cumulative variation between relaxed, continuous round optima. If the cumulative variation is sublinear, then the average expected regret decreases as the time horizon increases. Therefore, for a finite time horizon, the expected decisions provided by bOGD, on average, approach the optimal ones because the average error approaches zero.
Related work: bOGD is based on OCO [1], [2]. In online optimization, the closest work to ours is [12]. In this work, the authors consider binary decision variables for submodular loss functions and provide a static regret analysis. Several extensions of this work have been proposed, e.g., [13], [14]. Similarly to convexity in continuous optimization, in discrete/combinatorial optimization, submodularity usually implies that a problem can be solved efficiently [15]. Submodular minimization problems can be solved efficiently using either combinatorial algorithms [16] or convex optimization algorithms via the Lovász extension, a continuous and convex extension of the submodular function [15], [17]. In [12]. We also provide a different performance guarantee than [12] by showing that bOGD has a bounded finite-time dynamic regret bound. Randomized expert and bandit-based algorithms have also been developed for online problems with binary decision variables [12], [18]. In the general case, these algorithms are computationally inefficient due to the large number of possible experts or decisions, i.e., 2 n possible options must be considered, where n ∈ N is the number of experts or decisions [12]. Several efficient algorithms for binary decisions have been proposed in online linear optimization [19] (and the references therein) under restrictive assumptions, e.g., a constant total number of 1-decisions being selected and linear loss functions.
Binary constraints were considered in the context of timevarying optimization of power systems in [20]- [22]. In [20], a similar randomization step is used to accommodate loads with discrete settings. The performance of the randomization step is, however, only characterized through an asymptotic bound on the dual variables of the problem. Reference [21] also models discrete decisions and lockout using the approach of [22]. In [22], the authors extend the error diffusion algorithm. In each round, the decision is given by the projection onto the discrete set of the cumulative difference between the continuous (relaxed) and the discrete decisions. An example of demand response with heaters that includes binary decisions and lockout constraints is provided. The performance analysis of [21] and [22] ensures that the cumulative difference between the continuous and discrete decisions is bounded, but it does not characterize the difference between the round optimum and the discrete decision made in each round.
Our specific contributions are: • We handle binary constraints in OCO using a randomization step. To the best of our knowledge, binary decision variables have not previously been integrated into OCO. • We obtain expected dynamic regret bounds for the resulting algorithm, bOGD. We show that the regret is bounded from above by the sum of the relaxed optimum tracking error, which vanishes in time when standard assumptions are satisfied, and the rounding error. For finite time horizons, we provide a bound that is sublinear in time and linear in the cumulative variation of relaxed round optima. • We use bOGD for demand response of TCLs with binary on/off settings. We also account for the unavailability of loads for demand response caused by temperature deadbands, lockout constraints, and manual override.

II. OCO WITH BINARY CONSTRAINTS
We consider an OCO setting in which a decision maker sequentially minimizes a loss function with binary decisions. The loss function is specific to the current time instance or round. We denote the round by t and the time horizon by τ . Letx t ∈ {0, 1} n and x t ∈ [0, 1] n be, respectively, the discrete decision and the relaxed, continuous decision variables at round t. Let f t : [0, 1] n → R, n ∈ N, be the differentiable loss function at round t for t = 1, 2, . . . , τ . We assume that f t is convex and bounded over [0, 1] n . The convexity of f t and compactness of the relaxed domain imply that f t is Lipschitz continuous with respect to a norm · [23] for all x ∈ [0, 1] n and t = 1, 2, . . . , τ . Let L 1 , L 2 ∈ (0, +∞) be the Lipschitz continuity moduli with respect to the 1 -and 2norm, respectively. Thus, ∇f t (x) 1 ≤ L 1 and ∇f t (x) 2 ≤ L 2 for all t and x ∈ [0, 1] n and all t.
The binary-constrained OCO problem is as follows. In each round t, the decision maker must solve: where f t is only known after round t. The performance of OCO algorithms are evaluated in terms of the regret [1], [2], [24]. In this work, we use the dynamic regret [11], [24], [25], which represents the cumulative loss difference between the actual decision,x t , and the round optimum computed in hindsight, b t ∈ arg min x∈{0,1} n f t (x). In this case, the dynamic regret takes the following form: wherex t is the decision at t. Because we use an additional randomization step to deal with the binary nature of the decision variable, we bound the expectation of the dynamic regret. We seek an algorithm with a sublinear bound [1], [2], which implies that E [R τ ] /τ , the time-averaged regret, diminishes as the time horizon increases, and thus so does the average decision error. Finally, it is common to bound the dynamic regret as a function of the cumulative variation in the relaxed round optima, V τ [24], [25]. This term characterizes how much the sequence of relaxed optima changes through time.
We use the bOGD update to solve (1), given by with x 1 ∈ [0, 1] n andx 1 = R (x 1 ), and where λ ≥ 0 controls the optional 1 -regularizer, η > 0 is the descent step size to be set shortly, and R : [0, 1] n → {0, 1} n is a randomization function. The function R returns a vector made only of zeros or ones where each entry i is sampled from a Bernoulli random variable with probability p = x t (i). We note that bOGD is the first regret-bounded algorithm for OCO with binary constraints. It works as follows. In (2), the auxiliary, Algorithm 1 Binary online gradient descent (bOGD) Parameters: T , a, λ, and τ .

3:
Observe the loss function f t (x t ).

5: end for
continuous variable x t is updated using dynamic mirror descent with an 1 -regularizer and the 2 -norm-based Bregman divergence [25]. In (3), the randomization function converts the auxiliary variable to the binary decision vectorx t+1 . The bOGD update combines (2) and (3) to first perform a projection gradient descent step on the relaxed, continuous problem at time t, and then to obtain a binary decision using randomization. A full description of bOGD is presented in Algorithm 1.

III. REGRET ANALYSIS
We now present two intermediate results that will be used to derive bOGD's dynamic regret bounds. We first re-express the expected regret of bOGD in terms of a tracking and a rounding component.
Lemma 1: The expected regret of bOGD is bounded from above by where . The proof of this lemma is in Appendix A. Lemma 1 shows that the expected bOGD regret is upper bounded by the sum of the relaxed, continuous problem regret (first right-hand side term of (4)) and the cumulative rounding error due to the randomization step (second right-hand side term of (4)). We now bound the expected rounding error, i.e., the expected difference between the loss associated with the randomized binary and relaxed decisions.
Lemma 2: Let the binary decision variablex t be computed using bOGD. Then The proof of Lemma 2 is provided in Appendix B. Next, we present our regret bounds for bOGD. We provide a general bound in Theorem 1 and then give a sublinear, finite-time regret bound in Corollary 1.
Theorem 1 (Regret bound for bOGD): Let η = a √ τ , a > 0. The expected regret of bOGD is upper bounded by for any time horizon τ . The proof of Theorem 1 is provided in Appendix C. The regret bound of bOGD is based on Lemmas 1 and 2. Using Theorem 1, we can bound the expected regret with the sum of the rounding error and the error due to tracking relaxed optima. The tracking error is equivalent to the error made by the dynamic mirror descent [25]. The relaxed optimum tracking regret is sublinear if V τ < O( √ τ ). Lemma 2 quantifies the rounding error in each round. It grows linearly in τ because rounding error will inevitably occur in almost all rounds.
Using Lemmas 1 and 2, we can provide a sublinear regret bound for bOGD when it is used over the constrained time horizon T ≤ τ . The constrained time horizon T is based on the Lipschitz continuity modulus with respect to the 1-norm and the step size scaling factor, a. It can therefore be computed before implementation.
Lemma 3: Suppose T ≤ (aL 1 ) 2 and a > 0, and set η = a √ T . The expected regret of bOGD is upper bounded by The proof of Lemma 3 is presented in Appendix D. Lemma 3 means that if V T is sublinear, the expected worstcase performance bound of the decision maker will improve over time for t ≤ T . We use Lemma 3 to obtain the following regret bound for any finite time horizon, τ < ∞. This is similar to the regret analysis of [11].
Corollary 1 (Finite-time regret bound for bOGD): Let T ≤ (aL 1 ) 2 and a > 0. Using bOGD with η = a √ T , the expected cumulative regret over the finite time horizon, τ < ∞, is bounded from above by: Proof: Suppose that the algorithm is restarted after T ≤ (aL) 2 rounds. Let m ∈ N be the number of times the algorithm has been restarted. Let N = τ /T be the number of times the algorithm is required to be restarted throughout the time horizon τ . We assume that N ∈ N, be the cumulative regret from round t 0 to t 1 . By Lemma 3, we have, By definition, τ = N T , thus there exists 0 < < 1 given by = which completes the proof. Corollary 1 shows that for any finite time horizon and V τ < O (τ ), the regret is sublinear and the time-averaged regret (E [R τ ] /τ ) decreases as the time horizon increases. Due to our finite time analysis, we can accommodate V τ that is almost linear in T . We expect that similar results would hold for standard OCO algorithms [24], [25] if they were to be analyzed similarly.
Corollary 1's bound is looser than prevalent dynamic OCO algorithms [24]- [26] because of the τ term. If, for example, τ = 10 4 and T = 100, the regret is bounded by O τ 3/4 + O (V τ ). This increased regret bound order is explained in part by the randomization step used to deal with the binary constraints. The randomization adds an extra term to the regret of standard continuous-variable online gradient descent-based algorithms, as shown in Lemma 1. This term increases the order of the regret bound when moving from a constrained time horizon to any finite time horizon.

IV. APPLICATION TO DEMAND RESPONSE
We use bOGD for setpoint tracking with thermostatically controlled loads. Our formulation includes three types of constraints on the TCLs: (i) temperature preference constraints, (ii) manual override by the load user and (iii) lockout. The lockout imposes a M -minute downtime period when an air conditioner is off regardless of other constraints. Lockout is standard on most commercial air conditioning units and prevents their compressor from being turned off and on repeatedly [27]. Otherwise, operating the unit in such fashion can degrade the unit's efficiency and life span due to compressor failure [27], [28], and for these reasons, it is avoided. These constraints are modeled with round-dependent parameters of the loss function which we introduce next. Their only impact to the regret bound of bOGD is with respect to the Lipschitz constants L 1 and L 2 of the loss function, and cumulative variation V T of the OCO problem. We present next the setpoint tracking setup and then evaluate its performance in numerical simulations.

A. Setup
We consider n TCLs. The load parameters are: where θ(i) and θ(i) are respectively the maximum and minimum temperature of load i's temperature deadband. The load parameters are assumed to be known. The following online parameters are observed at the end of each round: • s t ∈ R, the power setpoint to track; •p t ∈ R n + , wherep t (i) is the power consumption at time t of load i's cooling unit when it is not available Implement binary decisionsx t = R (x t ).

3:
Observe all online parameters: p t ,p t u t , θ t , s t , θ ambient t .

5:
Update the relaxed decision variable x t+1 : x t+1 = arg min 6: end for for demand response because it is constrained by its temperature, lockout, or manual override. • p t ∈ R n + , where p t (i) represents the power consumption of load i and time t when it is controllable, i.e., when it is not constrained by the deadband, lockout, or manual override. • θ t ∈ R n , where θ t (i) is the indoor temperature at time t of load i. Let θ t ∈ R n be the vector of temperatures averaged over rounds 1 to t; • θ ambient t ∈ R is the ambient (outdoor) temperature. The ambient temperature is the same for all loads. This assumption simplifies the computation but can be relaxed; • u t ∈ {0, 1} n is the cooling unit override at time t of load i. When u t (i) = 1, the local cooling unit overrides the demand response control because the temperature is above the deadband. It also represents rounds when the user manually controls the cooling unit, which we model as uncertain. We note that the online parameters represent observations or measurements.
Lastly, letx t (i) = 1 andx t (i) = 0 be, respectively, the signal to turn on and off load i's cooling unit.
The model and update rule are given in Algorithm 2. We use (6) from [4] as the loss function. In (6), ρ > 0 and λ > 0 are numerical parameters. There are three terms, as explained below.
1) Setpoint tracking losses. This term is used to match the total power consumption of the loads to the regulation signal, s t . The power consumption of the TCLs is split into two components: the controllable part dispatched by the algorithm, p txt , and the uncontrollable part,p t u t , set by the loads to meet their constraints. The squared tracking error penalizes large deviations. 2) Sparsity regularizer. This 1-norm term is used to avoid sending nonzero control signals to loads that are not available at a given round, e.g., if their temperature is out of the deadband or during lockout. The availability of a load i is expressed by p t (i) = 0. It is also used to minimize the number of loads dispatched and to avoid sending small signals to the loads. The sparsity regularizer is directly incorporated to the update instead of being taken into account via the gradient. This is done to improve the regularization performance [29]. 3) Mean temperature regularizer. This 2-norm term minimizes the long-term impact of demand response on the loads by promoting a small difference between the average and desired temperatures. While the temperatures used in Algorithm 2 are based on measurements, we use the following discrete-time approximation to model the impact of turning on the cooling units on the temperature [5], [30]: where 1 is the n-dimensional vector of ones, B = diag exp − h r(i)c(i) , for i = 1, 2, . . . , n , and h > 0 is the round duration. The temperature deadband, the lockout constraints, and the manual override are incorporated into the model via p t . The loads measure their power consumption according to their availability and set p t locally, which is then observed by the algorithm. A load is available if its temperature is within the deadband, not in lockout, and not manually controlled by the user. The logical rules governing p t (i) are summarized below: The cooling unit is activated using override control, i.e., u t (i) = 1 andp t (i) = 0. • (manual override) If the load manually uses its cooling unit regardless of deadband constraints and demand response instructions, u t (i) = 1, p t (i) = 0, andp t (i) = 0.
and p k (i)x k (i) +p k (i)u k (i) = 0 for any k ∈ {t − 1, t − 2, . . . , t − K} where K is the number of rounds representing a duration of M minutes, then p t (i) = 0 and u t (i) = 0. In other words, if the cooling unit was shut down in the past M minutes, then it is unavailable for control. • (available load) Otherwise, load i is available and p t (i) = 0 and u t (i) = 0. Load i only implements the demand response controls if it is available. Therefore, it only has its air conditioner turned on by the aggregator if p t (i) = 0. We assume that the parsing is done locally by the load's back-up controller. If p t (i) = 0, the demand response control is ignored by the load, but it can be turned on by the override control, e.g., to keep the temperature within the deadband. Note that when in lockout, we have p t (i) = 0 and u(i) = 0, and the air conditioner is always off.
Lastly, a switching cost could be added to (6) to penalize frequent changes in controls. By reducing these changes, the load should be less frequently in lockout, and the aggregator would benefit from increased load availability. This is a topic for future work.

B. Numerical example
We consider an aggregation of n = 1000 TCLs. We assume that the loads have access to two-way communication infrastructure. They can receive cooling instructions and can report their power consumption and temperature to and from the demand response aggregator. For example, the different sensors, thermostat and cooling unit's controller, can all be connected using different local communication protocols, e.g. Wi-Fi or ZigBee [31], to a hub which is itself internet enabled. Information to and from the demand response aggregator can then be communicated via the Internet.
All load parameters are sampled uniformly from [30, Table  I]. We consider a round duration of h = 1 minute and set the lockout time M to be 5 minutes. Let s t = s 0 + w t be the random and intermittent regulation signals where w t is constant for 5 rounds and then sampled according to w t ∼ N(0, 300). We set s 0 = 2400 kW so that loads can balance maintaining their temperature within their deadband and tracking the setpoints. The initial decision x 1 (i) is set randomly to 0 or 1 with a probability of 0.5 for all i = 1, 2, . . . , n.
The ambient temperature for the short time horizon is θ ambient t = θ ambient 0 +0.25 sin (tπ/T ) where θ ambient 0 = 34 • C. We let the initial temperature of the TCLs be their desired ones, θ d . The load temperature evolves as (7) plus zero-mean Gaussian noise with variance 0.025. The regularizer parameters are set to σ = 500 and λ = 250, and the step size parameter to a = 4 × 10 −4 . For the numerical calculations, we use the parser CVXPY [32] with the solver Gurobi [33]. Figure 1 shows the power consumption of bOGD; of bOGD without randomization; and of the optimal dispatch, all of which include the uncontrollable part of the TCLs power consumption; the setpoint; and the uncontrollable power consumption presented individually. The uncontrollable power consumption,p t u t , represents all decisions taken locally by the loads to ensure that their temperatures stay within the deadband. The relative difference between the power consumption using randomized decisions and the relaxed, continuous decisions is, on average, 1.30%. The average relative tracking error of the randomized and relaxed decisions are 6.51% and 6.46%, respectively. We note the higher tracking error at the start of the simulation. This is due to the limited number of temperature measurements used by the mean-temperature regularizer in the first rounds. We present the setpoint tracking root mean square error (RMSE) for bOGD and its counterpart without randomization (relaxed decisions) in Table I. The  second column of Table I also shows the relative RMSE with respect to the average of the signal, s t = 2412.09 kW. The RMSE corroborates the small difference in performance between bOGD with and without randomization (relaxed) when used in demand response. The method requires, on average,  loads. This illustrates the algorithm's high scalability and the potential for real-time implementation. Figure 2 shows two temperature profiles observed during the simulation. In Figure 2a, the TCL is dispatched on several occasions, including once over several rounds. Near the end of the simulation, the TCL is constrained to the upper limit of its deadband. Because of the randomization step, a load may become stuck at a high temperature, thus preventing it from providing sustained flexibility throughout the time horizon. Figure 2b presents a load that, when lockout and deadband constraints permit, is frequently dispatched to follow the setpoint, sometimes providing an increase in power consumption continuously over several rounds. Figure 3 shows the regret for bOGD with and without randomization (relaxed decisions), averaged over 100 randomization steps ( bOGD 100 ), and its finite-time regret bound. The averaged regret approximates the expected regret. Figure 3 shows that in the current setting the regret (i) outperforms the bound provided in Corollary 1, (ii) is sublinear, thus showing that the decisions made with bOGD are approaching the round optimum at t increases, and (iii) is similar to the regret without randomization and averaged over several simulations.

V. CONCLUSION
In this paper, motivated by real-world demand response constraints, we incorporate binary constraints into OCO. We show that the expected dynamic regret of bOGD: (i) is upper bounded by the sum of the cumulative relaxed optimum tracking and the rounding error when the time horizon is unconstrained and (ii) has a sublinear in time and linear in cumulative variation in round optima bound when constrained to a finite time horizon. We use bOGD for real-time demand response with TCLs. We model the discrete on/off settings of the cooling units and unavailability due to lockout, temperature deadbands, and manual override.
Numerical simulations show that the randomization step yields a 1.30% deviation, on average, from the relaxed decisions. The relative tracking error is 6.51% and 6.46%, respectively, for the binary and relaxed algorithms. The algorithm is easy to implement and does not need extensive monitoring, data, or models. On average, less than 0.1 second is required to compute decisions for 1000 loads.
Future directions for this work include obtaining an asymptotic and tighter regret bound for bOGD and modeling general, time-invariant equality and inequality constraints, for example, using randomized rounding techniques.

ACKNOWLEDGMENT
The authors thank Dr. J. Yuan for the helpful discussion.

A. Proof of Lemma 1
The expected regret of bOGD is where we recall that b t ∈ arg min xt∈{0,1} n f t (x t ) is a binaryinteger optimum. We can bound from above the right-hand side by because x t is a relaxed optimum and f t (x t ) ≤ f t (b t ). Rearranging the terms, we obtain which completes the proof.

B. Proof of Lemma 2
The Lipschitz continuity of f t with respect to · 2 yields We re-arrange the right-hand side to obtain   where we have used Jensen's inequality for concave function to obtain the second inequality. By definition of the randomization function, we have E [x t ] = x t , and thus, (8) can be re-expressed as: The expectation now represents the variance. Re-expressing the variance in terms of the first and second moment leads to We have E x t (i) 2 = x t (i) and E [x t (i)] 2 = x t (i) 2 which follows from the definition of R. Hence, we obtain x t (i) − x t (i) 2 ≤ L 2 n 4 and we have completed the proof.

C. Proof of Theorem 1
We use Lemma 1 and express the regret as: where R τ (relaxed) denotes the regret of the relaxed, continuous problem solved using dynamic mirror descent [25] with Φ t set to the identity matrix at all t, ψ (x) = 1 2 x 2 2 , and r (x) = λ x 1 . By [25,Theorem 2], we upper bound the R τ (relaxed) as where D max = n 2 ≥ 1 2 x − y 2 2 (the Bregman divergence with respect to ψ) for all x, y ∈ X , L ψ = n is a Lipschitz constant for 1 2 x − y 2 2 and σ = 1, the strong-convexity modulus of ψ. We then have We upper bound (9) using (10) and obtain Using Lemma 2 gives Letting η = a √ τ completes the proof.

D. Proof of Lemma 3
We start this proof from (11) of Appendix C. We have where we have multiplied the second term by L 1 /L 1 . By assumption, ηL 1 ≥ 1 and hence Setting η = a √ T completes the proof.