Search

The neural-network (NN)-based control method is a new emerging promising technique for controller design in a power electronic circuit (PEC). However, the optimization of NN-based controllers (NNCs) has significant challenges in two aspects. The first challenge is that the search space of the NNC optimization problem is such complex that the global optimization ability of the existing algorithms still needs to be improved. The second challenge is that the training process of the NNC parameters is very computationally expensive and requires a long execution time. Thus, in this article, we develop a powerful evolutionary computation-based algorithm to find a high-quality solution and reduce computational time. First, the differential evolution (DE) algorithm is adopted because it is a powerful global optimizer in solving a complex optimization problem. This can help to overcome the premature convergence in local optima to train the NNC parameters well. Second, to reduce the computational time, the DE is extended to distribute DE (DDE) by dispatching all the individuals to different distributed computing resources for parallel computing. Moreover, a resource-aware strategy (RAS) is designed to further efficiently utilize the resources by adaptively dispatching individuals to resources according to the real-time performance of the resources, which can simultaneously concern the computing ability and load state of each resource. Experimental results show that, compared with some other typical evolutionary algorithms, the proposed algorithm can get significantly better solutions within a shorter computational time. [ABSTRACT FROM AUTHOR]

Stochastic optimization methods have become a class of popular optimization tools in machine learning. Especially, stochastic gradient descent (SGD) has been widely used for machine learning problems, such as training neural networks, due to low per-iteration computational complexity. In fact, the Newton or quasi-newton (QN) methods leveraging the second-order information are able to achieve a better solution than the first-order methods. Thus, stochastic QN (SQN) methods have been developed to achieve a better solution efficiently than the stochastic first-order methods by utilizing approximate second-order information. However, the existing SQN methods still do not reach the best known stochastic first-order oracle (SFO) complexity. To fill this gap, we propose a novel faster stochastic QN method (SpiderSQN) based on the variance reduced technique of SIPDER. We prove that our SpiderSQN method reaches the best known SFO complexity of $\mathcal {O}(n+n^{1/2}\epsilon ^{-2})$ in the finite-sum setting to obtain an $\epsilon $ -first-order stationary point. To further improve its practical performance, we incorporate SpiderSQN with different momentum schemes. Moreover, the proposed algorithms are generalized to the online setting, and the corresponding SFO complexity of $\mathcal {O}(\epsilon ^{-3})$ is developed, which also matches the existing best result. Extensive experiments on benchmark data sets demonstrate that our new algorithms outperform state-of-the-art approaches for nonconvex optimization. [ABSTRACT FROM AUTHOR]

For portable devices with limited resources, it is often difficult to deploy deep networks due to the prohibitive computational overhead. Numerous approaches have been proposed to quantize weights and/or activations to speed up the inference. Loss-aware quantization has been proposed to directly formulate the impact of weight quantization on the model’s final loss. However, we discover that, under certain circumstances, such a method may not converge and end up oscillating. To tackle this issue, we introduce a novel loss-aware quantization algorithm to efficiently compress deep networks with low bit-width model weights. We provide a more accurate estimation of gradients by leveraging the Taylor expansion to compensate for the quantization error, which leads to better convergence behavior. Our theoretical analysis indicates that the gradient mismatch issue can be fixed by the newly introduced quantization error compensation term. Experimental results for both linear models and convolutional networks verify the effectiveness of our proposed method. [ABSTRACT FROM AUTHOR]

Currently, numerical optimization methods are used to solve distributed optimal power allocation (OPA) problems for islanded microgrid (MG) systems. Most of them are developed based on rigorous mathematical derivation. However, the complexity of such optimization algorithms inevitably creates a gap between theoretical analysis and real-time implementation. In order to bridge such a gap, in this article we provide a new distributed learning-based framework to solve the real-time OPA problem. Specifically, inspired by the human-thinking scheme, distributed deep neural networks (DNNs) together with a dynamic average consensus algorithm are first employed to obtain an approximate OPA solution in a distributed manner. Then a distributed balance generation and demand algorithm is designed to fine-tune it to obtain the final optimal feasible solution. In addition, it is theoretically proved that the proposed DNN can well approximate one existing OPA algorithm (Guo et al. 2018), where quantitative numbers of at most how many hidden layers and neurons are provided. Several experimental case studies show that our proposed distributed learning framework can achieve similar optimal results to those obtained by using typical existing distributed numerical optimization methods while it is superior in terms of simplicity and real-time capability. [ABSTRACT FROM AUTHOR]

