A new federated bandit problem with multiple adversaries, solved with a near-optimal algorithm.
problem Non-stochastic federated multi-armed bandit problem with multiple adversaries.
method Proposed a near-optimal federated bandit algorithm called FEDEXP3.
result Guaranteed sub-linear regret without exchanging sequences of selected arm identities or loss sequences among agents.
A new federated algorithm reduces regret in X-armed bandit problems.
problem Collaborative optimization of heterogeneous local objectives.
method Fed-PNE algorithm using hierarchical partitioning and weak smoothness.
result Achieves sublinear cumulative regret with minimal communication.
This paper tackles efficient federated learning for generalized linear bandits.
problem Limited communication efficiency restricts existing federated learning solutions to linear models.
method Proposes a communication-efficient solution framework using online and offline regression.
result Proves sub-linear regret and communication cost for generalized linear bandits.
Paper addresses robust federated linear bandits against Byzantine attacks.
problem Byzantine attacks on a small fraction of agents in federated learning.
method Proposes a geometric median-based robust aggregation oracle.
result Achieves sublinear regret bound of i l d e O ( T 3 / 4 ) ilde{\mathcal{O}}({T^{3/4}}) i l d e O ( T 3/4 ) robust to fewer than half Byzantine agents. A new algorithm optimizes local objectives in federated learning with heterogeneous clients.
problem Optimizing local objectives in federated learning with heterogeneous client data.
method Proposes PF-PNE algorithm with double elimination strategy.
result PF-PNE algorithm optimizes local objectives with arbitrary heterogeneity and protects client data confidentiality.
A simple algorithm reduces federated contextual linear bandits' regret efficiently.
problem Solving federated contextual linear bandits with asynchronous agents.
method Proposed a simple algorithm exttt{FedLinUCB} based on optimism principle.
result Proved exttt{FedLinUCB} has bounded regret i l d e O ( d ∑ m = 1 M T m ) ilde{O}(d\sqrt{\sum_{m=1}^M T_m}) i l d e O ( d ∑ m = 1 M T m ) and communication complexity i l d e O ( d M 2 ) ilde{O}(dM^2) i l d e O ( d M 2 ) . A new federated multi-armed bandit framework with personalization balances generalization and personalization.
problem Balancing generalization and personalization in federated multi-armed bandits.
method Proposed a Personalized Federated Upper Confidence Bound (PF-UCB) algorithm to achieve a O ( log ( T ) ) O(\log(T)) O ( log ( T )) regret. result PF-UCB achieves an O ( log ( T ) ) O(\log(T)) O ( log ( T )) regret regardless of personalization degree and has similar instance dependency to lower bound. Paper addresses federated contextual bandits with encryption.
problem Building contextual bandits with vertically distributed data.
method Design of O3M encryption scheme for LinUCB and LinTS.
result Proposed protocols achieve good performance and privacy.
Paper studies user-level differential privacy in federated linear contextual bandits.
problem Federated learning with user-level differential privacy constraints.
method Unified federated bandits framework, CDP and LDP definitions, ROBIN algorithm.
result Near-optimal learning under user-level CDP with privacy budget and number of clients.
A collaborative algorithm reduces regret in federated linear contextual bandits.
problem Optimizing decision-making in federated learning with heterogeneous data.
method Fed-PE algorithm, leveraging geometric structure of rewards, multi-client G-optimal design.
result Achieves near-optimal regrets with logarithmic communication costs.
Paper tackles federated learning with personalised bandit algorithms.
problem Optimizing local and global objectives in a heterogeneous environment.
method Surrogate objective function combining client preferences and global knowledge; phase-based elimination algorithm.
result Achieves sublinear regret with logarithmic communication overhead.
Paper develops a private algorithm for multi-agent learning in bandits.
problem Private cooperative learning in decentralized systems.
method Developed extsc{FedUCB} algorithm for multi-agent learning.
result Improves pseudoregret bounds and empirical performance.
A federated learning algorithm tackles unknown contexts in multi-arm bandits.
problem Learning optimal actions in federated multi-arm bandits with unobserved contexts.
method Elimination-based algorithm for linearly parametrized reward functions.
result Proved regret bound for linearly parametrized reward functions.
A new algorithm reduces communication costs for collaborative decision-making across clients.
problem Collaborative decision-making with sparse rewards and heterogeneous contexts.
method Federated Lasso algorithm for sparse linear contextual bandits.
result Achieves near-optimal regret with logarithmic communication costs.
FedConPE improves conversational recommender systems efficiency and privacy.
problem Efficiently eliciting user preferences in interactive systems with heterogeneous clients.
method Phase elimination-based federated conversational bandit algorithm with adaptive key term construction.
result Minimizes uncertainty across all dimensions in feature space and offers improved efficiency and privacy.
This work bridges federated learning and contextual bandits, enhancing FL's utility.
problem Limited use of federated learning in contextual bandits despite its potential.
method Proposes FedIGW, a novel federated contextual bandits design that leverages regression-based algorithms and integrates various FL components.
result FedIGW better harnesses FL innovations and provides flexible, modular, and seamless integration of FL elements.
This work improves privacy in federated combinatorial bandits by balancing regret and privacy.
problem Privacy-preserving learning in competitive online learning settings with quality constraints.
method Proposes P-FCB algorithm for federated combinatorial bandits, balancing regret and privacy.
result Improves regret while maintaining quality constraints and privacy guarantees.
Paper proposes FMAB framework for federated learning with two models: approximate and exact.
problem Uncertainty in client sampling and suboptimality gap in federated multi-armed bandits.
method Developed a general FMAB framework and two specific models (approximate and exact), proposing Fed2-UCB for the approximate model.
result Achieved O(log(T)) regret in the approximate model and order-optimal regret in the exact model.
Study on collaborative vs. non-collaborative online and bandit convex optimization.
problem Minimizing average regret in distributed online and bandit convex optimization.
method Analyzes the impact of collaboration in adaptive and zeroth-order feedback settings.
result Collaboration is beneficial in high-dimensional federated online optimization with limited feedback.
A new algorithm balances global reward and group constraints in federated multi-armed bandits.
problem Maximizing global reward while protecting client privacy in federated learning.
method Combinatorial contextual bandit with group constraints, using a two-output Gaussian process.
result TCGP-UCB incurs low regret, balancing super arm reward and group reward constraints.
A federated learning algorithm tackles linear bandits with adversarial actions, achieving optimal regret bounds.
problem Federated linear bandits with finite adversarial action sets.
method FedSupLinUCB algorithm, extending SupLinUCB and OFUL principles.
result Achieves a total regret of i l d e O ( d T ) ilde{O}(\sqrt{d T}) i l d e O ( d T ) , matching minimax lower bound and being order-optimal. This work introduces reward teaching for federated multi-armed bandits to guide clients towards global optimality.
problem Existing federated multi-armed bandits designs assume clients will follow the server's protocol, but this is not always feasible.
method Introduces reward teaching where the server adjusts clients' local rewards to encourage global optimality, using phased Teaching-After-Learning (TAL) and Teaching-While-Learning (TWL) algorithms.
result Demonstrates that TAL achieves logarithmic regrets with only logarithmic adjustment costs, and TWL outperforms TAL for UCB1 clients.
LIBO optimizes repeated bandit tasks without prior knowledge or regret.
problem Optimizing repeated bandit tasks without prior knowledge or regret.
method LIBO sequentially meta-learns a kernel to adapt to the environment and solve tasks with the latest estimate.
result LIBO achieves sublinear lifelong regret, converging to oracle performance as more tasks are solved.
Federated learning for combinatorial multi-agent bandits reduces regret and speeds up with fewer communications.
problem Online combinatorial optimization with noisy feedback and cooperation.
method Transforms offline algorithms into online multi-agent algorithms with sublinear regret and communication efficiency.
result Achieves sublinear regret and linear speedup with more agents, communication-efficient.
Paper tackles federated linear bandit learning with AirComp for noisy channels.
problem Minimize cumulative regret in federated linear bandit learning.
method Proposes a federated linear bandits scheme using over-the-air computation (AirComp) over noisy fading channels.
result Determines the regret bound of the proposed scheme.
New algorithm for collaborative bandit learning reduces sample complexity and regret.
problem Optimal arm identification in a multi-agent bandit model with communication.
method Phased elimination with data-dependent sampling schemes.
result Near-optimal algorithm for pure exploration in collaborative bandit learning.
The paper tackles personalized policy learning from diverse data sources in a federated setting.
problem Learning personalized decision policies from observational bandit feedback across multiple heterogeneous data sources.
method Introduces a novel regret analysis for distinguishing global and local regret, and presents a federated policy learning algorithm using local policies trained with doubly robust offline policy evaluation strategies.
result Establishes finite-sample upper bounds on global and local regret, characterizing them by source heterogeneity and distribution shift.
A novel algorithm reduces communication costs in federated best arm identification.
problem Identifying the best arm in a federated multi-armed bandit setup with minimal communication cost.
method Proposes a novel algorithm called FedElim that communicates only in exponential time steps.
result Demonstrates that communication is almost cost-free in FedElim, with a total cost at most 3 times the maximum under its variant.
Unified bounds for sketched bilinear forms in machine learning and statistics.
problem Uniform bounds on sketched bilinear forms for modern analyses.
method Generic chaining and new techniques for handling suprema over pairs of sets.
result Improved convergence bounds for sketched Federated Learning and bandit algorithms.
The thesis clarifies when local updates outperform centralized methods in heterogeneous data environments.
problem Understanding when local updates are more effective than centralized or mini-batch methods in distributed optimization.
method Fine-grained consensus-error-based analysis framework, focusing on bounded second-order heterogeneity and third-order smoothness.
result Local updates outperform centralized or mini-batch methods under realistic models of data heterogeneity.
This paper develops a federated EM algorithm for unsupervised learning of mixture models.
problem Theoretical foundations of unsupervised federated learning are lacking.
method Introduces a federated gradient EM algorithm (FedGrEM) for unsupervised learning of mixture models.
result Theoretical analysis shows FedGrEM outperforms local single-task learning.
A practical one-shot federated learning algorithm for cross-silo setting.
problem Limited applicability of existing one-shot federated learning algorithms due to specific model support and lack of privacy guarantees.
method FedKT, a one-shot federated learning algorithm that supports any classification models and provides differential privacy guarantees.
result FedKT significantly outperforms other state-of-the-art federated learning algorithms with a single communication round.
A framework to compare federated learning algorithms in high-dimensional settings.
problem Comparing the performance of federated learning algorithms in high-dimensional settings.
method Formulating federated learning as a multi-criterion objective and analyzing a linear regression model.
result Federated Averaging with simple client fine-tuning achieves the same asymptotic risk as more intricate approaches and outperforms without personalization.
Federated learning method improves covariate shift adaptation for missing target values.
problem Missing target values in federated learning.
method Federated covariate shift adaptation algorithm for missing target output values.
result Asymptotically unbiased and efficient algorithm for federated learning.
Paper analyzes and compares ELF algorithms for federated learning.
problem Improving efficiency and privacy in federated learning.
method Proposes P-ELF, D-ELF, and B-ELF algorithms with primal, dual, and bidirectional compression.
result Provides non-asymptotic convergence guarantees under Log-Sobolev inequality.
EM algorithm speeds up convergence in federated learning with heterogenous data.
problem Understanding convergence rates of federated learning algorithms under data heterogeneity.
method Characterized convergence rate of EM algorithm for FMLR model under various regimes.
result EM algorithm converges to ground truth with SNR ≥ √K in all regimes.
FedIV uses federated GMM for IV analysis in non-i.i.d. data.
problem Efficient IV analysis in non-i.i.d. federated data.
method Federated GMM via FedGDA algorithm.
result Federated solution consistently estimates local moment conditions.
New adaptive SGD algorithms for federated learning over physical channels.
problem Reducing communication cost in federated learning over physical channels.
method Proposed adaptive federated SGD algorithms considering channel noise and hardware constraints.
result Demonstrated convergence rates adaptive to stochastic gradient noise level.
New algorithm for federated learning with non-smooth regularizers.
problem Federated Learning with non-smooth composite optimization problems.
method Proposed Federated Dual Averaging (FedDualAvg) algorithm to overcome convergence issues.
result FedDualAvg outperforms other algorithms in federated composite optimization.
FPFL mitigates unfairness in private federated learning.
problem Differential privacy degrades model performance on under-represented groups.
method Extends modified method of differential multipliers to private federated learning.
result FPFL reduces unfairness in trained models on private federated learning.
Faster convergence in federated learning for non-convex problems.
problem Accelerating convergence in federated learning for non-convex models.
method Reformulated federated learning as gradient-based method with biased gradients, proving convergence for non-convex problems and proposing an accelerated algorithm.
result Proved federated averaging algorithm converges for non-convex problems and proposed an accelerated federated learning algorithm with convergence guarantee.
New algorithms solve nonconvex federated learning problems efficiently.
problem Nonconvex federated composite optimization in federated learning.
method FedDR and asyncFedDR algorithms combining Douglas-Rachford splitting, randomized block-coordinate strategies, and asynchronous implementation.
result Match communication complexity lower bound up to a constant factor.
New algorithm solves federated minimax optimization problems.
problem Federated minimax optimization challenges.
method Federated Stochastic Smoothed Gradient Descent Ascent (FESS-GDA).
result FESS-GDA uniformly solves federated minimax problems.
Second-order guarantees for federated learning algorithms.
problem Non-convex optimization in federated learning with saddle-points as bottlenecks.
method Drawing on recent results on second-order optimality in centralized and decentralized settings, establish second-order guarantees for federated learning algorithms.
result Established second-order guarantees for federated learning algorithms.
A novel decentralized algorithm improves minimax optimization in federated learning.
problem Minimax optimization in federated learning with data heterogeneity.
method Decentralized Gradient Tracking (K-GT-Minimax) for nonconvex-strongly-concave optimization.
result Demonstrates superior convergence rate for NC-SC minimax optimization.
Novel algorithm resists Byzantine attacks in federated learning for PCA and LRCS.
problem Byzantine attacks in federated learning for PCA and LRCS.
method Subspace-Median algorithm for federated PCA, altGDmin for LRCS.
result Provably Byzantine-resilient communication-efficient and sample-efficient algorithms.
Compressed Federated Distillation reduces communication in federated learning.
problem Communication constraints in Federated Learning.
method Compressed Federated Distillation (CFD) leverages soft labels and quantization techniques.
result Reduces communication by more than 4 orders of magnitude compared to Federated Averaging.
New algorithm reduces sample and communication complexities in federated Q-learning.
problem Optimal Q-function learning in federated Q-learning with limited communication.
method Introduced Fed-DVR-Q algorithm for order-optimal sample and communication complexities.
result Complete characterization of sample-communication complexity trade-off.