RIFLE: Robust Inference and Imputation
From Low Order Marginals
Sina Baharlouei
Daniel J. Epstein Department of Industrial and Systems Engineering

Kelechi Ogudu

Peng Dai

Sze-chuan Suen

Meisam Razaviyayn

Prevalence of Missing Values in Data-driven Tasks➢ Blank answers in questionnaires➢ Limitations of data gathering

1Prevalence of Missing Values in Data-driven Tasks➢ Blank answers in questionnaires➢ Limitations of data gathering

1Prevalence of Missing Values in Data-driven Tasks➢ Blank answers in questionnaires➢ Limitations of data gathering

1Prevalence of Missing Values in Data-driven Tasks➢ Blank answers in questionnaires➢ Limitations of data gathering➢ Blocks of missing values after merging different datasets➢ Related studies from different labs
1

Existing Approaches for Supervised Learning in the Presence of Missing Data

➢ Removing the rows containing missing entries➢ Losing information

2

Existing Approaches for Supervised Learning in the Presence of Missing Data

➢ Removing the rows containing missing entries➢ Losing information➢ Imputation and then prediction➢ Mean/Median imputation➢ Expectation Maximization [Little and Rubin, 1977]➢ KNN Imputer [Troyanskaya et al., 2001]➢ MissForest [Stekhoven et al., 2012]➢ Generative Adversarial Imputation Nets (GAIN) [Yoon et al., 2018]➢ The imputation error propagates to the prediction phase2

Existing Approaches for Supervised Learning in the Presence of Missing Data

➢ Removing the rows containing missing entries➢ Losing information➢ Imputation and then prediction➢ Mean/Median imputation➢ Expectation Maximization [Little and Rubin, 1977]➢ KNN Imputer [Troyanskaya et al., 2001]➢ MissForest [Stekhoven et al., 2012]➢ Generative Adversarial Imputation Nets (GAIN) [Yoon et al., 2018]➢ The imputation error propagates to the prediction phase➢ Prediction without imputation➢ Robust Optimization over uncertainty sets2

Robust Inference without Imputation➢ Prior Work: robustness over uncertainty sets around data points [Xu et al., 2009]3

Robust Inference without Imputation➢ Prior Work: robustness over uncertainty sets around data points [Xu et al., 2009]➢ Too many hyper-parameters (one per data point!)

3

Robust Inference without Imputation➢ Prior Work: robustness over uncertainty sets around data points [Xu et al., 2009]➢ Too many hyper-parameters (one per data point!)➢ Our Idea: Estimating first (mean) and second-order (covariance matrix) moments ofthe data distribution based on the available data3

Robust Inference without Imputation➢ Prior Work: robustness over uncertainty sets around data points [Xu et al., 2009]➢ Too many hyper-parameters (one per data point!)➢ Our Idea: Estimating first (mean) and second-order (covariance matrix) moments ofthe data distribution based on the available data3

Robust Inference without Imputation➢ Prior Work: robustness over uncertainty sets around data points [Xu et al., 2009]➢ Too many hyper-parameters (one per data point!)➢ Our Idea: Estimating first (mean) and second-order (covariance matrix) moments ofthe data distribution based on the available data3

Robust Inference without Imputation➢ Prior Work: robustness over uncertainty sets around data points [Xu et al., 2009]➢ Too many hyper-parameters (one per data point!)➢ Our Idea: Estimating first (mean) and second-order (covariance matrix) moments ofthe data distribution based on the available data3

Robust Inference without Imputation➢ Prior Work: robustness over uncertainty sets around data points [Xu et al., 2009]➢ Too many hyper-parameters (one per data point!)➢ Our Idea: Estimating first (mean) and second-order (covariance matrix) moments ofthe data distribution based on the available data3

Robust Inference without Imputation➢ Prior Work: robustness over uncertainty sets around data points [Xu et al., 2009]➢ Too many hyper-parameters (one per data point!)➢ Our Idea: Estimating first (mean) and second-order (covariance matrix) moments ofthe data distribution based on the available data3

Robust Inference without Imputation➢ Prior Work: robustness over uncertainty sets around data points [Xu et al., 2009]➢ Too many hyper-parameters (one per data point!)➢ Our Idea: Estimating first (mean) and second-order (covariance matrix) moments ofthe data distribution based on the available data

3

RIFLE: Robust Inference without Imputation

4

RIFLE: Robust Inference without Imputation➢ Estimations can be inaccurate for low-sample, high-dimensional, and/or datasets with alarge proportion of missing values

4

RIFLE: Robust Inference without Imputation➢ Estimations can be inaccurate for low-sample, high-dimensional, and/or datasets with alarge proportion of missing values➢ Estimating confidence intervals for first and second order moments using bootstrap

4

RIFLE: Robust Inference without Imputation➢ Estimations can be inaccurate for low-sample, high-dimensional, and/or datasets with alarge proportion of missing values➢ Estimating confidence intervals for first and second order moments using bootstrap➢ Solving a distributionally robust optimization over estimated confidence intervals

4

RIFLE: Robust Inference without Imputation➢ Estimations can be inaccurate for low-sample, high-dimensional, and/or datasets with alarge proportion of missing values➢ Estimating confidence intervals for first and second order moments using bootstrap➢ Solving a distributionally robust optimization over estimated confidence intervals

4

