Optimization
Multi-granularity Causal Structure Learning
Liang, Jiaxuan, Wang, Jun, Yu, Guoxian, Xia, Shuyin, Wang, Guoyin
However, these algorithms simply deem causal relationships stand exclusively at the level of individual variables Data science is moving from the data-centric paradigm forward (micro-variable), ignoring the collective interactions from the science-centric paradigm, and causal revolution multiple variables (macro-variable). For instance, the brain is sweeping across various research fields. Causality learning can be characterized at a micro granularity of neurons and endeavors to unearth causal relationships among variables their synapses, but high-order synergistic subsystems are from observational data and generate causal graph, widespread, which typically sit between canonical functional that is, directed acyclic graph (DAG). Unlike correlationbased networks and may serve an integrative role (Varley study, causality analysis reveals the causal mechanism et al. 2023). Actually, observational data can be regarded of data generation. Identifying causality holds paramount as knowledge in the lowest granularity level, while knowledge significance for stable inference and rational decisions can be regarded as the abstraction of data at different in many applications, such as recommendation systems granularity levels (Wang 2017; Wang et al. 2022). Similar (Wang et al. 2020), medical diagnostics (Richens, Lee, and viewpoints appear in the research of complex systems, Johri 2020), epidemiology (Vandenbroucke, Broadbent, and which suggests that causal relationship is more pronounced Pearce 2016) and many others (Von Kügelgen et al. 2022).
Optimizing accuracy and diversity: a multi-task approach to forecast combinations
Felici, Giovanni, Sudoso, Antonio M.
Forecast combination involves using multiple forecasts to create a single, more accurate prediction. Recently, feature-based forecasting has been employed to either select the most appropriate forecasting models or to optimize the weights of their combination. In this paper, we present a multi-task optimization paradigm that focuses on solving both problems simultaneously and enriches current operational research approaches to forecasting. In essence, it incorporates an additional learning and optimization task into the standard feature-based forecasting approach, focusing on the identification of an optimal set of forecasting methods. During the training phase, an optimization model with linear constraints and quadratic objective function is employed to identify accurate and diverse methods for each time series. Moreover, within the training phase, a neural network is used to learn the behavior of that optimization model. Once training is completed the candidate set of methods is identified using the network. The proposed approach elicits the essential role of diversity in feature-based forecasting and highlights the interplay between model combination and model selection when optimizing forecasting ensembles. Experimental results on a large set of series from the M4 competition dataset show that our proposal enhances point forecast accuracy compared to state-of-the-art methods.
Bayesian Optimization with Conformal Prediction Sets
Stanton, Samuel, Maddox, Wesley, Wilson, Andrew Gordon
Bayesian optimization is a coherent, ubiquitous approach to decision-making under uncertainty, with applications including multi-arm bandits, active learning, and black-box optimization. Bayesian optimization selects decisions (i.e. objective function queries) with maximal expected utility with respect to the posterior distribution of a Bayesian model, which quantifies reducible, epistemic uncertainty about query outcomes. In practice, subjectively implausible outcomes can occur regularly for two reasons: 1) model misspecification and 2) covariate shift. Conformal prediction is an uncertainty quantification method with coverage guarantees even for misspecified models and a simple mechanism to correct for covariate shift. We propose conformal Bayesian optimization, which directs queries towards regions of search space where the model predictions have guaranteed validity, and investigate its behavior on a suite of black-box optimization tasks and tabular ranking tasks. In many cases we find that query coverage can be significantly improved without harming sample-efficiency.
Perseus: Removing Energy Bloat from Large Model Training
Chung, Jae-Won, Gu, Yile, Jang, Insu, Meng, Luoxi, Bansal, Nikhil, Chowdhury, Mosharaf
Training large AI models on numerous GPUs consumes a massive amount of energy. We observe that not all energy consumed during training directly contributes to end-to-end training throughput, and a significant portion can be removed without slowing down training, which we call energy bloat. In this work, we identify two independent sources of energy bloat in large model training, intrinsic and extrinsic, and propose Perseus, a unified optimization framework that mitigates both. Perseus obtains the "iteration time-energy" Pareto frontier of any large model training job using an efficient iterative graph cut-based algorithm and schedules energy consumption of its forward and backward computations across time to remove intrinsic and extrinsic energy bloat. Evaluation on large models like GPT-3 and Bloom shows that Perseus reduces energy consumption of large model training by up to 30%, enabling savings otherwise unobtainable before.
Learning to Transmit with Provable Guarantees in Wireless Federated Learning
Li, Boning, Perazzone, Jake, Swami, Ananthram, Segarra, Santiago
We propose a novel data-driven approach to allocate transmit power for federated learning (FL) over interference-limited wireless networks. The proposed method is useful in challenging scenarios where the wireless channel is changing during the FL training process and when the training data are not independent and identically distributed (non-i.i.d.) on the local devices. Intuitively, the power policy is designed to optimize the information received at the server end during the FL process under communication constraints. Ultimately, our goal is to improve the accuracy and efficiency of the global FL model being trained. The proposed power allocation policy is parameterized using graph convolutional networks (GCNs), and the associated constrained optimization problem is solved through a primal-dual (PD) algorithm. Theoretically, we show that the formulated problem has a zero duality gap and, once the power policy is parameterized, optimality depends on how expressive this parameterization is. Numerically, we demonstrate that the proposed method outperforms existing baselines under different wireless channel settings and varying degrees of data heterogeneity.
KF-PLS: Optimizing Kernel Partial Least-Squares (K-PLS) with Kernel Flows
Duma, Zina-Sabrina, Susiluoto, Jouni, Lamminpää, Otto, Sihvonen, Tuomas, Reinikainen, Satu-Pia, Haario, Heikki
Partial Least-Squares (PLS) Regression is a widely used tool in chemometrics for performing multivariate regression. PLS is a bi-linear method that has a limited capacity of modelling non-linear relations between the predictor variables and the response. Kernel PLS (K-PLS) has been introduced for modelling non-linear predictor-response relations. In K-PLS, the input data is mapped via a kernel function to a Reproducing Kernel Hilbert space (RKH), where the dependencies between the response and the input matrix are assumed to be linear. K-PLS is performed in the RKH space between the kernel matrix and the dependent variable. Most available studies use fixed kernel parameters. Only a few studies have been conducted on optimizing the kernel parameters for K-PLS. In this article, we propose a methodology for the kernel function optimization based on Kernel Flows (KF), a technique developed for Gaussian process regression (GPR). The results are illustrated with four case studies. The case studies represent both numerical examples and real data used in classification and regression tasks. K-PLS optimized with KF, called KF-PLS in this study, is shown to yield good results in all illustrated scenarios. The paper presents cross-validation studies and hyperparameter analysis of the KF methodology when applied to K-PLS.
Amazon Locker Capacity Management
Sethuraman, Samyukta, Bansal, Ankur, Mardan, Setareh, Resende, Mauricio G. C., Jacobs, Timothy L.
Amazon Locker is a self-service delivery or pickup location where customers can pick up packages and drop off returns. A basic first-come-first-served policy for accepting package delivery requests to lockers results in lockers becoming full with standard shipping speed (3-5 day shipping) packages, and leaving no space left for expedited packages which are mostly Next-Day or Two-Day shipping. This paper proposes a solution to the problem of determining how much locker capacity to reserve for different ship-option packages. Yield management is a much researched field with popular applications in the airline, car rental, and hotel industries. However, Amazon Locker poses a unique challenge in this field since the number of days a package will wait in a locker (package dwell time) is, in general, unknown. The proposed solution combines machine learning techniques to predict locker demand and package dwell time, and linear programming to maximize throughput in lockers. The decision variables from this optimization provide optimal capacity reservation values for different ship options. This resulted in a year-over-year increase of 9% in Locker throughput worldwide during holiday season of 2018, impacting millions of customers.
Learning Polynomial Representations of Physical Objects with Application to Certifying Correct Packing Configurations
This paper introduces a novel approach for learning polynomial representations of physical objects. Given a point cloud data set associated with a physical object, we solve a one-class classification problem to bound the data points by a polynomial sublevel set while harnessing Sum-of-Squares (SOS) programming to enforce prior shape knowledge constraints. By representing objects as polynomial sublevel sets we further show it is possible to construct a secondary SOS program to certify whether objects are packed correctly, that is object boundaries do not overlap and are inside some container set. While not employing reinforcement learning (RL) in this work, our proposed secondary SOS program does provide a potential surrogate reward function for RL algorithms, autonomously rewarding agents that propose object rotations and translations that correctly pack objects within a given container set.
Robust Graph Neural Network based on Graph Denoising
Tenorio, Victor M., Rey, Samuel, Marques, Antonio G.
Graph Neural Networks (GNNs) have emerged as a notorious alternative to address learning problems dealing with non-Euclidean datasets. However, although most works assume that the graph is perfectly known, the observed topology is prone to errors stemming from observational noise, graph-learning limitations, or adversarial attacks. If ignored, these perturbations may drastically hinder the performance of GNNs. To address this limitation, this work proposes a robust implementation of GNNs that explicitly accounts for the presence of perturbations in the observed topology. For any task involving GNNs, our core idea is to i) solve an optimization problem not only over the learnable parameters of the GNN but also over the true graph, and ii) augment the fitting cost with a term accounting for discrepancies on the graph. Specifically, we consider a convolutional GNN based on graph filters and follow an alternating optimization approach to handle the (non-differentiable and constrained) optimization problem by combining gradient descent and projected proximal updates. The resulting algorithm is not limited to a particular type of graph and is amenable to incorporating prior information about the perturbations. Finally, we assess the performance of the proposed method through several numerical experiments.
Asynchronous Distributed Optimization with Delay-free Parameters
Wu, Xuyang, Liu, Changxin, Magnusson, Sindri, Johansson, Mikael
Existing asynchronous distributed optimization algorithms often use diminishing step-sizes that cause slow practical convergence, or use fixed step-sizes that depend on and decrease with an upper bound of the delays. Not only are such delay bounds hard to obtain in advance, but they also tend to be large and rarely attained, resulting in unnecessarily slow convergence. This paper develops asynchronous versions of two distributed algorithms, Prox-DGD and DGD-ATC, for solving consensus optimization problems over undirected networks. In contrast to alternatives, our algorithms can converge to the fixed point set of their synchronous counterparts using step-sizes that are independent of the delays. We establish convergence guarantees for strongly and weakly convex problems under both partial and total asynchrony. We also show that the convergence speed of the two asynchronous methods adapts to the actual level of asynchrony rather than being constrained by the worst-case. Numerical experiments demonstrate a strong practical performance of our asynchronous algorithms.