Search

In this paper, we study a discrete momentum consensus-based optimization (Momentum-CBO) algorithm which corresponds to a second-order generalization of the discrete first-order CBO [S.-Y. Ha, S. Jin and D. Kim, Convergence of a first-order consensus-based global optimization algorithm, Math. Models Methods Appl. Sci. 30 (2020) 2417–2444]. The proposed algorithm can be understood as the modification of ADAM-CBO, replacing the normalization term by unity. For the proposed Momentum-CBO, we provide a sufficient framework which guarantees the convergence of algorithm toward a global minimum of the objective function. Moreover, we present several experimental results showing that Momentum-CBO has an improved success rate of finding the global minimum compared to vanilla-CBO and show the stability of Momentum-CBO under different initialization schemes. We also show that Momentum-CBO can be used as the alternative of ADAM-CBO which does not have a proper convergence analysis. Finally, we give an application of Momentum-CBO for Lyapunov function approximation using symbolic regression techniques. [ABSTRACT FROM AUTHOR]

Experimentation is prevalent in online marketplaces and social networks to assess the effectiveness of new market intervention. To mitigate the interference among users in an experiment, a common practice is to use a cluster-based experiment, where the designer partitions the market into loosely connected clusters and assigns all users in the same cluster to the same variant (treatment or control). Given the experiment, we assume an unbiased Horvitz–Thompson estimator is used to estimate the total market effect of the treatment. We consider the optimization problem of choosing (correlated) randomized assignments of clusters to treatment and control to minimize the worst-case variance of the estimator under a constraint that the marginal assignment probability is q∈(0,1) for all clusters. This problem can be formulated as a linear program where both the number of decision variables and constraints are exponential in the number of clusters—and hence is generally computationally intractable. We develop a family of practical experiments that we refer to as independent block randomization (IBR) experiments. Such an experiment partitions clusters into blocks so that each block contains clusters of similar size. It then treats a fraction q of the clusters in each block (chosen uniformly at random) and does so independently across blocks. The optimal cluster partition can be obtained in a tractable way using dynamic programming. We show that these policies are asymptotically optimal when the number of clusters grows large and no cluster size dominates the rest. In the special case where cluster sizes take values in a finite set and the number of clusters of each size is a fixed proportion of the total number of clusters, the loss is only a constant that is independent of the number of clusters. Beyond the asymptotic regime, we show that the IBR experiment has a good approximation for any problem instance when q is not very tiny. We also examine the performance of the IBR experiments on data-driven numerical examples, including examples based on Airbnb and Facebook data. This paper was accepted by Itai Ashlagi, revenue management and market analytics. Funding: O. Candogan acknowledges NSF [Award 2216912] for "Institute for Data, Econometrics, Algorithms and Learning." Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2021.02741. [ABSTRACT FROM AUTHOR]

In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both nonadaptive and adaptive settings. It is shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to underrepresentation or overrepresentation of some particular groups. This motivates us to study the submodular maximization problem with group equality, in which we aim to select a group of items to maximize a (possibly nonmonotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint and other fairness notations. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0384. [ABSTRACT FROM AUTHOR]

Rank aggregation combines the preference rankings of multiple alternatives from different voters into a single consensus ranking, providing a useful model for a variety of practical applications but posing a computationally challenging problem. In this paper, we provide an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and an enhanced late acceptance local search method reinforced by a relaxed acceptance and replacement strategy and a fast incremental evaluation mechanism. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on both synthetic and real-world benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, a well-established machine learning task. We additionally analyze several key algorithmic components to gain insight into their operation. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant 72371157] and Shanghai Pujiang Programme [Grant 23PJC069]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0019) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0019). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Randomized matrix algorithms have become workhorse tools in scientific computing and machine learning. To use these algorithms safely in applications, they should be coupled with posterior error estimates to assess the quality of the output. To meet this need, this paper proposes two diagnostics: a leave-one-out error estimator for randomized low-rank approximations and a jackknife resampling method to estimate the variance of the output of a randomized matrix computation. Both of these diagnostics are rapid to compute for randomized low-rank approximation algorithms such as the randomized SVD and randomized Nystr\"om approximation, and they provide useful information that can be used to assess the quality of the computed output and guide algorithmic parameter choices. [ABSTRACT FROM AUTHOR]

