Search

Robust face clustering enjoys a wide range of applications for gate passes, surveillance systems and security analysis in embedded sensors. Nevertheless, existing algorithms have limitations in finding accurate clusters when data contain noise (e.g., occluded face clustering and recognition). It is known that in subspace clustering, the ℓ 1 - and ℓ 2 -norm regularizers can improve subspace preservation and connectivity, respectively, and the elastic net regularizer (i.e., the mixture of the ℓ 1 - and ℓ 2 -norms) provides a balance between the two properties. However, existing deterministic methods have high per iteration computational complexities, making them inapplicable to large-scale problems. To address this issue, this paper proposes the first accelerated stochastic variance reduction gradient (RASVRG) algorithm for robust subspace clustering. We also introduce a new momentum acceleration technique for the RASVRG algorithm. As a result of the involvement of this momentum, the RASVRG algorithm achieves both the best oracle complexity and the fastest convergence rate, and it reaches higher efficiency in practice for both strongly convex and not strongly convex models. Various experimental results show that the RASVRG algorithm outperformed existing state-of-the-art methods with elastic net and ℓ 1 -norm regularizers in terms of accuracy in most cases. As demonstrated on real-world face datasets with different manually added levels of pixel corruption and occlusion situations, the RASVRG algorithm achieved much better performance in terms of accuracy and robustness. [ABSTRACT FROM AUTHOR]

In recent years, there is massive development of new metaheuristics as stochastic methods. Meanwhile, there is not any metaheuristics is powerful to handle all problems as stated in the no-free-lunch (NFL) theory. Based on this circumstance, this paper introduces a new swarm-based metaheuristics with the main strategy moving toward the resultant of better swarm members and avoiding the resultant of worse swarm members called group better-worse algorithm (GBWA). It consists of five searches: moving toward the best swarm member, moving toward the resultant of better swarm members, moving away from the resultant of worse swarm members, searching locally, and jumping to the opposite area. GBWA is then evaluated in three ways. The first evaluation is a comparative evaluation where GBWA is compared to five recent metaheuristics: coati optimization algorithm (COA), average and subtraction-based optimization (ASBO), clouded leopard optimization (CLO), total interaction algorithm (TIA), and osprey optimization algorithm (OOA). The second evaluation is the individual search evaluation. The third evaluation is hyperparameter test. The collection of 23 classic functions is chosen as the use case in all evaluations. The result of the first evaluation shows that GBWA is better than COA, ASBO, CLO, TIA, and OOA in 20, 21, 20, 21, and 21 functions consecutively. Meanwhile, the result of the second evaluation shows the equal contribution between the motion toward the best swarm member and the motion toward the resultant of better swarm members. [ABSTRACT FROM AUTHOR]

Machine learning (ML) is evolving rapidly and has made many theoretical breakthroughs while widely applied in various fields. ML allows systems the ability to access data and use it to enable computers to execute cognitive processes such as learning and improving from previous experiences and solving complicated issues. Many first-order stochastic optimization methods have been used to solve the optimization model of ML. These algorithms adopt Barzilai-Borwein (BB) step size instead of fixed or diminishing step size to improve performance. However, the BB step size format involves fractional calculation, which inevitably leads to a zero denominator, especially when the objective function is non-convex. The BB technique will be violated if the denominator is near 0 or even negative. To improve the computation of the step size, a Positive Defined Stabilized Barzilai-Borwein (PDSBB) approach is introduced in this paper. Integrating PDSBB with the stochastic variance reduced gradient (SVRG) approach, a new method SVRG-PDSBB is proposed. Numerical experiments have shown that the new algorithm has stabilized the performance of the new step size, which successfully avoiding zero denominators and effectively solving the common problems in machine learning. The convergence of SVRG-PDSBB is theoretically and numerically proven, and the effectiveness of the new algorithm is shown by comparison with other algorithms. [ABSTRACT FROM AUTHOR]

This paper focuses on stochastic methods for solving smooth non-convex strongly-concave min-max problems, which have received increasing attention due to their potential applications in deep learning (e.g., deep AUC maximization, distributionally robust optimization). However, most of the existing algorithms are slow in practice, and their analysis revolves around the convergence to a nearly stationary point. We consider leveraging the Polyak-Łojasiewicz (PL) condition to design faster stochastic algorithms with stronger convergence guarantee. Although PL condition has been utilized for designing many stochastic minimization algorithms, their applications for non-convex min-max optimization remain rare. In this paper, we propose and analyze a generic framework of proximal stage-based method with many well-known stochastic updates embeddable. Fast convergence is established in terms of both the primal objective gap and the duality gap. Compared with existing studies, (i) our analysis is based on a novel Lyapunov function consisting of the primal objective gap and the duality gap of a regularized function, and (ii) the results are more comprehensive with improved rates that have better dependence on the condition number under different assumptions. We also conduct deep and non-deep learning experiments to verify the effectiveness of our methods. [ABSTRACT FROM AUTHOR]

