Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

SC09

4 - A Real-time Relocation Strategy for Station Based Autonomous Electric Vehicle Sharing System Li Li, PhD Candidate, New York University, New York, NY, United States, Saif Eddin G. Jabari This paper puts forward a distributed rebalance strategy for station based autonomous electric vehicle sharing system. The max-weight algorithm is adopted and the queue stability of the network is guaranteed. The rebalance decision is made by each station independently, and only local information, e.g. queue length of neighboring stations, is required for decision making. Hence the rebalancing strategy is able to be implemented in real time, regardless of how big the network size is. Another advantage of this algorithm is that it requires no knowledge of the demands, and can achieve the maximum throughput of the whole network. n SC09 North Bldg 124B First-order Methods in Structured Non-convex Optimization Sponsored: Optimization/Nonlinear Programming Sponsored Session Chair: Paul Grigas, UC Berkeley, Berkeley, CA, 94720-1777, United States 1 - Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization Meisam Razaviyayn, University of Southern California, 3715 McClintock Ave, Los Angeles, CA, 90089, United States, Maher Nouiehed We consider the problem of finding a second-order stationary point of a linearly constrained non-convex optimization problem. We show that, unlike the unconstrained scenario, the vanilla projected gradient descent algorithm fails to escape saddle points even in the presence of a single linear constraint. We then propose a trust region algorithm for linearly constrained optimization problem which converges to second order stationary points. Our algorithm is the first optimization procedure which can converge to $\epsilon$-first order stationary points of a non-manifold constrained optimization problem in $\widetilde{\mathcal{O}}(\epsilon^{-3/2})$ iterations, and at the same time can escape saddle points under strict saddle property. 2 - Gradient Boosting Machine: New Insights, Analysis and Algorithms Haihao Lu, Mathematics Department and Operations Research Center, MIT Rahul, Sloan School of Management, MIT Gradient Boosting Machine (GBM) is a powerful supervised learning algorithm, and has routinely featured as a top algorithm in Kaggle competitions and the KDDCup. It constructs additive models by greedily fitting a simple parameterized function (weak learner) to the current “residuals’’ at each iteration. In spite of the usefulness of GBM in practice, there is a huge gap between its theoretical understanding and the practical implementation. In this work, we propose Randomized Gradient Boosting Machine (RGBM), a new variant of GBM, in which we randomly picks a subset of weak learners and choose the best fit among them. A special case of RGBM corresponds to the column subsampling heuristic implemented in XGBoost. We show in theory that this approach is equivalent to a random-then-greedy coordinate descent in the coefficient space and/or a stochastic mirror descent in the ``residuals’’ space. With such understanding, we derive novel, comprehensive computational guarantees for RGBM by using techniques of first-order methods in convex optimization, which as a special case significantly improve the traditional convergence rate for GBM as well. As a byproduct, such understanding also leads to a natural step-size rule as an efficient replacement of the line-search step-size rule in GBM. 3 - Primal-dual Optimization for Online Advertising Alfonso Lobos Ruiz, UC Berkeley, IEOR, 4141 Etcheverry Hall, Berkeley, CA, 94720, United States, Paul Grigas We propose and study non-convex optimization problems that arise in the context of online advertising, a multi-billion-dollar industry involving multiple ad-exchanges as well as other players. We propose a general primal-dual algorithmic scheme, and we identify a fairly general set of sufficient conditions ù that hold for several auction types ù such that our dual formulation obtains the same optimal value as the original non-convex formulation. In the context of the management of a Demand-Side Platform (DSP), we demonstrate how our offline optimization model and algorithm leads to an implementable policy by a DSP which we applied in both artificial and real data showing the value of our approach.

4 - Generalization Error Bounds of SGD with Probabilistic Guarantee for Nonconvex Optimization

Yingbin Liang, The Ohio State University, 606 Dreese Lab, 2015 Neil Avenue, Columbus, OH, United States, Yi Zhou, Huishuai Zhang

The success of deep learning has led to a rising interest in the generalization property of the stochastic gradient descent (SGD) method, and stability is one popular approach to study it. In this work, we characterize the on-average stability of the iterates generated by SGD in terms of the on-average variance of the stochastic gradients, and establish various generalization error bounds with probabilistic guarantee for SGD for nonconvex loss functions. With strongly convex regularizers, we further establish the generalization error bounds for nonconvex loss functions under proximal SGD with exponential concentration in probability.

n SC10 North Bldg 125A

MSOM Data Challenge Competition Sponsored: Manufacturing & Service Oper Mgmt Sponsored Session Chair: Gad Allon, University of Pennsylvania, 3730 Walnut Street, Philadelphia, PA, 19104, United States 1 - MSOM Data Driven Research Challenge Finalists Gad Allon, University of Pennsylvania, 3730 Walnut Street, Philadelphia, PA, 19104, United States In this competition, researchers compete by building econometric models or data driven models using real data either to address some of the suggested questions below, or address questions of their own interest. The session will feature the finalists in the challenge. n SC11 North Bldg 125B Joint Session MSOM/Practice Curated: Empirical Topics in iFORM Sponsored: Manufacturing & Service Oper Mgmt/iFORM Sponsored Session Chair: Alex Yang, London Business School, London Business School Co-Chair: Nitish Jain, London Business School, London, NW1 4SA, United Kingdom 1 - Retailer Initiated Inventory-based Financing Weiming Zhu, IESE Business School, Avenida Pearson 21, Barcelona, 08034, Spain, Wei Luo We study a innovative financing scheme in which a large retailer provides short- term financing to a small retailer using the inventory of the small retailer as collateral. We analyze the effectiveness of such financing scheme and explore their impact on operational decisions and contract design. 2 - Buyer Preferred Commodity Price Risk Allocation: A Theoretical and Empirical Investigation of the BMW Supply Chain Panos Markou, Cambridge Judge Business School, Cambridge, United Kingdom, Daniel S. Corsten, Panos Kouvelis, Danko Turcic Downstream manufacturers are exposed to volatile commodity prices through their suppliers, and information asymmetry often means that they are disadvantaged in seeing true prices in opaque markets. We formalize a model of BMW’s supply chain, generate several predictions of how contracts should be allocated to suppliers under information asymmetry, and test these using a proprietary data set comprising contracting terms from 1,600 suppliers. 3 - Operational Disruptions and the Value of Credible Control Systems William Schmidt, Cornell University, 314 Sage Hall, Ithaca, NY, 14850, United States, Ananth Raman Operational disruptions can impact a firm’s risk, which manifests in a host of operational issues, including a higher holding cost for inventory, a higher financing cost for capacity expansion, and a higher perception of the firm’s risk among its supply chain partners. We empirically examine whether firms can meaningfully reduce the impact on their risk by implementing and credibly attesting to having effective internal control systems.

64