1 of 100

Towards Computation- and Communication-Efficient Distributed Learning

1

Pranay Sharma

^{ECE, CMU}

2 of 100

Big Data

2

Need lots of data

Introduction

3 of 100

Data is Naturally Distributed!

3

Edge-devices collect data

This data is used to train ML models

Introduction

4 of 100

Liu, et al. "Privacy-preserving traffic flow prediction: A federated learning approach." IEEE IoT Journal 2020.

Li, et al. "Federated learning: Challenges, methods, and future directions." IEEE SPMag, 2020.

Hard, et al. "Federated learning for mobile keyboard prediction." arXiv:1811.03604.

Image curtsey: https://envuetelematics.com/

4

Introduction

Image Classification

Next-word Prediction

Autonomous Driving

Let’s look at a few example applications.

- Suppose we have image or video data from roadside, and we want to identify pedestrians, vehicles, road signs, and the road itself. This is an image classification problem. The images or videos might come from user devices or traffic cameras.

- Or we want to train a predictive typing model, which suggests the possible next words, something like Google Gboard.

- Or it might be a more complex application like self-driving cars. Note that the image classification in traffic scenes we just discussed, forms one of several components here, because cars would need to identify road-signs, pedestrians, vehicles and lanes in real-time.

- All these applications have the following architecture: they have a central server and bunch of edge devices, shown here as phones, but they can by other kinds of devices as well.

In this talk, we will assume that the devices can only communicate with the server, not with each other.

5 of 100

5

Introduction

Model

Image Classification

6 of 100

Privacy

6

Individual user data should not be leaked

Introduction

7 of 100

Network constraints

Image from www.ookla.com

7

Server

Introduction

Communication is expensive

8 of 100

8

Introduction

Intermittent Availability

Devices are available when

Idle, plugged-in and on wifi

9 of 100

Federated Learning�(FL)

Kairouz, et al. "Advances and open problems in federated learning." Foundations and Trends® in Machine Learning (2021).

9

Distributed learning under

Privacy concerns
Network constraints
Intermittent client availability

(partial participation)

My work

Introduction

Theoretically study convergence of FL algorithms

Propose better FL algorithms

Optimization Theory, Machine Learning, Statistics

Devices don’t send raw data*

Infrequent communication with server

10 of 100

10

Server

Introduction

Data heterogeneity

System heterogeneity

11 of 100

11

Server

Clients

Introduction

Partial Client Participation

Small fraction of clients available

12 of 100

12

Server

Clients

Introduction

Network constraints

Infrequent

Communication Efficiency

13 of 100

13

Server

Clients

Introduction

Low-power devices

First-order methods

Computation Efficiency

14 of 100

14

Server

Clients

Introduction

Network constraints

Infrequent

Communication Efficiency

15 of 100

15

Server

Clients

Introduction

16 of 100

16

Server

Introduction

Clients

Partial Client Participation

Small fraction of clients available

17 of 100

17

Server

Clients

Introduction

18 of 100

18

Federated Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

Contributions

19 of 100

19

Federated Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

Contributions

Autonomous Driving

Robust Learning

Image Classification

20 of 100

20

Federated Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

Contributions

[KS+21]: NeurIPS

Optimal complexity guarantees under full-participation

[JSJ23]: NeurIPS

Distributed Mean Estimation

[CS+23]: ICML

Study cyclic client participation

[JSNJ22]: UAI

Study partial participation error

Our scheme eliminates this error

Full client participation
Near-optimal computation/communication
Client- AND server-side variance reduction

Study partial client participation in FedAvg
Most significant source of error
Propose FedVARP to eliminate this error

Clients are partitioned into groups
Groups become available in cyclic manner
Partial participation within each group
Privacy and convergence benefits

21 of 100

21

Federated Problems Considered
	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

Contributions

[SPJV22]: ICML

Nonconvex min-max in FL

Optimal/SOTA complexity

[SPJ23]: TMLR

FL with heterogeneous devices

Improved communication

Full client participation
Concave/Nonconcave in max
Optimal/SOTA computation complexity
Even improved existing centralized results

