Abstract
Over the last decades, Stochastic Gradient Descent (SGD) has been intensively studied by the Machine Learning community. Despite its versatility and excellent performance, the optimization of large models via SGD still is a time-consuming task. To reduce training time, it is common to distribute the training process across multiple devices. Recently, it has been shown that the convergence of asynchronous SGD (ASGD) will always be faster than mini-batch SGD. However, despite these improvements in the theoretical bounds, most ASGD convergence-rate proofs still rely on a centralized parameter server, which is prone to become a bottleneck when scaling out the gradient computations across many distributed processes. In this paper, we present a novel convergence-rate analysis for decentralized and asynchronous SGD (DASGD) which does not require partial synchronization among nodes nor restrictive network topologies. Specifically, we provide a bound of $\mathcal{O}(\sigma\epsilon^{-2}) + \mathcal{O}(QS{avg}\epsilon^{-3/2}) + \mathcal{O}(S{avg}\epsilon^{-1})$ for the convergence rate of DASGD, where $S{avg}$ is the average staleness between models, $Q$ is a constant that bounds the norm of the gradients, and $\epsilon$ is a (small) error that is allowed within the bound. Furthermore, when gradients are not bounded, we prove the convergence rate of DASGD to be $\mathcal{O}(\sigma\epsilon^{-2}) + \mathcal{O}(\sqrt{\hat{S}{avg}\hat{S}{max}}\epsilon^{-1})$, with $\hat{S}{max}$ and $\hat{S}_{avg}$ representing a loose version of the average and maximum staleness, respectively. Our convergence proof holds for a fixed stepsize and any non-convex, homogeneous, and L-smooth objective function. We anticipate that our results will be of high relevance for the adoption of DASGD by a broad community of researchers and developers.
Keyword: optimization
Automatic multi-dimensional pipelining for high-level synthesis of dataflow accelerators
Abstract
In recent years, there has been a surging demand for edge computing of image processing and machine learning workloads. This has reignited interest in the development of custom hardware accelerators that can deliver enhanced performance and improved energy efficiency. These workloads frequently demonstrate affine memory accesses and constant loop bounds. In this paper, we introduce an ILP-based automatic scheduler for high-level synthesis, with a specific emphasis on aggressive pipelining to enhance parallelism. In this study, we propose a unified Integer Linear Programming (ILP) formulation that can identify pipelining opportunities along multiple loop and scalar dimensions. Our multi-dimensional pipelining technique encompasses both inner loop pipelining and dataflow optimizations of Vitis HLS, while also being capable of handling more general memory access patterns compared to the dataflow optimization in Vitis HLS. Furthermore, our approach enables the generation of statically scheduled circuits, leading to improved resource efficiency. We have integrated our scheduler into a high-level synthesis compiler framework (HIR) based on MLIR and conducted performance evaluations. Our findings reveal that our scheduler, in comparison to Vitis HLS, can achieve more aggressive pipelining across multiple producer-consumer loop nests, resulting in reduced overall execution latency. The producer-consumer pipelined execution facilitated by our scheduler yields an average performance improvement of 2.42X across a set of representative benchmarks when compared to only loop pipelining. Furthermore, we achieved an average performance improvement of 1.30X over Vitis HLS with dataflow optimizations.
A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design
Abstract
Logic Synthesis (LS) plays a vital role in chip design -- a cornerstone of the semiconductor industry. A key task in LS is to transform circuits -- modeled by directed acyclic graphs (DAGs) -- into simplified circuits with equivalent functionalities. To tackle this task, many LS operators apply transformations to subgraphs -- rooted at each node on an input DAG -- sequentially. However, we found that a large number of transformations are ineffective, which makes applying these operators highly time-consuming. In particular, we notice that the runtime of the Resub and Mfs2 operators often dominates the overall runtime of LS optimization processes. To address this challenge, we propose a novel data-driven LS operator paradigm, namely PruneX, to reduce ineffective transformations. The major challenge of developing PruneX is to learn models that well generalize to unseen circuits, i.e., the out-of-distribution (OOD) generalization problem. Thus, the major technical contribution of PruneX is the novel circuit domain generalization framework, which learns domain-invariant representations based on the transformation-invariant domain-knowledge. To the best of our knowledge, PruneX is the first approach to tackle the OOD problem in LS operators. We integrate PruneX with the aforementioned Resub and Mfs2 operators. Experiments demonstrate that PruneX significantly improves their efficiency while keeping comparable optimization performance on industrial and very large-scale circuits, achieving up to $3.1\times$ faster runtime.
Sub-Array Selection in Full-Duplex Massive MIMO for Enhanced Self-Interference Suppression
Abstract
This study considers a novel full-duplex (FD) massive multiple-input multiple-output (mMIMO) system using hybrid beamforming (HBF) architecture, which allows for simultaneous uplink (UL) and downlink (DL) transmission over the same frequency band. Particularly, our objective is to mitigate the strong self-interference (SI) solely on the design of UL and DL RF beamforming stages jointly with sub-array selection (SAS) for transmit (Tx) and receive (Rx) sub-arrays at base station (BS). Based on the measured SI channel in an anechoic chamber, we propose a min-SI beamforming scheme with SAS, which applies perturbations to the beam directivity to enhance SI suppression in UL and DL beam directions. To solve this challenging nonconvex optimization problem, we propose a swarm intelligence-based algorithmic solution to find the optimal perturbations as well as the Tx and Rx sub-arrays to minimize SI subject to the directivity degradation constraints for the UL and DL beams. The results show that the proposed min-SI BF scheme can achieve SI suppression as high as 78 dB in FD mMIMO systems.
Tensor Networks for Solving Realistic Time-independent Boltzmann Neutron Transport Equation
Authors: Authors: Duc P. Truong, Mario I. Ortega, Ismael Boureima, Gianmarco Manzini, Kim Ø. Rasmussen, Boian S. Alexandrov
Abstract
Tensor network techniques, known for their low-rank approximation ability that breaks the curse of dimensionality, are emerging as a foundation of new mathematical methods for ultra-fast numerical solutions of high-dimensional Partial Differential Equations (PDEs). Here, we present a mixed Tensor Train (TT)/Quantized Tensor Train (QTT) approach for the numerical solution of time-independent Boltzmann Neutron Transport equations (BNTEs) in Cartesian geometry. Discretizing a realistic three-dimensional (3D) BNTE by (i) diamond differencing, (ii) multigroup-in-energy, and (iii) discrete ordinate collocation leads to huge generalized eigenvalue problems that generally require a matrix-free approach and large computer clusters. Starting from this discretization, we construct a TT representation of the PDE fields and discrete operators, followed by a QTT representation of the TT cores and solving the tensorized generalized eigenvalue problem in a fixed-point scheme with tensor network optimization techniques. We validate our approach by applying it to two realistic examples of 3D neutron transport problems, currently solved by the PARallel TIme-dependent SN (PARTISN) solver. We demonstrate that our TT/QTT method, executed on a standard desktop computer, leads to a yottabyte compression of the memory storage, and more than 7500 times speedup with a discrepancy of less than 1e-5 when compared to the PARTISN solution.
Towards Solving Industry-Grade Surrogate Modeling Problems using Physics Informed Machine Learning
Authors: Authors: Saakaar Bhatnagar, Andrew Comerford, Araz Banaeizadeh
Subjects: Computational Engineering, Finance, and Science (cs.CE)
Abstract
Deep learning combined with physics-based modeling represents an attractive and efficient approach for producing accurate and robust surrogate modeling. In this paper, a new framework that utilizes Physics Informed Neural Networks (PINN) to solve PDE-based problems for the creation of surrogate models for steady-state flow-thermal engineering design applications is introduced. The surrogate models developed through this framework are demonstrated on several use cases from electronics cooling to biomechanics. Additionally, it is demonstrated how these trained surrogate models can be combined with design optimization methods to improve the efficiency and reduced the cost of the design process. The former is shown through several realistic 3D examples and the latter via a detailed cost-benefit trade off. Overall, the findings of this paper demonstrate that hybrid data-PINN surrogate models combined with optimization algorithms can solve realistic design optimization and have potential in a wide variety of application areas.
Large Language Models as Optimizers
Authors: Authors: Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou, Xinyun Chen
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computation and Language (cs.CL)
Abstract
Optimization is ubiquitous. While derivative-based algorithms have been powerful tools for various problems, the absence of gradient imposes challenges on many real-world applications. In this work, we propose Optimization by PROmpting (OPRO), a simple and effective approach to leverage large language models (LLMs) as optimizers, where the optimization task is described in natural language. In each optimization step, the LLM generates new solutions from the prompt that contains previously generated solutions with their values, then the new solutions are evaluated and added to the prompt for the next optimization step. We first showcase OPRO on linear regression and traveling salesman problems, then move on to prompt optimization where the goal is to find instructions that maximize the task accuracy. With a variety of LLMs, we demonstrate that the best prompts optimized by OPRO outperform human-designed prompts by up to 8% on GSM8K, and by up to 50% on Big-Bench Hard tasks.
Equal Long-term Benefit Rate: Adapting Static Fairness Notions to Sequential Decision Making
Abstract
Decisions made by machine learning models may have lasting impacts over time, making long-term fairness a crucial consideration. It has been shown that when ignoring the long-term effect, naively imposing fairness criterion in static settings can actually exacerbate bias over time. To explicitly address biases in sequential decision-making, recent works formulate long-term fairness notions in Markov Decision Process (MDP) framework. They define the long-term bias to be the sum of static bias over each time step. However, we demonstrate that naively summing up the step-wise bias can cause a false sense of fairness since it fails to consider the importance difference of different time steps during transition. In this work, we introduce a long-term fairness notion called Equal Long-term Benefit Rate (ELBERT), which explicitly considers varying temporal importance and adapts static fairness principles to the sequential setting. Moreover, we show that the policy gradient of Long-term Benefit Rate can be analytically reduced to standard policy gradient. This makes standard policy optimization methods applicable for reducing the bias, leading to our proposed bias mitigation method ELBERT-PO. Experiments on three sequential decision making environments show that ELBERT-PO significantly reduces bias and maintains high utility. Code is available at https://github.com/Yuancheng-Xu/ELBERT.
RIS-Assisted Wireless Communications: Long-Term versus Short-Term Phase Shift Designs
Authors: Authors: Trinh Van Chien, Lam Thanh Tu, Waqas Khalid, Heejung Yu, Symeon Chatzinotas, Marco Di Renzo
Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)
Abstract
Reconfigurable intelligent surface (RIS) has recently gained significant interest as an emerging technology for future wireless networks thanks to its potential for improving the coverage probability in challenging propagation environments. This paper studies an RIS-assisted propagation environment, where a source transmits data to a destination in the presence of a weak direct link. We analyze and compare RIS designs based on long-term and short-term channel statistics in terms of coverage probability and ergodic rate. For the considered optimization designs, we derive closed-form expressions for the coverage probability and ergodic rate, which explicitly unveil the impact of both the propagation environment and the RIS on the system performance. Besides the optimization of the RIS phase profile, we formulate an RIS placement optimization problem with the aim of maximizing the coverage probability by relying only on partial channel state information. An efficient algorithm is proposed based on the gradient ascent method. Simulation results are illustrated in order to corroborate the analytical framework and findings. The proposed RIS phase profile is shown to outperform several heuristic benchmarks in terms of outage probability and ergodic rate. In addition, the proposed RIS placement strategy provides an extra degree of freedom that remarkably improves system performance.
Resource Management for IRS-assisted WP-MEC Networks with Practical Phase Shift Model
Abstract
Wireless powered mobile edge computing (WP-MEC) has been recognized as a promising solution to enhance the computational capability and sustainable energy supply for low-power wireless devices (WDs). However, when the communication links between the hybrid access point (HAP) and WDs are hostile, the energy transfer efficiency and task offloading rate are compromised. To tackle this problem, we propose to employ multiple intelligent reflecting surfaces (IRSs) to WP-MEC networks. Based on the practical IRS phase shift model, we formulate a total computation rate maximization problem by jointly optimizing downlink/uplink IRSs passive beamforming, downlink energy beamforming and uplink multi-user detection (MUD) vector at HAPs, task offloading power and local computing frequency of WDs, and the time slot allocation. Specifically, we first derive the optimal time allocation for downlink wireless energy transmission (WET) to IRSs and the corresponding energy beamforming. Next, with fixed time allocation for the downlink WET to WDs, the original optimization problem can be divided into two independent subproblems. For the WD charging subproblem, the optimal IRSs passive beamforming is derived by utilizing the successive convex approximation (SCA) method and the penalty-based optimization technique, and for the offloading computing subproblem, we propose a joint optimization framework based on the fractional programming (FP) method. Finally, simulation results validate that our proposed optimization method based on the practical phase shift model can achieve a higher total computation rate compared to the baseline schemes.
Deep Reinforcement Learning Enabled Joint Deployment and Beamforming in STAR-RIS Assisted Networks
Authors: Authors: Zhuoyuan Ma, Qi Zhao, Bai Yan, Jin Zhang
Abstract
In the new generation of wireless communication systems, reconfigurable intelligent surfaces (RIS) and simultaneously transmitting and reflecting reconfigurable intelligent surfaces (STAR-RIS) have become competitive network components to achieve intelligent and reconfigurable network environments. However, existing work has not fully studied the deployment freedom of STAR-RIS, which limits further improvements in network communication performance. Therefore, this paper proposes a solution based on a deep reinforcement learning algorithm to dynamically deploy STAR-RIS and hybrid beamforming to improve the total communication rate of users in mobile wireless networks. The paper constructs a STAR-RIS assisted multi-user multiple-input single-output (MU-MISO) mobile wireless network and jointly optimizes the dynamic deployment strategy of STAR-RIS and the hybrid beamforming strategy to maximize the long-term total communication rate of users. To solve this problem, the paper uses the Proximal Policy Optimization (PPO) algorithm to optimize the deployment of STAR-RIS and the joint beamforming strategy of STAR-RIS and the base station. The trained policy can maximize the downlink transmission rate of the system and meet the real-time decision-making needs of the system. Numerical simulation results show that compared with the traditional scheme without using STAR-RIS and fixed STAR-RIS deployment, the PPO method proposed in this paper can effectively improve the total communication rate of wireless network users in the service area.
Efficient Single Object Detection on Image Patches with Early Exit Enhanced High-Precision CNNs
Abstract
This paper proposes a novel approach for detecting objects using mobile robots in the context of the RoboCup Standard Platform League, with a primary focus on detecting the ball. The challenge lies in detecting a dynamic object in varying lighting conditions and blurred images caused by fast movements. To address this challenge, the paper presents a convolutional neural network architecture designed specifically for computationally constrained robotic platforms. The proposed CNN is trained to achieve high precision classification of single objects in image patches and to determine their precise spatial positions. The paper further integrates Early Exits into the existing high-precision CNN architecture to reduce the computational cost of easily rejectable cases in the background class. The training process involves a composite loss function based on confidence and positional losses with dynamic weighting and data augmentation. The proposed approach achieves a precision of 100% on the validation dataset and a recall of almost 87%, while maintaining an execution time of around 170 $\mu$s per hypotheses. By combining the proposed approach with an Early Exit, a runtime optimization of more than 28%, on average, can be achieved compared to the original CNN. Overall, this paper provides an efficient solution for an enhanced detection of objects, especially the ball, in computationally constrained robotic platforms.
Inter-Domain Routing with Extensible Criteria
Authors: Authors: Seyedali Tabaeiaghdaei, Marc Wyss, Giacomo Giuliari, Jelte van Bommel, Ahad N. Zehmakan, Adrian Perrig
Subjects: Networking and Internet Architecture (cs.NI)
Abstract
With the rapid evolution and diversification of Internet applications, their communication-quality criteria are continuously evolving. To globally optimize communication quality, the Internet's control plane thus needs to optimize inter-domain paths on diverse criteria, and should provide flexibility for adding new criteria or modifying existing ones. However, existing inter-domain routing protocols and proposals satisfy these requirements at best to a limited degree. We propose IREC, an inter-domain routing architecture that enables multi-criteria path optimization with extensible criteria through parallel execution and real-time addition of independent routing algorithms, together with the possibility for end domains to express their desired criteria to the control plane. We show IREC's viability by implementing it on a global testbed, and use simulations on a realistic Internet topology to demonstrate IREC's potential for path optimization in real-world deployments.
Interactive Hyperparameter Optimization in Multi-Objective Problems via Preference Learning
Authors: Authors: Joseph Giovanelli, Alexander Tornede, Tanja Tornede, Marius Lindauer
Abstract
Hyperparameter optimization (HPO) is important to leverage the full potential of machine learning (ML). In practice, users are often interested in multi-objective (MO) problems, i.e., optimizing potentially conflicting objectives, like accuracy and energy consumption. To tackle this, the vast majority of MO-ML algorithms return a Pareto front of non-dominated machine learning models to the user. Optimizing the hyperparameters of such algorithms is non-trivial as evaluating a hyperparameter configuration entails evaluating the quality of the resulting Pareto front. In literature, there are known indicators that assess the quality of a Pareto front (e.g., hypervolume, R2) by quantifying different properties (e.g., volume, proximity to a reference point). However, choosing the indicator that leads to the desired Pareto front might be a hard task for a user. In this paper, we propose a human-centered interactive HPO approach tailored towards multi-objective ML leveraging preference learning to extract desiderata from users that guide the optimization. Instead of relying on the user guessing the most suitable indicator for their needs, our approach automatically learns an appropriate indicator. Concretely, we leverage pairwise comparisons of distinct Pareto fronts to learn such an appropriate quality indicator. Then, we optimize the hyperparameters of the underlying MO-ML algorithm towards this learned indicator using a state-of-the-art HPO approach. In an experimental study targeting the environmental impact of ML, we demonstrate that our approach leads to substantially better Pareto fronts compared to optimizing based on a wrong indicator pre-selected by the user, and performs comparable in the case of an advanced user knowing which indicator to pick.
Enhancing Sample Utilization through Sample Adaptive Augmentation in Semi-Supervised Learning
Authors: Authors: Guan Gui, Zhen Zhao, Lei Qi, Luping Zhou, Lei Wang, Yinghuan Shi
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Abstract
In semi-supervised learning, unlabeled samples can be utilized through augmentation and consistency regularization. However, we observed certain samples, even undergoing strong augmentation, are still correctly classified with high confidence, resulting in a loss close to zero. It indicates that these samples have been already learned well and do not provide any additional optimization benefits to the model. We refer to these samples as ``naive samples". Unfortunately, existing SSL models overlook the characteristics of naive samples, and they just apply the same learning strategy to all samples. To further optimize the SSL model, we emphasize the importance of giving attention to naive samples and augmenting them in a more diverse manner. Sample adaptive augmentation (SAA) is proposed for this stated purpose and consists of two modules: 1) sample selection module; 2) sample augmentation module. Specifically, the sample selection module picks out {naive samples} based on historical training information at each epoch, then the naive samples will be augmented in a more diverse manner in the sample augmentation module. Thanks to the extreme ease of implementation of the above modules, SAA is advantageous for being simple and lightweight. We add SAA on top of FixMatch and FlexMatch respectively, and experiments demonstrate SAA can significantly improve the models. For example, SAA helped improve the accuracy of FixMatch from 92.50% to 94.76% and that of FlexMatch from 95.01% to 95.31% on CIFAR-10 with 40 labels.
Chasing Consistency in Text-to-3D Generation from a Single Image
Authors: Authors: Yichen Ouyang, Wenhao Chai, Jiayi Ye, Dapeng Tao, Yibing Zhan, Gaoang Wang
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Abstract
Text-to-3D generation from a single-view image is a popular but challenging task in 3D vision. Although numerous methods have been proposed, existing works still suffer from the inconsistency issues, including 1) semantic inconsistency, 2) geometric inconsistency, and 3) saturation inconsistency, resulting in distorted, overfitted, and over-saturated generations. In light of the above issues, we present Consist3D, a three-stage framework Chasing for semantic-, geometric-, and saturation-Consistent Text-to-3D generation from a single image, in which the first two stages aim to learn parameterized consistency tokens, and the last stage is for optimization. Specifically, the semantic encoding stage learns a token independent of views and estimations, promoting semantic consistency and robustness. Meanwhile, the geometric encoding stage learns another token with comprehensive geometry and reconstruction constraints under novel-view estimations, reducing overfitting and encouraging geometric consistency. Finally, the optimization stage benefits from the semantic and geometric tokens, allowing a low classifier-free guidance scale and therefore preventing oversaturation. Experimental results demonstrate that Consist3D produces more consistent, faithful, and photo-realistic 3D assets compared to previous state-of-the-art methods. Furthermore, Consist3D also allows background and object editing through text prompts.
Estimating the Coverage Measure and the Area Explored by a Line-Sweep Sensor on the Plane
Authors: Authors: Maria Costa Vianna, Eric Goubault, Luc Jaulin, Sylvie Putot
Subjects: Robotics (cs.RO); Systems and Control (eess.SY); Geometric Topology (math.GT)
Abstract
This paper presents a method for determining the area explored by a line-sweep sensor during an area-covering mission in a two-dimensional plane. Accurate knowledge of the explored area is crucial for various applications in robotics, such as mapping, surveillance, and coverage optimization. The proposed method leverages the concept of coverage measure of the environment and its relation to the topological degree in the plane, to estimate the extent of the explored region. In addition, we extend the approach to uncertain coverage measure values using interval analysis. This last contribution allows for a guaranteed characterization of the explored area, essential considering the often critical character of area-covering missions. Finally, this paper also proposes a novel algorithm for computing the topological degree in the 2-dimensional plane, for all the points inside an area of interest, which differs from existing solutions that compute the topological degree for single points. The applicability of the method is evaluated through a real-world experiment.
Short-Term Load Forecasting Using A Particle-Swarm Optimized Multi-Head Attention-Augmented CNN-LSTM Network
Authors: Authors: Paapa Kwesi Quansah
Subjects: Machine Learning (cs.LG); Neural and Evolutionary Computing (cs.NE); Systems and Control (eess.SY)
Abstract
Short-term load forecasting is of paramount importance in the efficient operation and planning of power systems, given its inherent non-linear and dynamic nature. Recent strides in deep learning have shown promise in addressing this challenge. However, these methods often grapple with hyperparameter sensitivity, opaqueness in interpretability, and high computational overhead for real-time deployment. In this paper, I propose a novel solution that surmounts these obstacles. Our approach harnesses the power of the Particle-Swarm Optimization algorithm to autonomously explore and optimize hyperparameters, a Multi-Head Attention mechanism to discern the salient features crucial for accurate forecasting, and a streamlined framework for computational efficiency. Our method undergoes rigorous evaluation using a genuine electricity demand dataset. The results underscore its superiority in terms of accuracy, robustness, and computational efficiency. Notably, our Mean Absolute Percentage Error of 1.9376 marks a significant advancement over existing state-of-the-art approaches, heralding a new era in short-term load forecasting.
Medoid Silhouette clustering with automatic cluster number selection
Abstract
The evaluation of clustering results is difficult, highly dependent on the evaluated data set and the perspective of the beholder. There are many different clustering quality measures, which try to provide a general measure to validate clustering results. A very popular measure is the Silhouette. We discuss the efficient medoid-based variant of the Silhouette, perform a theoretical analysis of its properties, provide two fast versions for the direct optimization, and discuss the use to choose the optimal number of clusters. We combine ideas from the original Silhouette with the well-known PAM algorithm and its latest improvements FasterPAM. One of the versions guarantees equal results to the original variant and provides a run speedup of $O(k^2)$. In experiments on real data with 30000 samples and $k$=100, we observed a 10464$\times$ speedup compared to the original PAMMEDSIL algorithm. Additionally, we provide a variant to choose the optimal number of clusters directly.
Convergence Analysis of Decentralized ASGD
Authors: Authors: Mauro DL Tosi, Martin Theobald
Subjects: Machine Learning (cs.LG); Distributed, Parallel, and Cluster Computing (cs.DC)
Abstract
Over the last decades, Stochastic Gradient Descent (SGD) has been intensively studied by the Machine Learning community. Despite its versatility and excellent performance, the optimization of large models via SGD still is a time-consuming task. To reduce training time, it is common to distribute the training process across multiple devices. Recently, it has been shown that the convergence of asynchronous SGD (ASGD) will always be faster than mini-batch SGD. However, despite these improvements in the theoretical bounds, most ASGD convergence-rate proofs still rely on a centralized parameter server, which is prone to become a bottleneck when scaling out the gradient computations across many distributed processes. In this paper, we present a novel convergence-rate analysis for decentralized and asynchronous SGD (DASGD) which does not require partial synchronization among nodes nor restrictive network topologies. Specifically, we provide a bound of $\mathcal{O}(\sigma\epsilon^{-2}) + \mathcal{O}(QS{avg}\epsilon^{-3/2}) + \mathcal{O}(S{avg}\epsilon^{-1})$ for the convergence rate of DASGD, where $S{avg}$ is the average staleness between models, $Q$ is a constant that bounds the norm of the gradients, and $\epsilon$ is a (small) error that is allowed within the bound. Furthermore, when gradients are not bounded, we prove the convergence rate of DASGD to be $\mathcal{O}(\sigma\epsilon^{-2}) + \mathcal{O}(\sqrt{\hat{S}{avg}\hat{S}{max}}\epsilon^{-1})$, with $\hat{S}{max}$ and $\hat{S}_{avg}$ representing a loose version of the average and maximum staleness, respectively. Our convergence proof holds for a fixed stepsize and any non-convex, homogeneous, and L-smooth objective function. We anticipate that our results will be of high relevance for the adoption of DASGD by a broad community of researchers and developers.
Adversarially Robust Deep Learning with Optimal-Transport-Regularized Divergences
Abstract
We introduce the $ARMOR_D$ methods as novel approaches to enhancing the adversarial robustness of deep learning models. These methods are based on a new class of optimal-transport-regularized divergences, constructed via an infimal convolution between an information divergence and an optimal-transport (OT) cost. We use these as tools to enhance adversarial robustness by maximizing the expected loss over a neighborhood of distributions, a technique known as distributionally robust optimization. Viewed as a tool for constructing adversarial samples, our method allows samples to be both transported, according to the OT cost, and re-weighted, according to the information divergence. We demonstrate the effectiveness of our method on malware detection and image recognition applications and find that, to our knowledge, it outperforms existing methods at enhancing the robustness against adversarial attacks. $ARMOR_D$ yields the robustified accuracy of $98.29\%$ against $FGSM$ and $98.18\%$ against $PGD^{40}$ on the MNIST dataset, reducing the error rate by more than $19.7\%$ and $37.2\%$ respectively compared to prior methods. Similarly, in malware detection, a discrete (binary) data domain, $ARMOR_D$ improves the robustified accuracy under $rFGSM^{50}$ attack compared to the previous best-performing adversarial training methods by $37.0\%$ while lowering false negative and false positive rates by $51.1\%$ and $57.53\%$, respectively.
Managing the Uncertainty in System Dynamics Through Distributionally Robust Stability-Constrained Optimization
Abstract
With the increasing penetration of Inverter-Based Resources (IBRs) and their impact on power system stability and operation, the concept of stability-constrained optimization has drawn significant attentions from researchers. In order to manage the parametric uncertainty due to inaccurate modeling that influences the system dynamics, this work proposes a distributionally robust stability constraint formulation, where the propagation mechanism from uncertainty of the system dynamic parameters to the stability constraint coefficients is established and managed. Since these coefficients are connected to the uncertain parameters through highly nonlinear and implicit functions, an approximation approach utilizing Taylor expansion and the Delta method is developed to estimate the statistical moments of the stability constraint coefficients based on the first and second-order derivatives, with which an ambiguity set for the distributionally robust optimization can be formulated. The accuracy of the uncertainty propagation as well as the effectiveness of the distributionally robust stability constraints are demonstrated through detailed case studies in the modified IEEE 39-bus system.
Mapping of CNNs on multi-core RRAM-based CIM architectures
Authors: Authors: Rebecca Pelke, Nils Bosbach, Jose Cubero, Felix Staudigl, Rainer Leupers, Jan Moritz Joseph
Abstract
RRAM-based multi-core systems improve the energy efficiency and performance of CNNs. Thereby, the distributed parallel execution of convolutional layers causes critical data dependencies that limit the potential speedup. This paper presents synchronization techniques for parallel inference of convolutional layers on RRAM-based CIM architectures. We propose an architecture optimization that enables efficient data exchange and discuss the impact of different architecture setups on the performance. The corresponding compiler algorithms are optimized for high speedup and low memory consumption during CNN inference. We achieve more than 99% of the theoretical acceleration limit with a marginal data transmission overhead of less than 4% for state-of-the-art CNN benchmarks.
Training Acceleration of Low-Rank Decomposed Networks using Sequential Freezing and Rank Quantization
Authors: Authors: Habib Hajimolahoseini, Walid Ahmed, Yang Liu
Abstract
Low Rank Decomposition (LRD) is a model compression technique applied to the weight tensors of deep learning models in order to reduce the number of trainable parameters and computational complexity. However, due to high number of new layers added to the architecture after applying LRD, it may not lead to a high training/inference acceleration if the decomposition ranks are not small enough. The issue is that using small ranks increases the risk of significant accuracy drop after decomposition. In this paper, we propose two techniques for accelerating low rank decomposed models without requiring to use small ranks for decomposition. These methods include rank optimization and sequential freezing of decomposed layers. We perform experiments on both convolutional and transformer-based models. Experiments show that these techniques can improve the model throughput up to 60% during training and 37% during inference when combined together while preserving the accuracy close to that of the original models
Keyword: adam
There is no result
Keyword: gradient
Large Language Models as Optimizers
Authors: Authors: Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou, Xinyun Chen
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computation and Language (cs.CL)
Abstract
Optimization is ubiquitous. While derivative-based algorithms have been powerful tools for various problems, the absence of gradient imposes challenges on many real-world applications. In this work, we propose Optimization by PROmpting (OPRO), a simple and effective approach to leverage large language models (LLMs) as optimizers, where the optimization task is described in natural language. In each optimization step, the LLM generates new solutions from the prompt that contains previously generated solutions with their values, then the new solutions are evaluated and added to the prompt for the next optimization step. We first showcase OPRO on linear regression and traveling salesman problems, then move on to prompt optimization where the goal is to find instructions that maximize the task accuracy. With a variety of LLMs, we demonstrate that the best prompts optimized by OPRO outperform human-designed prompts by up to 8% on GSM8K, and by up to 50% on Big-Bench Hard tasks.
Equal Long-term Benefit Rate: Adapting Static Fairness Notions to Sequential Decision Making
Abstract
Decisions made by machine learning models may have lasting impacts over time, making long-term fairness a crucial consideration. It has been shown that when ignoring the long-term effect, naively imposing fairness criterion in static settings can actually exacerbate bias over time. To explicitly address biases in sequential decision-making, recent works formulate long-term fairness notions in Markov Decision Process (MDP) framework. They define the long-term bias to be the sum of static bias over each time step. However, we demonstrate that naively summing up the step-wise bias can cause a false sense of fairness since it fails to consider the importance difference of different time steps during transition. In this work, we introduce a long-term fairness notion called Equal Long-term Benefit Rate (ELBERT), which explicitly considers varying temporal importance and adapts static fairness principles to the sequential setting. Moreover, we show that the policy gradient of Long-term Benefit Rate can be analytically reduced to standard policy gradient. This makes standard policy optimization methods applicable for reducing the bias, leading to our proposed bias mitigation method ELBERT-PO. Experiments on three sequential decision making environments show that ELBERT-PO significantly reduces bias and maintains high utility. Code is available at https://github.com/Yuancheng-Xu/ELBERT.
RIS-Assisted Wireless Communications: Long-Term versus Short-Term Phase Shift Designs
Authors: Authors: Trinh Van Chien, Lam Thanh Tu, Waqas Khalid, Heejung Yu, Symeon Chatzinotas, Marco Di Renzo
Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)
Abstract
Reconfigurable intelligent surface (RIS) has recently gained significant interest as an emerging technology for future wireless networks thanks to its potential for improving the coverage probability in challenging propagation environments. This paper studies an RIS-assisted propagation environment, where a source transmits data to a destination in the presence of a weak direct link. We analyze and compare RIS designs based on long-term and short-term channel statistics in terms of coverage probability and ergodic rate. For the considered optimization designs, we derive closed-form expressions for the coverage probability and ergodic rate, which explicitly unveil the impact of both the propagation environment and the RIS on the system performance. Besides the optimization of the RIS phase profile, we formulate an RIS placement optimization problem with the aim of maximizing the coverage probability by relying only on partial channel state information. An efficient algorithm is proposed based on the gradient ascent method. Simulation results are illustrated in order to corroborate the analytical framework and findings. The proposed RIS phase profile is shown to outperform several heuristic benchmarks in terms of outage probability and ergodic rate. In addition, the proposed RIS placement strategy provides an extra degree of freedom that remarkably improves system performance.
Personalized Tucker Decomposition: Modeling Commonality and Peculiarity on Tensor Data
Authors: Authors: Jiuyun Hu, Naichen Shi, Raed Al Kontar, Hao Yan
Abstract
We propose personalized Tucker decomposition (perTucker) to address the limitations of traditional tensor decomposition methods in capturing heterogeneity across different datasets. perTucker decomposes tensor data into shared global components and personalized local components. We introduce a mode orthogonality assumption and develop a proximal gradient regularized block coordinate descent algorithm that is guaranteed to converge to a stationary point. By learning unique and common representations across datasets, we demonstrate perTucker's effectiveness in anomaly detection, client classification, and clustering through a simulation study and two case studies on solar flare detection and tonnage signal classification.
Second-order, Positive, and Unconditional Energy Dissipative Scheme for Modified Poisson-Nernst-Planck Equations
Abstract
First-order energy dissipative schemes in time are available in literature for the Poisson-Nernst-Planck (PNP) equations, but second-order ones are still in lack. This work proposes novel second-order discretization in time and finite volume discretization in space for modified PNP equations that incorporate effects arising from ionic steric interactions and dielectric inhomogeneity. A multislope method on unstructured meshes is proposed to reconstruct positive, accurate approximations of mobilities on faces of control volumes. Numerical analysis proves that the proposed numerical schemes are able to unconditionally ensure the existence of positive numerical solutions, original energy dissipation, mass conservation, and preservation of steady states at discrete level. Extensive numerical simulations are conducted to demonstrate numerical accuracy and performance in preserving properties of physical significance. Applications in ion permeation through a 3D nanopore show that the modified PNP model, equipped with the proposed schemes, has promising applications in the investigation of ion selectivity and rectification. The proposed second-order discretization can be extended to design temporal second-order schemes with original energy dissipation for a type of gradient flow problems with entropy.
BroadCAM: Outcome-agnostic Class Activation Mapping for Small-scale Weakly Supervised Applications
Authors: Authors: Jiatai Lin, Guoqiang Han, Xuemiao Xu, Changhong Liang, Tien-Tsin Wong, C. L. Philip Chen, Zaiyi Liu, Chu Han
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Abstract
Class activation mapping~(CAM), a visualization technique for interpreting deep learning models, is now commonly used for weakly supervised semantic segmentation~(WSSS) and object localization~(WSOL). It is the weighted aggregation of the feature maps by activating the high class-relevance ones. Current CAM methods achieve it relying on the training outcomes, such as predicted scores~(forward information), gradients~(backward information), etc. However, when with small-scale data, unstable training may lead to less effective model outcomes and generate unreliable weights, finally resulting in incorrect activation and noisy CAM seeds. In this paper, we propose an outcome-agnostic CAM approach, called BroadCAM, for small-scale weakly supervised applications. Since broad learning system (BLS) is independent to the model learning, BroadCAM can avoid the weights being affected by the unreliable model outcomes when with small-scale data. By evaluating BroadCAM on VOC2012 (natural images) and BCSS-WSSS (medical images) for WSSS and OpenImages30k for WSOL, BroadCAM demonstrates superior performance than existing CAM methods with small-scale data (less than 5\%) in different CNN architectures. It also achieves SOTA performance with large-scale training data. Extensive qualitative comparisons are conducted to demonstrate how BroadCAM activates the high class-relevance feature maps and generates reliable CAMs when with small-scale training data.
A new numerical mesoscopic scale one-domain approach solver for free fluid/porous medium interaction
Authors: Authors: Costanza Arico, Rainer Helmig, Daniele Puleo, Martin Schneider
Abstract
A new numerical continuum \textit{one-domain} approach (ODA) solver is presented for the simulation of the transfer processes between a free fluid and a porous medium. The solver is developed in the \textit{mesoscopic} scale framework, where a continuous variation of the physical parameters of the porous medium (e.g., porosity and permeability) is assumed. The Navier-Stokes-Brinkman equations are solved along with the continuity equation, under the hypothesis of incompressible fluid. The porous medium is assumed to be fully saturated and can potentially be anisotropic. The domain is discretized with unstructured meshes allowing local refinements. A fractional time step procedure is applied, where one predictor and two corrector steps are solved within each time iteration. The predictor step is solved in the framework of a marching in space and time procedure, with some important numerical advantages. The two corrector steps require the solution of large linear systems, whose matrices are sparse, symmetric and positive definite, with $\mathcal{M}$-matrix property over Delaunay-meshes. A fast and efficient solution is obtained using a preconditioned conjugate gradient method. The discretization adopted for the two corrector steps can be regarded as a Two-Point-Flux-Approximation (TPFA) scheme, which, unlike the standard TPFA schemes, does not require the grid mesh to be $\mathbf{K}$-orthogonal, (with $\mathbf{K}$ the anisotropy tensor). As demonstrated with the provided test cases, the proposed scheme correctly retains the anisotropy effects within the porous medium. Furthermore, it overcomes the restrictions of existing mesoscopic scale one-domain approachs proposed in the literature.
Insights Into the Inner Workings of Transformer Models for Protein Function Prediction
Authors: Authors: Markus Wenzel, Erik Grüner, Nils Strodthoff
Abstract
Motivation: We explored how explainable AI (XAI) can help to shed light into the inner workings of neural networks for protein function prediction, by extending the widely used XAI method of integrated gradients such that latent representations inside of transformer models, which were finetuned to Gene Ontology term and Enzyme Commission number prediction, can be inspected too. Results: The approach enabled us to identify amino acids in the sequences that the transformers pay particular attention to, and to show that these relevant sequence parts reflect expectations from biology and chemistry, both in the embedding layer and inside of the model, where we identified transformer heads with a statistically significant correspondence of attribution maps with ground truth sequence annotations (e.g., transmembrane regions, active sites) across many proteins. Availability and Implementation: Source code can be accessed at https://github.com/markuswenzel/xai-proteins .
Manipulation of Neuronal Network Firing Patterns using Temporal Deep Unfolding-based MPC
Abstract
Because neuronal networks are intricate systems composed of interconnected neurons, their control poses challenges owing to their nonlinearity and complexity. In this paper, we propose a method to design control input to a neuronal network to manipulate the firing patterns of modules within the network. We propose a methodology for designing a control input based on temporal deep unfolding-based model predictive control (TDU-MPC), a control methodology based on the deep unfolding technique actively investigated in the context of wireless signal processing. During the method development, we address the unique characteristics of neuron dynamics, such as zero gradients in firing times, by approximating input currents using a sigmoid function. The effectiveness of the proposed method is confirmed via numerical simulations. In networks with 15 and 30 neurons, the control was achieved to switch the firing frequencies of two modules without directly applying control inputs. This study includes a tailored methodology for networked neurons, the extension of TDU-MPC to nonlinear systems with reset dynamics, and the achievement of desired firing patterns in neuronal networks.
Convergence Analysis of Decentralized ASGD
Authors: Authors: Mauro DL Tosi, Martin Theobald
Subjects: Machine Learning (cs.LG); Distributed, Parallel, and Cluster Computing (cs.DC)
Abstract
Over the last decades, Stochastic Gradient Descent (SGD) has been intensively studied by the Machine Learning community. Despite its versatility and excellent performance, the optimization of large models via SGD still is a time-consuming task. To reduce training time, it is common to distribute the training process across multiple devices. Recently, it has been shown that the convergence of asynchronous SGD (ASGD) will always be faster than mini-batch SGD. However, despite these improvements in the theoretical bounds, most ASGD convergence-rate proofs still rely on a centralized parameter server, which is prone to become a bottleneck when scaling out the gradient computations across many distributed processes. In this paper, we present a novel convergence-rate analysis for decentralized and asynchronous SGD (DASGD) which does not require partial synchronization among nodes nor restrictive network topologies. Specifically, we provide a bound of $\mathcal{O}(\sigma\epsilon^{-2}) + \mathcal{O}(QS{avg}\epsilon^{-3/2}) + \mathcal{O}(S{avg}\epsilon^{-1})$ for the convergence rate of DASGD, where $S{avg}$ is the average staleness between models, $Q$ is a constant that bounds the norm of the gradients, and $\epsilon$ is a (small) error that is allowed within the bound. Furthermore, when gradients are not bounded, we prove the convergence rate of DASGD to be $\mathcal{O}(\sigma\epsilon^{-2}) + \mathcal{O}(\sqrt{\hat{S}{avg}\hat{S}{max}}\epsilon^{-1})$, with $\hat{S}{max}$ and $\hat{S}_{avg}$ representing a loose version of the average and maximum staleness, respectively. Our convergence proof holds for a fixed stepsize and any non-convex, homogeneous, and L-smooth objective function. We anticipate that our results will be of high relevance for the adoption of DASGD by a broad community of researchers and developers.
Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck
Authors: Authors: Benjamin L. Edelman, Surbhi Goel, Sham Kakade, Eran Malach, Cyril Zhang
Abstract
This work investigates the nuanced algorithm design choices for deep learning in the presence of computational-statistical gaps. We begin by considering offline sparse parity learning, a supervised classification problem which admits a statistical query lower bound for gradient-based training of a multilayer perceptron. This lower bound can be interpreted as a multi-resource tradeoff frontier: successful learning can only occur if one is sufficiently rich (large model), knowledgeable (large dataset), patient (many training iterations), or lucky (many random guesses). We show, theoretically and experimentally, that sparse initialization and increasing network width yield significant improvements in sample efficiency in this setting. Here, width plays the role of parallel search: it amplifies the probability of finding "lottery ticket" neurons, which learn sparse features more sample-efficiently. Finally, we show that the synthetic sparse parity task can be useful as a proxy for real problems requiring axis-aligned feature learning. We demonstrate improved sample efficiency on tabular classification benchmarks by using wide, sparsely-initialized MLP models; these networks sometimes outperform tuned random forests.
Prime and Modulate Learning: Generation of forward models with signed back-propagation and environmental cues
Abstract
Deep neural networks employing error back-propagation for learning can suffer from exploding and vanishing gradient problems. Numerous solutions have been proposed such as normalisation techniques or limiting activation functions to linear rectifying units. In this work we follow a different approach which is particularly applicable to closed-loop learning of forward models where back-propagation makes exclusive use of the sign of the error signal to prime the learning, whilst a global relevance signal modulates the rate of learning. This is inspired by the interaction between local plasticity and a global neuromodulation. For example, whilst driving on an empty road, one can allow for slow step-wise optimisation of actions, whereas, at a busy junction, an error must be corrected at once. Hence, the error is the priming signal and the intensity of the experience is a modulating factor in the weight change. The advantages of this Prime and Modulate paradigm is twofold: it is free from normalisation and it makes use of relevant cues from the environment to enrich the learning. We present a mathematical derivation of the learning rule in z-space and demonstrate the real-time performance with a robotic platform. The results show a significant improvement in the speed of convergence compared to that of the conventional back-propagation.
Abstract
Scene reconstruction in the presence of high-speed motion and low illumination is important in many applications such as augmented and virtual reality, drone navigation, and autonomous robotics. Traditional motion estimation techniques fail in such conditions, suffering from too much blur in the presence of high-speed motion and strong noise in low-light conditions. Single-photon cameras have recently emerged as a promising technology capable of capturing hundreds of thousands of photon frames per second thanks to their high speed and extreme sensitivity. Unfortunately, traditional computer vision techniques are not well suited for dealing with the binary-valued photon data captured by these cameras because these are corrupted by extreme Poisson noise. Here we present a method capable of estimating extreme scene motion under challenging conditions, such as low light or high dynamic range, from a sequence of high-speed image frames such as those captured by a single-photon camera. Our method relies on iteratively improving a motion estimate by grouping and aggregating frames after-the-fact, in a stratified manner. We demonstrate the creation of high-quality panoramas under fast motion and extremely low light, and super-resolution results using a custom single-photon camera prototype. For code and supplemental material see our $\href{https://wisionlab.com/project/panoramas-from-photons/}{\text{project webpage}}$.
Keyword: sgd
Convergence Analysis of Decentralized ASGD
Keyword: optimization
Automatic multi-dimensional pipelining for high-level synthesis of dataflow accelerators
A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design
Sub-Array Selection in Full-Duplex Massive MIMO for Enhanced Self-Interference Suppression
Tensor Networks for Solving Realistic Time-independent Boltzmann Neutron Transport Equation
Towards Solving Industry-Grade Surrogate Modeling Problems using Physics Informed Machine Learning
Large Language Models as Optimizers
Equal Long-term Benefit Rate: Adapting Static Fairness Notions to Sequential Decision Making
RIS-Assisted Wireless Communications: Long-Term versus Short-Term Phase Shift Designs
Resource Management for IRS-assisted WP-MEC Networks with Practical Phase Shift Model
Deep Reinforcement Learning Enabled Joint Deployment and Beamforming in STAR-RIS Assisted Networks
Efficient Single Object Detection on Image Patches with Early Exit Enhanced High-Precision CNNs
Inter-Domain Routing with Extensible Criteria
Interactive Hyperparameter Optimization in Multi-Objective Problems via Preference Learning
Enhancing Sample Utilization through Sample Adaptive Augmentation in Semi-Supervised Learning
Chasing Consistency in Text-to-3D Generation from a Single Image
Estimating the Coverage Measure and the Area Explored by a Line-Sweep Sensor on the Plane
Short-Term Load Forecasting Using A Particle-Swarm Optimized Multi-Head Attention-Augmented CNN-LSTM Network
Medoid Silhouette clustering with automatic cluster number selection
Convergence Analysis of Decentralized ASGD
Adversarially Robust Deep Learning with Optimal-Transport-Regularized Divergences
Managing the Uncertainty in System Dynamics Through Distributionally Robust Stability-Constrained Optimization
Mapping of CNNs on multi-core RRAM-based CIM architectures
Training Acceleration of Low-Rank Decomposed Networks using Sequential Freezing and Rank Quantization
Keyword: adam
There is no result
Keyword: gradient
Large Language Models as Optimizers
Equal Long-term Benefit Rate: Adapting Static Fairness Notions to Sequential Decision Making
RIS-Assisted Wireless Communications: Long-Term versus Short-Term Phase Shift Designs
Personalized Tucker Decomposition: Modeling Commonality and Peculiarity on Tensor Data
Second-order, Positive, and Unconditional Energy Dissipative Scheme for Modified Poisson-Nernst-Planck Equations
BroadCAM: Outcome-agnostic Class Activation Mapping for Small-scale Weakly Supervised Applications
A new numerical mesoscopic scale one-domain approach solver for free fluid/porous medium interaction
Insights Into the Inner Workings of Transformer Models for Protein Function Prediction
Manipulation of Neuronal Network Firing Patterns using Temporal Deep Unfolding-based MPC
Convergence Analysis of Decentralized ASGD
Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck
Prime and Modulate Learning: Generation of forward models with signed back-propagation and environmental cues
Keyword: super-resolution
Panoramas from Photons