News & EventsDepartment Events
Events
-
Apr2
EVENT DETAILS
Students from the IEMS department will present a seminar based on their award winning papers
AKHIL SINGLA
Title: Optimal Control of Join Decision in Fork-Jon Queues
Abstract: In fork-join (FJ) queues, each incoming job to the system is copied and sent to all its parallel servers. A job is completed when all or some of the copies are processed by parallel servers. These FJ queues are prevalent in diverse domains of service operations like fact-checking for social media platforms, hospital diagnosis operations, legal systems etc. FJ queueing systems can capture the trade-off between speed and accuracy that commonly arises in knowledge-based service systems. In this paper, we study the optimal control of “join decision” in FJ queues. A join decision determines how many copies of a job should be processed before the job leaves the system. We fully characterize the structure of the optimal dynamic join decision policy with respect to the parameters that affect the trade-off between speed and accuracy. To overcome the curse of dimensionality, we propose an intuitive, easy-to-compute and easy-to-implement heuristic policy that uses total number of jobs in the system to make join decision. This heuristic is shown to perform within 2% optimality gap and performs better than some commonly used benchmark policies. The heuristic policy also allows managers to achieve a desired service-level that balances speed and accuracy of the operations.
SHIMA DEZFULIAN
Title: Derivative-Free Bound-Constrained Optimization for Solving Structured Problems with Surrogate Models
Abstract: We propose and analyze a model-based derivative-free (DFO) algorithm for solving bound-constrained optimization problems where the objective function is the composition of a smooth function and a vector of black-box functions. We assume that the black-box functions are smooth and the evaluation of them is the computational bottleneck of the algorithm. The distinguishing feature of our algorithm is the use of approximate function values at interpolation points which can be obtained by an application-specific surrogate model that is cheap to evaluate. As an example, we consider the situation in which a sequence of related optimization problems is solved and present a regression-based approximation scheme that uses function values that were evaluated when solving prior problem instances. In addition, we propose and analyze a new algorithm for obtaining interpolation points that handles unrelaxable bound constraints. Our numerical results show that our algorithm outperforms a state-of-the-art DFO algorithm for solving a least-squares problem from a chemical engineering application when a history of black-box function evaluations is available.
XIAOCHUN NIU
Title: Exact Community Recovery in the Geometric SBM
Abstract: We study the problem of exact community recovery in the Geometric Stochastic Block Model (GSBM), where each vertex has an unknown community label as well as a known position, generated according to a Poisson point process in the d-dimensional euclidean space. Edges are formed independently conditioned on the community labels and positions, where vertices may only be connected by an edge if they are within a prescribed distance of each other. The GSBM thus favors the formation of dense local subgraphs, which commonly occur in real-world networks, a property that makes the GSBM qualitatively very different from the standard Stochastic Block Model (SBM). We propose a linear-time algorithm for exact community recovery, which succeeds down to the information-theoretic threshold, confirming a conjecture of Abbe, Baccelli, and Sankararaman. The algorithm involves two phases. The first phase exploits the density of local subgraphs to propagate estimated community labels among sufficiently occupied subregions, and produces an almost-exact vertex labeling. The second phase then refines the initial labels using a Poisson testing procedure. Thus, the GSBM enjoys local to global amplification just as the SBM, with the advantage of admitting an information-theoretically optimal, linear-time algorithm.
YUCHEN LOU
Title: Noise-Tolerant Optimization Methods for the Solution of a Robust Desing Problem
Abstract: The development of nonlinear optimization algorithms capable of performing reliably in the presence of noise has garnered considerable attention lately. This motivates the questions of whether well-established methods in the literature can be modified to cope with noise, and whether they are applicable in real-world problems. This paper advocates for strategies to create noise-tolerant nonlinear optimization algorithms by adapting classical deterministic methods. These adaptations follow certain design guidelines described in this work, which make use of estimates of the noise level in the problem. The application of our methodology is illustrated by the development of a line search gradient projection method, which is tested on a practical engineering design problem. It is shown that a new self-calibrated line search and noise-aware finite-difference techniques are effective even in the high noise regime. Numerical experiments with a systematic design investigate the resiliency of key algorithmic components. A convergence analysis of the line search gradient projection method establishes convergence to a neighborhood of the solution.
TIME Tuesday, April 2, 2024 at 11:00 AM - 12:00 PM
LOCATION A230, Technological Institute map it
CONTACT Kendall Minta kendall.minta@gmail.com EMAIL
CALENDAR Department of Industrial Engineering and Management Sciences (IEMS)
-
Apr9
EVENT DETAILS
Abstract: Many reinforcement/machine learning problems involve loss minimization, min-max optimization and fixed-point equations, all of which can be cast under the framework of Variational Inequalities (VIs). Stochastic methods like SGD, SEG and TD/Q Learning are prevalent, and their constant stepsize versions have gained popularity due to effectiveness and robustness. Viewing the iterates of these algorithms as a Markov chain, we study their fine-grained probabilistic behavior. In particular, we establish finite-time geometric convergence of the iterates distribution, and relate the ergodicity properties of the Markov chain to the characteristics of the VI, algorithm and data.
Using techniques of coupling and basic adjoint relationship, we characterize the limit distribution and how its bias depends on the stepsize. For smooth problems, exemplified by TD learning and smooth min-max optimization, the bias is proportional to the stepsize. For nonsmooth problems, exemplified by Q-learning and generalized linear model with nonsmooth link functions (e.g., ReLU), the bias has drastically different behavior and scales with the square root of the stepsize.
This precise probabilistic characterization allows for variance reduction via tail-averaging and bias reduction via Richardson-Romberg extrapolation. The combination of constant stepsize, averaging and extrapolation provides a favorable balance between fast mixing and low long-run error, and we demonstrate its effectiveness in statistical inference compared to traditional diminishing stepsize schemes.
Bio: Qiaomin Xie is an assistant professor in the Department of Industrial and Systems Engineering at the University of Wisconsin-Madison. Her research interests lie in the fields of reinforcement learning, applied probability, game theory and stochastic networks, with applications to computer and communication networks. She was previously a visiting assistant professor at School of Operations Research and Information Engineering at Cornell University (2019-2021). Prior to that, she was a postdoctoral researcher with LIDS at MIT. Qiaomin received her Ph.D. in Electrical and Computing Engineering from University of Illinois Urbana-Champaign in 2016. She received her B.S. in Electronic Engineering from Tsinghua University. She is a recipient of NSF CAREER Award, JPMorgan Faculty Research Award, Google Systems Research Award and UIUC CSL PhD Thesis Award.
TIME Tuesday, April 9, 2024 at 11:00 AM - 12:00 PM
LOCATION A230, Technological Institute map it
CONTACT Kendall Minta kendall.minta@gmail.com EMAIL
CALENDAR Department of Industrial Engineering and Management Sciences (IEMS)
-
Apr9
EVENT DETAILS
Abstract: Many reinforcement/machine learning problems involve loss minimization, min-max optimization and fixed-point equations, all of which can be cast under the framework of Variational Inequalities (VIs). Stochastic methods like SGD, SEG and TD/Q Learning are prevalent, and their constant stepsize versions have gained popularity due to effectiveness and robustness. Viewing the iterates of these algorithms as a Markov chain, we study their fine-grained probabilistic behavior. In particular, we establish finite-time geometric convergence of the iterates distribution, and relate the ergodicity properties of the Markov chain to the characteristics of the VI, algorithm and data.
Using techniques of coupling and basic adjoint relationship, we characterize the limit distribution and how its bias depends on the stepsize. For smooth problems, exemplified by TD learning and smooth min-max optimization, the bias is proportional to the stepsize. For nonsmooth problems, exemplified by Q-learning and generalized linear model with nonsmooth link functions (e.g., ReLU), the bias has drastically different behavior and scales with the square root of the stepsize.
This precise probabilistic characterization allows for variance reduction via tail-averaging and bias reduction via Richardson-Romberg extrapolation. The combination of constant stepsize, averaging and extrapolation provides a favorable balance between fast mixing and low long-run error, and we demonstrate its effectiveness in statistical inference compared to traditional diminishing stepsize schemes.
Bio: Qiaomin Xie is an assistant professor in the Department of Industrial and Systems Engineering at the University of Wisconsin-Madison. Her research interests lie in the fields of reinforcement learning, applied probability, game theory and stochastic networks, with applications to computer and communication networks. She was previously a visiting assistant professor at School of Operations Research and Information Engineering at Cornell University (2019-2021). Prior to that, she was a postdoctoral researcher with LIDS at MIT. Qiaomin received her Ph.D. in Electrical and Computing Engineering from University of Illinois Urbana-Champaign in 2016. She received her B.S. in Electronic Engineering from Tsinghua University. She is a recipient of NSF CAREER Award, JPMorgan Faculty Research Award, Google Systems Research Award and UIUC CSL PhD Thesis Award.
TIME Tuesday, April 9, 2024 at 11:00 AM - 12:00 PM
LOCATION A230, Technological Institute map it
CONTACT Kendall Minta kendall.minta@gmail.com EMAIL
CALENDAR Department of Industrial Engineering and Management Sciences (IEMS)
-
Jun10
EVENT DETAILSmore info
McCormick School of Engineering PhD Hooding and Master’s Degree Recognition Ceremony
TIME Monday, June 10, 2024 at 9:00 AM - 11:00 AM
LOCATION Welsh-Ryan Arena
CONTACT Amy Pokrass amy.pokrass@northwestern.edu EMAIL
CALENDAR McCormick School of Engineering and Applied Science
-
Jun10
TIME Monday, June 10, 2024 at 2:00 PM - 4:00 PM
LOCATION Welsh-Ryan Arena
CONTACT Amy Pokrass amy.pokrass@northwestern.edu EMAIL
CALENDAR McCormick School of Engineering and Applied Science