Search

In this paper, we propose an efficient boosting method with theoretical guarantees for binary classification. There are three key ingredients of the proposed boosting method: a fully corrective greedy (FCG) update, a differentiable squared hinge (also called truncated quadratic) loss function, and an efficient alternating direction method of multipliers (ADMM) solver. Compared with traditional boosting methods, on one hand, the FCG update accelerates the numerical convergence rate, and on the other hand, the squared hinge loss inherits the robustness of the hinge loss for classification and maintains the theoretical benefits of the square loss in regression. The ADMM solver with guaranteed fast convergence then provides an efficient implementation for the proposed boosting method. We conduct both theoretical analysis and numerical verification to show the outperformance of the proposed method. Theoretically, a fast learning rate of order O ( (m / log m) − 1 / 2) is proved under certain standard assumptions, where m is the size of sample set. Numerically, a series of toy simulations and real data experiments are carried out to verify the developed theory. [ABSTRACT FROM AUTHOR]

Learning representation from relative similarity comparisons, often called ordinal embedding, gains rising attention in recent years. Most of the existing methods are based on semi-definite programming (SDP), which is generally time-consuming and degrades the scalability, especially confronting large-scale data. To overcome this challenge, we propose a stochastic algorithm called SVRG-SBB, which has the following features: i) achieving good scalability via dropping positive semi-definite (PSD) constraints as serving a fast algorithm, i.e., stochastic variance reduced gradient (SVRG) method, and ii) adaptive learning via introducing a new, adaptive step size called the stabilized Barzilai-Borwein (SBB) step size. Theoretically, under some natural assumptions, we show the O(1/T) rate of convergence to a stationary point of the proposed algorithm, where T is the number of total iterations. Under the further Polyak-Łojasiewicz assumption, we can show the global linear convergence (i.e., exponentially fast converging to a global optimum) of the proposed algorithm. Numerous simulations and real-world data experiments are conducted to show the effectiveness of the proposed algorithm by comparing with the state-of-the-art methods, notably, much lower computational cost with good prediction performance. [ABSTRACT FROM AUTHOR]

Nonconvex reformulations via low-rank factorization for stochastic convex semidefinite optimization problem have attracted arising attention due to their empirical efficiency and scalability. Compared with the original convex formulations, the nonconvex ones typically involve much fewer variables, allowing them to scale to scenarios with millions of variables. However, it opens a new challenge that under what conditions the nonconvex stochastic algorithms may find the population minimizer within the optimal statistical precision despite their empirical success in applications. In this paper, we provide an answer that the stochastic gradient descent (SGD) method can be adapted to solve the nonconvex reformulation of the original convex problem, with a global linear convergence when using a fixed step size, i.e., converging exponentially fast to the population minimizer within an optimal statistical precision in the restricted strongly convex case. If a diminishing step size is adopted, the bad effect caused by the variance of gradients on the optimization error can be eliminated but the rate is dropped to be sublinear. The core of our treatment relies on a novel second-order descent lemma, which is more general than the existing best result in the literature and improves the analysis on both online and batch algorithms. The developed theoretical results and effectiveness of the suggested SGD are also verified by a series of experiments. [ABSTRACT FROM AUTHOR]

Consensus optimization has received considerable attention in recent years. A number of decentralized algorithms have been proposed for convex consensus optimization. However, to the behaviors or consensus nonconvex optimization, our understanding is more limited. When we lose convexity, we cannot hope that our algorithms always return global solutions though they sometimes still do. Somewhat surprisingly, the decentralized consensus algorithms, DGD and Prox-DGD, retain most other properties that are known in the convex setting. In particular, when diminishing (or constant) step sizes are used, we can prove convergence to a (or a neighborhood of) consensus stationary solution under some regular assumptions. It is worth noting that Prox-DGD can handle nonconvex nonsmooth functions if their proximal operators can be computed. Such functions include SCAD, MCP, and $\ell _q$ quasi-norms, $q\in [0,1)$. Similarly, Prox-DGD can take the constraint to a nonconvex set with an easy projection. To establish these properties, we have to introduce a completely different line of analysis, as well as modify existing proofs that were used in the convex setting. [ABSTRACT FROM AUTHOR]

