Search

In real-world applications, it is important for machine learning algorithms to be robust against data outliers or corruptions. In this paper, we focus on improving the robustness of a large class of learning algorithms that are formulated as low-rank semi-definite programming (SDP) problems. Traditional formulations use the square loss, which is notorious for being sensitive to outliers. We propose to replace this with more robust noise models, including the $\ell _1$ ℓ 1 -loss and other nonconvex losses. However, the resultant optimization problem becomes difficult as the objective is no longer convex or smooth. To alleviate this problem, we design an efficient algorithm based on majorization-minimization. The crux is on constructing a good optimization surrogate, and we show that this surrogate can be efficiently obtained by the alternating direction method of multipliers (ADMM). By properly monitoring ADMM's convergence, the proposed algorithm is empirically efficient and also theoretically guaranteed to converge to a critical point. Extensive experiments are performed on four machine learning applications using both synthetic and real-world data sets. Results show that the proposed algorithm is not only fast but also has better performance than the state-of-the-arts. [ABSTRACT FROM AUTHOR]

In this paper we provide a theoretical and numerical comparison of convergence rates of forward-backward, Douglas-Rachford, and Peaceman-Rachford algorithms for minimizing the sum of a convex proper lower semicontinuous function and a strongly convex differentiable function with Lipschitz continuous gradient. Our results extend the comparison made in [1], when both functions are smooth, to the context where only one is assumed differentiable. Optimal step-sizes and rates of the three algorithms are compared theoretically and numerically in the context of texture segmentation problem, obtaining very sharp estimations and illustrating the high efficiency of Peaceman-Rachford splitting. [ABSTRACT FROM AUTHOR]

This paper investigates the resource allocation problem for a group of agents communicating over a strongly connected directed graph, where the total objective function of the problem is composted of the sum of the local objective functions incurred by the agents. With local convex sets, we first design a continuous-time projection algorithm over a strongly connected and weight-balanced directed graph. Our convergence analysis indicates that when the local objective functions are strongly convex, the output state of the projection algorithm could asymptotically converge to the optimal solution of the resource allocation problem. In particular, when the projection operation is not involved, we show the exponential convergence at the equilibrium point of the algorithm. Second, we propose an adaptive continuous-time gradient algorithm over a strongly connected and weight-unbalanced directed graph for the reduced case without local convex sets. In this case, we prove that the adaptive algorithm converges exponentially to the optimal solution of the considered problem, where the local objective functions and their gradients satisfy strong convexity and Lipachitz conditions, respectively. Numerical simulations illustrate the performance of our algorithms. [ABSTRACT FROM AUTHOR]

In this article, we consider a class of decentralized nonsmooth composite optimization problems over undirected graphs. The global optimization problem is to minimize the sum of local objective functions consisting of a Lipschitz-differentiable convex function and two possibly nonsmooth convex functions, one of which contains a bounded linear operator. The goal is to solve the global optimization problem through decentralized computation and communication over a network of agents without a central coordinator. Through using triple proximal splitting operators to deal with the nonsmooth terms, we come up with a novel decentralized algorithm with uncoordinated stepsizes, where the stepsizes with independent upper bounds are also distributed for agents or edges over the communication network. Furthermore, we establish the sublinear convergence rate for the proposed algorithm in terms of the first-order optimality residual in a nonergodic sense. Simulation experiments on a constrained quadratic programming problem and an optimal load-sharing problem are carried out to verify the correctness of the theoretical results. [ABSTRACT FROM AUTHOR]

In this article, the distributed finite-time and fixed-time optimization problems are investigated by adopting the zero-gradient-sum (ZGS) framework in multiagent systems. Specifically, when the local convex functions are nonquadratic, a basic optimization protocol is proposed to obtain a finite-time convergence, such that the networked system can cooperatively seek the optimal solution of the global objective, the sum of local objective, in a limited time. By utilizing the property of quadratic functions, a reduced algorithm can remove the dependence of initial conditions in the estimation of the upper bound of settling time and achieve a fixed-time result. Besides, the problem with time-varying topologies is studied by introducing a modified algorithm with an artificial potential function to preserve the network connectivity. Finally, the validity of the protocols is demonstrated via some example simulations. [ABSTRACT FROM AUTHOR]

