On the Power of Federated Learning for Online Sparse Linear Regression with Decentralized Data

Authors: Junfan Li, Xiao Zhang, Zenglin Xu, Liqiang Nie
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: Federated learning, online learning

Abstract:
In this paper, we study the necessity of federated learning (FL) for online linear regression with decentralized data. Previous work proved that FL is unnecessary for minimizing regret in full information setting, while we prove that it can be necessary if only limited attributes of each instance are observed. We call this problem online sparse linear regression with decentralized data (OSLR-DecD). We propose a federated algorithm for OSLR-DecD, and prove a lower bound on the regret of any noncooperative algorithm. In the case of $d=o(M)$, the upper bound on the regret of our algorithm is smaller than the lower bound, demonstrating the necessity of FL, in which $M$ is the number of clients and $d$ is the dimension of data. When $M=1$, we give the first lower bound on the regret and improve previous upper bounds. We invent three new techniques including an any-time federated online mirror descent with negative entropy regularization, a paradigm for client-server collaboration with privacy protection, and a reduction from online sparse linear regression to prediction with limited advice for establishing the lower bound on the regret, some of which might be of independent interest.

Decision: reject
Reviewer scores: 8, 3, 5, 6

Reviews and discussion:
<thread>
creation date:
1730194935767

thread_type:
official_review

<thread_object>
creator: reviewer_193r

<content>
summary:
This paper delves into the importance of federated learning (FL) in the context of online sparse linear regression (OSLR) with decentralized data (DecD). The authors challenge the previous consensus that FL is unnecessary for minimizing regret in full information settings by demonstrating that FL becomes essential when only limited attributes of each instance are observable.

The paper introduces the problem of online sparse linear regression with decentralized data (OSLR-DecD), where data is scattered across multiple clients, and each client can only observe a limited number of attributes for each instance. The authors propose a federated algorithm called FedAMRO for OSLR-DecD and establish a lower bound on the regret of any noncooperative algorithm. They prove that in scenarios where the dimensionality of data (d) is much smaller than the number of clients (M), the upper bound on the regret of FedAMRO is smaller than the lower bound for noncooperative algorithms, thus highlighting the necessity of FL.

strengths:
1. An upper bound on the regret for FedAMRO, showing its effectiveness in OSLR-DecD.

2. A lower bound on the regret for any noncooperative algorithm, reinforcing the advantage of federated learning in OSLR-DecD when d is of smaller order than M.

3. The first lower and upper bounds on the regret for OSLR when M equals 1.

4. Three new techniques: any-time federated online mirror descent with negative entropy regularization, a client-server collaboration paradigm with privacy protection, and a reduction from online sparse linear regression to prediction with limited advice for establishing regret bounds.

weaknesses:
1. The paper assumes that the dimensionality of data (d) is much smaller than the number of clients (M) to establish the necessity of federated learning. This assumption might not hold in real-world scenarios where the data can be high-dimensional or the number of clients limited. Whether this result can generalize to  high-dimensional sparse regression method ? such as lasso?  

2. The experimental section of the paper validates the theoretical findings on a limited number of datasets. The generalization of the results to other types of data or different problem domains is not extensively tested. A more rigorous experimental validation involving a broader and more diverse set of datasets would strengthen the paper's conclusions.

questions:
1. How does the proposed Federated Algorithm for Online Sparse Linear Regression with Decentralized Data (FedAMRO) scale with the increase in the number of clients (M) and the dimensionality of data (d), especially when both M and d are large? What are the potential bottlenecks, and how might they be addressed?

2. How robust is the proposed FedAMRO algorithm to data heterogeneity across clients? 

Because I am not a professional researcher in the field of federated optimization, I find the conclusions of this article quite interesting. In the sparse case, it actually draws a contrary conclusion to the general setting, so I give it a score of 6.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730479621736

thread_type:
official_review

<thread_object>
creator: reviewer_8vcg

<content>
summary:
This paper addresses the challenge of online linear regression with partial feedback in a decentralized data environment (OSLR-DecD). The authors explore the role of federated learning in this context, proposing and proving the upper bound of the regret for a federated algorithm named FedAMRO for OSLR-DecD. They establish a regret lower bound for any noncooperative algorithm, showing that, in cases where $d=o(M)$, the regret upper bound of FedAMRO is smaller than this lower bound. This result underscores the effectiveness and importance of the federated learning approach within the decentralized, partial-feedback setting.

strengths:
1. This paper addresses the problem of online linear regression with partial information feedback, which is a topic with broad applicability across real-world scenarios where data is decentralized and feedback is limited.

2. By proving both the upper bound of the regret under the federated setting and the lower bound of the regret under the noncooperative setting for the problem, the authors provide a thorough and well-rounded analysis, and answer the question of federated learning in this problem.