This paper proposes a fast decentralized algorithm for solving a consensus optimization problem defined in a directed networked multi-agent system, where the local objective functions have the smooth + nonsmooth composite form, and are possibly nonconvex . Examples of such problems include decentralized compressed sensing and constrained quadratic programming problems, as well as many decentralized regularization problems. We extend the existing algorithms PG-EXTRA and ExtraPush to a new algorithm PG-ExtraPush for composite consensus optimization over a directed network. This algorithm takes advantage of the proximity operator like in PG-EXTRA to deal with the nonsmooth term, and employs the push-sum protocol like in ExtraPush to tackle the bias introduced by the directed network. With a proper step size, we show that PG-ExtraPush converges to an optimal solution at a linear rate under some regular assumptions. We conduct a series of numerical experiments to show the effectiveness of the proposed algorithm. Specifically, with a proper step size, PG-ExtraPush performs linear rates in most of cases, even in some nonconvex cases, and is significantly faster than Subgradient-Push, even if the latter uses a hand-optimized step size. The established theoretical results are also verified by the numerical results. [ABSTRACT FROM AUTHOR]

This paper studies the ℓ q ( 0 < q < 1 ) regularized least squares regression ( ℓ q LS) problem, which arises in many applications of signal processing and machine learning. The iterative thresholding algorithm is an important algorithm for solving the ℓ q LS problem, and can be viewed as a Jacobi-type iterative method. This paper proposes a Gauss–Seidel version of iterative thresholding algorithm called GAITA for solving the ℓ q LS problem. Under certain conditions, we establish its global convergence 1 1 The global convergence in this paper is defined in the sense that the entire sequence converges regardless of the initial point. , eventual linear rate, and the convergence to a local minimizer. Compared to the Jacobi counterpart, the proposed algorithm can allow larger step sizes and converge much faster. The effectiveness of the proposed algorithm is justified with numerical experiments on both synthetic data and real data. [ABSTRACT FROM AUTHOR]

Recently, the spherical data processing has emerged in many applications and attracted a lot of attention. Among all the methods for dealing with the spherical data, the spherical neural networks (SNNs) method has been recognized as a very efficient tool due to SNNs possess both good approximation capability and spacial localization property. For better localized approximant, weighted approximation should be considered since different areas of the sphere may play different roles in the approximation process. In this paper, using the minimal Riesz energy points and the spherical cap average operator, we first construct a class of well-localized SNNs with a bounded sigmoidal activation function, and then study their approximation capabilities. More specifically, we establish a Jackson-type error estimate for the weighted SNNs approximation in the metric of L p space for the well developed doubling weights. [ABSTRACT FROM AUTHOR]

In recent studies on sparse modeling, the nonconvex regularization approaches (particularly, Lq regularization with q\in(0,1)) have been demonstrated to possess capability of gaining much benefit in sparsity-inducing and efficiency. As compared with the convex regularization approaches (say, L1 regularization), however, the convergence issue of the corresponding algorithms are more difficult to tackle. In this paper, we deal with this difficult issue for a specific but typical nonconvex regularization scheme, the L1/2 regularization, which has been successfully used to many applications. More specifically, we study the convergence of the iterative half thresholding algorithm (the half algorithm for short), one of the most efficient and important algorithms for solution to the L1/2 regularization. As the main result, we show that under certain conditions, the half algorithm converges to a local minimizer of the L1/2 regularization, with an eventually linear convergence rate. The established result provides a theoretical guarantee for a wide range of applications of the half algorithm. We provide also a set of simulations to support the correctness of theoretical assertions and compare the time efficiency of the half algorithm with other known typical algorithms for L1/2 regularization like the iteratively reweighted least squares (IRLS) algorithm and the iteratively reweighted l1 minimization (IRL1) algorithm. [ABSTRACT FROM PUBLISHER]