Partial participation
System heterogeneity across clients

Different no. of local steps
Different local optimizers

SOTA communication cost

22 of 100

22

Federated Problems Considered
	Reinforcement Learning	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

Contributions

[KSJM22]: ICML (Long)

FL with stochastic approx.

First to prove linear speedup with Markov noise

23 of 100

23

Federated Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

Contributions

[KSJM22]: ICML (Long)

FL with stochastic approx.

First to prove linear speedup with Markov noise

[SPJV22]: ICML

Nonconvex min-max in FL

Optimal/SOTA complexity

[KS+21]: NeurIPS

Optimal complexity guarantees under full-participation

[SPJ23]: TMLR

FL with heterogeneous devices

Improved communication

[JSJ23]: NeurIPS

Distributed Mean Estimation

Correlation-aware sparsification

[CS+23]: ICML

Study cyclic client participation

[JSNJ22]: UAI

Study partial participation error

Our scheme eliminates this error

24 of 100

24

Federated Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

[KSJM22]: ICML (Long)

FL with stochastic approx.

First to prove linear speedup with Markov noise

[SPJV22]: ICML

Nonconvex min-max in FL

Optimal/SOTA complexity

[SPJ23]: TMLR

FL with heterogeneous devices

Improved communication

[CS+23]: ICML

Study cyclic client participation

[JSNJ22]: UAI

Study partial participation error

FedVARP eliminates this error

Clustering improves memory cost

Min-max in FL

[KS+21]: NeurIPS

Optimal complexity guarantees under full-participation

[JSJ23]: NeurIPS

Distributed Mean Estimation

Correlation-aware sparsification

25 of 100

25

Federated Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

[KSJM22]: ICML (Long)

FL with stochastic approx.

First to prove linear speedup with Markov noise

[SPJV22]: ICML

Nonconvex min-max in FL

Optimal/SOTA complexity

[SPJ23]: TMLR

FL with heterogeneous devices

Improved communication

[CS+23]: ICML

Study cyclic client participation

[JSNJ22]: UAI

Study partial participation error

FedVARP eliminates this error

Clustering improves memory cost

Min-max in FL

[KS+21]: NeurIPS

Optimal complexity guarantees under full-participation

[JSJ23]: NeurIPS

Distributed Mean Estimation

Correlation-aware sparsification

26 of 100

26

Min-max in FL

[SPJV22]: ICML

Nonconvex min-max in FL

Optimal/SOTA complexity

Rohan Panda

Pramod K. Varshney

Gauri Joshi

[SPJ23]: TMLR

FL with device heterogeneity

Improved communication

Sharma, Panda, and Joshi.

“Federated Minimax Optimization with Client Heterogeneity.” TMLR, 2023.

Sharma, Panda, Joshi, and Varshney.

“Federated Minimax Optimization: Improved Convergence Analyses and Algorithms.” ICML, 2022.

27 of 100

NIH Chest X-ray Dataset of 14 Common Thorax Diseases

Naghsh, et al. "Max–min fairness design for MIMO interference channels: A minorization–maximization approach." IEEE TSP 2019.

27

Minimization: not enough!

Min-max in FL

Robust Learning

Data Imbalance

Power Allocation in MIMO channels

Artificial Data Generation

GANs

Min-max

28 of 100

28

GANs

Generator Model

Discriminator Model

Real/Fake

Min-max in FL

Artificial

Real

29 of 100

Naghsh, et al. "Max–min fairness design for MIMO interference channels: A minorization–maximization approach." IEEE TSP, 2019.

29

Min-max

Min-max in FL

Robust Learning

Data Imbalance

Power Allocation in MIMO channels

Artificial Data Generation

30 of 100

30

Min-max in FL

No. of clients

Local data

31 of 100

31

(Stochastic) Gradient Descent Ascent

Min-max in FL

Ascent

Descent

Step-sizes

32 of 100

First proposed in Deng and Mahdavi, "Local stochastic gradient descent ascent: Convergence analysis and communication efficiency." AISTATS, 2021.

32

Local SGDA (FedAvg)