In this article, we propose a novel feature selection approach, named unsupervised feature selection with constrained $\ell _{2,0}$ -norm (row-sparsity constrained) and optimized graph (RSOGFS), which unifies feature selection and similarity matrix construction into a general framework instead of independently performing the two-stage process; thus, the similarity matrix preserving the local manifold structure of data can be determined adaptively. Unlike those sparse learning-based feature selection methods that can only solve the relaxation or approximation problems by introducing sparsity regularization term into the objective function, the proposed method directly tackles the original $\ell _{2,0}$ -norm constrained problem to achieve group feature selection. Two optimization strategies are provided to solve the original sparse constrained problem. The convergence and approximation guarantees for the new algorithms are rigorously proved, and the computational complexity and parameter determination are theoretically analyzed. Experimental results on real-world data sets show that the proposed method for solving a nonconvex problem is superior to the state of the arts for solving the relaxed or approximate convex problems. [ABSTRACT FROM AUTHOR]

In this article, we come up with a novel Nesterov gradient and heavy-ball double accelerated distributed synchronous optimization algorithm, called NHDA, and adopt a general asynchronous model to further propose an effective asynchronous algorithm, called ASY-NHDA, for distributed optimization problem over directed graphs, where each agent has access to a local objective function and computes the optimal solution via communicating only with its immediate neighbors. Our goal is to minimize a sum of all local objective functions satisfying strong convexity and Lipschitz continuity. Consider a general asynchronous model, where agents communicate with their immediate neighbors and start a new computation independently, that is, agents can communicate with their neighbors at any time without any coordination and use delayed information from their in-neighbors to compute a new update. Delays are arbitrary, unpredictable, and time-varying but bounded. The theoretical analysis of NHDA is based on analyzing the interaction among the consensus, the gradient tracking, and the optimization processes. As for the analysis of ASY-NHDA, we equivalently transform the asynchronous system into an augmented synchronous system without delays and prove its convergence through using the generalized small gain theorem. The results show that NHDA and ASY-NHDA converge to the optimal solution at a linear convergence as long as the largest step size is positive and less than an explicitly estimated upper bound, and the largest momentum parameter is nonnegative and less than an upper bound. Finally, we demonstrate the advantages of ASY-NHDA through simulations. [ABSTRACT FROM AUTHOR]

Composite function optimization problem often arises in machine learning known as regularized empirical minimization. We introduce the acceleration technique to the Newton-type proximal method and propose a novel algorithm called accelerated proximal subsampled Newton method (APSSN). APSSN only subsamples a small subset of samples to construct an approximate Hessian that achieves computational efficiency. At the same time, APSSN still keeps a fast convergence rate. Furthermore, we obtain the scaled proximal mapping by solving its dual problem using the semismooth Newton method instead of resorting to the first-order methods. Due to our sampling strategy and the fast convergence rate of the semismooth Newton method, we can get the scaled proximal mapping efficiently. Both our theoretical analysis and empirical study show that APSSN is an effective and computationally efficient algorithm for composite function optimization problems. [ABSTRACT FROM AUTHOR]

