Search

Bi-Level Optimization (BLO) is originated from the area of economic game theory and then introduced into the optimization community. BLO is able to handle problems with a hierarchical structure, involving two levels of optimization tasks, where one task is nested inside the other. In machine learning and computer vision fields, despite the different motivations and mechanisms, a lot of complex problems, such as hyper-parameter optimization, multi-task and meta learning, neural architecture search, adversarial learning and deep reinforcement learning, actually all contain a series of closely related subproblms. In this paper, we first uniformly express these complex learning and vision problems from the perspective of BLO. Then we construct a best-response-based single-level reformulation and establish a unified algorithmic framework to understand and formulate mainstream gradient-based BLO methodologies, covering aspects ranging from fundamental automatic differentiation schemes to various accelerations, simplifications, extensions and their convergence and complexity properties. Last but not least, we discuss the potentials of our unified BLO framework for designing new algorithms and point out some promising directions for future research. A list of important papers discussed in this survey, corresponding codes, and additional resources on BLOs are publicly available at: https://github.com/vis-opt-group/BLO. [ABSTRACT FROM AUTHOR]

This paper compares three modern and two classical multiobjective optimizers (MOOs) as applied to real-world problems in electromagnetics. The behavior of sophisticated optimizers on simple test functions has been studied exhaustively. In contrast, the algorithms here are tested on practical applications, where the function evaluations are computationally expensive, making the convergence rate a crucial factor. The examples considered include the optimization of a narrowband slot antenna, a mushroom-type electromagnetic bandgap structure, and an ultrawideband Vivaldi antenna. Another popular topic in the literature is in comparing classical MOOs on electromagnetics problems. The modern optimizers chosen in this paper are state of the art and each has a distinct design philosophy. This paper introduces two unique MOOs to the electromagnetics community: BORG, an auto-adaptive genetic algorithm and the Multi-Objective Covariance Matrix Adaptation Evolutionary Strategy (MO-CMA-ES), an extension of the popular single-objective CMA-ES. These algorithms are compared to the Multi-objective Evolutionary Algorithm based on Decomposition (MOEA/D), a Chebysheff scalarization algorithm, and two classical MOOs. This paper will study the behavior of these algorithms on problems in electromagnetics with a limited number of function evaluations using five distinct metrics and will provide useful guidelines and recommended optimizer settings. [ABSTRACT FROM AUTHOR]

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest $k$ -path problem ($k$ -VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph $G$ of order $n$ , BP algorithm converges to the unique optimal solution of $k$ -VDSP on $G$ within $O(n^{2}w_{max})$ iterations, provided that the weight $w_{e}$ is nonnegative integral for each arc $e\in E(G)$ , where $w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of $k$ -VDSP to the case of multiple sources or sinks. [ABSTRACT FROM AUTHOR]

When solving constrained optimization problems (COPs) by evolutionary algorithms, the search algorithm plays a crucial role. In general, we expect that the search algorithm has the capability to balance not only diversity and convergence but also constraints and objective function during the evolution. For this purpose, this paper proposes a composite differential evolution (DE) for constrained optimization, which includes three different trial vector generation strategies with distinct advantages. In order to strike a balance between diversity and convergence, one of these three trial vector generation strategies is able to increase diversity, and the other two exhibit the property of convergence. In addition, to accomplish the tradeoff between constraints and objective function, one of the two trial vector generation strategies for convergence is guided by the individual with the least degree of constraint violation in the population, and the other is guided by the individual with the best objective function value in the population. After producing offspring by the proposed composite DE, the feasibility rule and the $\boldsymbol {\varepsilon }$ constrained method are combined elaborately for selection in this paper. Moreover, a restart scheme is proposed to help the population jump out of a local optimum in the infeasible region for some extremely complicated COPs. By assembling the above techniques together, a constrained composite DE is proposed. The experiments on two sets of benchmark test functions with various features, i.e., 24 test functions from IEEE CEC2006 and 18 test functions with 10 dimensions and 30 dimensions from IEEE CEC2010, have demonstrated that the proposed method shows better or at least competitive performance against other state-of-the-art methods. [ABSTRACT FROM AUTHOR]

This paper proposes a momentum algorithm based on Borges difference and an adaptive momentum (Adam) algorithm based on Borges difference to update parameters, which can adjust the momentum information more flexibly. The Borges difference is proposed from the definition of Borges derivative to be combined with the gradient algorithm in convolutional neural networks. The proposed momentum algorithm based on Borges difference and Adam algorithm based on Borges difference can be adjusted more flexibly in order to speed up the convergence. The parameter optimization algorithm with the Borges difference presents a better performance compared with the integer-order momentum algorithm and integer-order Adam algorithm, with the proposed nonlinear adjustment method for the parameter tuning of convolutional neural networks. By analyzing experimental results of Fashion-MNIST dataset and CIFAR-10 dataset, the optimization algorithms based on Borges difference proposed in this paper gain better effects on the optimization model compared with the corresponding ones based on the integer-order difference, and can speed up the convergence speed and recognition accuracy of the image recognition. [ABSTRACT FROM AUTHOR]

Total variation (TV) is a one of the most popular regularizers for stabilizing the solution of ill-posed inverse problems. This paper proposes a novel proximal-gradient algorithm for minimizing TV regularized least-squares cost functionals. Unlike traditional methods that require nested iterations for computing the proximal step of TV, our algorithm approximates the latter with several simple proximals that have closed form solutions. We theoretically prove that the proposed parallel proximal method achieves the TV solution with arbitrarily high precision at a global rate of converge that is equivalent to the fast proximal-gradient methods. The results in this paper have the potential to enhance the applicability of TV for solving very large-scale imaging inverse problems. [ABSTRACT FROM AUTHOR]

This paper proposes a united-based imperialist competitive algorithm (UICA) for compensatory neural fuzzy systems. The original imperialist competitive algorithm (ICA) comprises numerous empires in the population, and each empire comprises one imperialist and some colonies. Each country represents a feasible solution in the empire, and the more favorable solutions become imperialists, taking over less favorable solutions (i.e., colonies). In the ICA, each colony moves toward its relevant imperialist according to an assimilation policy. This paper proposes a UICA that focuses on this assimilation policy to explore the characteristics of the colonies. The assimilation policy consists of three major parts in this paper. In the first part, a colony searches for the best previous position of the colony. In the second part, the colony faces the best-so-far imperialist. In the third part, the colony moves toward the corresponding imperialist of the colony. The proposed UICA was applied to nonlinear system problems, and the experimental results indicated that the proposed UICA is effective. [ABSTRACT FROM PUBLISHER]

This paper revisits the temporal difference (TD) learning algorithm for the policy evaluation tasks in reinforcement learning. Typically, the performance of TD(0) and TD($\lambda$ λ ) is very sensitive to the choice of stepsizes. Oftentimes, TD(0) suffers from slow convergence. Motivated by the tight link between the TD(0) learning algorithm and the stochastic gradient methods, we develop a provably convergent adaptive projected variant of the TD(0) learning algorithm with linear function approximation that we term AdaTD(0). In contrast to the TD(0), AdaTD(0) is robust or less sensitive to the choice of stepsizes. Analytically, we establish that to reach an $\epsilon$ ε accuracy, the number of iterations needed is $\tilde{O}(\epsilon ^{-2}\ln ^4\frac{1}{\epsilon }/\ln ^4\frac{1}{\rho })$ O ˜ (ε - 2 ln 4 1 ε / ln 4 1 ρ) in the general case, where $\rho$ ρ represents the speed of the underlying Markov chain converges to the stationary distribution. This implies that the iteration complexity of AdaTD(0) is no worse than that of TD(0) in the worst case. When the stochastic semi-gradients are sparse, we provide theoretical acceleration of AdaTD(0). Going beyond TD(0), we develop an adaptive variant of TD($\lambda$ λ ), which is referred to as AdaTD($\lambda$ λ ). Empirically, we evaluate the performance of AdaTD(0) and AdaTD($\lambda$ λ ) on several standard reinforcement learning tasks, which demonstrate the effectiveness of our new approaches. [ABSTRACT FROM AUTHOR]

Variance reduction is popular in accelerating gradient descent and stochastic gradient descent for optimization problems defined on both euclidean space and Riemannian manifold. This paper further improves on existing variance reduction methods for non-convex Riemannian optimization, including R-SVRG and R-SRG/R-SPIDER by providing a unified framework for batch size adaptation. Such framework is more general than the existing works by considering retraction and vector transport and mini-batch stochastic gradients. We show that the adaptive-batch variance reduction methods require lower gradient complexities for both general non-convex and gradient dominated functions, under both finite-sum and online optimization settings. Moreover, under the new framework, we complete the analysis of R-SVRG and R-SRG, which is currently missing in the literature. We prove convergence of R-SVRG with much simpler analysis, which leads to curvature-free complexity bounds. We also show improved results for R-SRG under double-loop convergence, which match the optimal complexities as the R-SPIDER. In addition, we prove the first online complexity results for R-SVRG and R-SRG. Lastly, we discuss the potential of adapting batch size for non-smooth, constrained and second-order Riemannian optimizers. Extensive experiments on a variety of applications support the analysis and claims in the paper. [ABSTRACT FROM AUTHOR]

Over the decades, multiple approaches have been proposed to solve convex programs. The development of interior-point methods allowed solving a more general set of convex programs known as semi-definite and second-order cone programs. However, these methods are excessively slow for high dimensions. On the other hand, optimization algorithms on manifolds have shown great abilities in finding solutions to non-convex problems in a reasonable time. This paper suggests using a Riemannian optimization approach to solve a subset of convex optimization problems wherein the optimization variable is a doubly stochastic matrix. Optimization over the set of doubly stochastic matrices is crucial for multiple communications and signal processing applications, especially graph-based clustering. The paper introduces and investigates the geometries of three convex manifolds, namely the doubly stochastic, the symmetric, and the definite multinomial manifolds which generalize the simplex, also known as the multinomial manifold. Theoretical complexity analysis and numerical simulation results testify the efficiency of the proposed method over state-of-the-art algorithms. In particular, they reveal that the proposed framework outperforms conventional generic and specialized approaches, especially in high dimensions. [ABSTRACT FROM AUTHOR]

This paper presents novel numerical approaches to finding the secrecy capacity of the multiple-input multiple-output (MIMO) wiretap channel subject to multiple linear transmit covariance constraints, including sum power constraint, per antenna power constraints and interference power constraint. An analytical solution to this problem is not known and existing numerical solutions suffer from slow convergence rate and/or high per-iteration complexity. Deriving computationally efficient solutions to the secrecy capacity problem is challenging since the secrecy rate is expressed as a difference of convex functions (DC) of the transmit covariance matrix, for which its convexity is only known for some special cases. In this paper we propose two low-complexity methods to compute the secrecy capacity along with a convex reformulation for degraded channels. In the first method we capitalize on the accelerated DC algorithm which requires solving a sequence of convex subproblems, for which we propose an efficient iterative algorithm where each iteration admits a closed-form solution. In the second method, we rely on the concave-convex equivalent reformulation of the secrecy capacity problem which allows us to derive the so-called partial best response algorithm to obtain an optimal solution. Notably, each iteration of the second method can also be done in closed form. The simulation results demonstrate a faster convergence rate of our methods compared to other known solutions. We carry out extensive numerical experiments to evaluate the impact of various parameters on the achieved secrecy capacity. [ABSTRACT FROM AUTHOR]

This paper investigates the stochastic optimization problem focusing on developing scalable parallel algorithms for deep learning tasks. Our solution involves a reformation of the objective function for stochastic optimization in neural network models, along with a novel parallel computing strategy, coined the weighted aggregating stochastic gradient descent (WASGD). Following a theoretical analysis on the characteristics of the new objective function, WASGD introduces a decentralized weighted aggregating scheme based on the performance of local workers. Without any center variable, the new method automatically gauges the importance of local workers and accepts them by their contributions. Furthermore, we have developed an enhanced version of the method, WASGD+, by (1) implementing a designed sample order and (2) upgrading the weight evaluation function. To validate the new method, we benchmark our pipeline against several popular algorithms including the state-of-the-art deep neural network classifier training techniques (e.g., elastic averaging SGD). Comprehensive validation studies have been conducted on four classic datasets: CIFAR-100, CIFAR-10, Fashion-MNIST, and MNIST. Subsequent results have firmly validated the superiority of the WASGD scheme in accelerating the training of deep architecture. Better still, the enhanced version, WASGD+, is shown to be a significant improvement over its prototype. [ABSTRACT FROM AUTHOR]

This paper explores the non-convex composition optimization consisting of inner and outer finite-sum functions with a large number of component functions. This problem arises in important applications such as nonlinear embedding and reinforcement learning. Although existing approaches such as stochastic gradient descent (SGD) and stochastic variance reduced gradient (SVRG) descent can be applied to solve this problem, their query complexities tend to be high, especially when the number of inner component functions is large. Therefore, to significantly improve the query complexity of current approaches, we have devised the stochastic composition via variance reduction (SCVR). What's more, we analyze the query complexity under different numbers of inner function and outer function. Based on different kinds of estimation of inner component function, we also present the SCVRII algorithm, though the order of query complexities are the same with SCVR. Additionally, we propose an extension to handle the mini-batch cases, which improve the query complexity under the optimal mini-batch size. The experimental results validate our proposed algorithms and theoretical analyses. [ABSTRACT FROM AUTHOR]

In this paper, we propose a hybrid genetic algorithm (GA) for the optimal shape design of an axially symmetric dual-reflector antenna by combining the GA with the moving least square (MLS), which enhances the convergence rate and the global search performance. The MLS is used to construct local interpolation functions from non-uniform sample data and to estimate new superior positions. By combining these superior positions in the next generation, the MLS-GA shows better search performance for the global optimum and a faster convergence rate than those of the conventional GA. To verify the proposed MLS-GA, we applied it to the optimal shape design of the DRA at the W-band. [ABSTRACT FROM AUTHOR]

This paper concerns the problem of recovering an unknown but structured signal ${x}\in \mathbb {R} ^{n}$ from $m$ -quadratic measurements of the form ${y}_{r}= \left |{\langle {a}_{r}, {x}\rangle }\right |^{{2}}$ for ${r}={1},{2},\ldots, {m}$. We focus on the under-determined setting where the number of measurements is significantly smaller than the dimension of the signal (${m} < < {n}$). We formulate the recovery problem as a nonconvex optimization problem where prior structural information about the signal is enforced through constrains on the optimization variables. We prove the projected gradient descent, when initialized in a neighborhood of the desired signal, converges to the unknown signal at a linear rate. These results hold for any closed constraint set (convex or non-convex) providing convergence guarantees to the global optimum even when the objective function and constraint set are nonconvex. Furthermore, these results hold with a number of measurements that are only a constant factor away from the minimal number of measurements required to uniquely identify the unknown signal. Our results provide the first provably tractable algorithm for this data-poor regime, breaking local sample complexity barriers that have emerged in this paper. In this paper, we utilize and further develop powerful tools for uniform convergence of empirical processes that may have broader implications for rigorous understanding of constrained nonconvex optimization heuristics. [ABSTRACT FROM AUTHOR]

This paper presents nonlinear optimization-based position and speed estimation scheme for IPMSM drives with arbitrary signal injection generated by inherent switching ripples associated with finite control set model predictive control (FCSMPC). The existing standard sensorless techniques are not suitable for FCSMPC which applies voltage vectors directly to an electrical machine without a modulator. The proposed method optimizes the nonlinear cost function derived from the standard IPMSM model with respect to position and speed at every sampling interval. This method can be applied to any type of signal injection and, hence, an ideal candidate for sensorless FCSMPC. In this method, the signal injection is needed only to generate persistent excitation to maintain the observability at low speeds. A strong persistent excitation is always present with FCSMPC except at standstill where the control applies null vector when the reference currents are zero. This situation is overcome in this paper by introducing a small negative $d$ -axis current at standstill. Thus, the proposed method can estimate the position and speed over a wide speed range starting from standstill to the rated speed without a changeover or additional signal injection. This paper also presents detailed convergence analysis and proposes a compensator for standstill operation that prevents converging to saddle and symmetrical solutions, and therefore, also eliminates the well-known ambiguity of $\pi$ rad in position estimation. The performance of the proposed sensorless scheme is experimentally verified for a wide range of operating conditions. [ABSTRACT FROM AUTHOR]

The integration of mobile edge computing (MEC) into an ultra-dense network (UDN) can provide ubiquitous task offloading services to computation-demanding users leveraging densely deployed micro base stations. The conventional multi-user task offloading strategies are performed centrally, where a central node makes global task offloading decisions on server selection and resource allocation. In practice, the deployment becomes prohibitively complex with the increasing number of users as it involves high communication overhead and complex global optimization operations. In this paper, we develop a novel decentralized task offloading strategy in UDN, enabling users to independently make local task offloading decisions. We formulate the associated optimization problem to minimize the long-term average task delay among all users. On this basis, we develop a novel calibrated contextual bandit learning (CCBL) algorithm, where users can learn the computational delay functions of micro base stations and predict the task offloading decisions of other users in a decentralized manner. The convergence of the proposed CCBL algorithm is verified via the approachability theory. Moreover, we transfer the target of calibrated learning from all micro base stations to a single user and propose a user-oriented CCBL algorithm to further decrease the computational complexity and increase the convergence rate. Simulation results illustrate that our proposed algorithm outperforms the existing decentralized algorithms and approaches the centralized one. [ABSTRACT FROM AUTHOR]

We consider a class of nonconvex regularized optimization problems, which appear frequently in machine learning and data processing. Due to the structure of the problems, the iteratively reweighted algorithm was developed and applied to the consensus optimization. In this paper, we propose the acceleration of this scheme by adding an inertial term in each iteration. The proposed algorithms inherit the advantages of classical decentralized algorithms: they can be implemented over a connected network, in which the agents communicate with their neighbors and perform local computations. We also employ the diminishing stepsizes technique for the iteratively reweighted algorithm and consider its acceleration. In specific cases, our algorithms reduce to existing decentralized schemes and also indicate novel ones. Mathematically, we prove the convergence for both algorithms with several assumptions on the objective functions. With Kurdyka-Łojasiewicz property, convergence rates can be derived for constant stepsize case. Numerical results demonstrate the efficiency of the algorithms. [ABSTRACT FROM AUTHOR]

The spiral optimization (SPO) algorithm proposed by Tamura and Yasuda is a relatively novel and simple search concept inspired by natural spiral phenomena. This algorithm searches continuous space using no gradient and only spiral trajectories composed of spiral vectors generated by deterministic spiral models. The primary purpose of this paper is to propose conditions and settings that mathematically ensure the convergence of the SPO algorithm to a stationary point. The conditions relating to the sizes and directions of the spiral vectors and the initial search points are based on direct search theory and recent SPO algorithm theories. The presented convergence was numerically verified using test functions with different properties. [ABSTRACT FROM AUTHOR]

This paper proposes a novel proximal-gradient algorithm for a decentralized optimization problem with a composite objective containing smooth and nonsmooth terms. Specifically, the smooth and nonsmooth terms are dealt with by gradient and proximal updates, respectively. The proposed algorithm is closely related to a previous algorithm, PG-EXTRA (W. Shi, Q. Ling, G. Wu, and W. Yin, “A proximal gradient algorithm for decentralized composite optimization,” IEEE Trans. Signal Process., vol. 63, no. 22, pp. 6013–6023, 2015), but has a few advantages. First of all, agents use uncoordinated step-sizes, and the stable upper bounds on step-sizes are independent of network topologies. The step-sizes depend on local objective functions, and they can be as large as those of the gradient descent. Second, for the special case without nonsmooth terms, linear convergence can be achieved under the strong convexity assumption. The dependence of the convergence rate on the objective functions and the network are separated, and the convergence rate of the new algorithm is as good as one of the two convergence rates that match the typical rates for the general gradient descent and the consensus averaging. We provide numerical experiments to demonstrate the efficacy of the introduced algorithm and validate our theoretical discoveries. [ABSTRACT FROM AUTHOR]

This paper presents a preconditioned Krasnoselskii-Mann (KM) algorithm with an improved EM preconditioner (IEM-PKMA) for higher-order total variation (HOTV) regularized positron emission tomography (PET) image reconstruction. The PET reconstruction problem can be formulated as a three-term convex optimization model consisting of the Kullback–Leibler (KL) fidelity term, a nonsmooth penalty term, and a nonnegative constraint term which is also nonsmooth. We develop an efficient KM algorithm for solving this optimization problem based on a fixed-point characterization of its solution, with a preconditioner and a momentum technique for accelerating convergence. By combining the EM precondtioner, a thresholding, and a good inexpensive estimate of the solution, we propose an improved EM preconditioner that can not only accelerate convergence but also avoid the reconstructed image being “stuck at zero.” Numerical results in this paper show that the proposed IEM-PKMA outperforms existing state-of-the-art algorithms including, the optimization transfer descent algorithm and the preconditioned L-BFGS-B algorithm for the differentiable smoothed anisotropic total variation regularized model, the preconditioned alternating projection algorithm, and the alternating direction method of multipliers for the nondifferentiable HOTV regularized model. Encouraging initial experiments using clinical data are presented. [ABSTRACT FROM AUTHOR]

This paper proposes a decentralized algorithm for solving a consensus optimization problem defined in a static networked multi-agent system, where the local objective functions have the smooth+nonsmooth composite form. Examples of such problems include decentralized constrained quadratic programming and compressed sensing problems, as well as many regularization problems arising in inverse problems, signal processing, and machine learning, which have decentralized applications. This paper addresses the need for efficient decentralized algorithms that take advantages of proximal operations for the nonsmooth terms. We propose a proximal gradient exact first-order algorithm (PG-EXTRA) that utilizes the composite structure and has the best known convergence rate. It is a nontrivial extension to the recent algorithm EXTRA. At each iteration, each agent locally computes a gradient of the smooth part of its objective and a proximal map of the nonsmooth part, as well as exchanges information with its neighbors. The algorithm is “exact” in the sense that an exact consensus minimizer can be obtained with a fixed step size, whereas most previous methods must use diminishing step sizes. When the smooth part has Lipschitz gradients, PG-EXTRA has an ergodic convergence rate of O\left(1\over k\right) in terms of the first-order optimality residual. When the smooth part vanishes, PG-EXTRA reduces to P-EXTRA, an algorithm without the gradients (so no “G” in the name), which has a slightly improved convergence rate at o\left(1\over k\right) in a standard (non-ergodic) sense. Numerical experiments demonstrate effectiveness of PG-EXTRA and validate our convergence results [ABSTRACT FROM PUBLISHER]

Distributed primal-dual methods have been widely used for solving large-scale constrained optimization problems. The majority of existing results focus on the problems with decoupled constraints. Some recent works have studied the problems subject to separable globally coupled constraints. This paper considers the distributed optimization problems with globally coupled constraints over networks without requiring the separability of the globally coupled constraints. This is made possible by the local estimates of the constraint violations. For solving such a problem, we propose a primal-dual algorithm in the augmented Lagrangian framework, combining the average consensus technique. We first establish a non-ergodic convergence rate of $\mathcal {O}(1/k)$ in terms of the objective residual for solving a distributed constrained convex optimization problem, where $k$ is the iteration counter. Specifically, the global objective function is the aggregate of the local convex and possibly non-smooth costs, and the coupled constraint is the sum of the local linear equality constraints. The numerical results illustrate the performance of the proposed method. [ABSTRACT FROM AUTHOR]

The distributed Volt/Var control solution is a promising one for active distribution networks (ADNs), but a critical issue is how to improve the distributed algorithm's convergence with less communication burden. In this paper, we propose a bi-level consensus alternation direction multiplier method-based fully distributed Volt/Var optimization algorithm (B-FADMM) for ADNs by exploiting inverter-based rapid control devices. In the first level, the Volt/Var optimal solution of subpartitions is obtained in parallel, and the second level completes the variable increment of each partition to correct the search direction of the first level. In the algorithm, firstly, an adaptive matrix $\omega $ initialization strategy is proposed to adapt to the different magnitude of variables, which avoids non-convergence or slow convergence of the algorithm. Secondly, the null-space method is used in the second level of the algorithm to obtain the null-space basis matrix on the active constraint of the subpartition, which reduces the dimensions of the problem and the computational complexity. In addition, the conjugate gradient (CG) algorithm is used to update the dual multiplier of each partition only by exchanging coupling information among partitions, which protects information privacy. Experiments showed the proposed approach attains the same result as the centralized, the computational performance of the proposed method is far superior to some popular other distributed methods in terms of accuracy, computational efficiency, and scalability. [ABSTRACT FROM AUTHOR]

Over-the-air computation (AirComp) is a disruptive technique for fast wireless data aggregation in Internet of Things (IoT) networks via exploiting the waveform superposition property of multiple-access channels. However, the performance of AirComp is bottlenecked by the worst channel condition among all links between the IoT devices and the access point. In this paper, a reconfigurable intelligent surface (RIS) assisted AirComp system is proposed to boost the received signal power and thus mitigate the performance bottleneck by reconfiguring the propagation channels. With an objective to minimize the AirComp distortion, we propose a joint design of AirComp transceivers and RIS phase-shifts, which however turns out to be a highly intractable non-convex programming problem. To this end, we develop a novel alternating minimization framework in conjunction with the successive convex approximation technique, which is proved to converge monotonically. To reduce the computational complexity, we transform the subproblem in each alternation as a smooth convex-concave saddle point problem, which is then tackled by proposing a Mirror-Prox method that only involves a sequence of closed-form updates. Simulations show that the computation time of the proposed algorithm can be two orders of magnitude smaller than that of the state-of-the-art algorithms, while achieving a similar distortion performance. [ABSTRACT FROM AUTHOR]

This paper studies the convergence properties of the well-known message-passing algorithm for convex optimisation. Under the assumption of pairwise separability and scaled diagonal dominance, asymptotic convergence is established and a simple bound for the convergence rate is provided for message-passing. In comparison with previous results, our results do not require the given convex program to have known convex pairwise components and that our bound for the convergence rate is tighter and simpler. When specialised to quadratic optimisation, we generalise known results by providing a very simple bound for the convergence rate. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the $\ell _1$ norm of a linear map over the sphere, which arises in various machine learning applications such as orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The problem is numerically challenging due to its nonsmooth objective and nonconvex constraint, and its algorithmic aspects have not been well explored. In this paper, we show how the manifold structure of the sphere can be exploited to design fast algorithms with provable guarantees for tackling this problem. Specifically, our contribution is fourfold. First, we present a manifold proximal point algorithm (ManPPA) for the problem and show that it converges at a global sublinear rate. Furthermore, we show that ManPPA can achieve a local quadratic convergence rate when applied to sharp instances of the problem. Second, we develop a semismooth Newton-based inexact augmented Lagrangian method for computing the search direction in each iteration of ManPPA and show that it has an asymptotic superlinear convergence rate. Third, we propose a stochastic variant of ManPPA called StManPPA, which is well suited for large-scale computation, and establish its sublinear convergence rate. Both ManPPA and StManPPA have provably faster convergence rates than existing subgradient-type methods. Fourth, using ManPPA as a building block, we propose a new heuristic method for solving a matrix analog of the problem, in which the sphere is replaced by the Stiefel manifold. The results from our extensive numerical experiments on the ODL and RSR problems demonstrate the efficiency and efficacy of our proposed methods. [ABSTRACT FROM AUTHOR]

Stochastic compositional optimization generalizes classic (non-compositional) stochastic optimization to the minimization of compositions of functions. Each composition may introduce an additional expectation. The series of expectations may be nested. Stochastic compositional optimization is gaining popularity in applications such as reinforcement learning and meta learning. This paper presents a new Stochastically Corrected Stochastic Compositional gradient method (SCSC). SCSC runs in a single-time scale with a single loop, uses a fixed batch size, and guarantees to converge at the same rate as the stochastic gradient descent (SGD) method for non-compositional stochastic optimization. This is achieved by making a careful improvement to a popular stochastic compositional gradient method. It is easy to apply SGD-improvement techniques to accelerate SCSC. This helps SCSC achieve state-of-the-art performance for stochastic compositional optimization. In particular, we apply Adam to SCSC, and the exhibited rate of convergence matches that of the original Adam on non-compositional stochastic optimization. We test SCSC using the model-agnostic meta-learning tasks. [ABSTRACT FROM AUTHOR]

Coupled Matrix Tensor Factorization (CMTF) facilitates the integration and analysis of multiple data sources and helps discover meaningful information. Nonnegative CMTF (N-CMTF) has been employed in many applications for identifying latent patterns, prediction, and recommendation. However, due to the added complexity with coupling between tensor and matrix data, existing N-CMTF algorithms exhibit poor computation efficiency. In this paper, a computationally efficient N-CMTF factorization algorithm is presented based on the column-wise element selection, preventing frequent gradient updates. Theoretical and empirical analyses show that the proposed N-CMTF factorization algorithm is not only more accurate but also more computationally efficient than existing algorithms in approximating the tensor as well as in identifying the underlying nature of factors. [ABSTRACT FROM AUTHOR]

In this paper, we investigate resource allocation for IRS-assisted green multiuser multiple-input single-output (MISO) systems. To minimize the total transmit power, both the beamforming vectors at the access point (AP) and the phase shifts at multiple IRSs are jointly optimized, while taking into account the minimum required quality-of-service (QoS) of multiple users. First, two novel algorithms, namely a penalty-based alternating minimization (AltMin) algorithm and an inner approximation (IA) algorithm, are developed to tackle the non-convexity of the formulated optimization problem when perfect channel state information (CSI) is available. Existing designs employ semidefinite relaxation in AltMin-based algorithms, which, however, cannot ensure convergence. In contrast, the proposed penalty-based AltMin and IA algorithms are guaranteed to converge to a stationary point and a Karush-Kuhn-Tucker (KKT) solution of the design problem, respectively. Second, the impact of imperfect knowledge of the CSI of the channels between the AP and the users is investigated. To this end, a non-convex robust optimization problem is formulated and the penalty-based AltMin algorithm is extended to obtain a stationary solution. Simulation results reveal a key trade-off between the speed of convergence and the achievable total transmit power for the two proposed algorithms. In addition, we show that the proposed algorithms can significantly reduce the total transmit power at the AP compared to various baseline schemes and that the optimal numbers of transmit antennas and IRS reflecting elements, which maximize the system energy efficiency of the considered system, are finite. [ABSTRACT FROM AUTHOR]

This paper studies the learning ability of consensus and diffusion distributed learners from continuous streams of data arising from different but related statistical distributions. Four distinctive features for diffusion learners are revealed in relation to other decentralized schemes even under left-stochastic combination policies. First, closed-form expressions for the evolution of their excess-risk are derived for strongly convex risk functions under a diminishing step-size rule. Second, using these results, it is shown that the diffusion strategy improves the asymptotic convergence rate of the excess-risk relative to non-cooperative schemes. Third, it is shown that when the in-network cooperation rules are designed optimally, the performance of the diffusion implementation can outperform that of naive centralized processing. Finally, the arguments further show that diffusion outperforms consensus strategies asymptotically and that the asymptotic excess-risk expression is invariant to the particular network topology. The framework adopted in this paper studies convergence in the stronger mean-square-error sense, rather than in distribution, and develops tools that enable a close examination of the differences between distributed strategies in terms of asymptotic behavior, as well as in terms of convergence rates. [ABSTRACT FROM AUTHOR]

Adaptive stochastic gradient descent, which uses unbiased samples of the gradient with stepsizes chosen from the historical information, has been widely used to train neural networks for computer vision and pattern recognition tasks. This paper revisits the theoretical aspects of two classes of adaptive stochastic gradient descent methods, which contain several existing state-of-the-art schemes. We focus on the presentation of novel findings: In the general smooth case, the nonergodic convergence results are given, that is, the expectation of the gradients’ norm rather than the minimum of past iterates is proved to converge; We also studied their performances under Polyak-Łojasiewicz property on the objective function. In this case, the nonergodic convergence rates are given for the expectation of the function values. Our findings show that more substantial restrictions on the steps are needed to guarantee the nonergodic function values’ convergence (rates). [ABSTRACT FROM AUTHOR]

We consider a distributed stochastic optimization problem in networks with finite number of nodes. Each node adjusts its action to optimize the global utility of the network, which is defined as the sum of local utilities of all nodes. While Gradient descent method is a common technique to solve such optimization problem, the computation of the gradient may require much information exchange. In this paper, we consider that each node can only have a noisy numerical observation of its local utility, of which the closed-form expression is not available. This assumption is quite realistic, especially when the system is either too complex or constantly changing. Nodes may exchange partially the observation of their local utilities to estimate the global utility at each timeslot. We propose a distributed algorithm based on stochastic perturbation, under the assumption that each node has only part of the local utilities of the other nodes. We use stochastic approximation tools to prove that our algorithm converges almost surely to the optimum, given that the objective function is smooth and strictly concave. The convergence rate is also derived, under the additional assumption of strongly concave objective function. It is shown that the convergence rate scales as O (K−0.5) after a sufficient number of iterations K > K0, which is the optimal rate order in terms of K for our problem. Although the proposed algorithm can be applied to general optimization problems, we perform simulations for a typical power control problem in wireless networks and present numerical results to corroborate our claims. [ABSTRACT FROM AUTHOR]

With the increasing of the data size and the development of multi-core computers, asynchronous parallel stochastic optimization algorithms such as KroMagnon have gained significant attention. In this paper, we propose a new Sparse approximation and asynchronous parallel Stochastic Variance Reduced Gradient (SSVRG) method for sparse and high-dimensional machine learning problems. Unlike standard SVRG and its asynchronous parallel variant, KroMagnon, the snapshot point of SSVRG is set to the average of all the iterates in the previous epoch, which allows it to take much larger learning rates and also makes it more robust to the choice of learning rates. In particular, we use the sparse approximation of the popular SVRG estimator to perform completely sparse updates at all iterations. Therefore, SSVRG has a much lower per-iteration computational cost than its dense counterpart, SVRG++, and is very friendly to asynchronous parallel implementation. Moreover, we provide the convergence guarantees of SSVRG for both strongly convex and non-strongly convex problems, while existing asynchronous algorithms (e.g., KroMagnon and ASAGA) only have convergence guarantees for strongly convex problems. Finally, we extend SSVRG to non-smooth and asynchronous parallel settings. Numerical experimental results demonstrate that SSVRG converges significantly faster than the state-of-the-art asynchronous parallel methods, e.g., KroMagnon, and is usually more than three orders of magnitude faster than SVRG++. [ABSTRACT FROM AUTHOR]

The increasing application of voltage source converter (VSC) based high voltage direct current (VSC-HVDC) technology in power grids has raised the importance of incorporating DC grids and converters into the existing transmission network. This poses significant challenges in dealing with the resulting optimal power flow (OPF) problem. In this paper, a recently proposed nonconvex distributed optimization algorithm—Augmented Lagrangian based Alternating Direction Inexact Newton method (aladin), is tailored to solve the nonconvex AC/DC OPF problem for emerging voltage source converter (VSC) based multiterminal high voltage direct current (VSC-MTDC) meshed AC/DC hybrid systems. The proposed scheme decomposes this AC/DC hybrid OPF problem and handles it in a fully distributed way. Compared to the existing state-of-art Alternating Direction Method of Multipliers (admm), which is in general, not applicable for nonconvex problems, aladin has a theoretical convergence guarantee. Applying these two approaches to VSC-MTDC coupled with an IEEE benchmark AC power system illustrates that the tailored aladin outperforms admm in convergence speed and numerical robustness. [ABSTRACT FROM AUTHOR]

Federated Learning (FL) enables the multiple participating devices to collaboratively contribute to a global neural network model while keeping the training data locally. Unlike the centralized training setting, the non-IID, imbalanced (statistical heterogeneity) and distribution shifted training data of FL is distributed in the federated network, which will increase the divergences between the local models and the global model, further degrading performance. In this paper, we propose a flexible clustered federated learning (CFL) framework named FlexCFL, in which we 1) group the training of clients based on the similarities between the clients’ optimization directions for lower training divergence; 2) implement an efficient newcomer device cold start mechanism for framework scalability and practicality; 3) flexibly migrate clients to meet the challenge of client-level data distribution shift. FlexCFL can achieve improvements by dividing joint optimization into groups of sub-optimization and can strike a balance between accuracy and communication efficiency in the distribution shift environment. The convergence and complexity are analyzed to demonstrate the efficiency of FlexCFL. We also evaluate FlexCFL on several open datasets and made comparisons with related CFL frameworks. The results show that FlexCFL can significantly improve absolute test accuracy by $+10.6\%$ + 10. 6 % on FEMNIST compared with FedAvg, $+3.5\%$ + 3. 5 % on FashionMNIST compared with FedProx, $+8.4\%$ + 8. 4 % on MNIST compared with FeSEM, $+4.7\%$ + 4. 7 % on Sentiment140 compare with IFCA. The experiment results show that FlexCFL is also communication efficient in the distribution shift environment. [ABSTRACT FROM AUTHOR]