Decentralization is a promising method of scaling up parallel machine learning systems. In this paper, we provide a tight lower bound on the iteration complexity for such methods in a stochastic non-convex setting. Our lower bound reveals a theoretical gap in known convergence rates of many existing decentralized training algorithms, such as D-PSGD. We prove by construction this lower bound is tight and achievable. Motivated by our insights, we further propose DeTAG, a practical gossip-style decentralized algorithm that achieves the lower bound with only a logarithm gap. While a simple version of DeTAG with plain SGD and constant step size suffice for achieving theoretical limits, we additionally provide convergence bound for DeTAG under general non-increasing step size and momentum. Empirically, we compare DeTAG with other decentralized algorithms on multiple vision benchmarks, including CIFAR10/100 and ImageNet. We substantiate our theory and show DeTAG converges faster on unshuffled data and in sparse networks. Furthermore, we study a DeTAG variant, DeTAG*, that practically speeds up data-center-scale model training. This manuscript is the extended version for (Lu and De Sa, 2021). [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]

Stochastic optimization (SO) algorithms based on the Powerball function, namely powered stochastic optimization (PoweredSO) algorithms, have been confirmed, effectively, and demonstrated great potential in the context of large-scale optimization and machine learning tasks. Nevertheless, the issue of how to determine the learning rate for PoweredSO is a challenge and still unsolved problem. In this paper, we propose a class of adaptive PoweredSO approaches that are efficient, scalable and robust. It takes advantage of the hypergradient descent (HD) technique to automatically acquire an online learning rate for PoweredSO-like methods. In the first part, we study the behavior of the canonical PoweredSO algorithm, the Powerball stochastic gradient descent (pbSGD) method, with HD. The existing PoweredSO algorithms also suffer from the high variance because they take the similar algorithmic framework to SO algorithms, arising from sampling tactics. Therefore, the second portion develops an adaptive powered variance-reduced optimization method via utilizing both variance-reduced technique and HD. Moreover, we present the convergence analysis of the proposed algorithms and explore their iteration complexity on non-convex cases. Numerical experiments are conducted on machine learning tasks, verifying the superior performance over modern SO algorithms. • We propose a type of adaptive powered stochastic optimization algorithms. • The theoretical analysis of the resulting algorithms is established. • Experiments on machine learning tasks verify the efficacy of the algorithms. [ABSTRACT FROM AUTHOR]

There has been a surge of works bridging MCMC sampling and optimization, with a specific focus on translating non-asymptotic convergence guarantees for optimization problems into the analysis of Langevin algorithms in MCMC sampling. A conspicuous distinction between the convergence analysis of Langevin sampling and that of optimization is that all known convergence rates for Langevin algorithms depend on the dimensionality of the problem, whereas the convergence rates for optimization are dimension-free for convex problems. Whether a dimension independent convergence rate can be achieved by the Langevin algorithm is thus a long-standing open problem. This paper provides an affirmative answer to this problem for the case of either Lipschitz or smooth convex functions with normal priors. By viewing Langevin algorithm as composite optimization, we develop a new analysis technique that leads to dimension independent convergence rates for such problems. [ABSTRACT FROM AUTHOR]

This paper studies some asymptotic properties of adaptive algorithms widely used in optimization and machine learning, and among them Adagrad and Rmsprop, which are involved in most of the blackbox deep learning algorithms. Our setup is the non-convex landscape optimization point of view, we consider a one time scale parametrization and the situation where these algorithms may or may not be used with mini-batches. We adopt the point of view of stochastic algorithms and establish the almost sure convergence of these methods when using a decreasing step-size towards the set of critical points of the target function. With a mild extra assumption on the noise, we also obtain the convergence towards the set of minimizers of the function. Along our study, we also obtain a "convergence rate" of the methods, in the vein of the works of Ghadimi and Lan (2013). [ABSTRACT FROM AUTHOR]

