1 of 34

Yanhui Zhu

yanhui@iastate.edu

October 27, 2024

Department of Computer Science

Iowa State University

Submodular Optimization: Variants, Theory and Applications

Yanhui Zhu

2 of 34

2

Yanhui Zhu

Ph.D. in Computer Science (expected May 2025)

IOWA STATE UNIVERSITY

Research: Algorithms, Machine Learning, Data science.

​

​

​

​

On Job Market for Faculty/PostDocs Positions

About Me

Yanhui Zhu

3 of 34

3

Overview of My Research

Yanhui Zhu

4 of 34

4

Big Data

Pictures

Audios

Social networks

Videos

Introduction

The Internet

Yanhui Zhu

5 of 34

5

Workflow

Introduction

Cleaning Normalization

Scaling

Encoding

…

Preprocessing

Feature Selection

Active Learning

Text Summarization

Influence Maximization

Clustering

…

Algorithms

Important Features

Labeled Data

Summarization

Influential Users

Clustered Labels

…

Decision

Yanhui Zhu

6 of 34

6

Workflow

Introduction

Feature Selection

Active Learning

Text Summarization

Influence Maximization

Clustering

…

Algorithms

Also,

optimization problems

Optimization objectives are

Submodular

General algorithms to solve a class of tasks with theoretical guarantees.

Submodular Optimization

Goal

Yanhui Zhu

7 of 34

7

Workflow

Introduction

Feature Selection

Active Learning

Text Summarization

Influence Maximization

Clustering

…

Algorithms

Submodular Optimization

Theoretically rigorous

Explainable

Cost-effective

Extendable

General algorithms to solve a class of tasks with theoretical guarantees.

Goal

Yanhui Zhu

8 of 34

8

Data summarization

More Applications

Introduction

Social network analysis

k-medoid clustering

Yanhui Zhu

9 of 34

9

Algorithms

Submodular optimization

Evolutionary computation

Algorithmic machine learning and fairness

Applications

Network science

Social network analysis

Reinforcement learning (multi-armed bandit)

​

Current Research

DCABES-17

Geofluids

Applied Energy

IJCAI 2024

CIKM 2024

UAI 2023a

UAI 2023b

ICML 2023

IEEE Trans. Big Data (2024)

Applied Soft Computing (2020)

Electronic Health Record (EHR)

Geo-science (sedimental analysis)

Environmental sciences (net ecosystem carbon exchange)

​

Data Science

Introduction

Yanhui Zhu

10 of 34

10

What do Submodular Functions Look Like?

Yanhui Zhu

11 of 34

11

Full menu:

$8

$5

$12

$11

$1

$4

$3

Price function:

f :

 

 

 

 

f is modular or linear.

Submodular Function Optimization

An example: order a meal

11 + 3

Yanhui Zhu

12 of 34

12

Full menu:

$8

$5

$12

$11

$1

$4

$3

Price function:

f :

 

 

 

 

Submodular Function Optimization

An example: order a meal

11 + 3

f is submodular:

Combo deals.

Combo Deal

A sandwich + A drink

Price: $12

12

14

 

Yanhui Zhu

13 of 34

13

Submodular Function Optimization

Submodular Functions

  • Discrete domain.
  • Similar to log or sqrt functions.

Diminishing Return

Yanhui Zhu

14 of 34

14

 

Submodular Function Optimization

Submodular Set Functions

Yanhui Zhu

15 of 34

15

Data summarization

More Applications of Submodular Optimization

Introduction

Social network analysis

k-medoid clustering

Yanhui Zhu

16 of 34

16

videos, text, pictures …

  • relevance
  • reliability
  • diversity

Data Summarization

Submodular Function Optimization

Yanhui Zhu

17 of 34

17

 

Submodular

Data Summarization

Submodular Function Optimization

Yanhui Zhu

18 of 34

18

Find k pictures that can best represent the entire database.

 

Submodular maximization with cardinality (size) constraint.

Cardinality Constraint

 

Submodular Function Optimization

Yanhui Zhu

19 of 34

19

Four Variants of Submodular Optimization

  • Cost Constraint
  • Regularized Submodular Maximization
  • Submodular Constraint
  • k-submodular Maximization

Yanhui Zhu

20 of 34

20

 

  • Submodular Objective:

 

Find some pictures within B MB that can best represent the entire database.

Submodular maximization with cost constraint.

Cost constrained submodular maximization

Variant 1: Cost Constraint

 

Yanhui Zhu

21 of 34

21

Reference

Approximation Ratio

Time Complexity

Bian et al., 2020

​

​

Qian et al., 2017

​

​

Our algorithm 1(IJCAI-24)