Min-max in FL

33 of 100

33

Local SGDA

Min-max in FL

Local stochastic

gradients

34 of 100

34

Local SGDA

Min-max in FL

Communication

Client Computation

1 round

35 of 100

35

Assumptions - I

Min-max in FL

smooth

Client drift

36 of 100

Nouiehed, et al. "Solving a class of non-convex min-max games using iterative first order methods." NeurIPS 2019.

Guo, et al. “Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks.” ICML, 2020.

36

Assumptions – II.A

Min-max in FL

smooth

Imbalanced Classification

37 of 100

37

Stationarity

smooth

Min-max in FL

38 of 100

Lin, et al. “On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems. " ICML, 2020.

Deng and Mahdavi, "Local stochastic gradient descent ascent: Convergence analysis and communication efficiency." AISTATS, 2021.

38

Existing Results

smooth

Work	Computation	Communication

Min-max in FL

39 of 100

Lin, et al. “On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems. " ICML, 2020.

Deng and Mahdavi, "Local stochastic gradient descent ascent: Convergence analysis and communication efficiency." AISTATS, 2021.

39

Existing Results

smooth

Work	Computation	Communication

		-

Min-max in FL

40 of 100

[SPJV22]: Sharma, et al. “Federated Minimax Optimization: Improved Convergence Analyses and Algorithms.” ICML, 2022.

[SPJ23]: Sharma, et al. “Federated Minimax Optimization with Client Heterogeneity.” TMLR, 2023.

40

Our Results

smooth

Work	Computation	Communication

		-

Min-max in FL

41 of 100

[SPJV22]: Sharma, et al. “Federated Minimax Optimization: Improved Convergence Analyses and Algorithms.” ICML, 2022.

[SPJ23]: Sharma, et al. “Federated Minimax Optimization with Client Heterogeneity.” TMLR, 2023.

41

Our Results

Work	Computation	Communication

		-

smooth

Min-max in FL

42 of 100

[SPJV22]: Sharma, et al. “Federated Minimax Optimization: Improved Convergence Analyses and Algorithms.” ICML, 2022.

42

Proof Intuition

smooth

Client drift error

Similar to minimization

Local noise variance
Client-drift

Min-max in FL

- If we look at how the function phi changes between consecutive rounds, it looks something like this. These are the global x’s at round t and t+1. We have the client drift. This much is similar to what we get in minimization problems.

- We get one more term, which measures how much phi differs from the actual function value.

- We can bound this maximization error as follows, where we get a contraction due to strong-concavity, and some error due to noise variance and client drift.

- To get a recursion, we want r.h.s. To depend on quantities at time t. To do that, we decompose this term as follows. The first term, we already bounded above. The 2nd term is good, since it depends on time t. The final term is tricky and takes some work.

- But, we eventually do get a recursive bound on the maximization error. Now we just need to solve this big recursion.

43 of 100

Lin, et al. “On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems. " ICML, 2020.

[SPJV22]: Sharma, et al. “Federated Minimax Optimization: Improved Convergence Analyses and Algorithms.” ICML, 2022.

43

Proof Intuition

smooth

Min-max in FL

Stronger contraction

Worse error

Weaker contraction

Better error

- If we look at how the function phi changes between consecutive rounds, it looks something like this. These are the global x’s at round t and t+1. We have the client drift. This much is similar to what we get in minimization problems.

- We get one more term, which measures how much phi differs from the actual function value.

- We can bound this maximization error as follows, where we get a contraction due to strong-concavity, and some error due to noise variance and client drift.

- To get a recursion, we want r.h.s. To depend on quantities at time t. To do that, we decompose this term as follows. The first term, we already bounded above. The 2nd term is good, since it depends on time t. The final term is tricky and takes some work.

- But, we eventually do get a recursive bound on the maximization error. Now we just need to solve this big recursion.

44 of 100

[SPJV22]: Sharma, et al. “Federated Minimax Optimization: Improved Convergence Analyses and Algorithms.” ICML, 2022.