While many distributed optimization algorithms have been proposed for solving smooth or convex problems over the networks, few of them can handle non-convex and non-smooth problems. Based on a proximal primal-dual approach, this paper presents a new (stochastic) distributed algorithm with Nesterov momentum for accelerated optimization of non-convex and non-smooth problems. Theoretically, we show that the proposed algorithm can achieve an $\epsilon$ -stationary solution under a constant step size with $\mathcal {O}(1/\epsilon ^2)$ computation complexity and $\mathcal {O}(1/\epsilon)$ communication complexity when the epigraph of the non-smooth term is a polyhedral set. When compared to the existing gradient tracking based methods, the proposed algorithm has the same order of computation complexity but lower order of communication complexity. To the best of our knowledge, the presented result is the first stochastic algorithm with the $\mathcal {O}(1/\epsilon)$ communication complexity for non-convex and non-smooth problems. Numerical experiments for a distributed non-convex regression problem and a deep neural network based classification problem are presented to illustrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel adaptive importance sampling (AIS) algorithm for probabilistic inference. The sampler learns a proposal distribution adaptation strategy by framing AIS as a reinforcement learning problem. Under this structure, the proposal distribution of the sampler is treated as an agent whose state is controlled using a parameterized policy. At each iteration of the algorithm, the agent earns a reward that is related to its contribution to the variance of the AIS estimator of the normalization constant of the target distribution. Policy gradient methods are employed to learn a locally optimal policy that maximizes the expected value of the sum of all rewards. Numerical simulations on two different examples demonstrate promising results for the future application of the proposed method to complex Bayesian models. [ABSTRACT FROM AUTHOR]

This paper focuses on stochastic proximal gradient methods for optimizing a smooth nonconvex loss function with a non-smooth non-convex regularizer and convex constraints. To the best of our knowledge we present the rst non-asymptotic convergence bounds for this class of problem. We present two simple stochastic proximal gradient algorithms, for general stochastic and nite-sum optimization problems. In a numerical experiment we compare our algorithms with the current state-of-the-art deterministic algorithm and nd our algorithms to exhibit superior convergence. [ABSTRACT FROM AUTHOR]

Given repeated observations of several subjects over time, i.e. a longitudinal data set, this paper introduces a new model to learn a classification of the shapes progression in an unsupervised setting: we automatically cluster a longitudinal data set in different classes without labels. Our method learns for each cluster an average shape trajectory (or representative curve) and its variance in space and time. Representative trajectories are built as the combination of pieces of curves. This mixture model is flexible enough to handle independent trajectories for each cluster as well as fork and merge scenarios. The estimation of such non linear mixture models in high dimension is known to be difficult because of the trapping states effect that hampers the optimisation of cluster assignments during training. We address this issue by using a tempered version of the stochastic EM algorithm. Finally, we apply our algorithm on different data sets. First, synthetic data are used to show that a tempered scheme achieves better convergence. We then apply our method to different real data sets: 1D RECIST score used to monitor tumors growth, 3D facial expressions and meshes of the hippocampus. In particular, we show how the method can be used to test different scenarios of hippocampus atrophy in ageing by using an heteregenous population of normal ageing individuals and mild cognitive impaired subjects. [ABSTRACT FROM AUTHOR]

The fast proliferation of Internet of Things (IoT) exacerbates the current spectrum shortage. As a promising solution, licensed spectrum sharing has received great attentions recently. However, due to the unpredictable activities of incumbent users, the availability of the shared spectrum is uncertain, making the quality of service (QoS) provisioning based on it a difficult task, especially under multi-hop scenarios. In this paper, considering the energy-efficiency issue, we propose an end-to-end (E2E) QoS guaranteed green traffic off-loading scheme over the uncertain shared spectrums in multi-hop networks. Specifically, we formulate it into a two-step problem, an off-loaded traffic maximization (OTM) problem and an energy-efficiency improvement (EEI) problem. The former one is to determine the admitted sessions. To achieve the E2E QoS guarantee under the uncertain spectrum supply, we develop a concept of equivalent link capacity, and construct a risk-averse joint chance constraint. Since the formulated problem is intractable, we first develop a data-driven conservative transformation to make the joint chance constraint a set of deterministic individual ones. Then, we design a convex-hull-based and a substitution-based linearization approach to make all the constraints tractable. For the second step, the EEI problem with the same constraints as the OTM problem is designed to refine the resource scheduling for the admitted sessions to optimize the energy-efficiency. To deal with the fractional-form energy-efficiency objective, a Dinkelbach method based iterative algorithm is further developed. Numerical results have shown the effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]