Ordinal regression (OR) is one of the most important machine learning tasks. The kernel method is a major technique to achieve nonlinear OR. However, traditional kernel OR solvers are inefficient due to increased complexity introduced by multiple ordinal thresholds as well as the cost of kernel computation. Doubly stochastic gradient (DSG) is a very efficient and scalable kernel learning algorithm that combines random feature approximation with stochastic functional optimization. However, the theory and algorithm of DSG can only support optimization tasks within the unique reproducing kernel Hilbert space (RKHS), which is not suitable for OR problems where the multiple ordinal thresholds usually lead to multiple RKHSs. To address this problem, we construct a kernel whose RKHS can contain the decision function with multiple thresholds. Based on this new kernel, we further propose a novel DSG-like algorithm, DSGOR. In each iteration of DSGOR, we update the decision functional as well as the function bias with appropriately set learning rates for each. Our theoretic analysis shows that DSGOR can achieve O(1/t) convergence rate, which is as good as DSG, even though dealing with a much harder problem. Extensive experimental results demonstrate that our algorithm is much more efficient than traditional kernel OR solvers, especially on large-scale problems. [ABSTRACT FROM AUTHOR]

This article considers the problem of stochastic strongly convex optimization over a network of multiple interacting nodes. The optimization is under a global inequality constraint and the restriction that nodes have only access to the stochastic gradients of their objective functions. We propose an efficient distributed non-primal-dual algorithm, by incorporating the inequality constraint into the objective via a smoothing technique. We show that the proposed algorithm achieves an optimal O((1)/(T)) (T is the total number of iterations) convergence rate in the mean square distance from the optimal solution. In particular, we establish a high probability bound for the proposed algorithm, by showing that with a probability at least 1-δ, the proposed algorithm converges at a rate of O(ln(ln(T)/δ)/T). Finally, we provide numerical experiments to demonstrate the efficacy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We propose an asynchronous gradient sharing mechanism for the parallel actor–critic algorithms with improved exploration characteristics. The proposed algorithm (A3C-GS) has the property of automatically diversifying worker policies in the short term for exploration, thereby reducing the need for entropy loss terms. Despite policy diversification, the algorithm converges to the optimal policy in the long term. We show in our analysis that the gradient sharing operation is a composition of two contractions. The first contraction performs gradient computation, while the second contraction is a gradient sharing operation coordinated by locks. From these two contractions, certain short- and long-term properties result. For the short term, gradient sharing induces temporary heterogeneity in policies for performing needed exploration. In the long term, under a suitably small learning rate and gradient clipping, convergence to the optimal policy is theoretically guaranteed. We verify our results with several high-dimensional experiments and compare A3C-GS against other on-policy policy-gradient algorithms. Our proposed algorithm achieved the highest weighted score. Despite lower entropy weights, it performed well in high-dimensional environments that require exploration due to sparse rewards and those that need navigation in 3-D environments for long survival tasks. It consistently performed better than the base asynchronous advantage actor–critic (A3C) algorithm. [ABSTRACT FROM AUTHOR]

Machine learning, especially deep neural networks, has developed rapidly in fields, including computer vision, speech recognition, and reinforcement learning. Although minibatch stochastic gradient descent (SGD) is one of the most popular stochastic optimization methods for training deep networks, it shows a slow convergence rate due to the large noise in the gradient approximation. In this article, we attempt to remedy this problem by building a more efficient batch selection method based on typicality sampling, which reduces the error of gradient estimation in conventional minibatch SGD. We analyze the convergence rate of the resulting typical batch SGD algorithm and compare the convergence properties between the minibatch SGD and the algorithm. Experimental results demonstrate that our batch selection scheme works well and more complex minibatch SGD variants can benefit from the proposed batch selection strategy. [ABSTRACT FROM AUTHOR]

