Search

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]

The augmented Lagrangian method (ALM) is one of the most useful methods for constrained optimization. Its convergence has been well established under convexity assumptions or smoothness assumptions, or under both assumptions. ALM may experience oscillations and divergence when the underlying problem is simultaneously nonconvex and nonsmooth. In this paper, we consider the linearly constrained problem with a nonconvex (in particular, weakly convex) and nonsmooth objective. We modify ALM to use a Moreau envelope of the augmented Lagrangian and establish its convergence under conditions that are weaker than those in the literature. We call it the Moreau envelope augmented Lagrangian (MEAL) method. We also show that the iteration complexity of MEAL is o (ε - 2) to yield an ε -accurate first-order stationary point. We establish its whole sequence convergence (regardless of the initial guess) and a rate when a Kurdyka–Łojasiewicz property is assumed. Moreover, when the subproblem of MEAL has no closed-form solution and is difficult to solve, we propose two practical variants of MEAL, an inexact version called iMEAL with an approximate proximal update, and a linearized version called LiMEAL for the constrained problem with a composite objective. Their convergence is also established. [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]

This paper proposes a new learning system of low computational cost, called fast polynomial kernel learning (FPL), based on regularized least squares with polynomial kernel and subsampling. The almost optimal learning rate as well as the feasibility verifications including the subsampling mechanism and solvability of FPL are provided in the framework of learning theory. Our theoretical assertions are verified by numerous toy simulations and real data applications. The studies in this paper show that FPL can reduce the computational burden of kernel methods without sacrificing its generalization ability very much. [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]

In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, ϕ(x0,...,xp,y), subject to coupled linear equality constraints. Our ADMM updates each of the primal variables x0,...,xp,y, followed by updating the dual variable. We separate the variable y from xi's as it has a special role in our analysis. The developed convergence guarantee covers a variety of nonconvex functions such as piecewise linear functions, ℓq quasi-norm, Schatten-q quasi-norm (0

In this paper, we aim at developing scalable neural network-type learning systems. Motivated by the idea of constructive neural networks in approximation theory, we focus on constructing rather than training feed-forward neural networks (FNNs) for learning, and propose a novel FNNs learning system called the constructive FNN (CFN). Theoretically, we prove that the proposed method not only overcomes the classical saturation problem for constructive FNN approximation, but also reaches the optimal learning rate when the regression function is smooth, while the state-of-the-art learning rates established for traditional FNNs are only near optimal (up to a logarithmic factor). A series of numerical simulations are provided to show the efficiency and feasibility of CFN. [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]

Orthogonal greedy learning (OGL) is a stepwise learning scheme that starts with selecting a new atom from a specified dictionary via the steepest gradient descent (SGD) and then builds the estimator through orthogonal projection. In this paper, we found that SGD is not the unique greedy criterion and introduced a new greedy criterion, called as “ \delta -greedy threshold” for learning. Based on this new greedy criterion, we derived a straightforward termination rule for OGL. Our theoretical study shows that the new learning scheme can achieve the existing (almost) optimal learning rate of OGL. Numerical experiments are also provided to support that this new scheme can achieve almost optimal generalization performance while requiring less computation than OGL. [ABSTRACT FROM PUBLISHER]

We present a type of spherical neural network (SNN) with bounded sigmoidal activation function and study its interpolation capability. We find that the provided SNN can exactly interpolate the training samples. Furthermore, based on the special structure of the presented SNN, we can bound the interpolation error by the modulus of smoothness of the target function, which is different from the previous results on the spherical scattered data interpolation problem. [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]

In this paper, a novel method for synthetic aperture radar (SAR) imaging is proposed. The approach is based on L regularization to reconstruct the scattering field, which optimizes a quadratic error term of the SAR observation process subject to the interested scene sparsity. Compared to the conventional SAR imaging technique, the new method implements SAR imaging effectively at much lower sampling rate than the Nyquist rate, and produces high-quality images with reduced sidelobes and increased resolution. Also, over the prevalent greedy pursuit and L regularization based SAR imaging methods, there are remarkable performance improvements of the new method. On one hand, the new method significantly reduces the number of measurements needed for reconstruction, as supported by a phase transition diagram study. On the other hand, the new method is more robust to the observation noise. These fundamental properties of the new method are supported and demonstrated both by simulations and real SAR data experiments. [ABSTRACT FROM AUTHOR]

The displaced phase center antenna (DPCA) technique is an effective strategy to achieve wide-swath synthetic aperture radar (SAR) imaging with high azimuth resolution. However, traditionally, it requires strict limitation of the pulse repetition frequency (PRF) to avoid non-uniform sampling. Otherwise, any deviation could bring serious ambiguity if the data are directly processed using a matched filter. To break this limitation, a recently proposed spectrum reconstruction method is capable of recovering the true spectrum from the nonuniform samples. However, the performance is sensitive to the selection of the PRF. Sparse regularization based imaging may provide a way to overcome this sensitivity. The existing time-domain method, however, requires a large-scale observation matrix to be built, which brings a high computational cost. In this paper, we propose a frequency domain method, called the iterative spectrum reconstruction method, through integration of the sparse regularization technique with spectrum analysis of the DPCA signal. By approximately expressing the observation in the frequency domain, which is realized via a series of decoupled linear operations, the method performs SAR imaging which is then not directly based on the observation matrix, which reduces the computational cost from O( N) to O( N log N) (where N is the number of range cells), and is therefore more efficient than the time domain method. The sparse regularization scheme, realized via a fast thresholding iteration, has been adopted in this method, which brings the robustness of the imaging process to the PRF selection. We provide a series of simulations and ground based experiments to demonstrate the high efficiency and robustness of the method. The simulations show that the new method is almost as fast as the traditional mono-channel algorithm, and works well almost independently of the PRF selection. Consequently, the suggested method can be accepted as a practical and efficient wide-swath SAR imaging technique. [ABSTRACT FROM AUTHOR]