Informs Annual Meeting 2017

MB76

INFORMS Houston – 2017

MB74

how many times one will need to call the (stochastic) zeroth-order oracle in order to get an $\epsilon$ optimal solution in expectation. Such algorithms and analysis are important for various Bayesian optimization models and applications arising from revenue management. We shall also extend our discussions to include certain non-convex models. 2 - Dynamic Factorization and Partition of Complex Networks Mengdi Wang, Princeton University, 226 Sherrerd Hall, Princeton, NJ, 08544, United States, mengdiw@princeton.edu Finding the reduced-order structure is critical to understanding complex networks. Existing approaches are applicable only when the full network is explicitly observed. We focus on online factorization and partition of implicit large-scale networks based on observations from an associated random walk. We propose an efficient nonconvex stochastic gradient algorithm that processes dependent data dynamically generated by the underlying network and learn a low-dimensional representation. Using a diffusion approximation analysis, we show that the algorithm achieves nearly optimal performance in both sample and space complexity. The proposed approach is experimented on Manhattan taxi data. 3 - Tuning-free Heterogeneity Pursuit in Massive Networks Jinchi Lv, University of Southern California, IOM.Department, Heterogeneity is often natural in many contemporary applications involving massive data. While posing new challenges to effective learning, it can play a crucial role in powering meaningful scientific discoveries through the understanding of important differences among subpopulations of interest. In this paper, we exploit multiple networks with Gaussian graphs to encode the connectivity patterns of a large number of features on the subpopulations. To uncover the heterogeneity of these structures across subpopulations, we suggest a new framework of tuning-free heterogeneity pursuit (THP) via large-scale inference, where the number of networks is allowed to diverge. In particular, two new tests, the chi-based test and the linear functional-based test, are introduced and their asymptotic null distributions are established. Under mild regularity conditions, we establish that both tests are optimal in achieving the testable region boundary and the sample size requirement for the latter test is minimal. Both theoretical guarantees and the tuning-free feature stem from efficient multiple-network estimation by our newly suggested approach of heterogeneous group square-root Lasso (HGSL) for high-dimensional multi-response regression with heterogeneous noises. To solve this convex program, we further introduce a tuning-free algorithm that is scalable and enjoys provable convergence to the global optimum. Both computational and theoretical advantages of our procedure are elucidated through simulation and real data examples. 4 - Understanding Best Subset Selection and Relatives Rahul Mazumder, Massachusetts Institute of Technology, Sloan School of Management, 100 Main Street, Cambridge, MA, 02139, United States, rahulmaz@mit.edu Sparsity plays a key role in linear statistical modeling and beyond. In this talk I will discuss the best subset selection problem and recent computational techniques relying on integer optimization and first order optimization methods, that enable us to obtain high-quality, near-optimal solutions for best-subsets regression, for sizes well beyond what was considered possible. This sheds interesting new insights into the statistical behavior of subset selection problems vis-a-vis popular, computationally friendlier methods thereby motivating the design of new statistical estimators with better statistical and computational properties. 372E Discrete and Combinatorial Optimization Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Gerdus Benade, Carnegie Mellon University, Carnegie Mellon University, Pittsburgh, PA, 15213, United States, jbenade@andrew.cmu.edu 1 - A Matrix Selection Problem Consider a discrete-time dynamic system xk+1 = Mk xk among time horizon k = 0,1,2,...,T. The matrix Mk can be chosen as one of the given two matrices A or B. The matrix selection problem is defined as follows: given an initial vector x0, select matrices M1, M2, M3, ... MT, such that a linear function over the states x1, x2, x3, ... xT is minimized. This problem is motivated by various applications, e.g. cancer treatment planning, antibiotics design. We formulate this problem as a mixed-integer linear program and derive several families of facet-defining inequalities for the resulting formulation. MB76 Zeyang Wu, University of Minnesota, 609 Southeast Oak St Apt 2-12, Minneapolis, MN, 55414-2922, United States, wuxx1164@umn.edu, Qie He Marshall School of Business, Los Angeles, CA, 90089, United States, jinchilv@marshall.usc.edu, Yingying Fan

