Abstract
In the field of deep learning, Stochastic Gradient Descent (SGD) and its momentum-based variants are the predominant choices for optimization algorithms. Despite all that, these momentum strategies, which accumulate historical gradients by using a fixed $\beta$ hyperparameter to smooth the optimization processing, often neglect the potential impact of the variance of historical gradients on the current gradient estimation. In the gradient variance during training, fluctuation indicates the objective function does not meet the Lipschitz continuity condition at all time, which raises the troublesome optimization problem. This paper aims to explore the potential benefits of reducing the variance of historical gradients to make optimizer converge to flat solutions. Moreover, we proposed a new optimization method based on reducing the variance. We employed the Wiener filter theory to enhance the first moment estimation of SGD, notably introducing an adaptive weight to optimizer. Specifically, the adaptive weight dynamically changes along with temporal fluctuation of gradient variance during deep learning model training. Experimental results demonstrated our proposed adaptive weight optimizer, SGDF (Stochastic Gradient Descent With Filter), can achieve satisfactory performance compared with state-of-the-art optimizers.
Keyword: optimization
Relax: Composable Abstractions for End-to-End Dynamic Machine Learning
Authors: Authors: Ruihang Lai, Junru Shao, Siyuan Feng, Steven S. Lyubomirsky, Bohan Hou, Wuwei Lin, Zihao Ye, Hongyi Jin, Yuchen Jin, Jiawei Liu, Lesheng Jin, Yaxing Cai, Ziheng Jiang, Yong Wu, Sunghyun Park, Prakalp Srivastava, Jared G. Roesch, Todd C. Mowry, Tianqi Chen
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Programming Languages (cs.PL)
Abstract
Dynamic shape computations have become critical in modern machine learning workloads, especially in emerging large language models. The success of these models has driven demand for deploying them to a diverse set of backend environments. In this paper, we present Relax, a compiler abstraction for optimizing end-to-end dynamic machine learning workloads. Relax introduces first-class symbolic shape annotations to track dynamic shape computations globally across the program. It also introduces a cross-level abstraction that encapsulates computational graphs, loop-level tensor programs, and library calls in a single representation to enable cross-level optimizations. We build an end-to-end compilation framework using the proposed approach to optimize dynamic shape models. Experimental results on large language models show that Relax delivers performance competitive with state-of-the-art hand-optimized systems across platforms and enables deployment of emerging dynamic models to a broader set of environments, including mobile phones, embedded devices, and web browsers.
Static Virus Spread Algorithm for DNA Sequence Design
Abstract
DNA is not only the genetic material of life, but also a favorable material for a new computing model. Various research works based on DNA computing have been carried out in recent years. DNA sequence design is the foundation of such research. The sequence quality directly affects the universality, robustness, and stability of DNA computing. How to design DNA sequences depends on the biological properties and target requirements, which is a typical combinatorial optimization problem. In this paper, in order to design DNA sequences with high-quality, we propose a novel meta-heuristic evolutionary algorithm, termed the static virus spread algorithm (SVS). Through this algorithm, we focus on the constraints of universal DNA sequence design and produce a large number of DNA sequences with non-complementarity and small difference in melting temperature as the objectives, and fully considering the balanced proportion of the four bases. The computer simulation and polyacrylamide gel electrophoresis experiments show that the high-quality DNA sequences designed by this algorithm are effective, which is expected to provide a convenient tool for sequence preparation before DNA biochemical operations.
Safe Online Dynamics Learning with Initially Unknown Models and Infeasible Safety Certificates
Authors: Authors: Alexandre Capone, Ryan Cosner, Aaron Ames, Sandra Hirche
Subjects: Systems and Control (eess.SY); Artificial Intelligence (cs.AI); Robotics (cs.RO)
Abstract
Safety-critical control tasks with high levels of uncertainty are becoming increasingly common. Typically, techniques that guarantee safety during learning and control utilize constraint-based safety certificates, which can be leveraged to compute safe control inputs. However, excessive model uncertainty can render robust safety certification methods or infeasible, meaning no control input satisfies the constraints imposed by the safety certificate. This paper considers a learning-based setting with a robust safety certificate based on a control barrier function (CBF) second-order cone program. If the control barrier function certificate is feasible, our approach leverages it to guarantee safety. Otherwise, our method explores the system dynamics to collect data and recover the feasibility of the control barrier function constraint. To this end, we employ a method inspired by well-established tools from Bayesian optimization. We show that if the sampling frequency is high enough, we recover the feasibility of the robust CBF certificate, guaranteeing safety. Our approach requires no prior model and corresponds, to the best of our knowledge, to the first algorithm that guarantees safety in settings with occasionally infeasible safety certificates without requiring a backup non-learning-based controller.
AlberDICE: Addressing Out-Of-Distribution Joint Actions in Offline Multi-Agent RL via Alternating Stationary Distribution Correction Estimation
Authors: Authors: Daiki E. Matsunaga, Jongmin Lee, Jaeseok Yoon, Stefanos Leonardos, Pieter Abbeel, Kee-Eung Kim
Abstract
One of the main challenges in offline Reinforcement Learning (RL) is the distribution shift that arises from the learned policy deviating from the data collection policy. This is often addressed by avoiding out-of-distribution (OOD) actions during policy improvement as their presence can lead to substantial performance degradation. This challenge is amplified in the offline Multi-Agent RL (MARL) setting since the joint action space grows exponentially with the number of agents. To avoid this curse of dimensionality, existing MARL methods adopt either value decomposition methods or fully decentralized training of individual agents. However, even when combined with standard conservatism principles, these methods can still result in the selection of OOD joint actions in offline MARL. To this end, we introduce AlberDICE, an offline MARL algorithm that alternatively performs centralized training of individual agents based on stationary distribution optimization. AlberDICE circumvents the exponential complexity of MARL by computing the best response of one agent at a time while effectively avoiding OOD joint action selection. Theoretically, we show that the alternating optimization procedure converges to Nash policies. In the experiments, we demonstrate that AlberDICE significantly outperforms baseline algorithms on a standard suite of MARL benchmarks.
Joint Composite Latent Space Bayesian Optimization
Authors: Authors: Natalie Maus, Zhiyuan Jerry Lin, Maximilian Balandat, Eytan Bakshy
Abstract
Bayesian Optimization (BO) is a technique for sample-efficient black-box optimization that employs probabilistic models to identify promising input locations for evaluation. When dealing with composite-structured functions, such as f=g o h, evaluating a specific location x yields observations of both the final outcome f(x) = g(h(x)) as well as the intermediate output(s) h(x). Previous research has shown that integrating information from these intermediate outputs can enhance BO performance substantially. However, existing methods struggle if the outputs h(x) are high-dimensional. Many relevant problems fall into this setting, including in the context of generative AI, molecular design, or robotics. To effectively tackle these challenges, we introduce Joint Composite Latent Space Bayesian Optimization (JoCo), a novel framework that jointly trains neural network encoders and probabilistic models to adaptively compress high-dimensional input and output spaces into manageable latent representations. This enables viable BO on these compressed representations, allowing JoCo to outperform other state-of-the-art methods in high-dimensional BO on a wide variety of simulated and real-world problems.
Multi-scale Time-stepping of Partial Differential Equations with Transformers
Authors: Authors: AmirPouya Hemmasian, Amir Barati Farimani
Abstract
Developing fast surrogates for Partial Differential Equations (PDEs) will accelerate design and optimization in almost all scientific and engineering applications. Neural networks have been receiving ever-increasing attention and demonstrated remarkable success in computational modeling of PDEs, however; their prediction accuracy is not at the level of full deployment. In this work, we utilize the transformer architecture, the backbone of numerous state-of-the-art AI models, to learn the dynamics of physical systems as the mixing of spatial patterns learned by a convolutional autoencoder. Moreover, we incorporate the idea of multi-scale hierarchical time-stepping to increase the prediction speed and decrease accumulated error over time. Our model achieves similar or better results in predicting the time-evolution of Navier-Stokes equations compared to the powerful Fourier Neural Operator (FNO) and two transformer-based neural operators OFormer and Galerkin Transformer.
State-wise Safe Reinforcement Learning With Pixel Observations
Abstract
Reinforcement Learning(RL) in the context of safe exploration has long grappled with the challenges of the delicate balance between maximizing rewards and minimizing safety violations, the complexities arising from contact-rich or non-smooth environments, and high-dimensional pixel observations. Furthermore, incorporating state-wise safety constraints in the exploration and learning process, where the agent is prohibited from accessing unsafe regions without prior knowledge, adds an additional layer of complexity. In this paper, we propose a novel pixel-observation safe RL algorithm that efficiently encodes state-wise safety constraints with unknown hazard regions through the introduction of a latent barrier function learning mechanism. As a joint learning framework, our approach first involves constructing a latent dynamics model with low-dimensional latent spaces derived from pixel observations. Subsequently, we build and learn a latent barrier function on top of the latent dynamics and conduct policy optimization simultaneously, thereby improving both safety and the total expected return. Experimental evaluations on the safety-gym benchmark suite demonstrate that our proposed method significantly reduces safety violations throughout the training process and demonstrates faster safety convergence compared to existing methods while achieving competitive results in reward return.
Objectives Are All You Need: Solving Deceptive Problems Without Explicit Diversity Maintenance
Authors: Authors: Ryan Boldi, Li Ding, Lee Spector
Subjects: Neural and Evolutionary Computing (cs.NE)
Abstract
Navigating deceptive domains has often been a challenge in machine learning due to search algorithms getting stuck at sub-optimal local optima. Many algorithms have been proposed to navigate these domains by explicitly maintaining diversity or equivalently promoting exploration, such as Novelty Search or other so-called Quality Diversity algorithms. In this paper, we present an approach with promise to solve deceptive domains without explicit diversity maintenance by optimizing a potentially large set of defined objectives. These objectives can be extracted directly from the environment by sub-aggregating the raw performance of individuals in a variety of ways. We use lexicase selection to optimize for these objectives as it has been shown to implicitly maintain population diversity. We compare this technique with a varying number of objectives to a commonly used quality diversity algorithm, MAP-Elites, on a set of discrete optimization as well as reinforcement learning domains with varying degrees of deception. We find that decomposing objectives into many objectives and optimizing them outperforms MAP-Elites on the deceptive domains that we explore. Furthermore, we find that this technique results in competitive performance on the diversity-focused metrics of QD-Score and Coverage, without explicitly optimizing for these things. Our ablation study shows that this technique is robust to different subaggregation techniques. However, when it comes to non-deceptive, or ``illumination" domains, quality diversity techniques generally outperform our objective-based framework with respect to exploration (but not exploitation), hinting at potential directions for future work.
Predicting Ground Reaction Force from Inertial Sensors
Authors: Authors: Bowen Song, Marco Paolieri, Harper E. Stewart, Leana Golubchik, Jill L. McNitt-Gray, Vishal Misra, Devavrat Shah
Abstract
The study of ground reaction forces (GRF) is used to characterize the mechanical loading experienced by individuals in movements such as running, which is clinically applicable to identify athletes at risk for stress-related injuries. Our aim in this paper is to determine if data collected with inertial measurement units (IMUs), that can be worn by athletes during outdoor runs, can be used to predict GRF with sufficient accuracy to allow the analysis of its derived biomechanical variables (e.g., contact time and loading rate). In this paper, we consider lightweight approaches in contrast to state-of-the-art prediction using LSTM neural networks. Specifically, we compare use of LSTMs to k-Nearest Neighbors (KNN) regression as well as propose a novel solution, SVD Embedding Regression (SER), using linear regression between singular value decomposition embeddings of IMUs data (input) and GRF data (output). We evaluate the accuracy of these techniques when using training data collected from different athletes, from the same athlete, or both, and we explore the use of acceleration and angular velocity data from sensors at different locations (sacrum and shanks). Our results illustrate that simple machine learning methods such as SER and KNN can be similarly accurate or more accurate than LSTM neural networks, with much faster training times and hyperparameter optimization; in particular, SER and KNN are more accurate when personal training data are available, and KNN comes with benefit of providing provenance of prediction. Notably, the use of personal data reduces prediction errors of all methods for most biomechanical variables.
Self-Supervised Learning of Representations for Space Generates Multi-Modular Grid Cells
Abstract
To solve the spatial problems of mapping, localization and navigation, the mammalian lineage has developed striking spatial representations. One important spatial representation is the Nobel-prize winning grid cells: neurons that represent self-location, a local and aperiodic quantity, with seemingly bizarre non-local and spatially periodic activity patterns of a few discrete periods. Why has the mammalian lineage learnt this peculiar grid representation? Mathematical analysis suggests that this multi-periodic representation has excellent properties as an algebraic code with high capacity and intrinsic error-correction, but to date, there is no satisfactory synthesis of core principles that lead to multi-modular grid cells in deep recurrent neural networks. In this work, we begin by identifying key insights from four families of approaches to answering the grid cell question: coding theory, dynamical systems, function optimization and supervised deep learning. We then leverage our insights to propose a new approach that combines the strengths of all four approaches. Our approach is a self-supervised learning (SSL) framework - including data, data augmentations, loss functions and a network architecture - motivated from a normative perspective, without access to supervised position information or engineering of particular readout representations as needed in previous approaches. We show that multiple grid cell modules can emerge in networks trained on our SSL framework and that the networks and emergent representations generalize well outside their training distribution. This work contains insights for neuroscientists interested in the origins of grid cells as well as machine learning researchers interested in novel SSL frameworks.
Bounded and Unbiased Composite Differential Privacy
Authors: Authors: Kai Zhang, Yanjun Zhang, Ruoxi Sun, Pei-Wei Tsai, Muneeb Ul Hassan, Xin Yuan, Minhui Xue, Jinjun Chen
Abstract
The objective of differential privacy (DP) is to protect privacy by producing an output distribution that is indistinguishable between any two neighboring databases. However, traditional differentially private mechanisms tend to produce unbounded outputs in order to achieve maximum disturbance range, which is not always in line with real-world applications. Existing solutions attempt to address this issue by employing post-processing or truncation techniques to restrict the output results, but at the cost of introducing bias issues. In this paper, we propose a novel differentially private mechanism which uses a composite probability density function to generate bounded and unbiased outputs for any numerical input data. The composition consists of an activation function and a base function, providing users with the flexibility to define the functions according to the DP constraints. We also develop an optimization algorithm that enables the iterative search for the optimal hyper-parameter setting without the need for repeated experiments, which prevents additional privacy overhead. Furthermore, we evaluate the utility of the proposed mechanism by assessing the variance of the composite probability density function and introducing two alternative metrics that are simpler to compute than variance estimation. Our extensive evaluation on three benchmark datasets demonstrates consistent and significant improvement over the traditional Laplace and Gaussian mechanisms. The proposed bounded and unbiased composite differentially private mechanism will underpin the broader DP arsenal and foster future privacy-preserving studies.
Complex Organ Mask Guided Radiology Report Generation
Authors: Authors: Gu Tiancheng, Liu Dongnan, Li Zhiyuan, Cai Weidong
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI)
Abstract
The goal of automatic report generation is to generate a clinically accurate and coherent phrase from a single given X-ray image, which could alleviate the workload of traditional radiology reporting.However, in a real-world scenario, radiologists frequently face the challenge of producing extensive reports derived from numerous medical images, thereby medical report generation from multi-image perspective is needed.In this paper, we propose the Complex Organ Mask Guided (termed as COMG) report generation model, which incorporates masks from multiple organs (e.g., bones, lungs, heart, and mediastinum), to provide more detailed information and guide the model's attention to these crucial body regions. Specifically, we leverage prior knowledge of the disease corresponding to each organ in the fusion process to enhance the disease identification phase during the report generation process. Additionally, cosine similarity loss is introduced as target function to ensure the convergence of cross-modal consistency and facilitate model optimization.Experimental results on two public datasets show that COMG achieves a 11.4% and 9.7% improvement in terms of BLEU@4 scores over the SOTA model KiUT on IU-Xray and MIMIC, respectively.
MC-Stereo: Multi-peak Lookup and Cascade Search Range for Stereo Matching
Abstract
Stereo matching is a fundamental task in scene comprehension. In recent years, the method based on iterative optimization has shown promise in stereo matching. However, the current iteration framework employs a single-peak lookup, which struggles to handle the multi-peak problem effectively. Additionally, the fixed search range used during the iteration process limits the final convergence effects. To address these issues, we present a novel iterative optimization architecture called MC-Stereo. This architecture mitigates the multi-peak distribution problem in matching through the multi-peak lookup strategy, and integrates the coarse-to-fine concept into the iterative framework via the cascade search range. Furthermore, given that feature representation learning is crucial for successful learnbased stereo matching, we introduce a pre-trained network to serve as the feature extractor, enhancing the front end of the stereo matching pipeline. Based on these improvements, MC-Stereo ranks first among all publicly available methods on the KITTI-2012 and KITTI-2015 benchmarks, and also achieves state-of-the-art performance on ETH3D. The code will be open sourced after the publication of this paper.
A Comprehensive Dynamic Simulation Framework for Coupled Neuromusculoskeletal-Exoskeletal Systems
Abstract
The modeling and simulation of coupled neuromusculoskeletal-exoskeletal systems play a crucial role in human biomechanical analysis, as well as in the design and control of exoskeletons. However, conventional dynamic simulation frameworks have limitations due to their reliance on experimental data and their inability to capture comprehensive biomechanical signals and dynamic responses. To address these challenges, we introduce an optimization-based dynamic simulation framework that integrates a complete neuromusculoskeletal feedback loop, rigid-body dynamics, human-exoskeleton interaction, and foot-ground contact. Without relying on experimental measurements or empirical data, our framework employs a stepwise optimization process to determine muscle reflex parameters, taking into account multidimensional criteria. This allows the framework to generate a full range of kinematic and biomechanical signals, including muscle activations, muscle forces, joint torques, etc., which are typically challenging to measure experimentally. To validate the effectiveness of the framework, we compare the simulated results with experimental data obtained from a healthy subject wearing an exoskeleton while walking at different speeds (0.9, 1.0, and 1.1 m/s) and terrains (flat and uphill). The results demonstrate that our framework can effectively and accurately capture the qualitative differences in muscle activity associated with different functions, as well as the evolutionary patterns of muscle activity and kinematic signals under varying walking conditions. The simulation framework we propose has the potential to facilitate gait analysis and performance evaluation of coupled human-exoskeleton systems, as well as enable efficient and cost-effective testing of novel exoskeleton designs and control strategies.
NeuroEvoBench: Benchmarking Evolutionary Optimizers for Deep Learning Applications
Authors: Authors: Robert Tjarko Lange, Yujin Tang, Yingtao Tian
Subjects: Neural and Evolutionary Computing (cs.NE); Machine Learning (cs.LG)
Abstract
Recently, the Deep Learning community has become interested in evolutionary optimization (EO) as a means to address hard optimization problems, e.g. meta-learning through long inner loop unrolls or optimizing non-differentiable operators. One core reason for this trend has been the recent innovation in hardware acceleration and compatible software - making distributed population evaluations much easier than before. Unlike for gradient descent-based methods though, there is a lack of hyperparameter understanding and best practices for EO - arguably due to severely less 'graduate student descent' and benchmarking being performed for EO methods. Additionally, classical benchmarks from the evolutionary community provide few practical insights for Deep Learning applications. This poses challenges for newcomers to hardware-accelerated EO and hinders significant adoption. Hence, we establish a new benchmark of EO methods (NeuroEvoBench) tailored toward Deep Learning applications and exhaustively evaluate traditional and meta-learned EO. We investigate core scientific questions including resource allocation, fitness shaping, normalization, regularization & scalability of EO. The benchmark is open-sourced at https://github.com/neuroevobench/neuroevobench under Apache-2.0 license.
SplitMAC: Wireless Split Learning over Multiple Access Channels
Authors: Authors: Seonjung Kim, Yongjeong Oh, Yo-Seb Jeon
Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)
Abstract
This paper presents a novel split learning (SL) framework, referred to as SplitMAC, which reduces the latency of SL by leveraging simultaneous uplink transmission over multiple access channels. The key strategy is to divide devices into multiple groups and allow the devices within the same group to simultaneously transmit their smashed data and device-side models over the multiple access channels. The optimization problem of device grouping to minimize SL latency is formulated, and the benefit of device grouping in reducing the uplink latency of SL is theoretically derived. By examining a two-device grouping case, two asymptotically-optimal algorithms are devised for device grouping in low and high signal-to-noise ratio (SNR) scenarios, respectively, while providing proofs of their optimality. By merging these algorithms, a near-optimal device grouping algorithm is proposed to cover a wide range of SNR. Simulation results demonstrate that our SL framework with the proposed device grouping algorithm is superior to existing SL frameworks in reducing SL latency.
Time-Division Based Integrated Sensing, Communication, and Computing in Integrated Satellite-Terrestrial Networks
Abstract
In this paper, we investigate time-division based framework for integrated sensing, communication, and computing in integrated satellite-terrestrial networks. We consider a scenario, where Internet-of-Things devices on the ground operate with sensing and communication in a time-division manner, and can process the sensing results locally, at the edge, or in the cloud via the satellite communication link. Based on the proposed framework, we formulate a multi-dimensional optimization problem to maximize the utility performance of sensing, communication, and computing abilities. After decomposing the original optimization problem into two subproblems, we first derive the closed-form solution of the optimal task partitioning strategy for terrestrial users and satellite users. Then, we develop the joint subframe allocation and task partitioning strategy to optimize the overall performance, by means of which the Pareto optimal solutions can be obtained along the Pareto frontier. Extensive simulations are provided to demonstrated the effectiveness of the proposed strategy, which is 10% to 60% superior compared with the benchmarks. Also, the trade-off between the multidimensional resource and multi-functional performance is analyzed from the perspective of network design.
Payoff-based learning with matrix multiplicative weights in quantum games
Authors: Authors: Kyriakos Lotidis, Panayotis Mertikopoulos, Nicholas Bambos, Jose Blanchet
Subjects: Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Optimization and Control (math.OC); Quantum Physics (quant-ph)
Abstract
In this paper, we study the problem of learning in quantum games - and other classes of semidefinite games - with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the $\mathcal{O}(1/\sqrt{T})$ convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an $\mathcal{O}(T^{-1/4})$ rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.
Optimal Power Flow Solutions via Noise-Resilient Quantum-Inspired Interior-Point Methods
Abstract
This paper presents three quantum interior-point methods (QIPMs) tailored to tackle the DC optimal power flow (DCOPF) problem using noisy intermediate-scale quantum devices. The optimization model is redefined as a linearly constrained quadratic optimization. By incorporating the Harrow-Hassidim-Lloyd (HHL) quantum algorithm into the IPM framework, Newton's direction is determined through the resolution of linear equation systems. To mitigate the impact of HHL error and quantum noise on Newton's direction calculation, we present a noise-tolerant quantum IPM (NT-QIPM) approach. This approach provides high-quality OPF solutions even in scenarios where inexact solutions to the linear equation systems result in approximated Newton's directions. Moreover, to enhance performance in cases of slow convergence and uphold the feasibility of OPF outcomes upon convergence, we propose a hybrid strategy, classically augmented NT-QIPM. This technique is designed to expedite convergence relative to classical IPM while maintaining the solution accuracy. The efficacy of the proposed quantum IPM variants is studied through comprehensive simulations and error analyses on 3-bus, 5-bus, 118-bus, and 300-bus systems, highlighting their potential and promise in addressing challenging OPF scenarios. By modeling the errors and incorporating quantum computer noise, we simulate the proposed algorithms on both Qiskit and classical computers to gain a deeper understanding of the effectiveness and feasibility of our methods under realistic conditions.
Nonlinear Multi-objective Reinforcement Learning with Provable Guarantees
Abstract
We describe RA-E3 (Reward-Aware Explicit Explore or Exploit), an algorithm with provable guarantees for solving a single or multi-objective Markov Decision Process (MDP) where we want to maximize the expected value of a nonlinear function over accumulated rewards. This allows us to model fairness-aware welfare optimization for multi-objective reinforcement learning as well as risk-aware reinforcement learning with nonlinear Von Neumann-Morgenstern utility functions in the single objective setting. RA-E3 extends the classic E3 algorithm that solves MDPs with scalar rewards and linear preferences. We first state a distinct reward-aware version of value iteration that calculates a non-stationary policy that is approximately optimal for a given model of the environment. This sub-procedure is based on an extended form of Bellman optimality for nonlinear optimization that explicitly considers time and current accumulated reward. We then describe how to use this optimization procedure in a larger algorithm that must simultaneously learn a model of the environment. The algorithm learns an approximately optimal policy in time that depends polynomially on the MDP size, desired approximation, and smoothness of the nonlinear function, and exponentially on the number of objectives.
Preliminary Analysis on Second-Order Convergence for Biased Policy Gradient Methods
Abstract
Although the convergence of policy gradient algorithms to first-order stationary points is well-established, the objective functions of reinforcement learning problems are typically highly nonconvex. Therefore, recent work has focused on two extensions: ``global" convergence guarantees under regularity assumptions on the function structure, and second-order guarantees for escaping saddle points and convergence to true local minima. Our work expands on the latter approach, avoiding the restrictive assumptions of the former that may not apply to general objective functions. Existing results on vanilla policy gradient only consider an unbiased gradient estimator, but practical implementations under the infinite-horizon discounted setting, including both Monte-Carlo methods and actor-critic methods, involve gradient descent updates with a biased gradient estimator. We present preliminary results on the convergence of biased policy gradient algorithms to second-order stationary points, leveraging proof techniques from nonconvex optimization. In our next steps we aim to provide the first finite-time second-order convergence analysis for actor-critic algorithms.
Abstract
We outline an unsupervised method for temporal rank ordering of sets of historical documents, namely American State of the Union Addresses and DEEDS, a corpus of medieval English property transfer documents. Our method relies upon effectively capturing the gradual change in word usage via a bandwidth estimate for the non-parametric Generalized Linear Models (Fan, Heckman, and Wand, 1995). The number of possible rank orders needed to search through possible cost functions related to the bandwidth can be quite large, even for a small set of documents. We tackle this problem of combinatorial optimization using the Simulated Annealing algorithm, which allows us to obtain the optimal document temporal orders. Our rank ordering method significantly improved the temporal sequencing of both corpora compared to a randomly sequenced baseline. This unsupervised approach should enable the temporal ordering of undated document sets.
Pointer Networks with Q-Learning for OP Combinatorial Optimization
Authors: Authors: Alessandro Barro
Subjects: Machine Learning (cs.LG); Optimization and Control (math.OC)
Abstract
The Orienteering Problem (OP) presents a unique challenge in combinatorial optimization, emphasized by its widespread use in logistics, delivery, and transportation planning. Given the NP-hard nature of OP, obtaining optimal solutions is inherently complex. While Pointer Networks (Ptr-Nets) have exhibited prowess in various combinatorial tasks, their performance in the context of OP leaves room for improvement. Recognizing the potency of Q-learning, especially when paired with deep neural structures, this research unveils the Pointer Q-Network (PQN). This innovative method combines Ptr-Nets and Q-learning, effectively addressing the specific challenges presented by OP. We deeply explore the architecture and efficiency of PQN, showcasing its superior capability in managing OP situations.
Ephemeral Rollups are All you Need
Authors: Authors: Gabriele Picco, Andrea Fortugno
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
Abstract
In the realm of open and composable gaming, we envision platforms where users actively expand, create, engage, and immerse themselves in a rich world of entertainment. One promising avenue for achieving this vision is through fully on-chain (FOC) games, where both game state and logic reside on the blockchain, maximizing composability. However, we must grapple with inherent limitations and trade-offs, particularly in terms of costs and scalability. This paper proposes BOLT, a framework that leverages the Solana Virtual Machine (SVM) to scale FOC games without state fragmentation or compromised trust assumptions. The framework introduces a systematic approach for discovering, utilizing, and publishing modular pieces of logic as components deeply rooted in the Entity-Component-System (ECS) pattern. To enhance scalability and resource optimization, we introduce the concept of Ephemeral Rollups (ERs) that overcome the tradeoffs of L2s horizontal scaling. These dedicated runtimes can be customized to provide higher operational speed, configurable ticking mechanisms, provable sessions and gasless transactions without composability-scalability tradeoffs.
Uncertainty Estimation for Safety-critical Scene Segmentation via Fine-grained Reward Maximization
Authors: Authors: Hongzheng Yang, Cheng Chen, Yueyao Chen, Markus Scheppach, Hon Chi Yip, Qi Dou
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Abstract
Uncertainty estimation plays an important role for future reliable deployment of deep segmentation models in safety-critical scenarios such as medical applications. However, existing methods for uncertainty estimation have been limited by the lack of explicit guidance for calibrating the prediction risk and model confidence. In this work, we propose a novel fine-grained reward maximization (FGRM) framework, to address uncertainty estimation by directly utilizing an uncertainty metric related reward function with a reinforcement learning based model tuning algorithm. This would benefit the model uncertainty estimation through direct optimization guidance for model calibration. Specifically, our method designs a new uncertainty estimation reward function using the calibration metric, which is maximized to fine-tune an evidential learning pre-trained segmentation model for calibrating prediction risk. Importantly, we innovate an effective fine-grained parameter update scheme, which imposes fine-grained reward-weighting of each network parameter according to the parameter importance quantified by the fisher information matrix. To the best of our knowledge, this is the first work exploring reward optimization for model uncertainty estimation in safety-critical vision tasks. The effectiveness of our method is demonstrated on two large safety-critical surgical scene segmentation datasets under two different uncertainty estimation settings. With real-time one forward pass at inference, our method outperforms state-of-the-art methods by a clear margin on all the calibration metrics of uncertainty estimation, while maintaining a high task accuracy for the segmentation results. Code is available at \url{https://github.com/med-air/FGRM}.
Robust Generalization Strategies for Morpheme Glossing in an Endangered Language Documentation Context
Authors: Authors: Michael Ginn, Alexis Palmer
Subjects: Computation and Language (cs.CL); Machine Learning (cs.LG)
Abstract
Generalization is of particular importance in resource-constrained settings, where the available training data may represent only a small fraction of the distribution of possible texts. We investigate the ability of morpheme labeling models to generalize by evaluating their performance on unseen genres of text, and we experiment with strategies for closing the gap between performance on in-distribution and out-of-distribution data. Specifically, we use weight decay optimization, output denoising, and iterative pseudo-labeling, and achieve a 2% improvement on a test set containing texts from unseen genres. All experiments are performed using texts written in the Mayan language Uspanteko.
Architecting Intermediate Layers for Efficient Composition of Data Management and Machine Learning Systems
Abstract
Modern data analytics workloads combine relational data processing with machine learning (ML). Most DBMS handle these workloads by offloading these ML operations to external specialized ML systems. While both DBMS and ML systems go to great lengths to optimize performance for their specific workloads, significant performance is lost when used in combination, due to data movement across system boundaries, conversions between incompatible internal data formats, and the lack of cross system optimizations. A key idea to remove these bottlenecks is to integrate existing data manipulation systems with ML systems by building a common intermediate layer (IR). Although this idea has been explored before (Weld, Delite), previous such attempts require significant re-engineering of prior systems and still fall short in achieving best-of-breed performance for individual tasks (e.g., SQL, Deep Learning). Specifically, they rely on re-implementing existing systems using a generic set of operators and fail to match best-of-breed individual performance due to the inability to recover high-level optimizations from this generic IR through compiler analysis. We present Flern, the first intermediate-layer integration between DB and ML systems that are best-of-breed individually, competitive with the best compiled query engines such as HyPer on comprehensive relational benchmarks (TPC-H) and competitive with TensorFlow and PyTorch in state-of-the-art ML models (e.g., DeepSpeech, SqueezeNet, Transformers) and also represents a new state-of-the-art for integration. A key realization is to architect intermediate layers based on generative programming capabilities, which preserves high-level contextual information for cross optimizations and enables the construction of a variety of complex structures and cross system optimizations with minimal effort.
Mobility as a Resource (MaaR) for resilient human-centric automation: a vision paper
Authors: Authors: S. Travis Waller, Amalia Polydoropoulou, Leandros Tassiulas, Athanasios Ziliaskopoulos, Sisi Jian, Susann Wagenknecht, Georg Hirte, Tomasz Bednarz
Abstract
As a consequence of commoditization, mobility is moving from a product (i.e., traditional modes and vehicles), to a service (i.e., Mobility as a Service, MaaS); MaaS is the current state of transport research and emerging practice. However, as it is observed in other fields (e.g. computing) we argue that mobility will evolve from a service to a resource (Mobility as a Resource, MaaR); MaaR is the envisioned inevitable state, which will emerge for societal movement. Further, due to increasing scarcity of shared mobility spaces across traditional and emerging modes of mobility, the commoditization process must be viewed within the critical need for ethical and equitable solutions for the traveling public (i.e., research is needed to avoid hyper-market driven outcomes for society from the ongoing commoditization process). The evolution of mobility into a resource requires novel conceptual frameworks, technologies, processes and perspectives of analysis. A key component of the future MaaR system is the technological capacity to observe, allocate and manage (in real-time) the smallest envisionable units of mobility (i.e., atomic units of mobility capacity) while providing prioritized attention to human movement and ethical metrics related to access, consumption and impact. This paper proposes an initial design of new paradigms which synthesize and advance methodologies relating to highly dynamic capacity reservation systems for automated travel integrated with the mixed interaction of non-automated traffic flow management, travel network optimization, demand behavior forecasting, and progressive mobility planning that spans equity, sustainability, and resilience.
Kivi: Verification for Cluster Management
Authors: Authors: Bingzhe Liu, Gangmuk Lim, Ryan Beckett, P. Brighten Godfrey
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
Abstract
Modern cloud infrastructure is powered by cluster management systems such as Kubernetes and Docker Swarm. While these systems seek to minimize users' operational burden, the complex, dynamic, and non-deterministic nature of these systems makes them hard to reason about, potentially leading to failures ranging from performance degradation to outages. We present Kivi, the first system for verifying controllers and their configurations in cluster management systems. Kivi focuses on the popular system Kubernetes, and models its controllers and events into processes whereby their interleavings are exhaustively checked via model checking. Central to handling autoscaling and large-scale deployments is our design that seeks to find violations in a smaller and reduced topology. We also develop several model optimizations in Kivi to scale to large clusters. We show that Kivi is effective and accurate in finding issues in realistic and complex scenarios and showcase two new issues in Kubernetes controller source code.
Fast and Interpretable Face Identification for Out-Of-Distribution Data Using Vision Transformers
Authors: Authors: Hai Phan, Cindy Le, Vu Le, Yihui He, Anh Totti Nguyen
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Abstract
Most face identification approaches employ a Siamese neural network to compare two images at the image embedding level. Yet, this technique can be subject to occlusion (e.g. faces with masks or sunglasses) and out-of-distribution data. DeepFace-EMD (Phan et al. 2022) reaches state-of-the-art accuracy on out-of-distribution data by first comparing two images at the image level, and then at the patch level. Yet, its later patch-wise re-ranking stage admits a large $O(n^3 \log n)$ time complexity (for $n$ patches in an image) due to the optimal transport optimization. In this paper, we propose a novel, 2-image Vision Transformers (ViTs) that compares two images at the patch level using cross-attention. After training on 2M pairs of images on CASIA Webface (Yi et al. 2014), our model performs at a comparable accuracy as DeepFace-EMD on out-of-distribution data, yet at an inference speed more than twice as fast as DeepFace-EMD (Phan et al. 2022). In addition, via a human study, our model shows promising explainability through the visualization of cross-attention. We believe our work can inspire more explorations in using ViTs for face identification.
Signal Processing Meets SGD: From Momentum to Filter
Abstract
In the field of deep learning, Stochastic Gradient Descent (SGD) and its momentum-based variants are the predominant choices for optimization algorithms. Despite all that, these momentum strategies, which accumulate historical gradients by using a fixed $\beta$ hyperparameter to smooth the optimization processing, often neglect the potential impact of the variance of historical gradients on the current gradient estimation. In the gradient variance during training, fluctuation indicates the objective function does not meet the Lipschitz continuity condition at all time, which raises the troublesome optimization problem. This paper aims to explore the potential benefits of reducing the variance of historical gradients to make optimizer converge to flat solutions. Moreover, we proposed a new optimization method based on reducing the variance. We employed the Wiener filter theory to enhance the first moment estimation of SGD, notably introducing an adaptive weight to optimizer. Specifically, the adaptive weight dynamically changes along with temporal fluctuation of gradient variance during deep learning model training. Experimental results demonstrated our proposed adaptive weight optimizer, SGDF (Stochastic Gradient Descent With Filter), can achieve satisfactory performance compared with state-of-the-art optimizers.
InstructPix2NeRF: Instructed 3D Portrait Editing from a Single Image
Abstract
With the success of Neural Radiance Field (NeRF) in 3D-aware portrait editing, a variety of works have achieved promising results regarding both quality and 3D consistency. However, these methods heavily rely on per-prompt optimization when handling natural language as editing instructions. Due to the lack of labeled human face 3D datasets and effective architectures, the area of human-instructed 3D-aware editing for open-world portraits in an end-to-end manner remains under-explored. To solve this problem, we propose an end-to-end diffusion-based framework termed InstructPix2NeRF, which enables instructed 3D-aware portrait editing from a single open-world image with human instructions. At its core lies a conditional latent 3D diffusion process that lifts 2D editing to 3D space by learning the correlation between the paired images' difference and the instructions via triplet data. With the help of our proposed token position randomization strategy, we could even achieve multi-semantic editing through one single pass with the portrait identity well-preserved. Besides, we further propose an identity consistency module that directly modulates the extracted identity signals into our diffusion process, which increases the multi-view 3D identity consistency. Extensive experiments verify the effectiveness of our method and show its superiority against strong baselines quantitatively and qualitatively.
Prioritized Propagation in Graph Neural Networks
Authors: Authors: Yao Cheng, Minjie Chen, Xiang Li, Caihua Shan, Ming Gao
Abstract
Graph neural networks (GNNs) have recently received significant attention. Learning node-wise message propagation in GNNs aims to set personalized propagation steps for different nodes in the graph. Despite the success, existing methods ignore node priority that can be reflected by node influence and heterophily. In this paper, we propose a versatile framework PPro, which can be integrated with most existing GNN models and aim to learn prioritized node-wise message propagation in GNNs. Specifically, the framework consists of three components: a backbone GNN model, a propagation controller to determine the optimal propagation steps for nodes, and a weight controller to compute the priority scores for nodes. We design a mutually enhanced mechanism to compute node priority, optimal propagation step and label prediction. We also propose an alternative optimization strategy to learn the parameters in the backbone GNN model and two parametric controllers. We conduct extensive experiments to compare our framework with other 11 state-of-the-art competitors on 8 benchmark datasets. Experimental results show that our framework can lead to superior performance in terms of propagation strategies and node representations.
Abstract
In this paper, we propose Saturn, a new data system to improve the efficiency of multi-large-model training (e.g., during model selection/hyperparameter optimization). We first identify three key interconnected systems challenges for users building large models in this setting -- parallelism technique selection, distribution of GPUs over jobs, and scheduling. We then formalize these as a joint problem, and build a new system architecture to tackle these challenges simultaneously. Our evaluations show that our joint-optimization approach yields 39-49% lower model selection runtimes than typical current DL practice.
Imitation Learning based Alternative Multi-Agent Proximal Policy Optimization for Well-Formed Swarm-Oriented Pursuit Avoidance
Abstract
Multi-Robot System (MRS) has garnered widespread research interest and fostered tremendous interesting applications, especially in cooperative control fields. Yet little light has been shed on the compound ability of formation, monitoring and defence in decentralized large-scale MRS for pursuit avoidance, which puts stringent requirements on the capability of coordination and adaptability. In this paper, we put forward a decentralized Imitation learning based Alternative Multi-Agent Proximal Policy Optimization (IA-MAPPO) algorithm to provide a flexible and communication-economic solution to execute the pursuit avoidance task in well-formed swarm. In particular, a policy-distillation based MAPPO executor is firstly devised to capably accomplish and swiftly switch between multiple formations in a centralized manner. Furthermore, we utilize imitation learning to decentralize the formation controller, so as to reduce the communication overheads and enhance the scalability. Afterwards, alternative training is leveraged to compensate the performance loss incurred by decentralization. The simulation results validate the effectiveness of IA-MAPPO and extensive ablation experiments further show the performance comparable to a centralized solution with significant decrease in communication overheads.
The Pursuit of Human Labeling: A New Perspective on Unsupervised Learning
Abstract
We present HUME, a simple model-agnostic framework for inferring human labeling of a given dataset without any external supervision. The key insight behind our approach is that classes defined by many human labelings are linearly separable regardless of the representation space used to represent a dataset. HUME utilizes this insight to guide the search over all possible labelings of a dataset to discover an underlying human labeling. We show that the proposed optimization objective is strikingly well-correlated with the ground truth labeling of the dataset. In effect, we only train linear classifiers on top of pretrained representations that remain fixed during training, making our framework compatible with any large pretrained and self-supervised model. Despite its simplicity, HUME outperforms a supervised linear classifier on top of self-supervised representations on the STL-10 dataset by a large margin and achieves comparable performance on the CIFAR-10 dataset. Compared to the existing unsupervised baselines, HUME achieves state-of-the-art performance on four benchmark image classification datasets including the large-scale ImageNet-1000 dataset. Altogether, our work provides a fundamentally new view to tackle unsupervised learning by searching for consistent labelings between different representation spaces.
Simultaneous Time Synchronization and Mutual Localization for Multi-robot System
Abstract
Mutual localization stands as a foundational component within various domains of multi-robot systems. Nevertheless, in relative pose estimation, time synchronization is usually underappreciated and rarely addressed, although it significantly influences estimation accuracy. In this paper, we introduce time synchronization into mutual localization to recover the time offset and relative poses between robots simultaneously. Under a constant velocity assumption in a short time, we fuse time offset estimation with our previous bearing-based mutual localization by a novel error representation. Based on the error model, we formulate a joint optimization problem and utilize semi-definite relaxation (SDR) to furnish a lossless relaxation. By solving the relaxed problem, time synchronization and relative pose estimation can be achieved when time drift between robots is limited. To enhance the application range of time offset estimation, we further propose an iterative method to recover the time offset from coarse to fine. Comparisons between the proposed method and the existing ones through extensive simulation tests present prominent benefits of time synchronization on mutual localization. Moreover, real-world experiments are conducted to show the practicality and robustness.
An operator-splitting optimization approach for phase-field simulation of equilibrium shapes of crystals
Abstract
Computing equilibrium shapes of crystals (ESC) is a challenging problem in materials science that involves minimizing an orientation-dependent (i.e., anisotropic) surface energy functional subject to a prescribed mass constraint. The highly nonlinear and singular anisotropic terms in the problem make it very challenging from both the analytical and numerical aspects. Especially, when the strength of anisotropy is very strong (i.e., strongly anisotropic cases), the ESC will form some singular, sharp corners even if the surface energy function is smooth. Traditional numerical approaches, such as the $H^{-1}$ gradient flow, are unable to produce true sharp corners due to the necessary addition of a high-order regularization term that penalizes sharp corners and rounds them off. In this paper, we propose a new numerical method based on the Davis-Yin splitting (DYS) optimization algorithm to predict the ESC instead of using gradient flow approaches. We discretize the infinite-dimensional phase-field energy functional in the absence of regularization terms and transform it into a finite-dimensional constraint minimization problem. The resulting optimization problem is solved using the DYS method which automatically guarantees the mass-conservation and bound-preserving properties. We also prove the global convergence of the proposed algorithm. These desired properties are numerically observed. In particular, the proposed method can produce real sharp corners with satisfactory accuracy. Finally, we present numerous numerical results to demonstrate that the ESC can be well simulated under different types of anisotropic surface energies, which also confirms the effectiveness and efficiency of the proposed method.
Safe and Efficient Trajectory Optimization for Autonomous Vehicles using B-spline with Incremental Path Flattening
Abstract
B-spline-based trajectory optimization has been widely used in the field of robot navigation, as the convex hull property of the B-spline curve guarantees its dynamical feasibility with a small number of control variables. Several recent works demonstrated that a holonomic system like a drone, which has simple dynamical feasibility constraints, fully utilizes the B-spline property for trajectory optimization. Nevertheless, it is still challenging to leverage the B-splined-based optimization algorithm to generate a collision-free trajectory for autonomous vehicles because their complex vehicle kinodynamic constraints make it difficult to use the convex hull property. In this paper, we propose a novel incremental path flattening method with a new swept volume method that enables a B-splined-based trajectory optimization algorithm to incorporate vehicle kinematic collision avoidance constraints. Furthermore, a curvature constraint is added with other feasibility constraints (e.g. velocity and acceleration) for the vehicle kinodynamic constraints. Our experimental results demonstrate that our method outperforms state-of-the-art baselines in various simulated environments and verifies its valid tracking performance with an autonomous vehicle in a real-world scenario.
TabRepo: A Large Scale Repository of Tabular Model Evaluations and its AutoML Applications
Abstract
We introduce TabRepo, a new dataset of tabular model evaluations and predictions. TabRepo contains the predictions and metrics of 1206 models evaluated on 200 regression and classification datasets. We illustrate the benefit of our datasets in multiple ways. First, we show that it allows to perform analysis such as comparing Hyperparameter Optimization against current AutoML systems while also considering ensembling at no cost by using precomputed model predictions. Second, we show that our dataset can be readily leveraged to perform transfer-learning. In particular, we show that applying standard transfer-learning techniques allows to outperform current state-of-the-art tabular systems in accuracy, runtime and latency.
Obstacle- and Occlusion-Responsive Visual Tracking Control for Redundant Manipulators using Reachability Measure
Abstract
A vision system attached to a manipulator excels at tracing a moving target object while effectively handling obstacles, overcoming limitations arising from the camera's confined field of view and occluded line of sight. Meanwhile, the manipulator may encounter certain challenges, including restricted motion due to kinematic constraints and the risk of colliding with external obstacles. These challenges are typically addressed by assigning multiple task objectives to the manipulator. However, doing so can cause an increased risk of driving the manipulator to its kinematic limits, leading to failures in object tracking or obstacle avoidance. To address this issue, we propose a novel visual tracking control method for a redundant manipulator that takes the kinematic constraints into account via a reachability measure. Our method employs an optimization-based controller that considers object tracking, occlusion avoidance, collision avoidance, and the kinematic constraints represented by the reachability measure. Subsequently, it determines a suitable joint configuration through real-time inverse kinematics, accounting for dynamic obstacle avoidance and the continuity of joint configurations. To validate our approach, we conducted simulations and hardware experiments involving a moving target and dynamic obstacles. The results of our evaluations highlight the significance of incorporating the reachability measure.
Antenna Positioning and Beamforming Design for Movable-Antenna Enabled Multi-user Downlink Communications
Abstract
This paper investigates a multiple input single output (MISO) downlink communication system in which users are equipped with movable antennas (MAs). First, We adopt a field-response based channel model to characterize the downlink channel with respect to MAs' positions. Then, we aim to minimize the total transmit power by jointly optimizing the MAs' positions and beamforming matrix. To solve the resulting non-convex problem, we employ an alternating optimization (AO) algorithm based on penalty method and successive convex approximation (SCA) to obtain a sub-optimal solution. Numerical results demonstrate that the MA-enabled communication system perform better than conventional fixed position antennas.
DRAUC: An Instance-wise Distributionally Robust AUC Optimization Framework
Abstract
The Area Under the ROC Curve (AUC) is a widely employed metric in long-tailed classification scenarios. Nevertheless, most existing methods primarily assume that training and testing examples are drawn i.i.d. from the same distribution, which is often unachievable in practice. Distributionally Robust Optimization (DRO) enhances model performance by optimizing it for the local worst-case scenario, but directly integrating AUC optimization with DRO results in an intractable optimization problem. To tackle this challenge, methodically we propose an instance-wise surrogate loss of Distributionally Robust AUC (DRAUC) and build our optimization framework on top of it. Moreover, we highlight that conventional DRAUC may induce label bias, hence introducing distribution-aware DRAUC as a more suitable metric for robust AUC learning. Theoretically, we affirm that the generalization gap between the training loss and testing error diminishes if the training set is sufficiently large. Empirically, experiments on corrupted benchmark datasets demonstrate the effectiveness of our proposed method. Code is available at: https://github.com/EldercatSAM/DRAUC.
Multi-Step Optimal Tracking Control of Unknown Nonzero-Sum Games based on Least Squares and Linear Programming: An Application to a Fully-Automated, Dual-Hormone Artificial Pancreas
Authors: Authors: Alexandros Tanzanakis, John Lygeros
Abstract
We consider the problem of optimal tracking control of unknown discrete-time nonlinear nonzero-sum games. The related state-of-art literature is mostly focused on Policy Iteration algorithms and multiple neural network approximation, which may lead to practical implementation challenges and high computational burden. To overcome these problems, we propose a novel Q-function-based multi-step Value Iteration algorithm, which provides the potential to accelerate convergence speed and improve the quality of solutions, with an easy-to-realize initialization condition. A critic-only least squares implementation approach is then employed, which alleviates the computational complexity of commonly used multiple neural network-based methods. Afterwards, by introducing the coupled Bellman operator, a novel linear programming approach is derived, based on which Nash equilibria can be approximately computed by solving a set of tractable finite-dimensional optimization problems. We evaluate the tracking control capabilities of the proposed algorithms to the problem of fully-automated dual-hormone (i.e., insulin and glucagon) glucose control in Type 1 Diabetes Mellitus. The U.S. FDA-accepted DMMS.R simulator from the Epsilon Group is used to conduct extensive in-silico clinical studies on virtual patients under a variety of completely unannounced meal and exercise scenarios. Simulation results demonstrate the high reliability and exceptional performance of the proposed multi-step algorithmic framework to critical complex systems.
Unified Multi-modal Unsupervised Representation Learning for Skeleton-based Action Understanding
Abstract
Unsupervised pre-training has shown great success in skeleton-based action understanding recently. Existing works typically train separate modality-specific models, then integrate the multi-modal information for action understanding by a late-fusion strategy. Although these approaches have achieved significant performance, they suffer from the complex yet redundant multi-stream model designs, each of which is also limited to the fixed input skeleton modality. To alleviate these issues, in this paper, we propose a Unified Multimodal Unsupervised Representation Learning framework, called UmURL, which exploits an efficient early-fusion strategy to jointly encode the multi-modal features in a single-stream manner. Specifically, instead of designing separate modality-specific optimization processes for uni-modal unsupervised learning, we feed different modality inputs into the same stream with an early-fusion strategy to learn their multi-modal features for reducing model complexity. To ensure that the fused multi-modal features do not exhibit modality bias, i.e., being dominated by a certain modality input, we further propose both intra- and inter-modal consistency learning to guarantee that the multi-modal features contain the complete semantics of each modal via feature decomposition and distinct alignment. In this manner, our framework is able to learn the unified representations of uni-modal or multi-modal skeleton input, which is flexible to different kinds of modality input for robust action understanding in practical cases. Extensive experiments conducted on three large-scale datasets, i.e., NTU-60, NTU-120, and PKU-MMD II, demonstrate that UmURL is highly efficient, possessing the approximate complexity with the uni-modal methods, while achieving new state-of-the-art performance across various downstream task scenarios in skeleton-based action representation learning.
Benchmarking Differential Evolution on a Quantum Simulator
Authors: Authors: Parthasarathy Srinivasan
Subjects: Neural and Evolutionary Computing (cs.NE); Quantum Physics (quant-ph)
Abstract
The use of Evolutionary Algorithms (EA) for solving Mathematical/Computational Optimization Problems is inspired by the biological processes of Evolution. Few of the primitives involved in the Evolutionary process/paradigm are selection of 'Fit' individuals (from a population sample) for retention, cloning, mutation, discarding, breeding, crossover etc. In the Evolutionary Algorithm abstraction, the individuals are deemed to be solution candidates to an Optimization problem and additional solution(/sets) are built by applying analogies to the above primitives (cloning, mutation etc.) by means of evaluating a 'Fitness' function/criterion. One such algorithm is Differential Evolution (DE) which can be used to compute the minima of functions such as the rastrigin function and rosenbrock function. This work is an attempt to study the result of applying the DE method on these functions with candidate individuals generated on classical Turing modeled computation and comparing the same with those on state of the art Quantum computation.The study benchmarks the convergence of these functions by varying the parameters initialized and reports timing, convergence, and resource utilization results.
GPTuner: A Manual-Reading Database Tuning System via GPT-Guided Bayesian Optimization
Abstract
Modern database management systems (DBMS) expose hundreds of configurable knobs to control system behaviours. Determining the appropriate values for these knobs to improve DBMS performance is a long-standing problem in the database community. As there is an increasing number of knobs to tune and each knob could be in continuous or categorical values, manual tuning becomes impractical. Recently, automatic tuning systems using machine learning methods have shown great potentials. However, existing approaches still incur significant tuning costs or only yield sub-optimal performance. This is because they either ignore the extensive domain knowledge available (e.g., DBMS manuals and forum discussions) and only rely on the runtime feedback of benchmark evaluations to guide the optimization, or they utilize the domain knowledge in a limited way. Hence, we propose GPTuner, a manual-reading database tuning system. Firstly, we develop a Large Language Model (LLM)-based pipeline to collect and refine heterogeneous knowledge, and propose a prompt ensemble algorithm to unify a structured view of the refined knowledge. Secondly, using the structured knowledge, we (1) design a workload-aware and training-free knob selection strategy, (2) develop a search space optimization technique considering the value range of each knob, and (3) propose a Coarse-to-Fine Bayesian Optimization Framework to explore the optimized space. Finally, we evaluate GPTuner under different benchmarks (TPC-C and TPC-H), metrics (throughput and latency) as well as DBMS (PostgreSQL and MySQL). Compared to the state-of-the-art approaches, GPTuner identifies better configurations in 16x less time on average. Moreover, GPTuner achieves up to 30% performance improvement (higher throughput or lower latency) over the best-performing alternative.
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
Authors: Authors: Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
Abstract
We provide an algorithm which, with high probability, maintains a $(1-\epsilon)$-approximate maximum flow on an undirected graph undergoing $m$-edge additions in amortized $m^{o(1)} \epsilon^{-3}$ time per update. To obtain this result, we provide a more general algorithm that solves what we call the incremental, thresholded $p$-norm flow problem that asks to determine the first edge-insertion in an undirected graph that causes the minimum $\ell_p$-norm flow to decrease below a given threshold in value. Since we solve this thresholded problem, our data structure succeeds against an adaptive adversary that can only see the data structure's output. Furthermore, since our algorithm holds for $p = 2$, we obtain improved algorithms for dynamically maintaining the effective resistance between a pair of vertices in an undirected graph undergoing edge insertions. Our algorithm builds upon previous dynamic algorithms for approximately solving the minimum-ratio cycle problem that underlie previous advances on the maximum flow problem [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS '22] as well as recent dynamic maximum flow algorithms [v.d.Brand-Liu-Sidford, STOC '23]. Instead of using interior point methods, which were a key component of these recent advances, our algorithm uses an optimization method based on $\ell_p$-norm iterative refinement and the multiplicative weight update method. This ensures a monotonicity property in the minimum-ratio cycle subproblems that allows us to apply known data structures and bypass issues arising from adaptive queries.
DeepInception: Hypnotize Large Language Model to Be Jailbreaker
Authors: Authors: Xuan Li, Zhanke Zhou, Jianing Zhu, Jiangchao Yao, Tongliang Liu, Bo Han
Subjects: Machine Learning (cs.LG); Cryptography and Security (cs.CR)
Abstract
Despite remarkable success in various applications, large language models (LLMs) are vulnerable to adversarial jailbreaks that make the safety guardrails void. However, previous studies for jailbreaks usually resort to brute-force optimization or extrapolations of a high computation cost, which might not be practical or effective. In this paper, inspired by the Milgram experiment that individuals can harm another person if they are told to do so by an authoritative figure, we disclose a lightweight method, termed as DeepInception, which can easily hypnotize LLM to be a jailbreaker and unlock its misusing risks. Specifically, DeepInception leverages the personification ability of LLM to construct a novel nested scene to behave, which realizes an adaptive way to escape the usage control in a normal scenario and provides the possibility for further direct jailbreaks. Empirically, we conduct comprehensive experiments to show its efficacy. Our DeepInception can achieve competitive jailbreak success rates with previous counterparts and realize a continuous jailbreak in subsequent interactions, which reveals the critical weakness of self-losing on both open/closed-source LLMs like Falcon, Vicuna, Llama-2, and GPT-3.5/4/4V. Our investigation appeals that people should pay more attention to the safety aspects of LLMs and a stronger defense against their misuse risks. The code is publicly available at: https://github.com/tmlr-group/DeepInception.
Balancing Notions of Equity: Approximation Algorithms for Fair Portfolio of Solutions in Combinatorial Optimization
Authors: Authors: Swati Gupta, Jai Moondra, Mohit Singh
Abstract
Inspired by equity considerations, we consider top-$k$ norm, ordered norm, and symmetric monotonic norm objectives for various combinatorial optimization problems. Top-$k$ norms and ordered norms have natural interpretations in terms of minimizing the impact on individuals bearing largest costs. To model decision-making with multiple equity criteria, we study the notion of portfolios of solutions with the property that each norm or equity criteria has an approximately optimal solution in this portfolio. We attempt to characterize portfolios by their sizes and approximation factor guarantees for various combinatorial problems. For a given problem, we investigate whether (1) there exists a single solution that is approximately optimal for all norms, (2) there exists a small approximately optimal portfolio of size larger than 1, (3) there exist polynomial time algorithms to find these small portfolios. We study an algorithmic framework to obtain single solutions that are approximately optimal for all norms. We show the existence of such a solution for problems such as $k$-clustering, ordered set cover, scheduling for job completion time minimization, and scheduling for machine load minimization on identical machines. We also give efficient algorithms to find these solutions in most cases, except set cover where we show there is a gap in terms of computational complexity. Our work improves upon the best-known approximation factor across all norms for a single solution in $k$-clustering. For uncapacitated facility location and scheduling for machine load minimization with identical jobs, we obtain logarithmic sized portfolios, also providing a matching lower bound in the latter case. Our work results in new open combinatorial questions, which might be of independent interest.
On Finding Optimal (Dynamic) Arborescences
Authors: Authors: Joaquim Espada, Alexandre P. Francisco, Tatiana Rocher, Luís M. S. Russo, Cátia Vaz
Abstract
Let G = (V, E) be a directed and weighted graph with vertex set V of size n and edge set E of size m, such that each edge (u, v) \in E has a real-valued weight w(u, c). An arborescence in G is a subgraph T = (V, E') such that for a vertex u \in V, the root, there is a unique path in T from u to any other vertex v \in V. The weight of T is the sum of the weights of its edges. In this paper, given G, we are interested in finding an arborescence in G with minimum weight, i.e., an optimal arborescence. Furthermore, when G is subject to changes, namely edge insertions and deletions, we are interested in efficiently maintaining a dynamic arborescence in G. This is a well known problem with applications in several domains such as network design optimization and in phylogenetic inference. In this paper we revisit algorithmic ideas proposed by several authors for this problem, we provide detailed pseudo-code as well as implementation details, and we present experimental results on large scale-free networks and on phylogenetic inference. Our implementation is publicly available at \url{https://gitlab.com/espadas/optimal-arborescences}.
PROMPT: A Fast and Extensible Memory Profiling Framework
Authors: Authors: Ziyang Xu, Yebin Chon, Yian Su, Zujun Tan, Sotiris Apostolakis, Simone Campanoni, David I. August
Subjects: Performance (cs.PF); Programming Languages (cs.PL)
Abstract
Memory profiling captures programs' dynamic memory behavior, assisting programmers in debugging, tuning, and enabling advanced compiler optimizations like speculation-based automatic parallelization. As each use case demands its unique program trace summary, various memory profiler types have been developed. Yet, designing practical memory profilers often requires extensive compiler expertise, adeptness in program optimization, and significant implementation efforts. This often results in a void where aspirations for fast and robust profilers remain unfulfilled. To bridge this gap, this paper presents PROMPT, a pioneering framework for streamlined development of fast memory profilers. With it, developers only need to specify profiling events and define the core profiling logic, bypassing the complexities of custom instrumentation and intricate memory profiling components and optimizations. Two state-of-the-art memory profilers were ported with PROMPT while all features preserved. By focusing on the core profiling logic, the code was reduced by more than 65% and the profiling speed was improved by 5.3x and 7.1x respectively. To further underscore PROMPT's impact, a tailored memory profiling workflow was constructed for a sophisticated compiler optimization client. In just 570 lines of code, this redesigned workflow satisfies the client's memory profiling needs while achieving more than 90% reduction in profiling time and improved robustness compared to the original profilers.
Congestion-aware Ride-pooling in Mixed Traffic for Autonomous Mobility-on-Demand Systems
Authors: Authors: Fabio Paparella, Leonardo Pedroso, Theo Hofman, Mauro Salazar
Subjects: Systems and Control (eess.SY); Optimization and Control (math.OC)
Abstract
This paper presents a modeling and optimization framework to study congestion-aware ride-pooling Autonomous Mobility-on-Demand (AMoD) systems, whereby self-driving robotaxis are providing on-demand mobility, and users headed in the same direction share the same vehicle for part of their journey. Specifically, taking a mesoscopic time-invariant perspective and on the assumption of a large number of travel requests, we first cast the joint ride-pooling assignment and routing problem as a quadratic program that does not scale with the number of demands and can be solved with off-the-shelf convex solvers. Second, we compare the proposed approach with a significantly simpler decoupled formulation, whereby only the routing is performed in a congestion-aware fashion, whilst the ride-pooling assignment part is congestion-unaware. A case study of Sioux Falls reveals that such a simplification does not significantly alter the solution and that the decisive factor is indeed the congestion-aware routing. Finally, we solve the latter problem accounting for the presence of user-centered private vehicle users in a case study of Manhattan, NYC, characterizing the performance of the car-network as a function of AMoD penetration rate and percentage of pooled rides within it. Our results show that AMoD can significantly reduce congestion and travel times, but only if at least 40% of the users are willing to be pooled together. Otherwise, for higher AMoD penetration rates and low percentage of pooled rides, the effect of the additional rebalancing empty-vehicle trips can be even more detrimental than the benefits stemming from a centralized routing, worsening congestion and leading to an up to 15% higher average travel time.
Safe Collective Control under Noisy Inputs and Competing Constraints via Non-Smooth Barrier Functions
Authors: Authors: Clinton Enwerem, John S. Baras
Subjects: Systems and Control (eess.SY); Robotics (cs.RO)
Abstract
We consider the problem of safely coordinating ensembles of identical autonomous agents to conduct complex missions with conflicting safety requirements and under noisy control inputs. Using non-smooth control barrier functions (CBFs) and stochastic model-predictive control as springboards and by adopting an extrinsic approach where the ensemble is treated as a unified dynamic entity, we devise a method to synthesize safety-aware control inputs for uncertain collectives, drawing upon recent developments in Boolean CBF composition and extensions of CBFs to stochastic systems. Specifically, we approximate the combined CBF by a smooth function and solve a stochastic optimization problem, with agent-level forcing terms restricted to the resulting affine subspace of safe control inputs. For the smoothing step, we employ a polynomial approximation scheme, providing evidence for its advantage in generating more conservative yet sufficiently-filtered control signals than the smoother but more aggressive equivalents realized via an approximation technique based on the log-sum-exp function. To further demonstrate the utility of the proposed method, we present bounds for the expected value of the CBF approximation error, along with results from simulations of a single-integrator collective under velocity perturbations, comparing these results with those obtained using a naive state-feedback controller lacking safety filters.
Abstract
Various large language models (LLMs) have been proposed in recent years, including closed- and open-source ones, continually setting new records on multiple benchmarks. However, the development of LLMs still faces several issues, such as high cost of training models from scratch, and continual pre-training leading to catastrophic forgetting, etc. Although many such issues are addressed along the line of research on LLMs, an important yet practical limitation is that many studies overly pursue enlarging model sizes without comprehensively analyzing and optimizing the use of pre-training data in their learning process, as well as appropriate organization and leveraging of such data in training LLMs under cost-effective settings. In this work, we propose Ziya2, a model with 13 billion parameters adopting LLaMA2 as the foundation model, and further pre-trained on 700 billion tokens, where we focus on pre-training techniques and use data-centric optimization to enhance the learning process of Ziya2 on different stages. Experiments show that Ziya2 significantly outperforms other models in multiple benchmarks especially with promising results compared to representative open-source ones. Ziya2 (Base) is released at https://huggingface.co/IDEA-CCNL/Ziya2-13B-Base and https://modelscope.cn/models/Fengshenbang/Ziya2-13B-Base/summary.
Cross-Image Attention for Zero-Shot Appearance Transfer
Authors: Authors: Yuval Alaluf, Daniel Garibi, Or Patashnik, Hadar Averbuch-Elor, Daniel Cohen-Or
Subjects: Computer Vision and Pattern Recognition (cs.CV); Graphics (cs.GR)
Abstract
Recent advancements in text-to-image generative models have demonstrated a remarkable ability to capture a deep semantic understanding of images. In this work, we leverage this semantic knowledge to transfer the visual appearance between objects that share similar semantics but may differ significantly in shape. To achieve this, we build upon the self-attention layers of these generative models and introduce a cross-image attention mechanism that implicitly establishes semantic correspondences across images. Specifically, given a pair of images -- one depicting the target structure and the other specifying the desired appearance -- our cross-image attention combines the queries corresponding to the structure image with the keys and values of the appearance image. This operation, when applied during the denoising process, leverages the established semantic correspondences to generate an image combining the desired structure and appearance. In addition, to improve the output image quality, we harness three mechanisms that either manipulate the noisy latent codes or the model's internal representations throughout the denoising process. Importantly, our approach is zero-shot, requiring no optimization or training. Experiments show that our method is effective across a wide range of object categories and is robust to variations in shape, size, and viewpoint between the two input images.
Embedding First Order Logic into Kernel Machines
Authors: Authors: Michelangelo Diligenti, Marco Gori, Marco Maggini, Leonardo Rigutini
Abstract
In this paper we propose a general framework to integrate supervised and unsupervised examples with background knowledge expressed by a collection of first-order logic clauses into kernel machines. In particular, we consider a multi-task learning scheme where multiple predicates defined on a set of objects are to be jointly learned from examples, enforcing a set of FOL constraints on the admissible configurations of their values. The predicates are defined on the feature spaces, in which the input objects are represented, and can be either known a priori or approximated by an appropriate kernel-based learner. A general approach is presented to convert the FOL clauses into a continuous implementation that can deal with the outputs computed by the kernel-based predicates. The learning problem is formulated as a semi-supervised task that requires the optimization in the primal of a loss function that combines a fitting loss measure on the supervised examples, a regularization term, and a penalty term that enforces the constraints on both the supervised and unsupervised examples. Unfortunately, the penalty term is not convex and it can hinder the optimization process. However, it is possible to avoid poor solutions by using a two stage learning schema, in which the supervised examples are learned first and then the constraints are enforced.
Exploitation-Guided Exploration for Semantic Embodied Navigation
Abstract
In the recent progress in embodied navigation and sim-to-robot transfer, modular policies have emerged as a de facto framework. However, there is more to compositionality beyond the decomposition of the learning load into modular components. In this work, we investigate a principled way to syntactically combine these components. Particularly, we propose Exploitation-Guided Exploration (XGX) where separate modules for exploration and exploitation come together in a novel and intuitive manner. We configure the exploitation module to take over in the deterministic final steps of navigation i.e. when the goal becomes visible. Crucially, an exploitation module teacher-forces the exploration module and continues driving an overridden policy optimization. XGX, with effective decomposition and novel guidance, improves the state-of-the-art performance on the challenging object navigation task from 70% to 73%. Along with better accuracy, through targeted analysis, we show that XGX is also more efficient at goal-conditioned exploration. Finally, we show sim-to-real transfer to robot hardware and XGX performs over two-fold better than the best baseline from simulation benchmarking. Project page: xgxvisnav.github.io
Keyword: adam
Cryptanalysis of Nikooghadam et al.'s lightweight authentication protocol for Internet of Drones
Abstract
The Internet of Drones has emerged as a transformative technology with applications spanning various domains, including surveillance, delivery services, and disaster management. Secure communication between controller users and drones is paramount to ensure the transmitted data's confidentiality, integrity, and authenticity. Key agreement protocols are crucial in establishing secure communication channels between users and drones, enabling them to exchange sensitive information and control their operations securely. Recently Nikooghadam et al. proposed a lightweight mutual authentication and key agreement protocol for the Internet of drones. In this article, we provide a descriptive analysis of their proposed scheme and prove that Nikooghadam et al.'s scheme is vulnerable to user tracking attacks and stolen verifier attacks.
Keyword: gradient
Efficient Symbolic Policy Learning with Differentiable Symbolic Expression
Abstract
Deep reinforcement learning (DRL) has led to a wide range of advances in sequential decision-making tasks. However, the complexity of neural network policies makes it difficult to understand and deploy with limited computational resources. Currently, employing compact symbolic expressions as symbolic policies is a promising strategy to obtain simple and interpretable policies. Previous symbolic policy methods usually involve complex training processes and pre-trained neural network policies, which are inefficient and limit the application of symbolic policies. In this paper, we propose an efficient gradient-based learning method named Efficient Symbolic Policy Learning (ESPL) that learns the symbolic policy from scratch in an end-to-end way. We introduce a symbolic network as the search space and employ a path selector to find the compact symbolic policy. By doing so we represent the policy with a differentiable symbolic expression and train it in an off-policy manner which further improves the efficiency. In addition, in contrast with previous symbolic policies which only work in single-task RL because of complexity, we expand ESPL on meta-RL to generate symbolic policies for unseen tasks. Experimentally, we show that our approach generates symbolic policies with higher performance and greatly improves data efficiency for single-task RL. In meta-RL, we demonstrate that compared with neural network policies the proposed symbolic policy achieves higher performance and efficiency and shows the potential to be interpretable.
Client Orchestration and Cost-Efficient Joint Optimization for NOMA-Enabled Hierarchical Federated Learning
Abstract
Hierarchical federated learning (HFL) shows great advantages over conventional two-layer federated learning (FL) in reducing network overhead and interaction latency while still retaining the data privacy of distributed FL clients. However, the communication and energy overhead still pose a bottleneck for HFL performance, especially as the number of clients raises dramatically. To tackle this issue, we propose a non-orthogonal multiple access (NOMA) enabled HFL system under semi-synchronous cloud model aggregation in this paper, aiming to minimize the total cost of time and energy at each HFL global round. Specifically, we first propose a novel fuzzy logic based client orchestration policy considering client heterogenerity in multiple aspects, including channel quality, data quantity and model staleness. Subsequently, given the fuzzy based client-edge association, a joint edge server scheduling and resource allocation problem is formulated. Utilizing problem decomposition, we firstly derive the closed-form solution for the edge server scheduling subproblem via the penalty dual decomposition (PDD) method. Next, a deep deterministic policy gradient (DDPG) based algorithm is proposed to tackle the resource allocation subproblem considering time-varying environments. Finally, extensive simulations demonstrate that the proposed scheme outperforms the considered benchmarks regarding HFL performance improvement and total cost reduction.
Ultra-Long Sequence Distributed Transformer
Authors: Authors: Xiao Wang, Isaac Lyngaas, Aristeidis Tsaris, Peng Chen, Sajal Dash, Mayanka Chandra Shekar, Tao Luo, Hong-Jun Yoon, Mohamed Wahib, John Gouley
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Artificial Intelligence (cs.AI)
Abstract
Transformer models trained on long sequences often achieve higher accuracy than short sequences. Unfortunately, conventional transformers struggle with long sequence training due to the overwhelming computation and memory requirements. Existing methods for long sequence training offer limited speedup and memory reduction, and may compromise accuracy. This paper presents a novel and efficient distributed training method, the Long Short-Sequence Transformer (LSS Transformer), for training transformer with long sequences. It distributes a long sequence into segments among GPUs, with each GPU computing a partial self-attention for its segment. Then, it uses a fused communication and a novel double gradient averaging technique to avoid the need to aggregate partial self-attention and minimize communication overhead. We evaluated the performance between LSS Transformer and the state-of-the-art Nvidia sequence parallelism on a Wikipedia enwik8 dataset. Results show that our proposed method lead to 5.6x faster and 10.2x more memory-efficient implementation compared to state-of-the-art sequence parallelism on 144 Nvidia V100 GPUs. Moreover, our algorithm scales to an extreme sequence length of 50,112 at 3,456 GPUs, achieving 161% super-linear parallel efficiency and a throughput of 32 petaflops.
NeuroEvoBench: Benchmarking Evolutionary Optimizers for Deep Learning Applications
Authors: Authors: Robert Tjarko Lange, Yujin Tang, Yingtao Tian
Subjects: Neural and Evolutionary Computing (cs.NE); Machine Learning (cs.LG)
Abstract
Recently, the Deep Learning community has become interested in evolutionary optimization (EO) as a means to address hard optimization problems, e.g. meta-learning through long inner loop unrolls or optimizing non-differentiable operators. One core reason for this trend has been the recent innovation in hardware acceleration and compatible software - making distributed population evaluations much easier than before. Unlike for gradient descent-based methods though, there is a lack of hyperparameter understanding and best practices for EO - arguably due to severely less 'graduate student descent' and benchmarking being performed for EO methods. Additionally, classical benchmarks from the evolutionary community provide few practical insights for Deep Learning applications. This poses challenges for newcomers to hardware-accelerated EO and hinders significant adoption. Hence, we establish a new benchmark of EO methods (NeuroEvoBench) tailored toward Deep Learning applications and exhaustively evaluate traditional and meta-learned EO. We investigate core scientific questions including resource allocation, fitness shaping, normalization, regularization & scalability of EO. The benchmark is open-sourced at https://github.com/neuroevobench/neuroevobench under Apache-2.0 license.
Payoff-based learning with matrix multiplicative weights in quantum games
Authors: Authors: Kyriakos Lotidis, Panayotis Mertikopoulos, Nicholas Bambos, Jose Blanchet
Subjects: Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Optimization and Control (math.OC); Quantum Physics (quant-ph)
Abstract
In this paper, we study the problem of learning in quantum games - and other classes of semidefinite games - with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the $\mathcal{O}(1/\sqrt{T})$ convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an $\mathcal{O}(T^{-1/4})$ rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.
Preliminary Analysis on Second-Order Convergence for Biased Policy Gradient Methods
Abstract
Although the convergence of policy gradient algorithms to first-order stationary points is well-established, the objective functions of reinforcement learning problems are typically highly nonconvex. Therefore, recent work has focused on two extensions: ``global" convergence guarantees under regularity assumptions on the function structure, and second-order guarantees for escaping saddle points and convergence to true local minima. Our work expands on the latter approach, avoiding the restrictive assumptions of the former that may not apply to general objective functions. Existing results on vanilla policy gradient only consider an unbiased gradient estimator, but practical implementations under the infinite-horizon discounted setting, including both Monte-Carlo methods and actor-critic methods, involve gradient descent updates with a biased gradient estimator. We present preliminary results on the convergence of biased policy gradient algorithms to second-order stationary points, leveraging proof techniques from nonconvex optimization. In our next steps we aim to provide the first finite-time second-order convergence analysis for actor-critic algorithms.
Signal Processing Meets SGD: From Momentum to Filter
Abstract
In the field of deep learning, Stochastic Gradient Descent (SGD) and its momentum-based variants are the predominant choices for optimization algorithms. Despite all that, these momentum strategies, which accumulate historical gradients by using a fixed $\beta$ hyperparameter to smooth the optimization processing, often neglect the potential impact of the variance of historical gradients on the current gradient estimation. In the gradient variance during training, fluctuation indicates the objective function does not meet the Lipschitz continuity condition at all time, which raises the troublesome optimization problem. This paper aims to explore the potential benefits of reducing the variance of historical gradients to make optimizer converge to flat solutions. Moreover, we proposed a new optimization method based on reducing the variance. We employed the Wiener filter theory to enhance the first moment estimation of SGD, notably introducing an adaptive weight to optimizer. Specifically, the adaptive weight dynamically changes along with temporal fluctuation of gradient variance during deep learning model training. Experimental results demonstrated our proposed adaptive weight optimizer, SGDF (Stochastic Gradient Descent With Filter), can achieve satisfactory performance compared with state-of-the-art optimizers.
An operator-splitting optimization approach for phase-field simulation of equilibrium shapes of crystals
Abstract
Computing equilibrium shapes of crystals (ESC) is a challenging problem in materials science that involves minimizing an orientation-dependent (i.e., anisotropic) surface energy functional subject to a prescribed mass constraint. The highly nonlinear and singular anisotropic terms in the problem make it very challenging from both the analytical and numerical aspects. Especially, when the strength of anisotropy is very strong (i.e., strongly anisotropic cases), the ESC will form some singular, sharp corners even if the surface energy function is smooth. Traditional numerical approaches, such as the $H^{-1}$ gradient flow, are unable to produce true sharp corners due to the necessary addition of a high-order regularization term that penalizes sharp corners and rounds them off. In this paper, we propose a new numerical method based on the Davis-Yin splitting (DYS) optimization algorithm to predict the ESC instead of using gradient flow approaches. We discretize the infinite-dimensional phase-field energy functional in the absence of regularization terms and transform it into a finite-dimensional constraint minimization problem. The resulting optimization problem is solved using the DYS method which automatically guarantees the mass-conservation and bound-preserving properties. We also prove the global convergence of the proposed algorithm. These desired properties are numerically observed. In particular, the proposed method can produce real sharp corners with satisfactory accuracy. Finally, we present numerous numerical results to demonstrate that the ESC can be well simulated under different types of anisotropic surface energies, which also confirms the effectiveness and efficiency of the proposed method.
Weight-Sharing Regularization
Authors: Authors: Mehran Shakerinava, Motahareh Sohrabi, Siamak Ravanbakhsh, Simon Lacoste-Julien
Abstract
Weight-sharing is ubiquitous in deep learning. Motivated by this, we introduce ''weight-sharing regularization'' for neural networks, defined as $R(w) = \frac{1}{d - 1}\sum_{i > j}^d |w_i - w_j|$. We study the proximal mapping of $R$ and provide an intuitive interpretation of it in terms of a physical system of interacting particles. Using this interpretation, we design a novel parallel algorithm for $\operatorname{prox}_R$ which provides an exponential speedup over previous algorithms, with a depth of $O(\log^3 d)$. Our algorithm makes it feasible to train weight-sharing regularized deep neural networks with proximal gradient descent. Experiments reveal that weight-sharing regularization enables fully-connected networks to learn convolution-like filters.
Keyword: super-resolution
An Operator Learning Framework for Spatiotemporal Super-resolution of Scientific Simulations
Authors: Authors: Valentin Duruisseaux, Amit Chakraborty
Abstract
In numerous contexts, high-resolution solutions to partial differential equations are required to capture faithfully essential dynamics which occur at small spatiotemporal scales, but these solutions can be very difficult and slow to obtain using traditional methods due to limited computational resources. A recent direction to circumvent these computational limitations is to use machine learning techniques for super-resolution, to reconstruct high-resolution numerical solutions from low-resolution simulations which can be obtained more efficiently. The proposed approach, the Super Resolution Operator Network (SROpNet), frames super-resolution as an operator learning problem and draws inspiration from existing architectures to learn continuous representations of solutions to parametric differential equations from low-resolution approximations, which can then be evaluated at any desired location. In addition, no restrictions are imposed on the locations of (the fixed number of) spatiotemporal sensors at which the low-resolution approximations are provided, thereby enabling the consideration of a broader spectrum of problems arising in practice, for which many existing super-resolution approaches are not well-suited.
Keyword: sgd
Signal Processing Meets SGD: From Momentum to Filter
Keyword: optimization
Relax: Composable Abstractions for End-to-End Dynamic Machine Learning
Static Virus Spread Algorithm for DNA Sequence Design
Safe Online Dynamics Learning with Initially Unknown Models and Infeasible Safety Certificates
AlberDICE: Addressing Out-Of-Distribution Joint Actions in Offline Multi-Agent RL via Alternating Stationary Distribution Correction Estimation
Joint Composite Latent Space Bayesian Optimization
Multi-scale Time-stepping of Partial Differential Equations with Transformers
State-wise Safe Reinforcement Learning With Pixel Observations
Objectives Are All You Need: Solving Deceptive Problems Without Explicit Diversity Maintenance
Predicting Ground Reaction Force from Inertial Sensors
Self-Supervised Learning of Representations for Space Generates Multi-Modular Grid Cells
Bounded and Unbiased Composite Differential Privacy
Complex Organ Mask Guided Radiology Report Generation
MC-Stereo: Multi-peak Lookup and Cascade Search Range for Stereo Matching
A Comprehensive Dynamic Simulation Framework for Coupled Neuromusculoskeletal-Exoskeletal Systems
NeuroEvoBench: Benchmarking Evolutionary Optimizers for Deep Learning Applications
SplitMAC: Wireless Split Learning over Multiple Access Channels
Time-Division Based Integrated Sensing, Communication, and Computing in Integrated Satellite-Terrestrial Networks
Payoff-based learning with matrix multiplicative weights in quantum games
Optimal Power Flow Solutions via Noise-Resilient Quantum-Inspired Interior-Point Methods
Nonlinear Multi-objective Reinforcement Learning with Provable Guarantees
Preliminary Analysis on Second-Order Convergence for Biased Policy Gradient Methods
Temporal Sequencing of Documents
Pointer Networks with Q-Learning for OP Combinatorial Optimization
Ephemeral Rollups are All you Need
Uncertainty Estimation for Safety-critical Scene Segmentation via Fine-grained Reward Maximization
Robust Generalization Strategies for Morpheme Glossing in an Endangered Language Documentation Context
Architecting Intermediate Layers for Efficient Composition of Data Management and Machine Learning Systems
Mobility as a Resource (MaaR) for resilient human-centric automation: a vision paper
Kivi: Verification for Cluster Management
Fast and Interpretable Face Identification for Out-Of-Distribution Data Using Vision Transformers
Signal Processing Meets SGD: From Momentum to Filter
InstructPix2NeRF: Instructed 3D Portrait Editing from a Single Image
Prioritized Propagation in Graph Neural Networks
Saturn: Efficient Multi-Large-Model Deep Learning
Imitation Learning based Alternative Multi-Agent Proximal Policy Optimization for Well-Formed Swarm-Oriented Pursuit Avoidance
The Pursuit of Human Labeling: A New Perspective on Unsupervised Learning
Simultaneous Time Synchronization and Mutual Localization for Multi-robot System
An operator-splitting optimization approach for phase-field simulation of equilibrium shapes of crystals
Safe and Efficient Trajectory Optimization for Autonomous Vehicles using B-spline with Incremental Path Flattening
TabRepo: A Large Scale Repository of Tabular Model Evaluations and its AutoML Applications
Obstacle- and Occlusion-Responsive Visual Tracking Control for Redundant Manipulators using Reachability Measure
Antenna Positioning and Beamforming Design for Movable-Antenna Enabled Multi-user Downlink Communications
DRAUC: An Instance-wise Distributionally Robust AUC Optimization Framework
Multi-Step Optimal Tracking Control of Unknown Nonzero-Sum Games based on Least Squares and Linear Programming: An Application to a Fully-Automated, Dual-Hormone Artificial Pancreas
Unified Multi-modal Unsupervised Representation Learning for Skeleton-based Action Understanding
Benchmarking Differential Evolution on a Quantum Simulator
GPTuner: A Manual-Reading Database Tuning System via GPT-Guided Bayesian Optimization
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
DeepInception: Hypnotize Large Language Model to Be Jailbreaker
Balancing Notions of Equity: Approximation Algorithms for Fair Portfolio of Solutions in Combinatorial Optimization
On Finding Optimal (Dynamic) Arborescences
PROMPT: A Fast and Extensible Memory Profiling Framework
Congestion-aware Ride-pooling in Mixed Traffic for Autonomous Mobility-on-Demand Systems
Safe Collective Control under Noisy Inputs and Competing Constraints via Non-Smooth Barrier Functions
Ziya2: Data-centric Learning is All LLMs Need
Cross-Image Attention for Zero-Shot Appearance Transfer
Embedding First Order Logic into Kernel Machines
Exploitation-Guided Exploration for Semantic Embodied Navigation
Keyword: adam
Cryptanalysis of Nikooghadam et al.'s lightweight authentication protocol for Internet of Drones
Keyword: gradient
Efficient Symbolic Policy Learning with Differentiable Symbolic Expression
Client Orchestration and Cost-Efficient Joint Optimization for NOMA-Enabled Hierarchical Federated Learning
Ultra-Long Sequence Distributed Transformer
NeuroEvoBench: Benchmarking Evolutionary Optimizers for Deep Learning Applications
Payoff-based learning with matrix multiplicative weights in quantum games
Preliminary Analysis on Second-Order Convergence for Biased Policy Gradient Methods
Signal Processing Meets SGD: From Momentum to Filter
An operator-splitting optimization approach for phase-field simulation of equilibrium shapes of crystals
Weight-Sharing Regularization
Keyword: super-resolution
An Operator Learning Framework for Spatiotemporal Super-resolution of Scientific Simulations