Stochastic approximation (SA) algorithms have been widely applied in minimization problems when the loss functions and/or the gradient information are only accessible through noisy evaluations. Stochastic gradient (SG) descent–a first-order algorithm and a workhorse of much machine learning–is perhaps the most famous form of SA. Among all SA algorithms, the second-order simultaneous perturbation stochastic approximation (2SPSA) and the second-order stochastic gradient (2SG) are particularly efficient in handling high-dimensional problems, covering both gradient-free and gradient-based scenarios. However, due to the necessary matrix operations, the per-iteration floating-point-operations (FLOPs) cost of the standard 2SPSA/2SG is $O(p^{3})$ , where $p$ is the dimension of the underlying parameter. Note that the $O(p^{3})$ FLOPs cost is distinct from the classical SPSA-based per-iteration $O(1)$ cost in terms of the number of noisy function evaluations. In this work, we propose a technique to efficiently implement the 2SPSA/2SG algorithms via the symmetric indefinite matrix factorization and show that the FLOPs cost is reduced from $O(p^{3})$ to $O(p^{2})$. The formal almost sure convergence and rate of convergence for the newly proposed approach are directly inherited from the standard 2SPSA/2SG. The improvement in efficiency and numerical stability is demonstrated in two numerical studies. [ABSTRACT FROM AUTHOR]

Memcomputing is a novel computing paradigm that employs time non-local dynamical systems to compute with and in memory. The digital version of these machines [digital memcomputing machines or (DMMs)] is scalable, and is particularly suited to solve combinatorial optimization problems. One of its possible realizations is by means of standard electronic circuits, with and without memory. Since these elements are non-quantum, they can be described by ordinary differential equations. Therefore, the circuit representation of DMMs can also be simulated efficiently on our traditional computers. We have indeed previously shown that these simulations only require time and memory resources that scale linearly with the problem size when applied to finding a good approximation to the optimum of hard instances of the maximum-satisfiability problem. The state-of-the-art algorithms, instead, require exponential resources for the same instances. However, in that work, we did not push the simulations to the limit of the processor used. Since linear scalability at smaller problem sizes cannot guarantee linear scalability at much larger sizes, we have extended these results in a stress-test up to $64\times 10^{6}$ variables (corresponding to about 1 billion literals), namely the largest case that we could fit on a single core of an Intel Xeon E5-2860 with 128 GB of dynamic random-access memory (DRAM). For this test, we have employed a commercial simulator, Falcon of MemComputing, Inc. We find that the simulations of DMMs still scale linearly in both time and memory up to these very large problem sizes versus the exponential requirements of the state-of-the-art solvers. These results further reinforce the advantages of the physics-based memcomputing approach compared with traditional ones. [ABSTRACT FROM AUTHOR]

This paper deals with iterative Jacobian-based recursion technique for the root-finding problem of the vector-valued function, whose evaluations are contaminated by noise. Instead of a scalar step size, we use an iterate-dependent matrix gain to effectively weigh the different elements associated with the noisy observations. The analytical development of the matrix gain is built on an iterative-dependent linear function interfered by additive zero-mean white noise, where the dimension of the function is $ {M\ge 1}$ and the dimension of the unknown variable is $ {N\ge 1}$. Necessary and sufficient conditions for $ {M\ge N}$ algorithms are presented pertaining to algorithm stability and convergence of the estimate error covariance matrix. Two algorithms are proposed: one for the case where $ {M\ge N}$ and the second one for the antithesis. The two algorithms assume full knowledge of the Jacobian. The recursive algorithms are proposed for generating the optimal iterative-dependent matrix gain. The proposed algorithms here aim for per-iteration minimization of the mean square estimate error. We show that the proposed algorithm satisfies the presented conditions for stability and convergence of the covariance. In addition, the convergence rate of the estimation error covariance is shown to be inversely proportional to the number of iterations. For the antithesis $ {M< N}$ , contraction of the error covariance is guaranteed. This underdetermined system of equations can be helpful in training neural networks. Numerical examples are presented to illustrate the performance capabilities of the proposed multidimensional gain while considering nonlinear functions. [ABSTRACT FROM AUTHOR]

