More Like this

1. Exploring the Effect of Clustering Algorithms on Sample Average Approximation

   Jacobson, Daniel; Hassan, Menna; Dong, Zhijie S. (January 2021, 2021 Institute of Industrial and Systems Engineers (IISE) Annual Conference & Expo)

   null (Ed.)

   Stochastic Programming (SP) is used in disaster management, supply chain design, and other complex problems. Many of the real-world problems that SP is applied to produce large-size models. It is important but challenging that they are optimized quickly and efficiently. Existing optimization algorithms are limited in capability of solving these larger problems. Sample Average Approximation (SAA) method is a common approach for solving large scale SP problems by using the Monte Carlo simulation. This paper focuses on applying clustering algorithms to the data before the random sample is selected for the SAA algorithm. Once clustered, a sample is randomly selected from each of the clusters instead of from the entire dataset. This project looks to analyze five clustering techniques compared to each other and compared to the original SAA algorithm in order to see if clustering improves both the speed and the optimal solution of the SAA method for solving stochastic optimization problems. 

   more » « less
2. On unifying randomized methods for inverse problems

   https://doi.org/10.1088/1361-6420/acd36e  

   Wittmer, Jonathan; Krishnanunni, C G; Nguyen, Hai V; Bui-Thanh, Tan (June 2023, Inverse Problems)

   N/A (Ed.)

   Abstract This work unifies the analysis of various randomized methods for solving linear and nonlinear inverse problems with Gaussian priors by framing the problem in a stochastic optimization setting. By doing so, we show that many randomized methods are variants of a sample average approximation (SAA). More importantly, we are able to prove a single theoretical result that guarantees the asymptotic convergence for a variety of randomized methods. Additionally, viewing randomized methods as an SAA enables us to prove, for the first time, a single non-asymptotic error result that holds for randomized methods under consideration. Another important consequence of our unified framework is that it allows us to discover new randomization methods. We present various numerical results for linear, nonlinear, algebraic, and PDE-constrained inverse problems that verify the theoretical convergence results and provide a discussion on the apparently different convergence rates and the behavior for various randomized methods. 

   more » « less
3. A Comparative Evaluation of Supervised Machine Learning Classification Techniques for Engineering Design Applications

   https://doi.org/10.1115/1.4044524  

   Sharpe, Conner; Wiest, Tyler; Wang, Pingfeng; Seepersad, Carolyn Conner (December 2019, Journal of Mechanical Design)

   Abstract Supervised machine learning techniques have proven to be effective tools for engineering design exploration and optimization applications, in which they are especially useful for mapping promising or feasible regions of the design space. The design space mappings can be used to inform early-stage design exploration, provide reliability assessments, and aid convergence in multiobjective or multilevel problems that require collaborative design teams. However, the accuracy of the mappings can vary based on problem factors such as the number of design variables, presence of discrete variables, multimodality of the underlying response function, and amount of training data available. Additionally, there are several useful machine learning algorithms available, and each has its own set of algorithmic hyperparameters that significantly affect accuracy and computational expense. This work elucidates the use of machine learning for engineering design exploration and optimization problems by investigating the performance of popular classification algorithms on a variety of example engineering optimization problems. The results are synthesized into a set of observations to provide engineers with intuition for applying these techniques to their own problems in the future, as well as recommendations based on problem type to aid engineers in algorithm selection and utilization. 

   more » « less
4. Implicit Convex Regularizers of CNN Architectures: Convex Optimization of Two- and Three-Layer Networks in Polynomial Time

   Ergen, Tolga; Pilanci, Mert (January 2021, International Conference on Learning Representations (ICLR) 2021)

   We study training of Convolutional Neural Networks (CNNs) with ReLU activations and introduce exact convex optimization formulations with a polynomial complexity with respect to the number of data samples, the number of neurons, and data dimension. More specifically, we develop a convex analytic framework utilizing semi-infinite duality to obtain equivalent convex optimization problems for several two- and three-layer CNN architectures. We first prove that two-layer CNNs can be globally optimized via an `2 norm regularized convex program. We then show that multi-layer circular CNN training problems with a single ReLU layer are equivalent to an `1 regularized convex program that encourages sparsity in the spectral domain. We also extend these results to three-layer CNNs with two ReLU layers. Furthermore, we present extensions of our approach to different pooling methods, which elucidates the implicit architectural bias as convex regularizers. 

   more » « less
5. Algorithmic Collusion Without Threats

   https://doi.org/10.4230/LIPIcs.ITCS.2025.10  

   Arunachaleswaran, Eshwar Ram; Collina, Natalie; Kannan, Sampath; Roth, Aaron; Ziani, Juba (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   There has been substantial recent concern that automated pricing algorithms might learn to collude Supra-competitive prices can emerge as a Nash equilibrium of repeated pricing games, in which sellers play strategies which threaten to punish their competitors if they ever defect from a set of supra-competitive prices, and these strategies can be automatically learned. But threats are anti-competitive on their face. In fact, a standard economic intuition is that supra-competitive prices emerge from either the use of threats, or a failure of one party to correctly optimize their payoff. Is this intuition correct? Would explicitly preventing threats in algorithmic decision-making prevent supra-competitive prices when sellers are optimizing for their own revenue? No. We show that supra-competitive prices can robustly emerge even when both players are using algorithms which do not explicitly encode threats, and which optimize for their own revenue. Since deploying an algorithm is a form of commitment, we study sequential Bertrand pricing games (and a continuous variant) in which a first mover deploys an algorithm and then a second mover optimizes within the resulting environment. We show that if the first mover deploys any algorithm with a no-regret guarantee, and then the second mover even approximately optimizes within this now static environment, monopoly-like prices arise. The result holds for any no-regret learning algorithm deployed by the first mover and for any pricing policy of the second mover that obtains them profit at least as high as a random pricing would - and hence the result applies even when the second mover is optimizing only within a space of non-responsive pricing distributions which are incapable of encoding threats. In fact, there exists a set of strategies, neither of which explicitly encode threats that form a Nash equilibrium of the simultaneous pricing game in algorithm space, and lead to near monopoly prices. This suggests that the definition of algorithmic collusion; may need to be expanded, to include strategies without explicitly encoded threats. 

   more » « less