This paper studies distributed algorithms for (strongly convex) composite optimization problems over mesh networks, subject to quantized communications. Instead of focusing on a specific algorithmic design, a black-box model is proposed, casting linearly convergent distributed algorithms in the form of fixed-point iterates. The algorithmic model is equipped with a novel random or deterministic Biased Compression (BC) rule on the quantizer design, and a new Adaptive encoding Non-uniform Quantizer (ANQ) coupled with a communication-efficient encoding scheme, which implements the BC-rule using a finite number of bits (below machine precision). This fills a gap existing in most state-of-the-art quantization schemes, such as those based on the popular compression rule, which rely on communication of some scalar signals with negligible quantization error (in practice quantized at the machine precision). A unified communication complexity analysis is developed for the black-box model, determining the average number of bits required to reach a solution of the optimization problem within a target accuracy. It is shown that the proposed BC-rule preserves linear convergence of the unquantized algorithms, and a trade-off between convergence rate and communication cost under ANQ-based quantization is characterized. Numerical results validate our theoretical findings and show that distributed algorithms equipped with the proposed ANQ have more favorable communication cost than algorithms using state-of-the-art quantization rules. [ABSTRACT FROM AUTHOR]

This paper proposes an adaptive particle swarm optimization (APSO) based on a kernel support vector machine (KSVM). The proposed algorithm improves the convergence speed and exploration capability of the APSO by employing an individual adaptive parameter control based on the KSVM. To verify the algorithm’s effectiveness, it was compared with both the conventional PSO and APSO based on test functions. Finally, we applied the proposed algorithm to the optimal design of a synchronous reluctance motor (Syn-RM). [ABSTRACT FROM AUTHOR]