Asynchronous stochastic algorithms with various variance reduction techniques (such as SVRG, S2GD, SAGA and q-SAGA) are popular in solving large scale learning problems. Recently, Reddi et al. (2015) proposed an unified variance reduction framework (i.e., HSAG) to analyze the asynchronous stochastic gradient optimization. However, the HSAG framework cannot incorporate the S2GD technique, the analysis of the HSAG framework is limited to the SVRG and SAGA techniques on the smooth convex optimization. They did not analyze other important various variance techniques (e.g., S2GD and q-SAGA) and other important optimization problems (e.g., convex optimization with non-smooth regularization and non-convex optimization with cardinality constraint). In this paper, we bridge this gap by using an unified q-memorization framework for various variance reduction techniques (including SVRG, S2GD, SAGA, q-SAGA) to analyze asynchronous stochastic algorithms for three important optimization problems. Specifically, based on the q-memorization framework, 1) we propose an asynchronous stochastic gradient hard thresholding algorithm with q-memorization (AsySGHT-qM) for the non-convex optimization with cardinality constraint, and prove that the convergence rate of AsySGHT-qM before reaching the inherent error induced by gradient hard thresholding methods is geometric. 2) We propose an asynchronous stochastic proximal gradient algorithm (AsySPG-qM) for the convex optimization with non-smooth regularization, and prove that AsySPG-qM can achieve a linear convergence rate. 3) We propose an asynchronous stochastic gradient descent algorithm (AsySGD-qM) for the general non-convex optimization problem, and prove that AsySGD-qM can achieve a sublinear convergence rate to stationary points. The experimental results on various large-scale datasets confirm the fast convergence of our AsySGHT-qM, AsySPG-qM and AsySGD-qM through concrete realizations of SVRG and SAGA. [ABSTRACT FROM AUTHOR]

Network slicing has been considered as a promising candidate to provide customized services for vehicular applications that have extremely high requirements of latency and reliability. However, the high mobility of vehicles poses significant challenges to resource management in such a stochastic vehicular environment with time-varying service demands. In this paper, we develop an online network slicing scheduling strategy for joint resource block (RB) allocation and power control in vehicular networks. The long-term time-averaged total system capacity is maximized while guaranteeing strict ultra-reliable and low-latency requirements of vehicle communication links, subject to stability constraints of task queues. The formulated problem is a mixed integer nonlinear stochastic optimization problem, which is decoupled into three subproblems by leveraging Lyapunov optimization. In order to tackle this problem, we propose an online algorithm, namely JRPSV, to obtain the optimal RB allocation and power control at each time slot according to the current network state. Furthermore, rigorous theoretical analysis is conducted for the proposed JRPSV algorithm, indicating that the system capacity and the system average latency obey a $[ {{\mathcal O}({1/V}),{\mathcal O}(V)} ]$ trade-off with the control parameter $V$. Extensive simulation results are provided to validate the theoretical analysis and demonstrate the effectiveness of JRPSV as well as the impacts of various parameters. [ABSTRACT FROM AUTHOR]

In this paper, we propose a unified view of gradient-based algorithms for stochastic convex composite optimization by extending the concept of estimate sequence introduced by Nesterov. More precisely, we interpret a large class of stochastic optimization methods as procedures that iteratively minimize a surrogate of the objective, which covers the stochastic gradient descent method and variants of the incremental approaches SAGA, SVRG, and MISO/Finito/SDCA. This point of view has several advantages: (i) we provide a simple generic proof of convergence for all of the aforementioned methods; (ii) we naturally obtain new algorithms with the same guarantees; (iii) we derive generic strategies to make these algorithms robust to stochastic noise, which is useful when data is corrupted by small random perturbations. Finally, we propose a new accelerated stochastic gradient descent algorithm and a new accelerated SVRG algorithm that is robust to stochastic noise. [ABSTRACT FROM AUTHOR]

We consider learning problems over training sets in which both, the number of training examples and the dimension of the feature vectors, are large. To solve these problems we propose the random parallel stochastic algorithm (RAPSA). We call the algorithm random parallel because it utilizes multiple parallel processors to operate on a randomly chosen subset of blocks of the feature vector. RAPSA is doubly stochastic since each processor utilizes a random set of functions to compute the stochastic gradient associated with a randomly chosen sets of variable coordinates. Algorithms that are parallel in either of these dimensions exist, but RAPSA is the first attempt at a methodology that is parallel in both the selection of blocks and the selection of elements of the training set. In RAPSA, processors utilize the randomly chosen functions to compute the stochastic gradient component associated with a randomly chosen block. The technical contribution of this paper is to show that this minimally coordinated algorithm converges to the optimal classifier when the training objective is strongly convex. Moreover, we present an accelerated version of RAPSA (ARAPSA) that incorporates the objective function curvature information by premultiplying the descent direction by a Hessian approximation matrix. We further extend the results for asynchronous settings and show that if the processors perform their updates without any coordination the algorithms are still convergent to the optimal argument. RAPSA and its extensions are then numerically evaluated on a linear estimation problem and a binary image classification task using the MNIST handwritten digit dataset. [ABSTRACT FROM AUTHOR]