weaknesses:
A primary weakness of this paper is the lack of clarity in conveying the intuition behind the core analytical ideas. The authors introduce numerous complex notations early on, often before providing a clear explanation of the algorithms’ key ideas, leaving many of the notations insufficiently defined. Additionally, the absence of a full algorithm description in the main text makes it challenging to grasp the algorithm’s foundational approach. The paper also lacks a proof outline or sketch, making it difficult to follow the reasoning behind the results. Sections 4 and 5 introduce extensive variable definitions for the pseudocode, yet both the algorithm and analysis remain inadequately explained. Furthermore, certain parts of the problem definition in the introduction and Sections 3.1 and 3.2 appear repetitive, occupying space that could be more effectively used to clarify the algorithm and its analysis.

questions:
1. Could the authors give some intuition or high-level explanation of the algorithm design in Algorithms 2 and 3?
2. Could the authors explain how the core part of the analysis of Algorithm 2 is different from previous work?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730653396111

thread_type:
official_review

<thread_object>
creator: reviewer_mvgq

<content>
summary:
This paper studies the problem of federated learning for online sparse linear regression (OSLR) with decentralized data. The authors first propose a new algorithm AMRO for OSLR, which improves the previous best regret, then extend AMRO to federated learning setting, and demonstrates the necessity of federated learning for OSLR by comparing the upper regret bound of FedAMRO and the lower regret bound of noncooperative algorithm.

strengths:
1) This paper studies the problem of online linear regression with decentralized data, and proposes a federated algorithm with theoretical guarantees on its regret bound.
2) The lower bound on the regret of any noncooperative algorithm is also analyzed, which can demonstrate that federated learning is indeed necessary for the studied problem.
3) Experimental results are provided to verify the performance of the proposed algorithm.

weaknesses:
1) In this paper, the definition of regret for federated learning seems a bit strange. I understand that it follows Patel et al., 2023. However, in decentralized learning, the regret is commonly defined as $Reg^{(i)}(\\mathbf{w})=\sum\_{j=1}^M \sum\_{t=1}^T [l(f_t^i(\\mathbf{x}_t^{j}),y\_t^{(j)}) - l(\\mathbf{w}^\top \\mathbf{x}\_t^{(j)}, y_t^{(j)})] $ [1][2][3]. Note that this definition considers the global loss of the learned hypothesis $f_t^i(\cdot)$ of the single client $i$. By contrast, the definition in this paper considers the sum of each local loss, i.e., $\sum\_{j=1}^M l(\\hat{y}\_t^{(j)},y\_t^{(j)})=\sum\_{j=1}^M l(f_t^j(\\mathbf{x}_t^{j}),y\_t^{(j)})$. 

2) Moreover, I believe this strange definition of regret is the main reason for the pessimistic result of Patel et al., 2023 (i.e., the collaboration among clients is actually unnecessary in the full information setting). If we adopt the commonly used regret, the pessimistic result is no longer valid. In this case, the motivation of this paper may be questionable, since collaboration among clients is indeed necessary.

3) The literature review is poor. There do exist many related but missed studies, especially the mentioned works on decentralized online convex optimization [1][2][3] and the previous works on online sparse linear regression.

4) It is also unclear why the problem of online sparse linear regression with decentralized learning should be investigated.

[1] Yan et al. Distributed Autonomous Online Learning: Regrets and Intrinsic Privacy-Preserving Properties. IEEE Transactions on Knowledge and Data Engineering, 2013.

[2] Hosseini et al. Online distributed optimization via dual averaging. In CDC, 2013.

[3] Wan et al. "Nearly Optimal Regret for Decentralized Online Convex Optimization". In COLT, 2024.

questions:
1) In this paper, the derived regret bound is related to $b$. Should different values of $b$ be tested on a dataset to verify its impact on loss?
2) When extending AMRO to FedAMRO, you modified $\\hat{\\mathbf{x}}$ and $\\widetilde{\\mathbf{x}}$ due to privacy constraints. Are there any theoretical results on privacy analysis?
3) Why does FedAMRO update $\\mathbf{w}\_{t+1,i}$ on the server? It seems that the communication costs can be reduced by updating it on the clients, calculating the cost, and then transmitting it to the server.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730725157752

thread_type:
official_review

<thread_object>
creator: reviewer_vnsb

<content>
summary:
This paper considers the federated online sparse linear regression problem, where each client can only observe part of the feature vector at each round. The authors propose the Aggregated OMD algorithm and establish the regret bound. They also establish the lower bound for non-cooperative algorithms. Their results reveal an interesting fact: unlike the full-information setting, where non-cooperative algorithms are optimal, federated learning can achieve better performance than non-cooperative algorithms.

strengths:
1. The problem is well-motivated, and the results provide an interesting contrast to federated full-information online linear regression.

2. Technically solid: improvements on regrets of OSLR and a new reduction from sparse linear regression to online prediction with limited advice.