Antenna array has been extensively applied to wireless communication systems. Optimal design of antenna array is very useful to attain desired spatial beam and reduce signal degradation. Potential search directions in artificial bee colony (ABC) algorithm are mixed with both large step size and small step size. This could lead to the malfunction of employed bee stage and onlooker bee stage of ABC algorithm. This paper proposes to improve the effectiveness of ABC by a similarity induced search method. This method adaptively adjusts search step size. Employed bees perform large step size search, while onlooker bees do small step size search. Scout bees could probe potential high-quality solutions in neighborhoods. The proposed algorithm is tested on antenna array design problem. Compared with four other algorithms, the results verify the effectiveness of the proposed algorithm. Furthermore, the scalability of the proposed algorithm is also analyzed in terms of array element and computational time. Scalability analysis also shows that the proposed algorithm is suitable for solving antenna array design problems. [ABSTRACT FROM AUTHOR]

This paper studies linear distributed estimation of an unknown random parameter vector in a bandwidth-constrained multisensor network. To meet the bandwidth limitations, each sensor converts its observation into a low-dimensional datum via a suitable linear transformation. Then, the fusion center estimates the parameter vector by linearly combining all the received low-dimensional data, aiming at minimizing the estimation mean square error. The main purpose of this paper is to jointly determine the compression dimension of each sensor (referred to as dimension assignment) and design the corresponding compression matrix when the total compression dimensions is limited. Such a joint design problem can be formulated as a rank-constrained optimization problem and it is shown to be NP-hard for the first time. In addition, successive quadratic upper-bound minimization (SQUM), SQUM-block coordinate descent (SQUM-BCD) and nuclear norm regularization (NNR) methods are developed to solve it approximately. Furthermore, we show that any accumulation point of the sequence generated by the SQUM method satisfies the Karush-Kuhn-Tucker conditions of the rank-constrained optimization problem, and the Phase II algorithm of the SQUM-BCD and NNR methods (both are two-phase algorithms and have the same Phase II algorithm) guarantees convergence at least to a stationary point. Numerical experiments illustrate the advantages of the proposed methods compared with the existing method. [ABSTRACT FROM AUTHOR]