Submodular maximization is a NP-hard combinatorial optimization problem regularly used in machine learning and data mining with large-scale data sets. To quantify the running time of approximation algorithms, the query complexity and adaptive complexity are two important measures, where the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially many function evaluations in parallel. These two concepts reasonably quantify the efficiency and practicability of parallel computation. In this paper, we consider the problem of maximizing a nonnegative monotone DR-submodular function over a bounded integer lattice with a cardinality constraint in a value oracle model. Prior to our work, Soma and Yoshida (Math Program 172:539–563, 2018) have studied this problem and present an approximation algorithm with almost optimal approximate ratio and the same adaptivity and query complexity. We develop two novel algorithms, called low query algorithm and low adaptivity algorithm, which have approximation ratios equal to Soma and Yoshida (2018), but reach a new record of query complexity and adaptivity. As for methods, compared with the threshold greedy in Soma and Yoshida (2018), the low query algorithm reduces the number of possible thresholds and improves both the adaptivity and query complexity. The low adaptivity algorithm further integrates a vector sequencing technique to accelerate adaptive complexity in an exponential manner while only making logarithmic sacrifices on oracle queries. [ABSTRACT FROM AUTHOR]

Machine learning-based model predictive control (ML-MPC) has been developed to control nonlinear processes with unknown first-principles models. While ML models can capture nonlinear dynamics of complex systems, the complexity of ML models leads to increased computation time for real-time implementation of ML-MPC. To address this issue, in this work, we propose an explicit ML-MPC framework for nonlinear processes using multi-parametric programming. Specifically, a self-adaptive approximation algorithm is first developed to obtain a piecewise linear affine function that approximates the behaviors of ML models. Then, multi-parametric quadratic programming (mpQP) problems are formulated to generate the solution map for states in discretized state–space. Furthermore, to accelerate the implementation of explicit ML-MPC, a neighbor-first search algorithm is developed. Finally, an example of a chemical reactor is used to demonstrate the effectiveness of the explicit ML-MPC. • An explicit MPC framework for MPCs using a general class of ML models. • A self-adaptive algorithm for approximating ML models with the desired accuracy. • Neighbor-first search algorithm for accelerating implementation of explicit ML-MPC. • Improvement of computational efficiency demonstrated in a chemical process example. [ABSTRACT FROM AUTHOR]

Aiming at the problems in the existing white-feather broiler sound signal classification research, such as not considering the information and requirements in the real engineering application scenarios, not finding new applicable sound features, not providing the basis for the selection of classification learners, and the problems in the existing white-feather broiler sound signal filtering research, such as not carrying out in-depth research, not considering the signal characteristics, not analyzing the filtering effects in detail. Therefore, in this paper, the authors cleverly combined four methods of signal filtering, signal classification, machine learning, and sparse representation to propose a filtering and classification method for white-feather broiler sound signals based on sparse representation. Specifically, in terms of signal filtering, the signal characteristics of the white-feather broiler sound signal was carefully analyzed, a combination of noise reduction processing and signal reconstruction was newly proposed, and three classic and effective approximation algorithms were adopted, then the optimal filtering method of "using OMPA for noise reduction processing, and using 50-atom OMPA for signal reconstruction" was obtained. In terms of signal classification, in addition to the time-frequency domain and Mel-Frequency Cepstral Coefficients (abbr. MFCCs), time-frequency parameter features from sparse representations were newly extracted, and a total of 60-dimensional sound features were calculated on the frame signals, thus the data set was created. Feature engineering was performed on the data set, finally, the high-quality data set was obtained. Several common machine learning classification algorithms were used to train classification learners on the data set, and random forest with better performance was selected for parameter optimization. The parameter-optimized classification learner achieved the highest average prediction accuracy of 94.09%. Majority voting was newly proposed to process the prediction results to get the required signal classification result. On this basis, a new definition of classification accuracy suitable for white-feather broiler sound signals was newly proposed. Test results in real engineering application scenarios show that, the classification accuracy achieved by the proposed method on unknown white-feather broiler sound signals is about 88.89%. Compared with the existing research, the optimal filtering method considers the signal characteristics for the first time and achieves good filtering effects. The trained classification learner obtains excellent prediction effects and achieves good classification effects on several real sound types. This study is an important supplement to existing research on animal sound signal processing and classification, and provides important reference for the subsequent white-feather broiler health monitoring research. • Skillfully combine four methods to construct a signal processing and classification scheme. • Perform signal filtering based on sparse representation for the first time. • Use sparse representation to extract new time-frequency parameter features for the first time. • Obtain the optimal classification learner for white-feather broiler sound signal classification. • Newly propose the definition of classification accuracy for engineering application requirements. [ABSTRACT FROM AUTHOR]