Sitemap

A list of all the posts and pages found on the site. For you robots out there is an XML version available for digesting as well.

Page Not Found

Page not found. Your pixels are in another canvas.

Jupyter notebook markdown generator

Posts

Future Blog Post

less than 1 minute read

Published: January 01, 2199

This post will show up by default. To disable scheduling of future posts, edit config.yml and set future: false.

Blog Post number 4

less than 1 minute read

Published: August 14, 2015

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

Blog Post number 3

less than 1 minute read

Published: August 14, 2014

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

Blog Post number 2

less than 1 minute read

Published: August 14, 2013

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

Blog Post number 1

less than 1 minute read

Published: August 14, 2012

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

portfolio

Portfolio item number 1

Short description of portfolio item number 1

Portfolio item number 2

Short description of portfolio item number 2

publications

On the Structure of Cardinality-Constrained Assortment Optimization

Published in , 2017

We study the static assortment optimization problem with cardinality constraints, i.e., the problem of offering an assortment of items of constrained size that will maximize expected revenue. This is generally regarded as a challenging problem, with identified hardness results in the existing literature for a number of popular and/or well-studied choice models. Motivated by existing approaches in the unconstrained setting that find successful exploitation of identified structure to devise either exact or approximate solution methods, we introduce another structural property of possible interest for study in the cardinality constrained setting. Recently, the work of Jagabathula (2016) has identified the optimality of a local search method for the cardinality constrained static assortment problem under Multinomial Logit (MNL) Choice, making MNL a rare case study of tractability among cardinality constrained problems. So we first revisit the MNL constrained assortment problem under a new lens in search of structure that explains its “tractability.” Following this, we study the extent to which this property holds in other choice models. Indeed, we find that local search is optimal for some other choice models, and remains so even under more generalized cardinality constraints. Finally, we provide and test some algorithms (which require black-box access to the expected revenue function) that can be applied to the joint assortment and pricing problem under certain choice models, showing favorable performance small to moderate-sized problems against some current approaches.

Recommended citation: Louis Chen, David Simchi-Levi. (2017). "On the Structure of Cardinality-Constrained Assortment Optimization." https://www.dropbox.com/s/tbpw3ig9vzrl3xw/AssortmentPaper.pdf?dl=0

Distributionally Robust Max Flows with Marginals

Published in Symposium on Simplicity in Algorithms (S0SA 2020), 2020

Consider an s-t flow network in which the arc capacities are distributed according to an unknown distribution, but with known marginals. We study the problem of finding a coupling of the marginals that yields the worst, expected Max-flow value. Towards solving this optimization problem, we identify a primal-dual formulation. As one might expect, the form relates to the well-known Max Flow, Min-Cut theorem. And this leads to the rather intriguing interpretation as a 2-player, zero-sum game wherein player 1 chooses what to set the arc capacities to and player 2 chooses an s-t cut. Our contributions in this talk are twofold: (1) we present a linear program (that is efficient with finite-supported marginals) that not only computes the worst-case expected value but is of a form amenable in a two-stage network design formulation, and (2) we show that the problem of finding the worst-case coupling of the stochastic arc capacities boils down to finding an optimal distribution over the set of s-t cuts, which we show can be found efficiently.

Recommended citation: Louis Chen, Will Ma, James Orlin, David Simchi-Levi. (2020). "Distributionally Robust Max Flows with Marginals." SOSA 2020. 1(2). https://www.dropbox.com/s/z59207hnz3iihi0/ltexpprt.pdf?dl=0

Correlation Robust Influence Maximization

Published in Thirty-fourth Annual Conference on Neural Information Processing Systems (NeurIPS 2020), 2020

We propose a distributionally robust model for the influence maximization problem. Unlike the classic independent cascade model [16], this model’s diffusion process is adversarially adapted to the choice of seed set. Hence, instead of optimizing under the assumption that all influence relationships in the network are independent, we seek a seed set whose expected influence under the worst correlation, i.e. the “worst-case, expected influence”, is maximized. We show that this worst-case influence can be efficiently computed, and though the optimization is NP-hard, a (1 − 1/e) approximation guarantee holds. We also analyze the structure to the adversary’s choice of diffusion process, and contrast with established models. Beyond the key computational advantages, we also highlight the extent to which the independence assumption may cost optimality, and provide insights from numerical experiments comparing the adversarial and independent cascade model.

Recommended citation: Louis Chen, Divya Padmanabhan, Chee Chin Lim, Karthik Natarajan (2020). " Correlation Robust Influence Maximization." . https://papers.nips.cc/paper/2020/file/4ee78d4122ef8503fe01cdad3e9ea4ee-Paper.pdf

Distributionally Robust Linear and Discrete Optimization with Marginals