We consider a class of popular distributed non-convex optimization problems, in which agents connected by a network $\mathcal {G}$ collectively optimize a sum of smooth (possibly non-convex) local objective functions. We address the following question: if the agents can only access the gradients of local functions, what are the fastest rates that any distributed algorithms can achieve, and how to achieve those rates. First, we show that there exist difficult problem instances, such that it takes a class of distributed first-order methods at least $\mathcal {O}(1/\sqrt{\xi ({ \mathcal {G} })} \times \bar{L} /{\epsilon })$ communication rounds to achieve certain $\epsilon$ -solution [where $\xi ({ \mathcal {G} })$ denotes the spectral gap of the graph Laplacian matrix, and $\bar{L}$ is some Lipschitz constant]. Second, we propose (near) optimal methods whose rates match the developed lower rate bound (up to a ploylog factor). The key in the algorithm design is to properly embed the classical polynomial filtering techniques into modern first-order algorithms. To the best of our knowledge, this is the first time that lower rate bounds and optimal methods have been developed for distributed non-convex optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we propose to fit a sparse logistic regression model by a weakly convex regularized nonconvex optimization problem. The idea is based on the finding that a weakly convex function as an approximation of the $\ell _0$ pseudo norm is able to better induce sparsity than the commonly used $\ell _1$ norm. For a class of weakly convex sparsity inducing functions, we prove the nonconvexity of the corresponding problem and study its local optimality conditions and the choice of the regularization parameter. Despite the nonconvexity, a method based on proximal gradient descent is used to solve the general weakly convex sparse logistic regression, and its convergence behavior is studied theoretically. Then, the general framework is applied to a specific weakly convex function, and a local optimality condition and a bound on the logistic loss at a local optimum are provided. The solution method is instantiated in this case as an iterative firm-shrinkage algorithm, and a Nesterov acceleration is used with a convergence guarantee. Its effectiveness is demonstrated in numerical experiments by both randomly generated and real datasets. [ABSTRACT FROM AUTHOR]

This article studies the distributed composite optimization problem over relay-assisted networks (DCOP-RNs). By combining the local primal–dual updates with a data fusion strategy, an effective distributed algorithm is developed to solve the DCOP-RN. Compared with the existing linearized alternating direction method of multipliers (ADMMs), this article provides a novel interpretation of the proposed algorithm. More specifically, it is shown that the proposed algorithm can be interpreted as a simplified proximal augmented Lagrangian method. Within this framework, a simplified convergence analysis of the algorithm is conducted, based on which the convergence to an optimal solution to the DCOP-RN is proved. Further, taking into account the limited bandwidth in real networks, this article proposes a quantized distributed algorithm to solve the DCOP-RN. Especially, a relationship between the quantization resolution and the convergence accuracy of the algorithm is established. Finally, simulation examples verify the theoretical results. [ABSTRACT FROM AUTHOR]

In this article, the problem of the distributed convex optimization is investigated, where the target is to collectively minimize a sum of local convex functions over an unbalanced directed multiagent network. Each agent in the network possesses only its private local objective function, and the sum of all local objective functions constitutes the global objective function. We particularly consider the scenario, where the underlying interaction network is strongly connected and the relevant weight matrix is row stochastic. To collectively figure out the optimization problem, a distributed accelerated convergence algorithm where agents utilize uncoordinated step-sizes is presented by incorporating consensus of multiagent networks into distributed inexact gradient tracking technique. Most of the existing methods require all agents to possess the out-degree information of their in-neighbors, which is impractical and hardly inevitable as interpreted in this article. By utilizing the small-gain theorem, we prove that if the maximum step-size is positive and sufficiently small (constrained by a specific upper bound), the proposed algorithm, termed as SGT-FROST, converges geometrically to the optimal solution given that the objective functions are smooth and strongly convex. A certain convergence rate is also shown. Simulations confirm the findings in this article. [ABSTRACT FROM AUTHOR]

In this article, we propose a novel distributed alternating direction method of multipliers (ADMM) algorithm with synergetic communication and computation, called SCCD-ADMM, to reduce the total communication and computation cost of the system. Explicitly, in the proposed algorithm, each node interacts with only part of its neighboring nodes, the number of which is progressively determined according to a heuristic searching procedure, which takes into account both the predicted convergence rate and the communication and computation costs at each iteration, resulting in a trade-off between communication and computation. Then the node chooses its neighboring nodes according to an importance sampling distribution derived theoretically to minimize the variance with the latest information it locally stores. Finally, the node updates its local information with a new update rule which adapts to the number of communication nodes. We prove the convergence of the proposed algorithm and provide an upper bound of the convergence variance brought by randomness. Extensive simulations validate the excellent performances of the proposed algorithm in terms of convergence rate and variance, the overall communication and computation cost, the impact of network topology as well as the time for evaluation, in comparison with the traditional counterparts. [ABSTRACT FROM AUTHOR]