Convolutional sparse coding (CSC) is a useful tool in many image and audio applications. Maximizing the performance of CSC requires that the dictionary used to store the features of signals can be learned from real data. The so-called convolutional dictionary learning (CDL) problem is formulated within a nonconvex, nonsmooth optimization framework. Most existing CDL solvers alternately update the coefficients and dictionary in an iterative manner. However, these approaches are prone to running redundant iterations, and their convergence properties are difficult to analyze. Moreover, most of those methods approximate the original nonconvex sparse inducing function using a convex regularizer to promote computational efficiency. This approach to approximation may result in nonsparse representations and, thereby, hinder the performance of the applications. In this paper, we deal with the nonconvex, nonsmooth constraints of the original CDL directly using the modified forward–backward splitting approach, in which the coefficients and dictionary are simultaneously updated in each iteration. We also propose a novel parameter adaption scheme to increase the speed of the algorithm used to obtain a usable dictionary and in so doing prove convergence. We also show that the proposed approach is applicable to parallel processing to reduce the computing time required by the algorithm to achieve convergence. The experimental results demonstrate that our method requires less time than the existing methods to achieve the convergence point while using a smaller final functional value. We also applied the dictionaries learned using the proposed and existing methods to an application involving signal separation. The dictionary learned using the proposed approach provides performance superior to that of comparable methods. [ABSTRACT FROM AUTHOR]

Boosting is a learning scheme that combines weak learners to produce a strong composite learner, with the underlying intuition that one can obtain accurate learner by combining “rough” ones. This paper aims at developing a new boosting strategy, called rescaled boosting (RBoosting), to accelerate the numerical convergence rate and, consequently, improve learning performances of the original boosting. Our studies show that RBoosting possesses the almost optimal numerical convergence rate in the sense that, up to a logarithmic factor, it can reach the minimax nonlinear approximation rate. We then use RBoosting to tackle classification problems and deduce corresponding statistical consistency and tight generalization error estimates. A series of theoretical and experimental results shows that RBoosting outperforms boosting in terms of generalization. [ABSTRACT FROM AUTHOR]

Conjugate gradient (CG) methods are a class of important methods for solving linear equations and nonlinear optimization problems. In this paper, we propose a new stochastic CG algorithm with variance reduction and we prove its linear convergence with the Fletcher and Reeves method for strongly convex and smooth functions. We experimentally demonstrate that the CG with variance reduction algorithm converges faster than its counterparts for four learning models, which may be convex, nonconvex or nonsmooth. In addition, its area under the curve performance on six large-scale data sets is comparable to that of the LIBLINEAR solver for the $L2$ -regularized $L2$ -loss but with a significant improvement in computational efficiency. 1 CGVR algorithm is available on github: https://github.com/xbjin/cgvr [ABSTRACT FROM AUTHOR]

A new evolutionary-learning algorithm is proposed to learn a decision maker (DM)’s best solution on a conflicting multiobjective space. Given the exemplary pairwise comparisons of solutions by a DM, we learn an ideal point (for the DM) that is used to evolve toward a better set of solutions. The process is repeated to get the DM’s best solution. The comparison of solutions in pairs facilitates the process of eliciting training information for the proposed learning model. Experimental study on standard multiobjective data sets shows that the proposed method accurately identifies a DM’s preferred zone in relatively a few generations and with a small number of preferences. Besides, it is found to be robust to inconsistencies in the preference statements. The results obtained are validated through a variant of the established NSGA-2 algorithm. [ABSTRACT FROM AUTHOR]

An artificial neural network (ANN) that mimics the information processing mechanisms and procedures of neurons in human brains has achieved a great success in many fields, e.g., classification, prediction, and control. However, traditional ANNs suffer from many problems, such as the hard understanding problem, the slow and difficult training problems, and the difficulty to scale them up. These problems motivate us to develop a new dendritic neuron model (DNM) by considering the nonlinearity of synapses, not only for a better understanding of a biological neuronal system, but also for providing a more useful method for solving practical problems. To achieve its better performance for solving problems, six learning algorithms including biogeography-based optimization, particle swarm optimization, genetic algorithm, ant colony optimization, evolutionary strategy, and population-based incremental learning are for the first time used to train it. The best combination of its user-defined parameters has been systemically investigated by using the Taguchi’s experimental design method. The experiments on 14 different problems involving classification, approximation, and prediction are conducted by using a multilayer perceptron and the proposed DNM. The results suggest that the proposed learning algorithms are effective and promising for training DNM and thus make DNM more powerful in solving classification, approximation, and prediction problems. [ABSTRACT FROM AUTHOR]