Published in Operations Research, 2021

In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to be specified up to only the marginal distributions. We generalize the primal-dual formulations for this problem from the set of joint distributions with absolutely continuous marginal distributions to arbitrary marginal distributions using techniques from optimal transport theory. While the robust bound is shown to be NP-hard to compute for linear optimization problems, we identify a sufficient condition for polynomial time solvability using extended formulations. This generalizes the known tractability results under marginal information from 0-1 polytopes to a class of integral polytopes and has implications on the solvability of distributionally robust optimization problems in areas such as scheduling which we discuss.

Recommended citation: Louis Chen, Will Ma, Karthik Natarajan, David Simchi-Levi, Zhenzhen Yan. (2021). "Distributionally Robust Linear and Discrete Optimization with Marginals." Operations Research. https://pubsonline.informs.org/doi/10.1287/opre.2021.2243

Robustness to Dependency in Influence Maximization

Published in Management Science, 2024

In this paper, we introduce a correlation robust model for the influence maximization problem. Unlike the classic independent cascade model, this model’s diffusion process is adversarially adapted to the choice of seed set. More precisely, rather than only the in- dependent coupling of known individual edge probabilities, we now evaluate a seed set’s expected influence under all possible correlations - specifically, the one that presents the worst-case. We show that any seed set’s worst-case expected influence can be efficiently computed, and though optimizing the worst-case (over seed sets) is NP-hard, a (1 − 1/e) approximation algorithm can be obtained. We provide structural insights from the model and contrast it with the independent cascade model. We discuss how the proposed model can be extended to optimize other objectives by controlling for conservatism using a mix- ture of the independent and the worst-case distribution or by incorporating risk criterion in choosing the seed set. Finally we provide insights from numerical experiments to illustrate the usefulness of the model.

Recommended citation: Louis Chen, Chee Chin Lim, Divya Padmanabhan, Karthik Natarajan (2024). "Robustness to Dependency in Influence Maximization." . https://pubsonline.informs.org/doi/10.1287/mnsc.2021.03445

Rockafellian Relaxation and Stochastic Optimization under Perturbations

Published in Mathematics of Operations Research, 2024

In practice, optimization models are often prone to unavoidable inaccuracies due to lack of data and dubious assumptions. Traditionally, this placed special emphasis on risk-based and robust formulations, and their focus on “conservative” decisions. We develop, in contrast, an “optimistic” framework based on Rockafellian relaxations in which optimization is conducted not only over the original decision space but also jointly with a choice of model perturbation. The framework enables us to address challenging problems with ambiguous probability distributions from the areas of two-stage stochastic optimization without relatively complete recourse, probability functions lacking continuity properties, expectation constraints, and outlier analysis. We are also able to circumvent the fundamental difficulty in stochastic optimization that convergence of distributions fails to guarantee convergence of expectations. The framework centers on the novel concepts of exact and asymptotically exact Rockafellians, with interpretations of “negative” regularization emerging in certain settings. We illustrate the role of Phi-divergence, examine rates of convergence under changing distributions, and explore extensions to first-order optimality conditions. The main development is free of assumptions about convexity, smoothness, and even continuity of objective functions.

Recommended citation: Johannes Royset, Louis Chen, Eric Eckstrand (2024). "Rockafellian Relaxation and Stochastic Optimization under Perturbations." https://pubsonline.informs.org/doi/full/10.1287/moor.2022.0122

On the Adversarial Robustness of Benjamini Hochberg

Published in Thirty-Eighth Annual Conference on Neural Information Processing (NeurIPS 2024), 2024

The Benjamini-Hochberg (BH) procedure is widely used to control the false detection rate (FDR) in multiple testing. Applications of this control abound in drug discovery, forensics, anomaly detection, and, in particular, machine learning, ranging from nonparametric outlier detection to out-of-distribution detection and one-class classification methods. Considering this control could be relied upon in critical safety/security contexts, we investigate its adversarial robustness. More precisely, we study under what conditions BH does and does not exhibit adversarial robustness, we present a class of simple and easily implementable adversarial test-perturbation algorithms, and we perform computational experiments. With our algorithms, we demonstrate that there are conditions under which BH control can be significantly broken with relatively few (even just one) test score perturbation(s), and provide non-asymptotic guarantees on the expected adversarial-adjustment to FDR. Our technical analysis involves a combinatorial reframing of the BH procedure as a balls into bins process, and drawing a connection to generalized ballot problems to facilitate an information-theoretic approach for deriving non-asymptotic lower bounds.

Recommended citation: Louis Chen, Roberto Szechtman, Matan Seri (2024). "On the Adversarial Robustness of Benjamini Hochberg." https://neurips.cc/

talks