Background: Computational approaches for the determination of biologically-active/native three-dimensional structures of proteins with novel sequences have to handle several challenges. The (conformation) space of possible three-dimensional spatial arrangements of the chain of amino acids that constitute a protein molecule is vast and high-dimensional. Exploration of the conformation spaces is performed in a sampling-based manner and is biased by the internal energy that sums atomic interactions. Even state-of-the-art energy functions that quantify such interactions are inherently inaccurate and associate with protein conformation spaces overly rugged energy surfaces riddled with artifact local minima. The response to these challenges in template-free protein structure prediction is to generate large numbers of low-energy conformations (also referred to as decoys) as a way of increasing the likelihood of having a diverse decoy dataset that covers a sufficient number of local minima possibly housing near-native conformations. Results: In this paper we pursue a complementary approach and propose to directly control the diversity of generated decoys. Inspired by hard optimization problems in high-dimensional and non-linear variable spaces, we propose that conformation sampling for decoy generation is more naturally framed as a multi-objective optimization problem. We demonstrate that mechanisms inherent to evolutionary search techniques facilitate such framing and allow balancing multiple objectives in protein conformation sampling. We showcase here an operationalization of this idea via a novel evolutionary algorithm that has high exploration capability and is also able to access lower-energy regions of the energy landscape of a given protein with similar or better proximity to the known native structure than several state-of-the-art decoy generation algorithms. Conclusions: The presented results constitute a promising research direction in improving decoy generation for template-free protein structure prediction with regards to balancing of multiple conflicting objectives under an optimization framework. Future work will consider additional optimization objectives and variants of improvement and selection operators to apportion a fixed computational budget. Of particular interest are directions of research that attenuate dependence on protein energy models. [ABSTRACT FROM AUTHOR]

The optimization of electrical machines and energy-harvesting devices has been one of the hot topics of research in recent years. In this context, advanced computational intelligence algorithms are suitable design tools, since they are able to optimize complex systems with a large number of constraints and free design parameters. This paper presents the social network optimization (SNO): a new population-based algorithm developed to guarantee an effective and faster exploration of the solution domain with respect to traditional optimization techniques. The proposed technique will be described and validated with a benchmark case study. Finally, the optimization problem of a tubular permanent magnet linear generator will be formulated in the context of vehicular energy-harvesting systems. [ABSTRACT FROM PUBLISHER]

Mineral concentrators can be designed to support several modes of operation, which can be optimized for different geometallurgical units. Nonetheless, alternative modes often require additional equipment and processing capacity, hence an associated capital expenditure. Moreover, the concentrator designs are often based on preliminary geological data, and are therefore subject to uncertainty. The current paper describes how stochastic mine planning algorithms may be extended to quantify the net present value (NPV) of alternative operational modes in mineral processing plants, under geological uncertainty. In particular, the Variable Neighbourhood Descent method of Lamghari et al. (2014) was originally developed for open-pit mine planning, and has now been adapted to evaluate concentrator operational modes. Sample computations are presented. [ABSTRACT FROM AUTHOR]

In this paper, we study Stochastic Composite Optimization (SCO) for sparse learning that aims to learn a sparse solution from a composite function. Most of the recent SCO algorithms have already reached the optimal expected convergence rate \mathcal O(1/\lambda T) , but they often fail to deliver sparse solutions at the end either due to the limited sparsity regularization during stochastic optimization (SO) or due to the limitation in online-to-batch conversion. Even when the objective function is strongly convex, their high probability bounds can only attain \mathcal O(\sqrt\log (1/\delta)/T) with $\delta$ is the failure probability, which is much worse than the expected convergence rate. To address these limitations, we propose a simple yet effective two-phase Stochastic Composite Optimization scheme by adding a novel powerful sparse online-to-batch conversion to the general Stochastic Optimization algorithms. We further develop three concrete algorithms, OptimalSL, LastSL and AverageSL, directly under our scheme to prove the effectiveness of the proposed scheme. Both the theoretical analysis and the experiment results show that our methods can really outperform the existing methods at the ability of sparse learning and at the meantime we can improve the high probability bound to approximately \mathcal {O}(\log (\log (T)/\delta)/\lambda T) . [ABSTRACT FROM AUTHOR]

