Nam Ho-Nguyen
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Nam Ho-Nguyen has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Fatma Kılınç-Karzan
Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
9 shared publications - Dabeen Lee
Department of Industrial and Systems Engineering KAIST 34141 Daejeon Republic of Korea
5 shared publications - Simge Küçükyavuz
Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208
3 shared publications - David Huckleberry Gutman
Texas A&M University, College Station, United States
2 shared publications - Duksang Lee
Discrete Mathematics Group Institute for Basic Science (IBS) Daejeon South Korea
1 shared publication Fatma Kilinç-Karzan
1 shared publication
Latest Publications
- Open Access
- 5 November 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 213 (1-2) , 907-940
A projection-free method for solving convex bilevel optimization problems
When faced with multiple minima of an inner-level convex optimization problem, the convex bilevel optimization problem selects an optimal solution which also minimizes an auxiliary outer-level convex objective of interest. Bilevel optimization requires a different approach compared to single-level optimization problems since the set of minimizers for the inner-level objective is not given explicitly. In this paper, we propose a new projection-free conditional gradient method for convex bilevel optimization which requires only a linear optimization oracle over the base domain. We establish $$O(t^{-1/2})$$ convergence rate guarantees for our method in terms of both inner- and outer-level objectives, and demonstrate how additional assumptions such as quadratic growth and strong convexity result in accelerated rates of up to $$O(t^{-1})$$ and $$O(t^{-2/3})$$ for inner- and outer-levels respectively. Lastly, we conduct a numerical study to demonstrate the performance of our method.- 5 November 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 213 (1-2) , 907-940
Open AccessA projection-free method for solving convex bilevel optimization problems
When faced with multiple minima of an inner-level convex optimization problem, the convex bilevel optimization problem selects an optimal solution which also minimizes an auxiliary outer-level convex objective of interest. Bilevel optimization requires a different approach compared to single-level optimization problems since the set of minimizers for the inner-level objective is not given explicitly. In this paper, we propose a new projection-free conditional gradient method for convex bilevel optimization which requires only a linear optimization oracle over the base domain. We establish $$O(t^{-1/2})$$ convergence rate guarantees for our method in terms of both inner- and outer-level objectives, and demonstrate how additional assumptions such as quadratic growth and strong convexity result in accelerated rates of up to $$O(t^{-1})$$ and $$O(t^{-2/3})$$ for inner- and outer-levels respectively. Lastly, we conduct a numerical study to demonstrate the performance of our method. - 23 August 2024
- Published by Springer Nature
- p. 1-4
Online Convex Optimization
- Open Access
Non-Smooth, Hölder-Smooth, and Robust Submodular Maximization
We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an $[(1-1/e)\OPT-\epsilon]$ guarantee when the function is monotone and H\"older-smooth, meaning that it admits a H\"older-continuous gradient. For functions that are non-differentiable or non-smooth, we propose a variant of the mirror-prox algorithm that attains an $[(1/2)\OPT-\epsilon]$ guarantee. We apply our algorithmic frameworks to robust submodular maximization and distributionally robust submodular maximization under Wasserstein ambiguity. In particular, the mirror-prox method applies to robust submodular maximization to obtain a single feasible solution whose value is at least $(1/2)\OPT-\epsilon$. For distributionally robust maximization under Wasserstein ambiguity, we deduce and work over a submodular-convex maximin reformulation whose objective function is H\"older-smooth, for which we may apply both the continuous greedy and the mirror-prox algorithms.Open AccessNon-Smooth, Hölder-Smooth, and Robust Submodular Maximization
We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an $[(1-1/e)\OPT-\epsilon]$ guarantee when the function is monotone and H\"older-smooth, meaning that it admits a H\"older-continuous gradient. For functions that are non-differentiable or non-smooth, we propose a variant of the mirror-prox algorithm that attains an $[(1/2)\OPT-\epsilon]$ guarantee. We apply our algorithmic frameworks to robust submodular maximization and distributionally robust submodular maximization under Wasserstein ambiguity. In particular, the mirror-prox method applies to robust submodular maximization to obtain a single feasible solution whose value is at least $(1/2)\OPT-\epsilon$. For distributionally robust maximization under Wasserstein ambiguity, we deduce and work over a submodular-convex maximin reformulation whose objective function is H\"older-smooth, for which we may apply both the continuous greedy and the mirror-prox algorithms. - 1 April 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Optimization
- Vol. 5 (2) , 211-232
Strong Formulations for Distributionally Robust Chance-Constrained Programs with Left-Hand Side Uncertainty Under Wasserstein Ambiguity
Distributionally robust chance-constrained programs (DR-CCPs) over Wasserstein ambiguity sets exhibit attractive out-of-sample performance and admit big-M–based mixed-integer programming reformulations with conic constraints. However, the resulting formulations often suffer from scalability issues as problem size increases. To address this shortcoming, we derive stronger formulations that scale well with respect to the problem size. Our focus is on ambiguity sets under the so-called left-hand side uncertainty, where the uncertain parameters affect the coefficients of the decision variables in the linear inequalities defining the safety sets. The interaction between the uncertain parameters and the variable coefficients in the safety set definition causes challenges in strengthening the original big-M formulations. By exploiting the connection between nominal chance-constrained programs and DR-CCP, we obtain strong formulations with significant enhancements. In particular, through this connection, we derive a linear number of valid inequalities, which can be immediately added to the formulations to obtain improved formulations in the original space of variables. In addition, we suggest a quantile-based strengthening procedure that allows us to reduce the big-M coefficients drastically. Furthermore, based on this procedure, we propose an exponential class of inequalities that can be separated efficiently within a branch-and-cut framework. The quantile-based strengthening procedure can be expensive. Therefore, for the special case of covering and packing type problems, we identify an efficient scheme to carry out this procedure. We demonstrate the computational efficacy of our proposed formulations on two classes of problems, namely stochastic portfolio optimization and resource planning. Funding: This work was supported by the DARPA Lagrange Program [Grant N660011824020], the National Science Foundation [Grant 1740707], the Office of Naval Research [Grant N00014-19-1-2321], and the Institute for Basic Science [Grants IBS-R029-C1 and IBS-R029-Y2].
- 1 April 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Optimization
- Vol. 5 (2) , 211-232
Strong Formulations for Distributionally Robust Chance-Constrained Programs with Left-Hand Side Uncertainty Under Wasserstein Ambiguity
Distributionally robust chance-constrained programs (DR-CCPs) over Wasserstein ambiguity sets exhibit attractive out-of-sample performance and admit big-M–based mixed-integer programming reformulations with conic constraints. However, the resulting formulations often suffer from scalability issues as problem size increases. To address this shortcoming, we derive stronger formulations that scale well with respect to the problem size. Our focus is on ambiguity sets under the so-called left-hand side uncertainty, where the uncertain parameters affect the coefficients of the decision variables in the linear inequalities defining the safety sets. The interaction between the uncertain parameters and the variable coefficients in the safety set definition causes challenges in strengthening the original big-M formulations. By exploiting the connection between nominal chance-constrained programs and DR-CCP, we obtain strong formulations with significant enhancements. In particular, through this connection, we derive a linear number of valid inequalities, which can be immediately added to the formulations to obtain improved formulations in the original space of variables. In addition, we suggest a quantile-based strengthening procedure that allows us to reduce the big-M coefficients drastically. Furthermore, based on this procedure, we propose an exponential class of inequalities that can be separated efficiently within a branch-and-cut framework. The quantile-based strengthening procedure can be expensive. Therefore, for the special case of covering and packing type problems, we identify an efficient scheme to carry out this procedure. We demonstrate the computational efficacy of our proposed formulations on two classes of problems, namely stochastic portfolio optimization and resource planning. Funding: This work was supported by the DARPA Lagrange Program [Grant N660011824020], the National Science Foundation [Grant 1740707], the Office of Naval Research [Grant N00014-19-1-2321], and the Institute for Basic Science [Grants IBS-R029-C1 and IBS-R029-Y2].
- 2 February 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 48 (1) , 127-159
Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds
We extend coordinate descent to manifold domains and provide convergence analyses for geodesically convex and nonconvex smooth objective functions. Our key insight is to draw an analogy between coo...
- 2 February 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 48 (1) , 127-159
Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds
We extend coordinate descent to manifold domains and provide convergence analyses for geodesically convex and nonconvex smooth objective functions. Our key insight is to draw an analogy between coo...
- 1 December 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 68 (12) , 8680-8698
Risk Guarantees for End-to-End Prediction and Optimization Processes
Prediction methods are often employed to estimate parameters of optimization models. Although the goal in an end-to-end framework is to achieve good performance on the subsequent optimization model, a formal understanding of the ways in which prediction methods can affect optimization performance is notably lacking. This paper identifies conditions on prediction methods that can guarantee good optimization performance. We provide two types of results: asymptotic guarantees under a well-known Fisher consistency criterion and nonasymptotic performance bounds under a more stringent criterion. We use these results to analyze optimization performance for several existing prediction methods and show that in certain settings, methods tailored to the optimization problem can fail to guarantee good performance. Conversely, optimization-agnostic methods can sometimes, surprisingly, have good guarantees. In a computational study on portfolio optimization, fractional knapsack, and multiclass classification problems, we compare the optimization performance of several prediction methods. We demonstrate that lack of Fisher consistency of the prediction method can indeed have a detrimental effect on performance. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by the National Science Foundation, Division of Civil, Mechanical and Manufacturing Innovation [Grant 1454548]. Supplemental Material: Data and the e-companion are available at https://doi.org/10.1287/mnsc.2022.4321 .
- 1 December 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 68 (12) , 8680-8698
Risk Guarantees for End-to-End Prediction and Optimization Processes
Prediction methods are often employed to estimate parameters of optimization models. Although the goal in an end-to-end framework is to achieve good performance on the subsequent optimization model, a formal understanding of the ways in which prediction methods can affect optimization performance is notably lacking. This paper identifies conditions on prediction methods that can guarantee good optimization performance. We provide two types of results: asymptotic guarantees under a well-known Fisher consistency criterion and nonasymptotic performance bounds under a more stringent criterion. We use these results to analyze optimization performance for several existing prediction methods and show that in certain settings, methods tailored to the optimization problem can fail to guarantee good performance. Conversely, optimization-agnostic methods can sometimes, surprisingly, have good guarantees. In a computational study on portfolio optimization, fractional knapsack, and multiclass classification problems, we compare the optimization performance of several prediction methods. We demonstrate that lack of Fisher consistency of the prediction method can indeed have a detrimental effect on performance. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by the National Science Foundation, Division of Civil, Mechanical and Manufacturing Innovation [Grant 1454548]. Supplemental Material: Data and the e-companion are available at https://doi.org/10.1287/mnsc.2022.4321 .
- 13 October 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 198 (2) , 1519-1582
An online convex optimization-based framework for convex bilevel optimization
- 13 October 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 198 (2) , 1519-1582
An online convex optimization-based framework for convex bilevel optimization
- 16 June 2022
- Published by Elsevier in Operations Research Letters
- Vol. 50 (5) , 458-462
Cyclic coordinate descent in the Hölder smooth setting
- 16 June 2022
- Published by Elsevier in Operations Research Letters
- Vol. 50 (5) , 458-462
Cyclic coordinate descent in the Hölder smooth setting
- Open Access
- 5 April 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 198 (2) , 1411-1447
Adversarial classification via distributional robustness with Wasserstein ambiguity
We study a model for adversarial classification based on distributionally robust chance constraints. We show that under Wasserstein ambiguity, the model aims to minimize the conditional value-at-risk of the distance to misclassification, and we explore links to adversarial classification models proposed earlier and to maximum-margin classifiers. We also provide a reformulation of the distributionally robust model for linear classification, and show it is equivalent to minimizing a regularized ramp loss objective. Numerical experiments show that, despite the nonconvexity of this formulation, standard descent methods appear to converge to the global minimizer for this problem. Inspired by this observation, we show that, for a certain class of distributions, the only stationary point of the regularized ramp loss minimization problem is the global minimizer.
- 5 April 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 198 (2) , 1411-1447
Open AccessAdversarial classification via distributional robustness with Wasserstein ambiguity
We study a model for adversarial classification based on distributionally robust chance constraints. We show that under Wasserstein ambiguity, the model aims to minimize the conditional value-at-risk of the distance to misclassification, and we explore links to adversarial classification models proposed earlier and to maximum-margin classifiers. We also provide a reformulation of the distributionally robust model for linear classification, and show it is equivalent to minimizing a regularized ramp loss objective. Numerical experiments show that, despite the nonconvexity of this formulation, standard descent methods appear to converge to the global minimizer for this problem. Inspired by this observation, we show that, for a certain class of distributions, the only stationary point of the regularized ramp loss minimization problem is the global minimizer.
- Open Access
Political districting without geography
Geographical considerations such as contiguity and compactness are necessary elements of political districting in practice. Yet an analysis of the problem without such constraints yields mathematical insights that can inform real-world model construction. In particular, it clarifies the sharp contrast between proportionality and competitiveness and how it might be overcome in a properly formulated objective function. It also reveals serious weaknesses of the much-discussed efficiency gap as a criterion for gerrymandering.
Open AccessPolitical districting without geography
Geographical considerations such as contiguity and compactness are necessary elements of political districting in practice. Yet an analysis of the problem without such constraints yields mathematical insights that can inform real-world model construction. In particular, it clarifies the sharp contrast between proportionality and competitiveness and how it might be overcome in a properly formulated objective function. It also reveals serious weaknesses of the much-discussed efficiency gap as a criterion for gerrymandering.