[SPJ23]: Sharma, et al. “Federated Minimax Optimization with Client Heterogeneity.” TMLR, 2023.

44

Our Results

Work	Computation	Communication

		-

smooth

Min-max in FL

45 of 100

45

Generalizing Local SGDA - I

Min-max in FL

Partial client participation

46 of 100

[SPJ23]: Sharma, et al. “Federated Minimax Optimization with Client Heterogeneity.” TMLR, 2023.

46

Min-max in FL

Effect of Partial Participation

Dashed – small data heterogeneity

Solid – large heterogeneity

47 of 100

[SPJV22]: Sharma, et al. “Federated Minimax Optimization: Improved Convergence Analyses and Algorithms.” ICML, 2022.

47

Local SGDA: Full Participation

Min-max in FL

smooth

Dominates

Work	Convergence Rate
Full Participation		Yes

48 of 100

[SPJV22]: Sharma, et al. “Federated Minimax Optimization: Improved Convergence Analyses and Algorithms.” ICML, 2022.

48

Local SGDA: Partial Participation

Min-max in FL

smooth

Work	Convergence Rate
Full Participation		Yes
		No

49 of 100

[SPJV22]: Sharma, et al. “Federated Minimax Optimization: Improved Convergence Analyses and Algorithms.” ICML, 2022.

49

Local SGDA: Partial Participation

Min-max in FL

smooth

Work	Convergence Rate
Full Participation		Yes
		No

Dominates

50 of 100

[SPJ23]: Sharma, et al. “Federated Minimax Optimization with Client Heterogeneity.” TMLR, 2023.

50

Our Results

smooth

Min-max in FL

Setting	Computation	Communication
Full Participation

51 of 100

[SPJ23]: Sharma, et al. “Federated Minimax Optimization with Client Heterogeneity.” TMLR, 2023.

FedVARP [JSNJ22]: UAI, 2022.

51

Our Results

smooth

Min-max in FL

Setting	Computation	Communication
Full Participation

No benefit of local steps!
Can be solved with Server Memory: FedVARP

52 of 100

52

Generalizing Local SGDA - II

Min-max in FL

Partial client participation

Unequal no. of local updates

53 of 100

Wang, et al. "Tackling the objective inconsistency problem in heterogeneous federated optimization." NeurIPS 2020.

Li, et al. "Federated optimization in heterogeneous networks." MLSys 2020.

53

Generalizing Local SGDA - III

Min-max in FL

Partial client participation

Unequal no. of local updates

Different local optimizers

Momentum-based, FedProx, etc.

Average

“Cleverly” aggregate

54 of 100

Nouiehed, et al. "Solving a class of non-convex min-max games using iterative first order methods." NeurIPS 2019.

Naghsh, et al. "Max–min fairness design for MIMO interference channels: A minorization–maximization approach." IEEE TSP, 2019.

54

smooth

Assumptions – II.B

Min-max in FL

Power Allocation in MIMO channels

55 of 100

55

Stationarity

smooth

Min-max in FL

56 of 100

[SPJV22]: Sharma, et al. “Federated Minimax Optimization: Improved Convergence Analyses and Algorithms.” ICML, 2022.

[SPJ23]: Sharma, et al. “Federated Minimax Optimization with Client Heterogeneity.” TMLR, 2023.

56

Our Results

Work	Computation	Communication
		-

smooth

Min-max in FL

57 of 100

Guo, et al. “Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks.” ICML, 2020.

Reisizadeh, et al. "Robust federated learning: The case of affine distribution shifts." NeurIPS, 2020.

57

Assumptions – II.C

smooth

Min-max in FL

GANs

Data Imbalance

58 of 100

58

Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

[SPJ23]: TMLR

Improved communication

Partial Client Participation

Device heterogeneity

[KSJM22]: ICML (Long)

Study Federated RL

First to prove linear speedup with Markov noise

[CS+23]: ICML

Study cyclic client participation

[JSNJ22]: UAI

Study partial participation error

FedVARP eliminates this error

Clustering improves memory cost

Min-max in FL

[KS+21]: NeurIPS

Optimal complexity guarantees under full-participation