This paper proposes a new family of algorithms for training neural networks (NNs). These are based on recent developments in the field of nonconvex optimization, going under the general name of successive convex approximation techniques. The basic idea is to iteratively replace the original (nonconvex, highly dimensional) learning problem with a sequence of (strongly convex) approximations, which are both accurate and simple to optimize. Different from similar ideas (e.g., quasi-Newton algorithms), the approximations can be constructed using only first-order information of the NN function, in a stochastic fashion, while exploiting the overall structure of the learning problem for a faster convergence. We discuss several use cases, based on different choices for the loss function (e.g., squared loss and cross-entropy loss), and for the regularization of the NN’s weights. We experiment on several medium-sized benchmark problems and on a large-scale data set involving simulated physical data. The results show how the algorithm outperforms the state-of-the-art techniques, providing faster convergence to a better minimum. Additionally, we show how the algorithm can be easily parallelized over multiple computational units without hindering its performance. In particular, each computational unit can optimize a tailored surrogate function defined on a randomly assigned subset of the input variables, whose dimension can be selected depending entirely on the available computational power. [ABSTRACT FROM AUTHOR]

We propose a weighted common subgraph (WCS) matching algorithm to find the most similar subgraphs in two labeled weighted graphs. WCS matching, as a natural generalization of equal-sized graph matching and subgraph matching, has found wide applications in many computer vision and machine learning tasks. In this brief, WCS matching is first formulated as a combinatorial optimization problem over the set of partial permutation matrices. Then, it is approximately solved by a recently proposed combinatorial optimization framework—graduated nonconvexity and concavity procedure. Experimental comparisons on both synthetic graphs and real-world images validate its robustness against noise level, problem size, outlier number, and edge density. [ABSTRACT FROM AUTHOR]

This paper analyzes data-based online nonlinear extremum-seeker (DONE), an online optimization algorithm that iteratively minimizes an unknown function based on costly and noisy measurements. The algorithm maintains a surrogate of the unknown function in the form of a random Fourier expansion. The surrogate is updated whenever a new measurement is available, and then used to determine the next measurement point. The algorithm is comparable with Bayesian optimization algorithms, but its computational complexity per iteration does not depend on the number of measurements. We derive several theoretical results that provide insight on how the hyperparameters of the algorithm should be chosen. The algorithm is compared with a Bayesian optimization algorithm for an analytic benchmark problem and three applications, namely, optical coherence tomography, optical beam-forming network tuning, and robot arm control. It is found that the DONE algorithm is significantly faster than Bayesian optimization in the discussed problems while achieving a similar or better performance. [ABSTRACT FROM AUTHOR]

In this paper, we consider the learning problem of multilayer perceptrons (MLPs) formulated as the problem of minimizing a smooth error function. As well known, the learning problem of MLPs can be a difficult nonlinear nonconvex optimization problem. Typical difficulties can be the presence of extensive flat regions and steep sided valleys in the error surface, and the possible large number of training data and of free network parameters. We define a wide class of batch learning algorithms for MLP, based on the use of block decomposition techniques in the minimization of the error function. The learning problem is decomposed into a sequence of smaller and structured minimization problems in order to advantageously exploit the structure of the objective function. Theoretical convergence results are established, and a specific algorithm is constructed and evaluated through an extensive numerical experimentation. The comparisons with the state-of-the-art learning algorithms show the effectiveness of the proposed techniques. [ABSTRACT FROM AUTHOR]

Even though the Hartley-entropy-based contrast function guarantees an unmixing local minimum, the reported nonsmooth optimization techniques that minimize this nondifferentiable function encounter computational bottlenecks. Toward this, Powell’s derivative-free optimization method has been extended to a Riemannian manifold, namely, oblique manifold, for the recovery of quasi-correlated sources by minimizing this contrast function. The proposed scheme has been demonstrated to converge faster than the related algorithms in the literature, besides the impressive source separation results in simulations involving synthetic sources having finite-support distributions and correlated images. [ABSTRACT FROM PUBLISHER]