The goal of this paper is to perform a segmentation of atherosclerotic plaques in view of evaluating their burden and to provide boundaries for computing properties such as the plaque deformation and elasticity distribution (elastogram and modulogram). The echogenicity of a region of interest comprising the plaque, the vessel lumen, and the adventitia of the artery wall in an ultrasonic B-mode image was modeled by mixtures of three Nakagami distributions, which yielded the likelihood of a Bayesian segmentation model. The main contribution of this paper is the estimation of the motion field and its integration into the prior of the Bayesian model that included a local geometrical smoothness constraint, as well as an original spatiotemporal cohesion constraint. The Maximum A Posteriori of the proposed model was computed with a variant of the exploration/selection algorithm. The starting point is a manual segmentation of the first frame. The proposed method was quantitatively compared with manual segmentations of all frames by an expert technician. Various measures were used for this evaluation, including the mean point-to-point distance and the Hausdorff distance. Results were evaluated on 94 sequences of 33 patients (for a total of 8988 images). We report a mean point-to-point distance of 0.24\pm 0.08 mm and a Hausdorff distance of 1.24\pm 0.40 mm. Our tests showed that the algorithm was not sensitive to the degree of stenosis or calcification. [ABSTRACT FROM PUBLISHER]

Abstract: The paper addresses a random search optimization method for nonlinear problems with continuous variables. The approach, called LJ-MM algorithm, deals with both unconstrained and constrained optimization problems. The algorithm was developed on the basis of the so called Luus–Jaakola (LJ) one, which was successfully used by several researchers to solve chemical and process engineering problems. The LJ-MM approach is aimed at highly multi-modal problems with sharp peaks. The major change in comparison with the LJ algorithm consists in different scheme of search space reduction rate. The tests carried out for several unconstrained and constrained problems proved its high performance for multi-modal problems with sharp peaks in particular. Also, they showed that it is the robust solver even in cases of problems with a smoother function. In all cases the performance of the LJ-MM approach depends only slightly on starting points and parameter setting. The detailed analysis of the test results and the comparison with the original LJ algorithm and others stochastic solvers is given in the paper. [Copyright &y& Elsevier]

In this paper, the joint problem of project selection and project scheduling under uncertain environment is formulated, analyzed, and solved by multistage stochastic programs. First of all, a general mathematical formulation which can address several versions of the problem is presented. A multi-period project selection and scheduling problem is introduced and modeled by multistage stochastic programs, which are effective for solving long-term planning problems under uncertainty. A set of scenarios and corresponding probabilities is applied to model the multivariate random data process (costs or revenues, available budget, chance of success). Then, due to computational complexity, a scenario tree of the resulted scenarios is constructed by scenario reduction algorithms. Finally, assuming resources of the projects to be limited and renewable, and present worth of profit of projects as the objective, the objective of the problem is maximized. Eventually, a case study is introduced and solved, and the results are presented. The effectiveness of the proposed algorithm is shown by the numerical results. [ABSTRACT FROM AUTHOR]

Adaptive control of traffic lights is a key component of any intelligent transportation system. Many real-time traffic light control (TLC) algorithms are based on graded thresholds, because precise information about the traffic congestion in the road network is hard to obtain in practice. For example, using thresholds L1 and L2, we could mark the congestion level on a particular lane as “low,” “medium,” or “high” based on whether the queue length on the lane is below L1, between L1 and L2, or above L2, respectively. However, the TLC algorithms that were proposed in the literature incorporate fixed values for the thresholds, which, in general, are not optimal for all traffic conditions. In this paper, we present an algorithm based on stochastic optimization to tune the thresholds that are associated with a TLC algorithm for optimal performance. We also propose the following three novel TLC algorithms: 1) a full-state Q-learning algorithm with state aggregation, 2) a Q-learning algorithm with function approximation that involves an enhanced feature selection scheme, and 3) a priority-based TLC scheme. All these algorithms are threshold based. Next, we combine the threshold-tuning algorithm with the three aforementioned algorithms. Such a combination results in several interesting consequences. For example, in the case of Q-learning with full-state representation, our threshold-tuning algorithm suggests an optimal way of clustering states to reduce the cardinality of the state space, and in the case of the Q-learning algorithm with function approximation, our (threshold-tuning) algorithm provides a novel feature adaptation scheme to obtain an “optimal” selection of features. Our tuning algorithm is an incremental-update online scheme with proven convergence to the optimal values of thresholds. Moreover, the additional computational effort that is required because of the integration of the tuning scheme in any of the graded-threshold-based TLC algorithms is minimal. Simulation results show a significant gain in performance when our threshold-tuning algorithm is used in conjunction with various TLC algorithms compared to the original TLC algorithms without tuning and with fixed thresholds. [ABSTRACT FROM PUBLISHER]