​

​

Our algorithm 2 (IJCAI-24)

​

​

Cost constrained submodular maximization

Variant 1: My Contribution – IJCAI 2024

  • New evolutionary algorithms for Problem 1
  • Improved approximation ratio
  • Improved running time.

Yanhui Zhu, Samik Basu, A. Pavan. "Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints.” In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI'24), pp. 7082-7090, 2024. 

Yanhui Zhu

22 of 34

22

SMC formulates the submodular utility maximization with limited budget.

Maximizing the recommendation quality while minimizing the picture size.

Cost constrained submodular maximization

Discussion

We maximize

f - c

 

Yanhui Zhu

23 of 34

23

 

 

Regularized Submodular Maximization

Variant 2: Regularized Submodular Maximization

We maximize

f - c

Yanhui Zhu

24 of 34

24

Reference

Approximation

Time Complexity

Jin et al., 2021

​

​

Harshaw et al., 2019

​

​

Our algorithm (CIKM-24)

​

​

  • Efficiency: Faster, only slightly worse than the tight guarantee (Jin et al., 2021).
  • Scalability and Extendability: Can handle the case when f is not submodular, but only weakly submodular or approximately submodular. (Jin et al., 2021 and Harshaw et al., 2019 cannot.)

Regularized Submodular Maximization

Variant 2: My Contribution – CIKM 2024

Yanhui Zhu, Samik Basu, A. Pavan. “Regularized unconstrained weakly submodular maximization.” In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management (CIKM), pp. 3537-3548, 2024.

Yanhui Zhu

25 of 34

25

What if the cost function c is also submodular?

Cost constrained submodular maximization

 

 

Variant 3: Submodular Constraint

Yanhui Zhu

26 of 34

26

Regularized Submodular Maximization

Variant 3: My Contribution – UAI 2023

 

We were the first to study this problem and provide theoretical results.

M. R. Padmanabhan, Yanhui Zhu, Samik Basu, and A. Pavan. “Maximizing submodular functions under submodular constraints." In Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 1618-1627. PMLR, 2023.

Yanhui Zhu

27 of 34

27

 

k-submodular maximization

Variant 4: k-submodular

 

 

 

No type info encoded

Yanhui Zhu

28 of 34

28

 

Variant 4: k-submodular

 

 

 

Type info encoded

 

k - submodular

k-submodular maximization

Yanhui Zhu

29 of 34

29

Give a summary of B pictures that can best represent the entire database, regardless of the kind of the pictures.

Variant 4: My Contributions – UAI 2023

k-submodular maximization

 

Reference

Approximation

Time Complexity

Ohsaka et al., 2015

​

​

Ohsaka et al., 2015

​

​

Our algorithm

(UAI-23)

​

​

Reference

Approximation

Time Complexity

Ohsaka et al., 2015

​

​

Ohsaka et al., 2015

​

​

Our algorithm

(UAI-23)

​

​

Guanyu Nie*,Yanhui Zhu*, Yididiya Y. Nadew, Samik Basu, A. Pavan, and Christopher John Quinn. “Size-constrained k-submodular maximization in near-linear time." In Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 1545-1554. PMLR, 2023.

(*equal contributions - alphabetical order).

total size constraint

individual size constraint

Yanhui Zhu

30 of 34

30

Conclusion

  • We propose to study the constrained submodular optimization problems.
  • We present our theoretical results of the four variants along with their applications.
  • The constrained submodular maximization problems have extensive applications in real-world machine learning tasks.

Yanhui Zhu

31 of 34

31

Algorithms

Submodular optimization

Evolutionary computation

Algorithmic machine learning and fairness

Distributed and parallel algorithms

Applications

Network science

Social network analysis

Reinforcement learning (multi-armed bandit)

Large language models

​

​

Future Research

Electronic Health Record (EHR)

Geo-science (sedimental analysis)

Environmental sciences (net ecosystem carbon exchange)

More data applications (interdisciplinary collaborations)

​

​

Data Science

Introduction

Yanhui Zhu

32 of 34

32

Acknowledgements

  • My advisor: Prof. Pavan Aduri & Prof. Samik Basu.
  • CIKM Conference Program and PhD Symposium Organizers/Chairs.
  • Travel support from Iowa State University.
  • NSF Travel Grant.

Yanhui Zhu

33 of 34

33

Yanhui Zhu

Ph.D. in Computer Science (expected May 2025)

IOWA STATE UNIVERSITY

Research: Algorithms, Machine Learning, Data science.

​

​

​

​

On Job Market for Faculty/PostDocs Positions

Questions

Yanhui Zhu

34 of 34

34

Questions

Yanhui Zhu