Online convex optimization (OCO) encapsulates supervised learning when training sets are large-scale or dynamic, and has grown essential as data has proliferated. OCO decomposes learning into a sequence of sub-problems, each of which must be solved with limited information. To ensure safe model adaption or to avoid overfitting, constraints are often imposed, which are often addressed with projections or Lagrangian relaxation. To avoid this complexity incursion, we propose to study Frank-Wolfe (FW), which operates by updating in collinear directions with the gradient but guaranteed to be feasible. We specifically focus on its use in non-stationary settings, motivated by the fact that its iterates have structured sparsity that may be employed as a distribution-free change-point detector. We establish performance in terms of dynamic regret, which quantifies cost accumulation as compared with the optimal at each individual time slot. Specifically, for convex losses, we establish O(T1/2) dynamic regret up to metrics of non-stationarity. We relax the algorithm's required information to only noisy gradient estimates, i.e., partial feedback. We also consider a mini-batching ‘Meta-Frank Wolfe’, and characterize its dynamic regret. Experiments on matrix completion problem and background separation in video demonstrate favorable performance of the proposed scheme. Moreover, the structured sparsity of FW is experimentally observed to yield the sharpest tracker of change points among alternative approaches to non-stationary online convex optimization. [ABSTRACT FROM AUTHOR]

The group Lasso is an extension of the Lasso for feature selection on (predefined) nonoverlapping groups of features. The nonoverlapping group structure limits its applicability in practice. There have been several recent attempts to study a more general formulation where groups of features are given, potentially with overlaps between the groups. The resulting optimization is, however, much more challenging to solve due to the group overlaps. In this paper, we consider the efficient optimization of the overlapping group Lasso penalized problem. We reveal several key properties of the proximal operator associated with the overlapping group Lasso, and compute the proximal operator by solving the smooth and convex dual problem, which allows the use of the gradient descent type of algorithms for the optimization. Our methods and theoretical results are then generalized to tackle the general overlapping group Lasso formulation based on the $(\ell_q)$ norm. We further extend our algorithm to solve a nonconvex overlapping group Lasso formulation based on the capped norm regularization, which reduces the estimation bias introduced by the convex penalty. We have performed empirical evaluations using both a synthetic and the breast cancer gene expression dataset, which consists of 8,141 genes organized into (overlapping) gene sets. Experimental results show that the proposed algorithm is more efficient than existing state-of-the-art algorithms. Results also demonstrate the effectiveness of the nonconvex formulation for overlapping group Lasso. [ABSTRACT FROM AUTHOR]

Much research has been devoted to the problem of restoring Poissonian images, namely for medical and astronomical applications. However, the restoration of these images using state-of-the-art regularizers (such as those based upon multiscale representations or total variation) is still an active research area, since the associated optimization problems are quite challenging. In this paper, we propose an approach to deconvolving Poissonian images, which is based upon an alternating direction optimization method. The standard regularization [or maximum a posteriori (MAP)] restoration criterion, which combines the Poisson log-likelihood with a (nonsmooth) convex regularizer (log-prior), leads to hard optimization problems: the log-likelihood is nonquadratic and nonseparable, the regularizer is nonsmooth, and there is a nonnegativity constraint. Using standard convex analysis tools, we present sufficient conditions for existence and uniqueness of solutions of these optimization problems, for several types of regularizers: total-variation, frame-based analysis, and frame-based synthesis. We attack these problems with an instance of the alternating direction method of multipliers (ADMM), which belongs to the family of augmented Lagrangian algorithms. We study sufficient conditions for convergence and show that these are satisfied, either under total-variation or frame-based (analysis and synthesis) regularization. The resulting algorithms are shown to outperform alternative state-of-the-art methods, both in terms of speed and restoration accuracy. [ABSTRACT FROM AUTHOR]

We consider the problem of decentralized consensus optimization, where the sum of $n$ smooth and strongly convex functions are minimized over $n$ distributed agents that form a connected network. In particular, we consider the case that the communicated local decision variables among nodes are quantized in order to alleviate the communication bottleneck in distributed optimization. We propose the Quantized Decentralized Gradient Descent (QDGD) algorithm, in which nodes update their local decision variables by combining the quantized information received from their neighbors with their local information. We prove that under standard strong convexity and smoothness assumptions for the objective function, QDGD achieves a vanishing mean solution error under customary conditions for quantizers. To the best of our knowledge, this is the first algorithm that achieves vanishing consensus error in the presence of quantization noise. Moreover, we provide simulation results that show tight agreement between our derived theoretical convergence rate and the numerical results. [ABSTRACT FROM AUTHOR]