In object classification, feature combination can usually be used to combine the strength of multiple complementary features and produce better classification results than any single one. While multiple kernel learning (MKL) is a popular approach to feature combination in object classification, it does not always perform well in practical applications. On one hand, the optimization process in MKL usually involves a huge consumption of computation and memory space. On the other hand, in some cases, MKL is found to perform no better than the baseline combination methods. This observation motivates us to investigate the underlying mechanism of feature combination with average combination and weighted average combination. As a result, we empirically find that in average combination, it is better to use a sample of the most powerful features instead of all, whereas in one type of weighted average combination, the best classification accuracy comes from a nearly sparse combination. We integrate these observations into the k-nearest neighbors (kNNs) framework, based on which we further discuss some issues related to sparse solution and MKL. Finally, by making use of the kNN framework, we present a new weighted average combination method, which is shown to perform better than MKL in both accuracy and efficiency in experiments. We believe that the work in this paper is helpful in exploring the mechanism underlying feature combination. [ABSTRACT FROM PUBLISHER]

The support vector machine (SVM) remains a popular classifier for its excellent generalization performance and applicability of kernel methods; however, it still requires tuning of a regularization parameter, $C$ , to achieve optimal performance. Regularization path-following algorithms efficiently solve the solution at all possible values of the regularization parameter relying on the fact that the SVM solution is piece-wise linear in $C$ . The SVMPath originally introduced by Hastie et al., while representing a significant theoretical contribution, does not work with semidefinite kernels. Ong et al. introduce a method improved SVMPath (ISVMP) algorithm, which addresses the semidefinite kernel; however, Singular Value Decomposition or QR factorizations are required, and a linear programming solver is required to find the next $C$ value at each iteration. We introduce a simple implementation of the path-following algorithm that automatically handles semidefinite kernels without requiring a method to detect singular matrices nor requiring specialized factorizations or an external solver. We provide theoretical results showing how this method resolves issues associated with the semidefinite kernel as well as discuss, in detail, the potential sources of degeneracy and cycling and how cycling is resolved. Moreover, we introduce an initialization method for unequal class sizes based upon artificial variables that work within the context of the existing path-following algorithm and do not require an external solver. Experiments compare performance with the ISVMP algorithm introduced by Ong et al. and show that the proposed method is competitive in terms of training time while also maintaining high accuracy. [ABSTRACT FROM AUTHOR]

We introduce a novel algorithm for solving learning problems where both the loss function and the regularizer are nonconvex but belong to the class of difference of convex (DC) functions. Our contribution is a new general purpose proximal Newton algorithm that is able to deal with such a situation. The algorithm consists in obtaining a descent direction from an approximation of the loss function and then in performing a line search to ensure a sufficient descent. A theoretical analysis is provided showing that the iterates of the proposed algorithm admit as limit points stationary points of the DC objective function. Numerical experiments show that our approach is more efficient than the current state of the art for a problem with a convex loss function and a nonconvex regularizer. We have also illustrated the benefit of our algorithm in high-dimensional transductive learning problem where both the loss function and regularizers are nonconvex. [ABSTRACT FROM PUBLISHER]

Despite the great success of graph-based transductive learning methods, most of them have serious problems in scalability and robustness. In this paper, we propose an efficient and robust graph-based transductive classification method, called minimum tree cut (MTC), which is suitable for large-scale data. Motivated from the sparse representation of graph, we approximate a graph by a spanning tree. Exploiting the simple structure, we develop a linear-time algorithm to label the tree such that the cut size of the tree is minimized. This significantly improves graph-based methods, which typically have a polynomial time complexity. Moreover, we theoretically and empirically show that the performance of MTC is robust to the graph construction, overcoming another big problem of traditional graph-based methods. Extensive experiments on public data sets and applications on web-spam detection and interactive image segmentation demonstrate our method’s advantages in aspect of accuracy, speed, and robustness. [ABSTRACT FROM AUTHOR]

