Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

TD07

We study the convergence of Stochastic Gradient Descent (SGD) with diminishing stepsize (non-adaptive) in the strong convex case. First, we notice that the Bounded Gradient (BG) assumption is in conflict with strong convexity. Without assuming BG, prior work shows that a diminishing stepsize of O(1/t) achieves an expected convergence rate of O(1/t). Here, we demonstrate a simple example of a strong objective function together with a straightforward proof of a O(1/t) lower bound on the expected convergence rate (where we do not need a bound on the computed gradients in SGD). The concrete expressions of the upper bound from prior work and this lower bound are about a 32 factor apart for moderate and large t. 2 - Catalyst for Gradient-based Nonconvex Optimization Courtney Paquette, Lehigh University, 1182 Jaeger St, Columbus, OH, 43206, United States We introduce a generic scheme to solve nonconvex optimization problems using gradient-based algorithms originally designed for minimizing convex functions. Even though these methods may originally require convexity to operate, the proposed approach allows one to use them without assuming any knowledge about the convexity of the objective. In general, the scheme is guaranteed to produce a stationary point with a worst-case efficiency typical of first-order methods, and when the objective turns out to be convex, it automatically accelerates in the sense of Nesterov and achieves near optimal convergence rate in function values. 3 - On Linear Convergence for Douglas Rachford Splitting and ADMM Pontus Giselsson, Lund University, Lund, Sweden Several local and global linear convergence rate results for ADMM have recently appeared in the literature. Many of these are derived under strong monotonicity and smoothness assumptions. It is well known that ADMM is Douglas-Rachford splitting applied to a Fenchel dual problem formulation. In this talk, we show that the recent linear convergence results for ADMM follow from our results on contraction factors for the Douglas-Rachford operator under similar assumptions. Our analysis improves on previous analyses in three aspects 1) the contraction factors are provably sharp 2) the results hold in more general Hilbert space settings 3) the proofs are more compact as they are based on operator theory. 4 - Stochastic Quasi Newton Methods – Past, Present, and Future Albert Solomon Berahas, Postdoctoral Research Fellow, Northwestern University, 2145 Sheridan Road, C210, Evanston, IL, 60208, United States, Jorge Nocedal, Martin Takac In this talk, we present a survey of stochastic quasi-Newton (SQN) methods; methods that attempt to judiciously incorporate second-order information using only gradient information and that alleviate some of the problems that plague stochastic first-order methods. We begin with an overview of recents developments of SQN methods, and then describe in detail the multi-batch L- BFGS method and its extensions. We present, in general form, convergence analyses for SQN methods, and illustrate the performance of several SQN methods on a plethora of machine learning tasks. Finally, we discuss open questions and the future of SQN methods. n TD09 North Bldg 124B Optimization for Machine Learning Sponsored: Optimization/Nonlinear Programming Sponsored Session Chair: Aryan Mokhtari, Massachusetts Institute of Technology, Cambridge, MA, 02139, United States Chair: Asuman Ozdaglar, Massachusetts Institute of Technology, Cambridge, MA, 02139, United States 1 - Stochastic Methods for Nonsmooth Nonconvex Optimization Damek Davis, Cornell University, 218 Rhodes Hall, Hoy Road, Ithaca, NY, 14850, United States, Dmitriy Drusvyatskiy We prove that the proximal stochastic subgradient method, applied to a weakly convex problem (i.e. difference of convex function and a quadratic), drives the gradient of the Moreau envelope to zero at the rate O(k^(-1/4)). This class of problems captures a variety of nonsmooth nonconvex formulations, now widespread in data science. As a consequence, we obtain the long-sought convergence rate of the standard projected stochastic gradient method for minimizing a smooth nonconvex function on a closed convex set. In the talk, I will also highlight other stochastic methods for which we can establish similar guarantees.

n TD07 North Bldg 123 Joint Session OPT/Practice Curated: Network Optimization Models and Algorithms for Evacuation Planning Sponsored: Optimization/Network Optimization Sponsored Session Chair: Maxim A. Dulebenets, Florida A&M University-Florida State University, Tallahassee, FL, 32311, United States 1 - Cost-effective Evacuation Network Design Under Travel Congestion Nadere Mansouri, Southern Methodist University, Dallas, TX, 75231, United States, Halit Uster We consider an evacuation network design problem under cost considerations and travel congestion. We propose a mathematical model that prescribes evacuee routes through the road network to shelter locations under evacuation time constraints. To solve our model, we devise an efficient Benders Decomposition framework and present an experimental on its effectiveness using data from Central Texas. We provide computational results illustrating the efficiency of our solution approach and an analysis of evacuation network design strategies. 2 - Cell-based Network Flow Model Under Uncertainty Considering Social Influence for Large-scale Evacuation Hyeong Suk Na, PhD Candidate, The Pennsylvania State University, 234 Leonhard Building, University Park, PA, 16802, United States, Necdet Serhat Aybat, Sukran Ilgin Guler, Soundar Kumara The emergency management agencies are faced with numerous challenges during the evacuation due to several unpredictable traffic conditions. This study addresses uncertainties of the road capacity induced by traffic congestion in a real evacuation situation. An evacuation network flow model based on the Cell Transmission Model with joint chance constraints is proposed to deal with the uncertainties and the model reliability is investigated. In addition, social media is transforming the way of communicating and sharing the evacuation-related information. A numerical case study examines the applicability of the proposed model and the social media influence for the evacuation process. 3 - Modeling a Latency Based Evacuation Process Hamoud S. Bin Obaid, University of Oklahoma, Norman, OK, 73071, United States, Theodore B. Trafalis A latency-based evacuation model (LBEM) is developed to optimize the evacuation procedure. The model is composed of two phases. In the first phase, the model builds the feasible space of the time path on every route, then the model uses the feasible space to build the constraints in the second phase as a mixed integer linear programming (MILP) model. The model is capable of capturing the latency of each group of evacuees as the travel time in the model is load-dependent. The evacuees are distributed fairly to balance between system optimum (SO) and user equilibrium (UE). Preliminary computational results are reported. 4 - Emergency Evacuation Planning Optimization in the Areas with Vulnerable Populations Maxim A. Dulebenets, Florida A&M University-Florida State University, Tallahassee, FL, 32311, United States, Olumide Abioye, Eren Erman Ozguven, Ren Moses, Walter Boot, Thobias Sando Many U.S. coastal areas, which are characterized with a significant presence of vulnerable populations (e.g., aging adults), often experience natural hazards. In order to facilitate emergency evacuation planning, this study proposes a set of exact and heuristic algorithms for assigning evacuees to the available evacuation routes and emergency shelters, considering socio-demographic characteristics of evacuees, which may further affect their driving ability. Numerical experiments are conducted to evaluate the proposed solution algorithms using real life emergency evacuation scenarios. n TD08 North Bldg 124A Recent Advances in Optimization Methods for Machine Learning Sponsored: Optimization/Nonlinear Programming Sponsored Session Chair: Lam Minh Nguyen, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 10598, United States 1 - Optimal Diminishing Stepsizes in SGD for Strongly Convex Objective Functions Marten van Dijk, PhD, University of Connecticut, Storrs-Mansfield, CT, 06269, United States

348