The decentralized unit commitment problem (DUCP) solved by autonomous distributed agents has been studied by many researchers. Several methods based on traditional distributed optimization approaches have been proposed for solving the DUCP. However, these existing methods do not determine the unit commitment (UC) decisions in a distributed manner or cannot theoretically guarantee convergence and optimality. This paper proposes a method for formulating and solving the DUCP using a recently published parallelizable augmented Lagrangian method, referred to as SDM-GS-ALM. SDM-GS-ALM is a parallelizable method for solving large-scale non-convex problems, and under mild conditions, its optimality and convergence have been proven. The DUCP can be modelled as a mixed-integer linear programming problem, and in this case, its global optimal solution can be obtained via SDM-GS-ALM. This paper focuses on the DUCP in integrated heat and electricity systems. The proposed model and solution method are both general and can be applied directly to solve the DUCP in power systems. The optimality and convergence of the proposed method are demonstrated in case studies. In three test systems, the gaps between the optimal objective values of the centralized UC problem and the DUCP are less than 0.001%. [ABSTRACT FROM AUTHOR]

This paper deals with the impact of linear approximations for the unknown nonconvex confidence region of chance-constrained ac optimal power flow problems. Such approximations are required for the formulation of tractable chance constraints. In this context, we introduce the first formulation of a chance-constrained second-order cone (SOC) OPF. The proposed formulation provides convergence guarantees due to its convexity, while it demonstrates high computational efficiency. Combined with an ac feasibility recovery, it is able to identify better solutions than chance-constrained nonconvex ac-OPF formulations. To the best of our knowledge, this paper is the first to perform a rigorous analysis of the ac feasibility recovery procedures for robust SOC-OPF problems. We identify the issues that arise from the linear approximations, and by using a reformulation of the quadratic chance constraints, we introduce new parameters able to reshape the approximation of the confidence region. We demonstrate our method on the IEEE 118-bus system. [ABSTRACT FROM AUTHOR]