Algorithms that jointly allocate resources across different layers are envisioned to boost the performance of wireless systems. Recent results have revealed that two of the most important parameters that critically affect the resulting cross-layer designs are channel- and queue-state information (QSI). Motivated by these results, this paper relies on stochastic convex optimization to develop optimal algorithms that use instantaneous fading and queue length information to allocate resources at the transport (flow-control), link, and physical layers. Focus is placed on a cellular system, where an access point exchanges information with different users over flat-fading orthogonal channels. Both uplink and downlink setups are considered. The allocation strategies are obtained as the solution of a constrained utility maximization problem that involves average performance metrics. It turns out that the optimal allocation at a given instant depends on the instantaneous channel-state information (CSI) and Lagrange multipliers, which are associated with the quality-of-service (QoS) requirements and the operating conditions of the system. The multipliers are estimated online using stochastic approximation tools and are linked with the window-averaged length of the queues. Capitalizing on those links, queue stability and average queuing delay of the developed algorithms are characterized, and a simple mechanism is devised to effect delay priorities among users. [ABSTRACT FROM PUBLISHER]

Multistage stochastic programs are effective for solving long-term planning problems under uncertainty. Multi-period project portfolio selection problems can be modeled by multistage stochastic programs. These models utilize a set of scenarios and corresponding probabilities to model the multivariate random data process (costs or revenues, available budget, chance of success). For most practical problems, the optimization problem that contains all possible scenarios is too large. Due to computational complexity, this program is often approximated by a model involving a (much) smaller number of scenarios. The scenario reduction algorithms determine a subset of the initial scenario set and assign new probabilities to the preserved scenarios such that optimal values and approximate solution sets remain close to each other. This paper presents a stochastic optimization model of pharmaceutical multi-period project selection problem using a real-option valuation method. Subsequently, it reduces scenarios via existing algorithms to generate a new (smaller) scenario tree. Model with reduced scenarios has been solved in this research. Numerical results indicate improved portfolios and show the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes a stochastic optimal relaxed control methodology based on reinforcement learning (RL) for solving the automatic generation control (AGC) under NERC's control performance standards (CPS). The multi-step Q(\lambda) learning algorithm is introduced to effectively tackle the long time-delay control loop for AGC thermal plants in non-Markov environment. The moving averages of CPS1/ACE are adopted as the state feedback input, and the CPS control and relaxed control objectives are formulated as multi-criteria reward function via linear weighted aggregate method. This optimal AGC strategy provides a customized platform for interactive self-learning rules to maximize the long-run discounted reward. Statistical experiments show that the RL theory based Q(\lambda) controllers can effectively enhance the robustness and dynamic performance of AGC systems, and reduce the number of pulses and pulse reversals while the CPS compliances are ensured. The novel AGC scheme also provides a convenient way of controlling the degree of CPS compliance and relaxation by online tuning relaxation factors to implement the desirable relaxed control. [ABSTRACT FROM PUBLISHER]

Learning automata are adaptive decision making devices that are found useful in a variety of machine learning and pattern recognition applications. Although most learning automata methods deal with the case of finitely many actions for the automaton, there are also models of continuous-action-set learning automata (CALA). A team of such CALA can be useful in stochastic optimization problems where one has access only to noise-corrupted values of the objective function. In this paper, we present a novel formulation for noise-tolerant learning of linear classifiers using a CALA team. We consider the general case of nonuniform noise, where the probability that the class label of an example is wrong may be a function of the feature vector of the example. The objective is to learn the underlying separating hyperplane given only such noisy examples. We present an algorithm employing a team of CALA and prove, under some conditions on the class conditional densities, that the algorithm achieves noise-tolerant learning as long as the probability of wrong label for any example is less than 0.5. We also present some empirical results to illustrate the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present a new model for deformations of shapes. A pseudolikelihood is based on the statistical distribution of the gradient vector field of the gray level. The prior distribution is based on the Probabilistic Principal Component Analysis (PPCA). We also propose a new model based on mixtures of PPCA that is useful in the case of greater variability in the shape. A criterion of global or local object specificity based on a preliminary color segmentation of the image is included into the model. The localization of a shape in an image is then viewed as minimizing the corresponding Gibbs field. We use the Exploration/Selection (E/S) stochastic algorithm in order to find the optimal deformation. This yields a new unsupervised statistical method for localization of shapes. In order to estimate the statistical parameters for the gradient vector field of the gray level, we use an Iterative Conditional Estimation (ICE) procedure. The color segmentation of the image can be computed with an Exploration/Selection/Estimation (ESE) procedure. [ABSTRACT FROM AUTHOR]