[JSJ23]: NeurIPS

Distributed Mean Estimation

Correlation-aware sparsification

59 of 100

59

Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

[KSJM22]: ICML (Long)

FL with stochastic approx.

First to prove linear speedup with Markov noise

[CS+23]: ICML

Study cyclic client participation

[JSNJ22]: UAI

Study partial participation error

FedVARP eliminates this error

Clustering improves memory cost

Reinforcement Learning

[KS+21]: NeurIPS

Optimal complexity guarantees under full-participation

[JSJ23]: NeurIPS

Distributed Mean Estimation

Correlation-aware sparsification

[SPJ23]: TMLR

Improved communication

Partial Client Participation

Device heterogeneity

60 of 100

Khodadadian, Sharma, Joshi, and Maguluri

“Federated Reinforcement Learning: Linear Speedup Under Markovian Sampling”

60

Reinforcement Learning

[KSJM22]: ICML (Long)

Study Federated Reinforcement Learning

Prove linear speedup with Markov noise

Sajad Khodadadian

Siva Theja Maguluri

Gauri Joshi

61 of 100

61

Reinforcement Learning

62 of 100

Image curtsey: https://www.wired.com and

https://thelastdriverlicenseholder.com

62

Distributed RL

RL is data-hungry!
Employ multiple agents in parallel to collect data

Reinforcement Learning

63 of 100

63

Distributed RL

Agents cannot always send their raw data
Communication is expensive
Need to preserve privacy!
Federated Learning

But RL has Markov noise!

Reinforcement Learning

64 of 100

64

Reinforcement Learning

Markov data

65 of 100

65

Quick Tutorial in RL

Reinforcement Learning

Policy

Initial state-action pair

Reward

Value function

66 of 100

66

Quick Tutorial in RL

Reinforcement Learning

Policy

Initial state-action pair

Reward

Value function

67 of 100

67

Stochastic Approximation

Reinforcement Learning

Noise

Step-size

68 of 100