We consider derivative-free algorithms for stochastic and nonstochastic convex optimization problems that use only function values rather than gradients. Focusing on nonasymptotic bounds on convergence rates, we show that if pairs of function values are available, algorithms for d -dimensional optimization that use gradient estimates based on random perturbations suffer a factor of at most \sqrt {d} in convergence rate over traditional stochastic gradient methods. We establish such results for both smooth and nonsmooth cases, sharpening previous analyses that suggested a worse dimension dependence, and extend our results to the case of multiple ( {m}\ge 2$ ) evaluations. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rate of such problems, establishing the sharpness of our achievable results up to constant (sometimes logarithmic) factors. [ABSTRACT FROM AUTHOR]

We introduce the decentralized Broyden–Fletcher–Goldfarb–Shanno (D-BFGS) method as a variation of the BFGS quasi-Newton method for solving decentralized optimization problems. Decentralized quasi-Newton methods are of interest in problems that are not well conditioned, making first-order decentralized methods ineffective, and in which second-order information is not readily available, making second-order decentralized methods impossible. D-BFGS is a fully distributed algorithm in which nodes approximate curvature information of themselves and their neighbors through the satisfaction of a secant condition. We additionally provide a formulation of the algorithm in asynchronous settings. Convergence of D-BFGS is established formally in both the synchronous and asynchronous settings and strong performance advantages relative to existing methods are shown numerically. [ABSTRACT FROM PUBLISHER]

The advances in convex optimization techniques have offered new formulations of design with improved control over the performance of FIR filters. By using lifting techniques, the design of a length-L FIR filter can be formulated as a convex semidefinite program (SDP) in terms of an L\times L matrix that must be rank-1. Although this formulation provides means for introducing highly flexible design constraints on the magnitude and phase responses of the filter, convex solvers implementing interior point methods almost never provide a rank-1 solution matrix. To obtain a rank-1 solution, we propose a novel Directed Iterative Rank Refinement (DIRR) algorithm, where at each iteration a matrix is obtained by solving a convex optimization problem. The semidefinite cost function of that convex optimization problem favors a solution matrix whose dominant singular vector is on a direction determined in the previous iterations. Analytically it is shown that the DIRR iterations provide monotonic improvement, and the global optimum is a fixed point of the iterations. Over a set of design examples it is illustrated that the DIRR requires only a few iterations to converge to an approximately rank-1 solution matrix. The effectiveness of the proposed method and its flexibility are also demonstrated for the cases where in addition to the magnitude constraints, the constraints on the phase and group delay of filter are placed on the designed filter. [ABSTRACT FROM PUBLISHER]

Efficient optimization techniques are important to manage interference in emerging dense wireless networks. Here, we address interference management through power control as a general utility maximization problem. For the class of utility functions that are concave in the logarithm of the optimization variables, we propose a power control algorithm based on fixed-point iterations. The iterations converge to the globally optimal power vector. One key benefit is that, for a network with N transmitters and a centralized implementation of the power control algorithm, the computational complexity per iteration of the algorithm is \cal O(N^2). When implemented in a distributed fashion and allowing for a signaling complexity of N messages per iteration, the computation complexity is reduced to \cal O(N). We show that the proposed centralized and distributed versions of the algorithm converge to the optimal power vector at a linear rate. Our numerical results suggest that in most instances, the algorithm takes fewer than ten iterations to converge, even fewer if the initialization is close to the optimal power vector. The proposed algorithm is, therefore, very efficient for power control in slowly fading channels. Furthermore, unlike previous works in the literature, the proposed algorithm does not require the objective function to be separable into a sum of individual utilities. As an example, we present results for power control in a two-hop decode-and-forward cooperative relay network and illustrate the performance gains due to interference management. [ABSTRACT FROM AUTHOR]

This article proposes a new algorithm to compute the projection on the set of images whose total variation is bounded by a constant. The projection is computed through a dual formulation that is solved by first order non-smooth optimization methods. This yields an iterative algorithm that applies iterative soft thresholding to the dual vector field, and for which we establish convergence rate on the primal iterates. This projection algorithm can then be used as a building block in a variety of applications such as solving inverse problems under a total variation constraint, or for texture synthesis. Numerical results are reported to illustrate the usefulness and potential applicability of our TV projection algorithm on various examples including denoising, texture synthesis, inpainting, deconvolution and tomography problems. We also show that our projection algorithm competes favorably with state-of-the-art TV projection methods in terms of convergence speed. [ABSTRACT FROM AUTHOR]