We develop a dynamic control strategy for minimizing energy expenditure in a time-varying wireless network with adaptive transmission rates. The algorithm operates without knowledge of traffic rates or channel statistics, and yields average power that is arbitrarily close to the minimum possible value achieved by an algorithm optimized with complete knowledge of future events. Proximity to this optimal solution is shown to be inversely proportional to network delay. We then present a similar algorithm that solves the related problem of maximizing network throughput subject to peak and average power constraints. The techniques used in this paper are novel and establish a foundation for stochastic network optimization. [ABSTRACT FROM AUTHOR]

This paper develops a control algorithm that can autonomously position an electrode so as to find and then maintain an optimal extracellular recording position. The algorithm was developed and tested in a two-neuron computational model representative of the cells found in cerebral cortex. The algorithm is based on a stochastic optimization of a suitably defined signal quality metric and is shown capable of finding the optimal recording position along representative sampling directions, as well as maintaining the optimal signal quality in the face of modeled tissue movements. The application of the algorithm to acute neurophysiological recording experiments and its potential implications to chronic recording electrode arrays are discussed. [ABSTRACT FROM AUTHOR]

This paper considers an interesting topic of recipe qualification during each fabrication step of semiconductor manufacturing. In particular, this type of stochastic optimization scheme within a discrete-event simulation process is discussed and a new optimization method, with the capability to anchor robust recipes for batch processing, is proposed, implemented and evaluated. A particular real-coded genetic algorithm (GA) suitable for resolving continuous optimization problems in noisy environments is developed. Four test functions appearing in the literature are used as a test-bed to assess the proposed genetic algorithm via a variety of experimental studies, showing that the new method can produce much more accurate estimates of the true optimum points than the other two optimization procedures, the Nelder-Mead (NM) simplex search procedure and a well-known variant (RS+S9) of Nelder-Mead suitable for stochastic optimization. As such, the new method could serve as a useful tool for process recipe optimization in noisy semiconductor manufacturing environments. Finally, the chemical mechanical planarization (CMP) process, a turnkey process during semiconductor fabrication, is simulated from batch to batch based on the real-data equipment model and the presented algorithm is employed to seek the optimal recipe profile while processing each batch of wafers sequentially through the CMP tool. [ABSTRACT FROM AUTHOR]

Images registration is the process by which we determine a transformation that provides the most accurate match between two images. The search for the matching transformation can be automated with the use of a suitable metric, but it can be very time-consuming and tedious. In this paper, we introduce a registration algorithm that combines a simple yet powerful search strategy based on a stochastic gradient with two similarity measures, correlation and mutual information, together with a wavelet-based multiresolution pyramid. We limit our study to pairs of images, which are misaligned by rotation and/or translation and present two main results. First, we demonstrate that in our application mutual information may be better suited for sub-pixel registration as it produces consistently sharper optimum peaks than correlation . Then, we show that the stochastic gradient search combined with either measure produces accurate results when applied to synthetic, as well as multitemporal or multisensor collections of satellite data. Mutual information is generally found to optimize with one-third the number of iterations required by correlation. Results also show that a multiresolution implementation of the algorithm yields significant improvements in terms of both speed and robustness over a single-resolution implementation. [ABSTRACT FROM AUTHOR]

• We propose an automatic step size for zeroth-order nonconvex stochastic optimization. • We provide a rigorous theoretical analysis of the proposed algorithm. • Extensive numerical experiments verify the efficacy of the proposed algorithm. The efficacy and simplicity of using only function evaluations in zeroth-order stochastic optimization (ZOSO) makes it achieve great attention in solving large scale learning tasks. However, the question of how to choose an appropriate step size sequence timely for ZOSO has been less researched. To fill this defect, this paper provides a fast automatic step size selection approach by using an improved Barzilai-Borwein (IBB) technique with the zeroth-order (ZO) gradient estimator for ZOSO. In detail, this work shows the efficacy of the IBB technique by applying it into the advanced ZOSO method, i.e., zeroth-order stochastic variance reduced gradient (ZO-SVRG) method, which leads to a method: ZO-SVRG-IBB. We theoretically analyze the convergence of the ZO-SVRG-IBB method under the random gradient estimator and the coordinate-wise gradient estimator settings, respectively, and show that the convergence rate of ZO-SVRG-IBB matches the best-known convergence rate of advanced ZOSO methods on nonconvex functions. We further show that the query complexity of ZO-SVRG-IBB is comparable to advanced ZOSO methods. Extensive numerical experiments performed on different datasets show that the proposed method outperforms or matches state-of-the-art ZOSO methods. [ABSTRACT FROM AUTHOR]