372C Combinatorial Optimization and Applications Sponsored: Computing Sponsored Session Chair: Illya V. Hicks, Rice University, Rice University, Houston, TX, 77005-1892, United States, ivhicks@rice.edu Co-Chair: Derek J. Mikesell, Rice University, P.O. Box 1892, Houston, TX, 77005, United States, djm13@rice.edu 1 - The Traveling Salesman Problem with Road Distances William J. Cook, University of Waterloo, Combinatorics and Optimization, Waterloo, ON, N2L.3G1, Canada, bico@uwaterloo.ca Following Dantzig, Fulkerson, and Johnson, we show that a certain tour of 49,603 sites in the US is shortest possible, measuring distance with point-to-point routes obtained from Google Maps. We highlight a cost-refinement technique that allows the cutting-plane method to generate lower bounds on the tour length without explicit knowledge of the full distance matrix. The talk is based on joint work with Daniel Espinoza, Marcos Goycoolea, and Keld Helsgaun. 2 - Redistricting with Optimal Minority Representation Boris Brimkov, PhD, Rice University, Houston, TX, United States, bb19@rice.edu Redistricting is the process of partitioning geographic regions and population groups into electorates for municipal and state legislatures. In states with diverse populations, districts in which minority demographic groups comprise voting majorities can help prevent minority vote dilution. While other aspects of the redistricting problem have been thoroughly investigated by the combinatorial optimization community, the formation of minority-majority districts has not yet received an adequate treatment. This talk will discuss several theoretical and computational investigations aimed at producing redistricting plans that are optimal with respect to minority representation. 3 - A Hybrid Metaheuristic for Finding Near Optimal Target Sets in Consensus Models Derek J.Mikesell, Rice University, P.O. Box 1892, MS-134, Houston, TX, 77005, United States, djm13@rice.edu Given a network, we consider the problem of selecting a subset of nodes $A$ of a fixed size $K$ such that the average hitting time to $A$ is minimized. This study is motivated by modeling communication models as a random walk on a weighted loopless directed graph, where the desired information is observed when a random walk reaches the chosen set. In general, this problem is NP-hard. In this paper we observe near-optimal solutions to this problem by considering a hybrid metaheuristic. This hybrid metaheuristic is formed from a discrete version of a simplified Cuckoo Optimization Algorithm and a Greedy Randomized Adaptive Search Procedure (\textit{GRASP}). Additionally, the restricted candidates for this method are chosen based on a spectral decomposition of the network - taking advantage of a random walks likelihood of staying within a cluster. Results show that better-than-greedy solutions can be obtained in a small number of iterations. 4 - Regression-Style Learning by Column Generation Ai Kagawa, Rutgers University, 100 Rockafeller Road, Building A, Piscataway, NJ, 08854, United States, ai.kagawa@gmail.com REPR (Rule-Enhanced Penalized Regression) is a column generation method to predict a scalar response from numerical observations. It enhances a penalized L1 or L2 regression model with new variables indicating whether observations lie inside certain multidimensional boxes. The column generation subproblem is the NP-hard RMA (Rectangular Maximum Agreement) problem, which we solve by parallel branch and bound. We empirically compare REPR to various alternatives and discuss accompanying data discretization techniques and tactics for reducing the computational load of the subproblems. 372D Interactions of Optimization and Statistical Learning I Sponsored: Optimization, Nonlinear Programming Sponsored Session Chair: Ethan Xingyuan Fang, Pennsylvania State University, University Park, PA, 16802, United States, xxf13@psu.edu 1 - Sample Complexity Analysis for Low-order Optimization Algorithms Shuzhong Zhang, University of Minnesota, 111 Church Street, Department of Industrial and Systems Engineer, Minneapolis, MN, 55455, United States, zhangs@umn.edu In this talk we study sample complexities for various zeroth-order algorithms for (stochastic) convex optimization. Essentially, the analysis is meant to understand MB75

191