Abstract: Finding the sparset solution of an underdetermined system of linear equations y=Ax has attracted considerable attention in recent years. Among a large number of algorithms, iterative thresholding algorithms are recognized as one of the most efficient and important classes of algorithms. This is mainly due to their low computational complexities, especially for large scale applications. The aim of this paper is to provide guarantees on the global convergence of a wide class of iterative thresholding algorithms. Since the thresholds of the considered algorithms are set adaptively at each iteration, we call them adaptively iterative thresholding (AIT) algorithms. As the main result, we show that as long as A satisfies a certain coherence property, AIT algorithms can find the correct support set within finite iterations, and then converge to the original sparse solution exponentially fast once the correct support set has been identified. Meanwhile, we also demonstrate that AIT algorithms are robust to the algorithmic parameters. In addition, it should be pointed out that most of the existing iterative thresholding algorithms such as hard, soft, half and smoothly clipped absolute deviation (SCAD) algorithms are included in the class of AIT algorithms studied in this paper. [Copyright &y& Elsevier]

Abstract: Sparse synthetic aperture radar (SAR) imaging has been highlighted in recent studies. As an important sparsity constraint, regularizer has been substantiated effectively when applied to SAR imaging. However, imaging suffers from a common challenge with other sparse SAR imaging methods: the computational complexity is costly, especially for high dimensional applications. This challenge is mainly due to that imaging is a gradient descent based method, of which the convergence is at most linear. Thus, a lot of iterations are often necessary to yield a satisfactory result. In this paper, we propose an accelerated imaging method by applying the block coordinate relaxation (BCR) scheme combined with the reduced Newton skill for acceleration. It is numerically shown that the proposed method keeps fast convergence within a very few iterations, and also maintains high reconstruction precision. We provide a series of simulations and two real SAR applications to demonstrate the superiority of the proposed method. Particularly, much faster convergence and higher reconstruction precision in imaging, of the proposed method over the other sparse SAR imaging methods. [Copyright &y& Elsevier]

As pairwise ranking becomes broadly employed for elections, sports competitions, recommendation, information retrieval and so on, attackers have strong motivation and incentives to manipulate or disrupt the ranking list. They could inject malicious comparisons into the training data to fool the target ranking algorithm. Such a technique is called “poisoning attack” in regression and classification tasks. In this paper, to the best of our knowledge, we initiate the first systematic investigation of data poisoning attack on the pairwise ranking algorithms, which can be generally formalized as the dynamic and static games between the ranker and the attacker, and can be modeled as certain kinds of integer programming problems mathematically. To break the computational hurdle of the underlying integer programming problems, we reformulate them into the distributionally robust optimization (DRO) problems, which are computational tractable. Based on such DRO formulations, we propose two efficient poisoning attack algorithms and establish the associated theoretical guarantees including the existence of Nash equilibrium and the generalization ability bounds. The effectiveness of the suggested poisoning attack strategies is demonstrated by a series of toy simulations and several real data experiments. These experimental results show that the proposed methods can significantly reduce the performance of the ranker in the sense that the correlation between the true ranking list and the aggregated results with toxic data can be decreased dramatically. [ABSTRACT FROM AUTHOR]

Hyperspectral image (HSI) denoising is an essential preprocessing step for improving HSI applications. Recently, subspace-based nonlocal low-rank approximation (SNLR) methods have shown their superiority. However, most of these methods ignore such a potentially important phenomenon, that is, real HSIs contain many high signal-to-noise ratio bands (HSNRBs), and thus result in the underutilization of information. In this paper, we propose a new method called Subspace-based Guided Nonlocal Low-Rank Approximation (SGNLR) for HSI denoising. Our method takes advantage of the abundant spatial information in the representation coefficients of HSNRBs to improve denoising performances. Specifically, we employ low-rank subspace representation to exploit the global spectral correlation of HSI and transform the HSI denoising task as the estimation of spectral basis and spatial representation coefficients (SRCs). Motivated by the consistency of coefficient features between the whole HSI and HSNRBs, we employ the SRCs of HSNRBs to guide the restoration of target coefficients. To restore the SRCs accurately, we design a powerful nonlocal low-rank approximation that takes into account the nonlocal self-similarity (NSS) of SRCs. An efficient algorithm based on alternating minimization is developed to optimize the proposed model. Extensive experiments on both simulated and real-world data demonstrate the outperformance of our method. • A novel insight is proposed for HSI denoising by incorporating guidance information. • This is the first attempt to incorporate guidance information into nonlocal methods. • The auxiliary information is used to guide the restoration of spatial coefficients. [ABSTRACT FROM AUTHOR]