Single-layer feedforward networks (SLFNs) have been proven to be a universal approximator when all the parameters are allowed to be adjustable. It is widely used in classification and regression problems. The SLFN learning involves two tasks: determining network size and training the parameters. Most current algorithms could not be satisfactory to both sides. Some algorithms focused on construction and only tuned part of the parameters, which may not be able to achieve a compact network. Other gradient-based optimization algorithms focused on parameters tuning while the network size has to be preset by the user. Therefore, trial-and-error approach has to be used to search the optimal network size. Because results of each trial cannot be reused in another trial, it costs much computation. In this paper, a hybrid constructive (HC)algorithm is proposed for SLFN learning, which can train all the parameters and determine the network size simultaneously. At first, by combining Levenberg–Marquardt algorithm and least-square method, a hybrid algorithm is presented for training SLFN with fixed network size. Then,with the hybrid algorithm, an incremental constructive scheme is proposed. A new randomly initialized neuron is added each time when the training entrapped into local minima. Because the training continued on previous results after adding new neurons, the proposed HC algorithm works efficiently. Several practical problems were given for comparison with other popular algorithms. The experimental results demonstrated that the HC algorithm worked more efficiently than those optimization methods with trial and error, and could achieve much more compact SLFN than those construction algorithms. [ABSTRACT FROM PUBLISHER]

Nonnegative matrix factorization (NMF) has recently become a very popular unsupervised learning method because of its representational properties of factors and simple multiplicative update algorithms for solving the NMF. However, for the common NMF approach of minimizing the Euclidean distance between approximate and true values, the convergence of multiplicative update algorithms has not been well resolved. This paper first discusses the convergence of existing multiplicative update algorithms. We then propose a new multiplicative update algorithm for minimizing the Euclidean distance between approximate and true values. Based on the optimization principle and the auxiliary function method, we prove that our new algorithm not only converges to a stationary point, but also does faster than existing ones. To verify our theoretical results, the experiments on three data sets have been conducted by comparing our proposed algorithm with other existing methods. [ABSTRACT FROM AUTHOR]

We consider the problem of dictionary learning and sparse coding, where the task is to find a concise set of basis vectors that accurately represent the observation data with only small numbers of active bases. Typically formulated as an L1-regularized least-squares problem, the problem incurs computational difficulty originating from the nondifferentiable objective. Recent approaches to sparse coding thus have mainly focused on acceleration of the learning algorithm. In this paper, we propose an even more efficient and scalable sparse coding algorithm based on the first-order smooth optimization technique. The algorithm finds the theoretically guaranteed optimal sparse codes of the epsilon-approximate problem in a series of optimization subproblems, where each subproblem admits analytic solution, hence very fast and scalable with large-scale data. We further extend it to nonlinear sparse coding using kernel trick by showing that the representer theorem holds for the kernel sparse coding problem. This allows us to apply dual optimization, which essentially results in the same linear sparse coding problem in dual variables, highly beneficial compared with the existing methods that suffer from local minima and restricted forms of kernel function. The efficiency of our algorithms is demonstrated for natural stimuli data sets and several image classification problems. [ABSTRACT FROM AUTHOR]

We present an exterior-point method (EPM) for training dual-soft margin support vector machines (SVMs). The EPM stems from nonlinear rescaling and augmented Lagrangian methods and allows iterates to approach the solution of a constrained nonlinear optimization problem from the exterior of the feasible set. Furthermore, the EPM produces and solves a well-conditioned system of linear equations at each iteration; thus, avoiding numerical inaccuracies that can occur when solving ill-conditioned systems. Therefore, the EPM may be an attractive alternative to existing quadratic programming solvers for training SVMs. We report numerical results for training the SVM with the EPM on data up to several thousand data points from the UC Irvine Machine Learning Repository. [ABSTRACT FROM AUTHOR]