Our work: [ICML'22: KSJM]

68

Reinforcement Learning

69 of 100

Our work: [ICML'22: KSJM]

69

Reinforcement Learning

Step-size

70 of 100

Our work: [ICML'22: KSJM]

70

Reinforcement Learning

71 of 100

Modified from Shen, et al. “Towards Understanding Asynchronous advantage actor critic: Convergence and linear speedup." arXiv:2012.15511.

71

Linear Speedup

Reinforcement Learning

Khaled, et al. "Tighter theory for local SGD on identical and heterogeneous data." AISTATS, 2020.

72 of 100

72

Reinforcement Learning

Setting	Computation	Communication
		-

73 of 100

Our work: [KSJM22]

73

Setting	Computation	Communication
		-

Reinforcement Learning

Linear Speedup

74 of 100

Chen, et al. "Finite-sample analysis of stochastic approximation using smooth convex envelopes." NeurIPS, 2020.

74

Federated Stochastic Approximation

Reinforcement Learning

75 of 100

Our work: [KSJM22]

75

Federated Stochastic Approximation

Setting	Computation	Communication
		-

Reinforcement Learning

Linear Speedup

Chen, et al. "Finite-sample analysis of stochastic approximation using smooth convex envelopes." NeurIPS, 2020.

Khaled, et al. "Tighter theory for local SGD on identical and heterogeneous data." AISTATS, 2020.

Heterogeneous environment?

76 of 100

76

Intuition

Reinforcement Learning

Linear Speedup

variance

77 of 100

77

Intuition

Reinforcement Learning

No Linear Speedup

variance

Crude Bound

78 of 100

78

Intuition

Reinforcement Learning

Linear Speedup

variance

Refined Bound

79 of 100

79

Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

[KSJM22]: ICML (Long)

FL with stochastic approx.

First to prove linear speedup with Markov noise

[CS+23]: ICML

Study cyclic client participation

[JSNJ22]: UAI

Study partial participation error

FedVARP eliminates this error

Clustering improves memory cost

Reinforcement Learning

[KS+21]: NeurIPS

Optimal complexity guarantees under full-participation

[JSJ23]: NeurIPS

Distributed Mean Estimation

Correlation-aware sparsification

[SPJ23]: TMLR

Improved communication

Partial Client Participation

Device heterogeneity

80 of 100

80

Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

Contributions

[KSJM22]: ICML (Long)

FL with stochastic approx.

First to prove linear speedup with Markov noise

[CS+23]: ICML

Study cyclic client participation

[JSNJ22]: UAI

Study partial participation error

FedVARP eliminates this error

Clustering improves memory cost

[KS+21]: NeurIPS

Optimal complexity guarantees under full-participation

[JSJ23]: NeurIPS

Distributed Mean Estimation

Correlation-aware sparsification

[SPJ23]: TMLR

Improved communication

Partial Client Participation

Device heterogeneity

81 of 100

Ghosh, et al. "Robust Federated Learning in a Heterogeneous Environment." ICML Privacy and Security Workshop, 2019.

81

So far: Distributed Learning

Future Directions

Clients have aligned interests
Learning in fixed environment
Client participation is taken for granted*

Fixed

82 of 100

Zhang, et al. "Multi-agent reinforcement learning: A selective overview of theories and algorithms." 2021.

Ozdaglar, et al. "Independent learning in stochastic games." arXiv:2111.11743.

Foster, et al. "On the complexity of multi-agent decision making: From learning in games to partial monitoring." COLT, 2023.

82

Future Directions

Clients have aligned interests
Learning in fixed environment
Client participation is taken for granted

Agents can have conflicting goals

Cooperative or competitive
Equilibrium concepts
Game-theory/Economics/MARL

83 of 100

Padakandla, et al. "Reinforcement learning algorithm for non-stationary environments." Applied Intelligence 2020.

Drusvyatskiy and Xiao. "Stochastic optimization with decision-dependent distributions." Math. OR 2023.

Narang, et al. "Multiplayer performative prediction: Learning in decision-dependent games." JMLR 2023.

83

Future Directions

Clients have aligned interests
Learning in fixed environment
Client participation is taken for granted

Agents with conflicting goals
Non-stationary environment

Cooperative or competitive
Equilibrium concepts
Game-theory/Economics/MARL

Opponent/environment-induced
Decision-dependent data
RL/Performative-prediction

84 of 100

Donahue and Kleinberg. "Models of fairness in federated learning." arXiv:2112.00818.

Karimireddy, et al. "Mechanisms that incentivize data sharing in federated learning." arXiv:2207.04557.

Huang, et al. "Evaluating and Incentivizing Diverse Data Contributions in Collaborative Learning." arXiv:2306.05592.

Dorner, et al. “Incentivizing Honesty among Competitors in Collaborative Learning and Optimization.” NeurIPS 2023.

84

Opponent/environment-induced
Decision-dependent data
RL/Performative-prediction

Cooperative or competitive
Equilibrium concepts
Game-theory/Economics/MARL

Future Directions

Clients have aligned interests
Learning in fixed environment
Client participation is taken for granted

Agents with conflicting goals
Non-stationary environment
Clients need incentives

Incentivizing collaboration
Measure & encourage diversity
Eliciting honest behavior

85 of 100

Ganesh, et al. "Why Is Public Pretraining Necessary for Private Model Training?" ICML’23.

Xu, et al. "Machine unlearning: A survey." ACM Computing Surveys 2023.

[1] Jia, et al. Model Sparsity Can Simplify Machine Unlearning. NeurIPS 2023.

85

Opponent/environment-induced
Decision-dependent data
RL/Performative-prediction

Future Directions

Agents with conflicting goals
Non-stationary environment
Clients need incentives
Privacy

Cooperative or competitive
Equilibrium concepts
Game-theory/Economics/MARL

Incentivizing collaboration
Measure & encourage diversity
Eliciting honest behavior

Efficient secure/private schemes
Competitive with non-private
Machine Unlearning^[1]/LLMs

86 of 100

86

Future Directions

Agents with conflicting goals
Non-stationary environment
Clients need incentives
Privacy

Cooperative or competitive
Equilibrium concepts
Game-theory/Economics/MARL

Opponent/environment-induced
Decision-dependent data
RL/Performative-prediction

Incentivizing collaboration
Measure & encourage diversity
Eliciting honest behavior

Efficient secure/private schemes
Competitive with non-private
Machine Unlearning/LLMs

87 of 100

Courses I can teach

SI423 - Linear algebra and applications
SC607 - Optimization
SC629 - Introduction to Probability and Random Processes
IE601 - Optimization Techniques
IE609 - Mathematical Optimization Techniques
SC653 - Optimization for Large Scale Machine Learning
EE659 - A First Course in Optimization
EE736 - Introduction to Stochastic Optimization
CS419 - Introducing to Machine Learning
CS605 - Probability and Statistics for Computer Science
CS709 - Convex Optimization
CS725 - Foundations of Machine Learning
EE6106 – Online Learning and Optimization

Additional courses

EE636 – Matrix Computations
EE635 - Applied Linear Algebra in EE
EE768 – Introduction to Machine Learning
IE613 - Online Machine Learning

87

Teaching

New Courses

Theory of Large-scale Optimization Methods
Recent Advances in Distributed Opt. and Learning
Short Courses on:

Differential Privacy
Deep Learning Theory
Monotone Operators
Multi-agent Reinforcement Learning
Stochastic Approximations

88 of 100

88

Acknowledgements

Future Directions

OPAL Lab (CMU)

CMU

Georgia Tech

Sajad

Siva-Theja

Google Research

Satyen Kale

Zheng Xu

Tong Zhang

Syracuse University: Pramod Varshney, Prashant, Swatantra, Sai

Ohio State: Kevin Liu

UMinnesota: Mingyi Hong

IITK: Ketan Rajawat

Carlee

Soummya

Aleks

Yae-Jee, Divyansh, Shuli, Baris, Neharika

Aushim, Rohan, Jiarui

89 of 100

89

Federated Problems Considered
	Minimization	Min-max	Reinforcement Learning
Communication& Computation Efficiency
Data and System Heterogeneity
Partial Client Participation

System Constraints

Contributions

[KSJM22]: ICML (Long)

FL with stochastic approx.

First to prove linear speedup with Markov noise

pranaysh@andrew.cmu.edu

Thank You!

Questions?

[CS+23]: ICML

Study cyclic client participation

[JSNJ22]: UAI

Study partial participation error

FedVARP eliminates this error

Clustering improves memory cost

[KS+21]: NeurIPS

Optimal complexity guarantees under full-participation

[JSJ23]: NeurIPS

Distributed Mean Estimation

Correlation-aware sparsification

[SPJ23]: TMLR

Improved communication

Partial Client Participation

Device heterogeneity

90 of 100

90

Actively Working on

FL Algorithms and Theory
Stochastic Optimization

Conv. in high-prob.^[1]
Min-max and multi-level problems
Non-smooth problems

Reinforcement Learning
Differential Privacy

91 of 100

91

Beyond Local SGDA

92 of 100

92

Normalized Updates

Beyond Local SGDA

93 of 100

Our work: [JSNJ22]: UAI

93

ClusterFedVARP

Partial Participation

Server

server

memory

94 of 100

Our work: [JSNJ22]: UAI

94

ClusterFedVARP

Server

Partial Participation

server

memory

Intra-cluster models aggregated

95 of 100

Our work: [JSNJ22]: UAI

95

ClusterFedVARP

Server

Partial Participation

server

memory

Memory updated for each selected cluster

Updated global model

aggregate

96 of 100

96

smooth

Robust Learning

Min-max in FL

Probability simplex

97 of 100

Liu, et al. "Max-min fairness linear transceiver design for a multi-user MIMO interference channel." ICC, 2011.

97

Min-max in Wireless

Future Directions

98 of 100

98

Stationarity

smooth

99 of 100

99

Stationarity

smooth

100 of 100

Davis and Drusvyatskiy. "Stochastic model-based minimization of weakly convex functions." SIAM Opt, 2019.

100

Min-max in FL