We study federated constrained optimization problems of the form w * = arg min
where f j and g j represent the local objective and constraint functions on the client j. This framework captures many real-world applications of federated learning [18,22,24], where models must be trained across private or geo-distributed data without central collection. Constraints g(w) ≤ 0 encode feasibility conditions such as fairness mandates, energy budgets, or safety margins in autonomous systems and battery management [1,5,19,38]. Still, solving (1) in realistic deployment scenarios remains challenging. We highlight three primary difficulties that simultaneously shape the design space for federated constrained optimization:
(i) Functional constraints. Federated tasks increasingly involve feasibility criteria beyond minimizing a loss: fairness across subpopulations [1], bounding risk exposure in financial models, or safety limits in batteries (e.g., maximum temperature rise). Enforcing such constraints requires algorithms that provide guarantees on feasibility without resorting to expensive projections or inner constrained solves each round.
(ii) Severe bandwidth limits. Deep neural network models involve millions of parameters, yet FL often operates on commodity wireless or edge networks, where it is infeasible to send full-precision parameter updates every round. Communication-efficient training requires compression techniques such as Top-K, Rand-K, or quantization [2,9,33].
(iii) Heterogeneous on-device compute. Devices participating in FL varies in orders of magnitude with their FLOPS, memory, and energy capacity. A common strategy is to allow clients to perform multiple local updates (E > 1) before each communication round [20], amortizing latency and increasing utilization. Yet, local updates cause drifts between client and global iterates, complicating convergence analysis, especially when constraints must be satisfied globally.
Despite the importance of these challenges for real-world FL applications, no existing method provides provable guarantees that addresses them simultaneously.
Limitations of existing approaches. Constrained versions of FedAvg [14] and primal-dual or AL/ADMM methods [4,6,8,13,21,25,26,39] can certify feasibility but rely on dual variable tuning, penalty scheduling, or inner projection steps. These methods also typically assume synchronous full participation and uncompressed updates, which is unrealistic in FL applications. Error-feedback compression algorithms, such as EF-SGD and Safe-EF [2,9,17,33], provide robustness against biased quantization, but do not incorporate local update drift (E > 1). Local-SGD methods [20] directly address compute heterogeneity but are unconstrained, offering neither feasibility nor compression robustness. Finally, switching-gradient methods (SGM) [23,27,30,36] provide a primal-only, projection-free mechanism for constrained optimization: if w t is nearly feasible, update along ∇f ; if not, update along ∇g. This design achieves the optimal O(ϵ -2 ) rate for convex, possibly non-smooth problems, and recent work [7,15] extends optimality guarantees to weakly convex objectives. However, all existing analyses assume centralized, synchronous, full-gradient access, which is not suitable for federated systems with compression and local updates.
• We investigate FedSGM as a unifying backbone for constrained FL by extending the primalonly philosophy of SGM. Unlike AL/ADMM-based methods, FedSGM avoids dual-variable tuning and penalty scheduling, ensuring lightweight per-round computation while certifying the feasibility of the averaged iterate.
• We analyze FedSGM under multiple local steps (E > 1) by bounding the drift between local and global iterates. This yields rates of the form O DG
, where D := ∥w 0 -w * ∥, T is the total number of rounds, G is the Lipschitz constant, and q u the uplink compression factor. The analysis recovers the canonical 1/
T rate from centralized SGM, while explicitly quantifying the impact of multi-step local updates and compression.
• We extend both hard switching, a binary choice of update, and soft switching [36], a smooth interpolation between ∇f and ∇g via a smooth weighting function based on the magnitude of violation. Theorem 2 recovers the hard switching regime while improving stability near the feasibility boundary, without impacting the convergence rate.
Together, these results provide the first convergence guarantees for constrained FL with uplinkunbiased compression, multiple local updates, and soft switching.
Notation. We write [T ] := {0, 1, . . . , T -1} for an index set of length T , and [n] := {1, 2, . . . , n} for the set of all clients. For a set A, |A| denotes its cardinality. We use Id to denote the identity mapping, i.e., Id(x) = x for all x. For a scalar z ∈ R, we define the positive part operator [z] + := max{0, z}. Additionally, 1 {•} denotes the standard binary indicator function.
In this work, we consider the problem defined in (1), which is a standard constrained optimization problem in the FL setting, where f j : R d → R denotes the local objective of client j and g j : R d → R denotes its local constraint function. Here, n is the total number of clients and w ∈ R d are the model parameters. The functions f (•) and g(•) represent the global objective and global constraint, respectively. The goal is to compute an ϵ-solution w that satisfies f ( w) -f (w * ) ≤ ϵ and g( w) ≤ ϵ. Following are the assumptions used in our analysis.
Assumption 1 Each function f j and g j is convex and G-Lipschitz continuous in R d . Consequently, f and g are also convex and G-Lipschitz. 2 , where q u ≥ 0 is the compression factor.
We introduce FedSGM, a projection-free and duality-free algorithm for constrained optimization in FL. FedSGM combines Federated learning with the Switching Gradient Method, focusing here on the setting with: (i) full client participation, (ii) both hard and soft switching between objective and constraint updates, (iii) multiple local updates per communication round, and (iv) uplink compression.
At round t, the server collects constraint values {g j (w t )} n j=1 and broadcasts the global average g(w t ). Each client j initializes w t j,0 = w t and performs E local steps. The update direction is
where σ β is the switching rule: hard switching σ β (z) = 1 {z>0} , or soft switching σ β (z) = min{1, [1 + βz] + }. Clients then set w t j,τ +1 = w t j,τ -ην t j,τ . After E steps, each client transmits the compressed difference ∆ t j,E = C((w t -w t j,E )/η), with C ≡ Id denoting no compression. The server updates
This unified design (Alg. 1, see Appendix A) cleanly subsumes both hard and soft switching under compression.
Motivation for Soft Switching. Hard switching enforces a binary rule: each client either optimizes the objective or the constraint, depending on whether the global violation g(w t ) is within the tolerance ϵ. While simple, this approach is highly sensitive when g(w t ) fluctuates around ϵ as already shown in the centralized case [36]. Such fluctuations can trigger frequent back-and-forth updates, amplifying client drift and resulting in unstable trajectories.
Soft switching provides a remedy by introducing a smooth interpolation between the two gradients [36]. Specifically, the switching weight σ β (g(w t )-ϵ) ensures that near the feasibility boundary, the update direction is a convex combination of ∇f j and ∇g j , rather than an abrupt choice. This smooth relaxation suppresses oscillations while preserving convergence guarantees. Our analysis demonstrates that, even under compression, soft switching attains the same order of convergence as hard switching, while empirical validation confirms its superior stability near the feasibility boundary. To the best of our knowledge, this is the first convergence guarantee establishing the effectiveness of soft switching for constrained FL with compression, thereby extending beyond prior results restricted to hard switching and single local updates [17]. Next, we state the theorems that provide the convergence guarantees for FedSGM in Algorithm 1.
Theorem 1 (Hard switching FedSGM) Consider the problem in (1) and Algorithm 1, under Assumptions 1 and 2 (only for compression). Let D := ∥w 0 -w * ∥ and define
where q u is client-to-server compression factor. Now, set the constraint threshold and step size as
then A is nonempty, w is well-defined, and w is an ϵ-solution of (1).
Theorem 2 (Soft switching FedSGM) Consider the problem in (1) and Algorithm 1, under Assumptions 1 and 2 (only for compression). Let D := ∥w 0 -w * ∥ and define
.
where q u is client-to-server compression factor. Now, set the constraint threshold and step size as
then A is nonempty, w is well-defined, and w is an ϵ-solution of (1).
The details of the proof are present in the Appendix A. Now, we discuss the implications of the statement of Theorems 1 and 2.
• n = 1, q u = 0, C j ≡ Id, E = 1 , i.e., centralized with no compression: In this case, we can infer from Theorems 1 and 2, that rates we receive is O DG/
T , corresponding to the rates present in [23,28,36].
• g j ≡ 0, ∀j ∈ [n], E = 1, i.e., no constraint: In this case, our algorithm reduces to the well-known
FedCOM method [12], where we recover the standard rate of O DG . The scaling of √ E captures the effect of client-drift in this federated constrained setting, deviating from the previous centralized results.
• FedSGM with uplink compression: We focus on the case where only uplink transmissions are compressed, which captures the dominant communication bottleneck in federated learning. Most prior works on uplink compression have studied restricted classes of compressors-such as absolute compression [34] or unbiased operators [10,11,29,35]-and largely target unconstrained or singlestep settings. Recent progress on biased compressors [3,16,31] has established convergence guarantees for unconstrained optimization, while constrained FL with compression has only been addressed under hard switching and single local updates [17]. In this work, we analyze FedSGM in the unbiased uplink regime, extending the scope to multiple local updates and, crucially, to soft switching between objective and constraint updates. To the best of our knowledge, this is the first convergence result showing that soft switching remains effective in constrained FL under uplink-unbiased compression, thereby laying the groundwork for subsequent extensions to biased and bi-directional compression.
We evaluate the proposed method in a federated Neyman-Pearson (NP) classification setting with constrained optimization objectives. The aim is to examine how different switching strategies behave under uplink compression, with particular focus on convergence, stability, and feasibility.
We consider the constrained optimization problem in (1), where the objective is to minimize the empirical loss on the majority class while ensuring that the loss on the minority class remains below a prescribed tolerance. For each client j, the local objective and constraint are defined as
where
j denote local samples of class 0 and class 1, respectively, and m j0 , m j1 are their cardinalities. The function ϕ is the binary logistic loss,
This captures the NP paradigm: f (w) enforces performance on the majority class, while the constraint g(w) ≤ ϵ ensures the minority class loss does not exceed the tolerance. We use the breast cancer dataset [37], containing 569 samples with 30 features. To simulate the federated setting, the data is split in an IID fashion between n = 10 clients, such that each client receives an equal number of samples and the same class ratio. Each client performs local gradient descent updates for E = 5 epochs before communication, and the global model is updated for T = 100 communication rounds. We compare both hard and soft switching using a tolerance = 0.1.
For communication efficiency, we evaluate using Rand-K [12,32] compressor, which transmits a fraction K/d of coordinates with unbiased scaling. Performance is measured in terms of the majority-class objective loss f (w), the minority-class constraint loss g(w), and the number of rounds in which the feasibility condition g(w) ≤ is violated. Each experiment is repeated with three random seeds, and we report mean trajectories with variance bands. From Figure 1, we observe that both hard and soft switching achieve convergence of the majority-class objective f (w). However, soft switching exhibits markedly improved stability in the constraint g(w): while hard switching frequently oscillates around the tolerance, soft switching maintains feasibility more consistently. This translates into a substantial reduction in the number of violations, with soft switching yielding around 4× fewer violations compared to hard switching. Notably, this improvement in feasibility is achieved without compromising the convergence behavior of the objective loss, and in fact ensures more stable results as evident from the variance plots, highlighting the advantage of soft switching in balancing accuracy and constraint satisfaction under communication compression.
FedSGM provides a unified algorithmic framework for constrained federated learning by integrating projection-free and duality-free switching-gradient methods with multi-step local updates and uplink compression. Our analysis provides the first convergence guarantees in this regime, yielding rates
with explicit dependence on the compression factor, and recovers classical centralized and FedCOM bounds as special cases. Beyond hard switching, we demonstrated that soft switching recovers the hard regime when β ≥ 2/ , but is empirically more stable near the feasibility boundary, suppressing oscillations without altering the rate. Overall, FedSGM robustly balances feasibility, client drift, and communication efficiency, and lays the foundation for extensions to biased/bidirectional compression and partial participation.
Algorithm 1: FedSGM(T, E, C j , η, β) Input: Number of rounds T ; local updates E; compression operator C j (with C j = Id denoting no compression); learning rate η; initial model w 0 ; switching rule σ β (•) (hard or soft) for t ← 0 to T -1 do foreach client j ∈ [n] // in parallel do send g j (w t ) to server // cheap single float communication end compute g(w t ) ← 1 n n j=1 g j (w t ) and broadcast; foreach client j ∈ [n] // in parallel do set w t j,0 ← w t ; for τ ← 0 to E -1 do compute switching weight α t ← σ β (g(w t ) -ϵ); update direction ν t j,τ ← (1 -α t )∇f j (w t j,τ ) + α t ∇g j (w t j,τ ); update w t j,τ +1 ← w t j,τ -ην t j,τ ; end send ∆ t j,E ← C j wt-w t j,E η to server; end server computes w t+1 ← w t -η • 1 n n j=1 ∆ t j,E and broadcasts; end A.1. Lemmas Lemma 3 (Bound on the Expected Norm of Compressed Aggregates) Under Assumptions 1 and 2, for all rounds t ∈ [T ], the following bound holds,
Proof Let X t j := E-1 τ =0 ν t j,τ . We aim to bound:
Using the identity for the second moment:
we apply this to our setup:
where the inequality uses independence across j and linearity of expectation. Applying Assumption 2 (variance bound of the compression operator), E C j ∥C j (X t j ) -X t j ∥ 2 ≤ q u ∥X t j ∥ 2 , we get,
Now substitute X t j = E-1 τ =0 ν t j,τ and apply Jensen's inequality again,
Hence,
Under Assumptions 1 and 2, for all rounds t ∈ [T ], the following bound holds,
Proof We now analyze the cross term in the squared distance recursion,
We handle the second term by applying the convexity of f j or g j . For t ∈ A, where updates use ∇f j we apply: f j (w * ) ≥ f j (w t j,τ ) + ∇f j (w t j,τ ), w * -w t j,τ , which implies:
-w t j,τ -w * , ∇f j (w t j,τ ) ≤ f j (w * ) -f j (w t j,τ ). Thus,
T ermB = -2η w t j,τ -w * , ∇f j (w t j,τ ) ≤ 2η f j (w * ) -f j (w t j,τ ) .
A argument holds for t ∈ B with ∇g j , resulting in T ermB ≤ 2η g j (w * ) -g j (w t j,τ ) . Again, while upper bounding T ermA, we need to deal with 2 cases depending on whether t ∈ A or t ∈ B. Firstly, we start with the case where t ∈ A, for any α > 0
Similarly, for t ∈ B, we get
Substituting the bounds for both T ermA and T ermB back into the original expectation furnishes the proof.
Therefore,
Theorem 6 (FedSGCM) Consider the problem in eq. ( 1) and Algorithm 1, under Assumptions 1 and 2. Define D := ∥w 0 -w * ∥ and
, where Γ = 2E 2 + Eq u 2n it holds that A is nonempty, w is well-defined, and w is an ϵ-solution for P .
Proof Using Algorithm 1, the update rule for the global model is
where we define the compressed update using a stochastic compression operator C j (•), and also
We analyze the squared distance to the optimal point w * as follows,
Taking the expectation with respect to the compression operator C j and using Lemmas 3 and 4, we get
Now our goal is to handle the term f j (w * ) f j (w t j,τ ), so we first rewrite, f j (w t j,τ ) ≥ f j (w t ) + ⟨∇f j (w t ), w t j,τ -w t ⟩ (by convexity)
Using Young's inequality with parameter α > 0, we get
Thus, we get,
Similarly, we can handle the other term with g and get,
So, putting these inequalities back in eq. ( 5) along with the use of Lemma 5 and eq. ( 1), we get
Now, for α = η, and rearranging the terms we get
Defining D := ∥w 0 -w * ∥ and summing the expression above for t = 0, 1, • • • , T -1 and then dividing by T , we get
Note that when ϵ is sufficiently large, A is nonempty. Assuming an empty A, we can find the largest "bad" ϵ:
for some N ≥ 0. With this choice, A is guaranteed to be nonempty. Now, we consider two cases. Either t∈A f (w t ) -f (w * ) ≤ 0 which implies by the convexity of f and g for w = 1 |A| t∈A w t we have
Otherwise, if t∈A f (w t ) -f (w * ) > 0, then
By rearranging
Implying f ( w) -f (w * ) < ϵ and further by convexity of g for w = 1 |A| t∈A w t , we also have g( w) ≤ ϵ.
Theorem 7 (FedSSGCM) Consider the problem in (1) and Algorithm 1, under Assumption 1. Define D := ∥w 0 -w * ∥ and
where
Then, if
, and β = 2 ϵ where Γ = 2E 2 + Eq 2n it holds that A is nonempty, w is well-defined, and w is an ϵ-solution for P .
Proof Using Algorithm 1, the update rule for the global model is
where,
We analyze the squared distance to the optimal point w * as follows,
Firstly, we start with upper-bounding T erm -A. Taking the expectation with respect to the compression operator C j and using Lemmas 3 and the fact that σ β (•) ∈ [0, 1], we have
Now we aim to upper bound T erm -B. First, we take the expectation with respect to C j and
Now we define σ t β = σ β (g(w t ) -ϵ) before we start upper bounding T erm -B 1 for any α > 0.
Similarly, we start to upper bound T erm -B 2 as well.
Putting T erm -B 1 and T erm -B 2 back in T erm -B, we get
Substituting T erm -A and T erm -B back in the original expression after taking the expectation w.r.t C j , we get for α = η
Note that for all t ∈ B it holds that σ β (g(w t ) -ϵ) = 1 and g(w t ) -g(w * ) ≥ ϵ. Further, for all t ∈ A if σ β (g(w t ) -ϵ) ≥ 0 it holds that g(w t ) -g(w * ) ≥ g(w t ) ≥ ϵ -1/β. With these observations, using convexity of f and g and decomposing the sum over t according to the definitions of A and B and division by T yields,
(10) Similar to the previous proofs, we first need to find the smallest ϵ to ensure A is non-empty. So, to find a lower bound on ϵ, assume A is empty in eq. ( 10) and observe that as long as condition
ET . Now, like before, we consider two cases based on the sign of t∈A 1 -σ t β f (w t ) -f (w * ) . As before, when the sum is non-positive we are done by the definition of A, which implies 0 < 1 -σ β (g(w t ) -ϵ) ≤ 1 and the convexity of f and g.
Assuming the sum is positive, dividing eq. ( 10) by t∈A 1 -σ t β (which by the definition of A is strictly positive), using convexity of f , and the definition of w, we have
where we used |B| = T -|A|.
Let us now find a lower bound on β to ensure the second term in the bound is non-positive. Note this is done for simplicity, and as long as the second term is O(ϵ), an ϵ-solution can be found. Immediate calculations show the second term in the bound is non-positive when
Since t∈A σ t β < T , a sufficient (and highly conservative) condition for all T ≥ 1 is to set β ≥ 2/ϵ. Thus, we proved the suboptimality gap result. The feasibility result is immediate given the definition of A and the convexity of g.
Then, if
, and η = D 2 4G 2 E 3 T it holds that A is nonempty, w is well-defined, and w is an ϵ-solution for P .
Proof Using Algorithm 1, the update rule for the global model is
We analyze the squared distance to the optimal point w * as follows,
Firstly, we start with upper-bounding T erm -A.
T erm
Now we can use Lemma 4 to bound T erm -B. So, putting T erm -A and T erm -B back into the expression we get
Now our goal is to handle the term f j (w * ) -f j (w t j,τ ), so we first rewrite, f j (w t j,τ ) ≥ f j (w t ) + ⟨∇f j (w t ), w t j,τ -w t ⟩ (by convexity)
Using Young's inequality with parameter α > 0, we get -⟨∇f j (w t ), w t j,τ -w t ⟩ ≤
Thus, we get,
Similarly, we can handle the other term with g and get,
So, putting these inequalities back in eq. ( 12) along with the use of Lemma 5 and eq. ( 1), we get
Now, for α = η, and rearranging the terms we get
Defining D := ∥w 0 -w * ∥ and summing the expression above for t = 0, 1, • • • , T -1 and then dividing by T , we get
Note that when ϵ is sufficiently large, A is nonempty. Assuming an empty A, we can find the largest "bad" ϵ:
for some N ≥ 0. With this choice, A is guaranteed to be nonempty. Now, we consider two cases. Either t∈A f (w t ) -f (w * ) ≤ 0 which implies by the convexity of f and g for w = 1 |A| t∈A w t we have
Otherwise, if t∈A f (w t ) -f (w * ) > 0, then
By rearranging
Implying f ( w) -f (w * ) < ϵ and further by convexity of g for w = 1 |A| t∈A w t , we also have g( w) ≤ ϵ. where
Then, if
, and β = 2 ϵ it holds that A is nonempty, w is well-defined, and w is an ϵ-solution for P .
Proof Using Algorithm 1, the update rule for the global model is
where, ν t j,τ = σ β (g(w t ) -ϵ)∇g j (w t j,τ ) + (1 -σ β (g(w t ) -ϵ))∇f j (w t j,τ )
We analyze the squared distance to the optimal point w * as follows,
Firstly, we start with upper-bounding T erm -A.
T erm
Now we aim to upper bound T erm -B.
-2η w t j,τ -w * , ν t j,τ )
T erm-B 2
Now we define σ t β = σ β (g(w t ) -ϵ) before we start upper bounding T erm -B 1 for any α > 0. T erm -B 1 = -2η w t -w t j,τ , ν t j,τ = -2ησ t β w t -w t j,τ , g j (w t j,τ ) -2η(1 -σ t β ) w t -w t j,τ , f j (w
t j,τ ) Y oung ′ s ≤ σ t β η α ∥w t -w t j,τ ∥ 2 + ηα∥∇g j (w t j,τ )∥ 2 + (1 -σ t β ) η α ∥w t -w t j,τ ∥ 2 + ηα∥∇f j (w t j,τ )∥ 2 G-Lip ≤ η α ∥w t -w t j,τ ∥ 2 + ηαG 2
Similarly, we start to upper bound T erm -B 2 as well.
T erm -B 2 = -2η w t j,τ -w * , ν t j,τ ) = -2ησ t β w t j,τ -w * , g j (w t j,τ ) -2η(1 -σ t β ) w t j,τ -w * , f j (w t j,τ )
Cvx.
≤ 2ησ t β g j (w * ) -g j (w t j,τ ) + 2η(1 -σ t β ) f j (w * ) -f j (w t j,τ ) ≤2ησ t β g j (w * ) -g j (w t ) +
1 2α ∥w t -w t j,τ ∥ 2 + α 2 G 2 (by Cvx., Young's, & G-Lip) + 2η(1 -σ t β ) f j (w * ) -f j (w t ) + 1 2α ∥w t -w t j,τ ∥ 2 + α 2 G 2 Putting T erm -B 1 and T erm -B 2 back in T erm -B, we get T erm -B ≤ 1 n n j=1 E-1 τ =0 2η α ∥w t -w t j,τ ∥ 2 + 2ηαG 2 + 2ησ t β (g j (w * ) -g j (w t )) +2η(1 -σ t β ) (f j (w * ) -f j (w t )) Lemma 5 ≤ 2 3α η 3 E 3 G 2 + 2ηαEG 2 + 2ηEσ t β (g(w * ) -g(w t )) + 2ηE(1 -σ t β ) (f (w * ) -f (w t )) Substituting T erm -A and T erm -B back in eq. (17), we get for α = η ∥w t+1 -w * ∥ 2 ≤ ∥w t -w * ∥ 2 + η 2 E 2 G 2 + 2η 2 EG 2 + 2 3 η 2 E 3 G 2 + 2ηEσ t β (g(w * ) -g(w t )) + 2ηE(1 -σ t β ) (f (w * ) -f (w t )) Let A = {t ∈ [T ]|g(w t ) < ϵ} and B = [T ]\A = {t ∈ [T ]|g(w t ) ≥ ϵ}. Note that for all t ∈ B it holds that σ β (g(w t ) -ϵ) = 1 and g(w t ) -g(w * ) ≥ ϵ. Further, for all t ∈ A if σ β (g(w t ) -ϵ) ≥ 0 it holds that g(w t ) -g(w * ) ≥ g(w t ) ≥ ϵ -1/β. With these observations, using convexity of f and g and decomposing the sum over t according to the definitions of A and B and division by T yields, D 2 2ηE + 1 2 ηEG 2 T + ηG 2 T + 1 3 ηE 2 G 2 T ≥ t∈A σ t β (g(w t ) -g(w * )) + t∈A (1 -σ t β ) (f (w t ) -f (w * )) + t∈B (g(w t ) -g(w * )) . Now choosing η = D 2 2G 2 ET Γ , where Γ = 1 2 E + 1 + 1 3 E 2 , we get 2D 2 G 2 T Γ E ≥ t∈A σ t β (g(w t ) -g(w * )) + t∈A (1 -σ t β ) (f (w t ) -f (w * )) + t∈B (g(w t ) -g(w * )) ≥ t∈A (1 -σ t β ) (f (w t ) -f (w * )) + ϵ|B| + ϵ -1 β t∈A σ t β .
(18) Similar to the previous proofs, we first need to find the smallest ϵ to ensure A is non-empty. So, to find a lower bound on ϵ, assume A is empty in eq. ( 18) and observe that as long as condition
< ϵ is met, A is non-empty. We choose to set ϵ = 2 2D 2 G 2 Γ ET . Now, like before, we consider two cases based on the sign of t∈A 1 -σ t β f (w t ) -f (w * ) . As before, when the sum is non-positive we are done by the definition of A, which implies 0 < 1 -σ β (g(w t ) -ϵ) ≤ 1 and the convexity of f and g.
Assuming the sum is positive, dividing eq. ( 18) by t∈A 1 -σ t β (which by the definition of A is strictly positive), using convexity of f , and the definition of w, we have f ( w) -f (w * ) ≤ 0.5ϵT -ϵ|B| -(ϵ -
1 β ) t∈A σ t β |A| -t∈A σ β (g(w t ) -ϵ) = ϵ + -0.5ϵT + β -1 t∈A σ t β |A| -t∈A σ t β ,
© A. Upadhyay, S.B. Moon & A. Hashemi.