Memory-based LT encoders (MBLTEs) have been shown to have better performance than the regular LT encoder in terms of bit error rate (BER) and decoding convergence speed. In this paper, we explore the entire family of MBLTEs for finite block-length codes over the binary erasure channel (BEC). We propose an algorithm to extend the first and second order MBLTE approach to an arbitrary $i$ -th order MBLTE. We analyze the performance of such encoders mathematically by characterizing the expected accumulated number of recovered variable nodes at each decoding round. We define the threshold of the memory-based encoding method (MBEM) and show that the performance of MBLTEs increases as the memory order increases up to the point where this threshold is achieved. Beyond this point, we show that the performance of MBLTEs saturates if the channel erasure probability is zero and degrades otherwise. We formulate an optimization problem to solve for the optimal memory order based on whether or not the MBEM threshold is achieved. We present an extensive set of numerical results. These show agreement between our analysis and computer simulations. They also show that our optimization problem is efficient in determining the optimal memory order of MBLTEs in terms of decoding convergence speed, BER/frame-error-rate, and error floor. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of learning a shallow artificial neural network that best fits a training data set. We study this problem in the over-parameterized regime where the numbers of observations are fewer than the number of parameters in the model. We show that with the quadratic activations, the optimization landscape of training, such shallow neural networks, has certain favorable characteristics that allow globally optimal models to be found efficiently using a variety of local search heuristics. This result holds for an arbitrary training data of input/output pairs. For differentiable activation functions, we also show that gradient descent, when suitably initialized, converges at a linear rate to a globally optimal model. This result focuses on a realizable model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to planted weight coefficients. [ABSTRACT FROM AUTHOR]

Optimal design of electric machines using finite-element analysis (FEA) necessitates too much computation time to maintain high accuracy. To reduce the computation time and obtain a global optimum in multi-modal problems, this paper presents differing extent mesh adaptive direct search (DEMADS). The proposed algorithm is classified into three groups according to the poll searching frame and mesh size for assigning a global and local searching. In particular, DEMADS shares information among solutions based on a parallel multi-start strategy for earlier stopping by deviation and checking revisits. The effectiveness of DEMADS has been validated and evaluated as the function call number and the convergence number at a global optimum using benchmarking function. Finally, it is applied to an optimization problem that minimize torque ripple of a spoke-type permanent magnet synchronous machine via FEA. [ABSTRACT FROM AUTHOR]