3. Numerical experiments are conducted to illustrate the superior performance of the proposed algorithm.

weaknesses:
1. There is still an $O(\sqrt{d})$ gap between the proposed upper bound and the lower bound.

2. Several explanations in the algorithm design are unclear, as mentioned in the questions section.

questions:
1. In line 265, the authors state that subtracting $y_t^2$ from the loss can enhance privacy protection. However, it seems that the reported information still involves $y_t$. Could the authors explain this point further?

2. In line 282, the authors mention that there are many approaches to define $\delta_{t,m}$. Could the authors clarify which general properties $\delta_{t,m}$ must satisfy to achieve the same regret guarantee in the main theorem?

3. The authors state that their operations in equations (3) and (4) differ from previous algorithm designs (subtracting $y_t^2$ or using non-zero $\delta_{t,m}$). Are these differences intended for privacy protection or to improve regret performance?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732284629443

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to All Reviewers

comment:
We thank the reviewers for taking the time to review our paper and offering valuable comments and constructive suggestions. **We have revised the manuscript and marked the revised parts suggested by Reviewers in red.** To be specific, our revised parts contain:

(1) We gave more explanations on “why subtracting $y^2_t$ from the loss can enhance privacy” posed by Reviewer VNSb. 

(2) We simplified the problem definition, provided high-level explanations on Algorithm 2 and Algorithm 3, and explained the differences between the analysis of Algorithm 2 and previous work (Appendix E due to space limitations), as recommended by Reviewer 8VCG.

(3) We provided a comparison between our problem and a related yet fundamentally different problem called distributed online convex optimization, as suggested by Reviewer MVgQ, **thereby addressing the crucial concerns raised by the Reviewer regarding our work**.

The reviewer MVgQ raised several concerns regarding the definition of regret and the motivation behind this paper. These two concerns might stem from the absence of explanations on the differences between online learning with decentralized data and distributed online convex optimization in our manuscript. We have provided comprehensive explanations addressing the concerns.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733157109354

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to Area Chair and All Reviewers

comment:
Dear Area Chair and Reviewers,

As there is still a disagreement between us and Reviewer MVgQ, we kindly ask you to concentrate more on the concerns raised by the Reviewer and our responses, during the Reviewers’ discussion period. For clarity, we summarize the main concerns and our responses as follows.  

The Reviewer believes that the definition of regret in this paper is not reasonable and should follow the definition in distributed online convex optimization (DOCO) [1,2,3]. In this case, the motivation of this work is questionable. The regret in this paper is defined by
$$
\forall w\in W,\quad
Reg(w)=\sum^T_{t=1}\sum^M_{j=1}[\ell(\langle w^j_t,x^j_t\rangle,y^j_t)
-\ell(\langle w,x^j_t\rangle,y^j_t)].
$$
The regret in DOCO is defined by 
$$
\forall i\in[M], \forall w\in W, 
Reg^i(w)=\sum^T_{t=1}\sum^M_{j=1}[\ell(\langle w^i_t,x^j_t\rangle,y^j_t)
-\ell(\langle w,x^j_t\rangle,y^j_t)].
$$
DOCO requires that the models on each client $i$ maintain a small regret for data across all clients. **Both of the two definitions are valid, as the objectives of DOCO and our specific focus, online learning with decentralized data (also known as federated online learning), are distinct**. **The regret defined in this paper aligns with the previous work on federated online learning [4-7] and distributed online learning [8-9]**. Next we explain why our definition is valid.

**(1)** Due to the privacy constraint, it is infeasible to evaluate a model learned on client $i$, denoted by $w^i_t$, on the other clients, as the data from other clients are not visible for $w^i_t$. In this scenario, computing $\sum^M_{j=1}\ell(\langle w^i_t,x^j_t\rangle,y^j_t)$ is unattainable. **The Reviewer agrees with the privacy constraint but still believes we should follow the defintion in DOCO. This argument insufficient to justify rejecting our definition.**

**(2)** The ultimate goal of online learning algorithms is to minimize the cumulative losses suffered along its run (please see Page 109 in [10]). A natural extension of the goal to online learning with decentralized data (OL-DecD) is to minimize the following cumulative losses 
$$
\sum^T_{t=1}\sum^M_{j=1}\ell(\langle w^j_t,x^j_t\rangle,y^j_t). 
$$
We introduce the notation of regret in the unrealizable case (please see Page 110 in [10]) and restate the goal as minimizing the regret.

**(3)** The goals of DOCO and OL-DecD are different**.

In DOCO (please see Eq. (4) in [1], and Eq. (2) in [2]), the goal is to solve $P_1$,
$$
P_1: \min_w\sum^T_{t=1}\sum^M_{j=1}\ell(\langle w, x^j_t\rangle, y^j_t).
$$
We denote by $L^\ast$ the minimum and $w^\ast$ the optimal solution. Algorithms for DOCO aim to output a $w^i$ that is a good approximation of $w^\ast$ and approximate $L^\ast$.