On the Structure of Cardinality Constrained Assortment Optimization

Published: November 15, 2016

Cardinality-Constrained assortment optimization, the problem of offering an assortment of items of constrained size that will maximize expected revenue, is generally regarded as a challenging problem. We provide a new perspective to the structural analysis, one that illuminates the optimality of “greedy solutions.” The approach reinterprets some known results for standard choice models but also provides some new ones as well.

Revisiting the Marginal Distribution Model: Extensions and Generalizations.

Published: July 20, 2017

Revisiting the Marginal Distribution Model: Extensions and Generalizations

Published: October 23, 2017

Distributionally Robust Linear and Discrete Optimization with Marginals

Published: July 05, 2018

We study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to be specified up to only the marginal distributions. We provide a primal-dual formulation for this problem. Though the robust bound is NP-hard, we identify a sufficient condition for polynomial time solvability using extended formulations. This generalizes the known tractability results under marginal information from 0-1 polytopes to a class of integral polytopes and has implications on the solvability of distributionally robust optimization problems in areas such as scheduling which we discuss. We present the Distributionally Robust Max-Flow problem to illustrate our theoretical results.

Distributionally Robust Max Flow

Published: November 06, 2018

In this talk, we consider the problem of distributionally robust network design. In this problem, the decision maker is to decide on the prepositioning of resources on arcs in a given s-t flow network in anticipation of an adversary’s selection of a probability distribution for the arc capacities, aimed to minimize the expected max flow. The adversary’s selection is limited to those distributions that are couplings of given arc capacity distributions, one for each arc. We show that we can efficiently solve the distributionally robust network design problem in the case of finite-supported marginals. Further, we take advantage of the network setting to efficiently solve for the distribution the adversary responds with. The primal-dual formulation of our previous work takes on a striking form in this study. As one might expect, the form relates to the well-known Max Flow, Min-Cut theorem. And this leads to the intriguing interpretation as a 2-player, zero-sum game wherein player 1 chooses what to set the arc capacities to and player 2 chooses an s-t cut. Essential to our analysis is the finding that the problem of finding the worst-case coupling of the stochastic arc capacities amounts to finding a distribution over the set of s-t cuts- this distribution being among the mixed strategies that player 2 would play in a Nash equilibrium. Furthermore, the support of such a distribution is a nested collection of s-t cuts, which implies an efficiently sized solution.

Distributionally Robust Optimal Omnichannel Stocking Decisions in Quick Fulfilment Systems

Published: July 01, 2019

This work is inspired by the daily operations of Hema supermarket, which is a recently established “new retail” model by Alibaba Group, China. In a Hema supermarket store, a single SKU may be presented with demand in the form of multiple channels. The challenge facing Hema is the question of how many units to stock in total between the warehouse and the store-front in advance of uncertain demand that arises in several consecutive time frames, each 30 minutes long. In this work, we provide the first distributionally robust optimization study in the setting of omnichannel inventory management, wherein we are to make a stocking decision robust to an adversary’s choice of coupling of available (marginal) demand distributions by channel and by time frame. The adversary’s coupling decision amounts to designing a random mathematical program with equilibrium constraints (MPEC). And we provide both a structural analysis of the adversary’s choice of couplingas well as an efficient procedure to find this coupling. In general, the overall distributionally robust stocking problem is non-concave. We provide sufficient conditions on the cost parameters under which this problem becomes concave, and hence tractable. Finally, we conduct experiments with Hema’s data. In these experiments, we compare and contrast the performance of our distributionally robust solution with the performance of a naive Newsvendor-like solution on various SKUs of varying sales volume and number of channels on a 5-hour time window from 2pm - 7pm on weekends. Numerical experiments show that the distributionally robust solutions generally outperform the stochastic Newsvendor-like solution. Furthermore, and interestingly, in all of our experiments, the distributionally robust inventory decision problems presented by the historical data provided by Hema are in fact concave.

Correlation Robust Influence Maximization

Published: December 06, 2020

We propose and study a distributionally robust influence maximization problem. Unlike the classic Independent Cascade model proposed in Kempe, Kleinberg, and Tardos (2003), we consider a model that involves an adversarial response to the selection of seed set. More precisely, rather than the spread of influence being determined by the independent coupling of random arcs, the spread of influence will be determined by an adversarial coupling of random arcs in response to any selection of seed set. Similarly to traditional stochastic models, the optimization problem remains NP-Hard. However, in contrast, with this newly introduced robust model, both the influence function and any node’s likelihood of being influenced can now be efficiently computed; furthermore, we show that even with an adversarial coupling, the greedy algorithm still guarantees a (1 - 1/e) - approximation of the optimum, as in the Independent Cascade model. Finally, we consider computational comparisons through experiments.