RIFLE: Robust Inference without Imputation➢ Estimations can be inaccurate for low-sample, high-dimensional, and/or datasets with alarge proportion of missing values➢ Estimating confidence intervals for first and second order moments using bootstrap➢ Solving a distributionally robust optimization over estimated confidence intervals➢ The proposed min-max problem is intractable in general.

4Distributionally Robust Ridge Regression

5Distributionally Robust Ridge Regression➢ Expanding the objective function leads to:5Distributionally Robust Ridge Regression➢ Expanding the objective function leads to:➢ How can we solve this problem efficiently?

5

First Idea for Solving the Robust Ridge Regression

6

First Idea for Solving the Robust Ridge Regression➢ Using Danskin’s theorem, applying gradient descent to6

First Idea for Solving the Robust Ridge Regression➢ Using Danskin’s theorem, applying gradient descent to➢ No closed-form for6

First Idea for Solving the Robust Ridge Regression➢ Using Danskin’s theorem, applying gradient descent to➢ No closed-form for6

First Idea for Solving the Robust Ridge Regression➢ Using Danskin’s theorem, applying gradient descent to➢ No closed-form for➢ Observation: the problem is convex-concave with convex constraints

6

Finding an Efficient Practical Solver

7

Finding an Efficient Practical Solver

7

Finding an Efficient Practical Solver

7

Finding an Efficient Practical Solver

7

Finding an Efficient Practical Solver➢ The minimization problem has a closed-form solution

7

Finding an Efficient Practical Solver➢ The minimization problem has a closed-form solution➢ Applying projected gradient ascent on

leads to:7

Finding an Efficient Practical Solver➢ The minimization problem has a closed-form solution➢ Applying projected gradient ascent on

leads to:7

Finding an Efficient Practical Solver➢ The minimization problem has a closed-form solution➢ Applying projected gradient ascent on

leads to:How to perform both projections?

7

An Alternative Approach for Projected Gradient Ascent➢ How to handle the joint projection to the set of box constraints and the PSD cone?

8

An Alternative Approach for Projected Gradient Ascent➢ How to handle the joint projection to the set of box constraints and the PSD cone?
➢ Removing the PSD constraint in the implementation (relaxation)

8

An Alternative Approach for Projected Gradient Ascent➢ How to handle the joint projection to the set of box constraints and the PSD cone?
➢ Removing the PSD constraint in the implementation (relaxation)➢ Idea: Using the dual formulation on the inner maximization problem

8

An Alternative Approach for Projected Gradient Ascent➢ How to handle the joint projection to the set of box constraints and the PSD cone?
➢ Removing the PSD constraint in the implementation (relaxation)➢ Idea: Using the dual formulation on the inner maximization problem

Writing the dual of inner maximization problem

8

An Alternative Approach for Projected Gradient Ascent➢ How to handle the joint projection to the set of box constraints and the PSD cone?
➢ Removing the PSD constraint in the implementation (relaxation)➢ Idea: Using the dual formulation on the inner maximization problem

Writing the dual of inner maximization problem

8Change of Variables

9Change of Variables9

Change of Variables

9Applying ADMM to the Dual Problem

10Applying ADMM to the Dual Problem➢ Defining two blocks of variables

10Applying ADMM to the Dual Problem➢ Defining two blocks of variables

10Applying ADMM to the Dual Problem➢ Defining two blocks of variables

10Applying ADMM to the Dual Problem➢ Defining two blocks of variables

10

RIFLE Consistency➢ Jointly normal dataset with linear relation between the predictors and the target➢ 40% missing values and 100 features➢ Changing the number of samples from 100 to 5 Million
11How Many Times RIFLE Outperforms All Existing Packages?

12How Many Times RIFLE Outperforms All Existing Packages?

➢ RIFLE wins more than the best imputer packages
12How Many Times RIFLE Outperforms All Existing Packages?

➢ RIFLE wins more than the best imputer packages
12

RIFLE Outperforms Other Algorithms for Lower Samples➢ Evaluation on Drive dataset (40% missing values completely at random)
MissForest: Stekhoven, Daniel J., and Peter Bühlmann. "MissForest: non-parametric missing value imputation for mixed-type data." Bioinformatics 28, (2012).
MICE: Royston, Patrick, and Ian R. White. "Multiple imputation by chained equations (MICE): implementation in Stata." Journal of statistical software 45 (2011).

Mean Imputer: Little, Roderick JA, and Donald B. Rubin. Statistical analysis with missing data. Vol. 793. John Wiley & Sons, (2019).
KNN Imputer: Troyanskaya, Olga et al., "Missing value estimation methods for DNA microarrays." Bioinformatics 17 (2001).
MIDA: Gondara, Lovedeep, and Ke Wang. "Mida: Multiple imputation using denoising autoencoders." In PKDD (2018).
Amelia: Honaker, James, Gary King, and Matthew Blackwell. "Amelia II: A program for missing data." Journal of statistical software 45 (2011).

13

Reference➢ Sina Baharlouei, Kelechi Ogudu, Peng Dai, Sze-chuan Suen and Meisam Razaviyayn. “RIFLE: Imputation
and Robust Inference from Low Order Marginals" In ICML Workshop on Duality Principles for Modern
Machine Learning, 2023.

➢ RIFLE Package: https://github.com/optimization-for-data-driven-science/RIFLE.

14