**For OL-DecD, by the definition of regret, we can rewrite the goal as approximating $L^\ast$, rather than producing an approximation of $w^\ast$.**

**Note that the difference is non-trivial. The collaboration among clients is necessary in DOCO, as we must approximate $w^\ast$. Otherwise, it is not necessary**. For example, we can independently run online gradient descent on each client, and obtain an approximation of $L^\ast$, i.e.,
$$
\sum^T_{t=1}\sum^M_{j=1}\ell(\langle w^j_t,x^j_t\rangle,y^j_t)
=L^\ast+O(M\sqrt{T}).
$$
In contrast, the optimal algorithm for DOCO [3] obtains a worse approximation of $L^\ast$, i.e.,
$$
\forall i\in [M],\quad
\sum^T_{t=1}\sum^M_{j=1}\ell(\langle w^i_t,x^j_t\rangle,y^j_t)
=L^\ast+O(\rho^{-0.25}M\sqrt{T\ln{T}}), ~\rho <1.
$$

It has been proved that collaboration is unnecessary for OL-DecD in full information setting. In this work, **we aim to explore whether it is necessary in partial information setting, such as, online sparse linear regression with decentralized data (OSLR-DecD). We also answer this question affirmatively**. **OSLR-DecD is a new, well-defined, and challenging problem and is valuable for understanding both the limitations and capabilities of federated learning.** 


Thanks.

**Reference**

[1] Yan et al. Distributed Autonomous Online Learning: Regrets and Intrinsic Privacy-Preserving Properties. TKDE, 2013.

[2] Hosseini et al. Online distributed optimization via dual averaging. CDC, 2013.

[3] Wan et al. "Nearly Optimal Regret for Decentralized Online Convex Optimization". COLT, 2024.

[4] Kwon et al. Tighter Regret Analysis and Optimization of Online Federated Learning. TPAMI, 2023.

[5] Dubey et al. Differentially-Private Federated Linear Bandits. NeurIPS, 2020.

[6] Li et al. Communication Efficient Federated Learning for Generalized Linear Bandits. NeurIPS, 2022.

[7] Huang et al. Federated Linear Contextual Bandits. NeurIPS, 2021.

[8] Wang et al. Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication. ICLR, 2020.

[9] Kamp et al. Communication-Efficient Distributed Online Prediction by Dynamic Model Synchronization. ECML, 2014.

[10] Shai Shalev-Shwartz. Online Learning and Online Convex Optimization. FTML, 2011.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper addresses the problem of online sparse linear regression with distributed data, proposing an algorithm along with regret upper and lower bounds. The main concerns with this paper are as follows: the design and analysis of the algorithm lack sufficient intuitive explanation, and the necessity of federated learning is demonstrated under a rather restrictive condition ($d \ll M$). Furthermore, there are concerns about the accuracy of the content, as detailed below. To meet the standards expected of papers presented at ICLR, these issues need to be addressed appropriately.  

1. **Lines 187–194**: The paper states that $S_i$ is a disjoint subset, which can be interpreted as $i \neq i' \implies S_i \cap S_{i'} = \emptyset$. However, under this condition, the optimal subset is not necessarily included in $\\{S_i\\}$.  
2. **Table 1**: Are the labels for Algo2 and Algo3 correct? Upon reviewing the referenced literature, I could not find regret upper bounds matching those described in the table.  
3. **Lemma 6**: The statement seems to omit the assumption $\beta_{t} > \beta_{t+1}$. Additionally, I could not verify the correctness of part (b). Specifically,  
$$
   \frac{1 - \frac{N - |A_t|}{N}\beta_{t+1}}{\eta_{t+1}} - \frac{1 - \frac{N - |A_t|}{N}\beta_{t}}{\eta_{t}} = \frac{1}{\eta_{t+1}} - \frac{1}{\eta_{t}} + \frac{N - |A_t|}{N} \left(\frac{\beta_{t}}{\eta_{t}} - \frac{\beta_{t+1}}{\eta_{t+1}}\right),
$$
   which does not always seem to be less than $(\frac{1}{\eta_{t+1}} - \frac{1}{\eta_{t}})$.  
4. **Binomial coefficients**: The notation $\binom{b}{d}$ appears in multiple locations, but it seems to be a typographical error for $\binom{d}{b}$.  

Moreover, while the paper invests significant effort in analyzing OMD with a time-variant learning rate, the analysis could potentially be greatly simplified by adopting an FTRL-type update instead. For instance, referring to Corollary 7.9 and Section 7.6 in [Orabona, Francesco. "A modern introduction to online learning." arXiv preprint arXiv:1912.13213 (2019).] is recommended.