Motivated by a recent framework for proving global convergence to critical points of nested alternating minimization algorithms, which was proposed for the case of smooth subproblems, we first show here that non-smoot...
详细信息
Motivated by a recent framework for proving global convergence to critical points of nested alternating minimization algorithms, which was proposed for the case of smooth subproblems, we first show here that non-smooth subproblems can also be handled within this framework. Specifically, we present a novel analysis of an optimization scheme that utilizes the FISTA method as a nested algorithm. We establish the global convergence of this nested scheme to critical points of non-convex and non-smooth optimization problems. In addition, we propose a hybrid framework that allows to implement FISTA when applicable, while still maintaining the global convergence result. The power of nested algorithms using FISTA in the non-convex and non-smooth setting is illustrated with some numerical experiments that show their superiority over existing methods.
Stochastic composite objective mirror descent (SCOMID) is an effective method for solving large-scale stochastic composite problems in machine learning. This method can efficiently use the geometric properties of a pr...
详细信息
Stochastic composite objective mirror descent (SCOMID) is an effective method for solving large-scale stochastic composite problems in machine learning. This method can efficiently use the geometric properties of a problem through a general distance function. However, most existing analyses rely on the convexity of the problem and the unbiased assumption of the stochastic gradient. In addition, the convergence results are obtained in expectation. To this end, we present an almost sure convergence analysis of SCOMID with biased gradient estimation in the non-convexnon-smooth setting. For this general case, the analysis shows that the minimum of the squared generalized projected gradient norm arbitrarily converges to zero with probability one. We also obtain the almost sure convergence of function values for SCOMID with time-varying stepsizes in the non-convex and non-smooth setting. Numerical experiments support our theoretical findings.
This paper addresses the problem of localization, which is inherently non-convex and non-smooth in a federated setting where the data is distributed across a multitude of devices. Due to the decentralized nature of fe...
详细信息
ISBN:
(纸本)9798350300673
This paper addresses the problem of localization, which is inherently non-convex and non-smooth in a federated setting where the data is distributed across a multitude of devices. Due to the decentralized nature of federated environments, distributed learning becomes essential for scalability and adaptability. Moreover, these environments are often plagued by outlier data, which presents substantial challenges to conventional methods, particularly in maintaining estimation accuracy and ensuring algorithm convergence. To mitigate these challenges, we propose a method that adopts an L1-norm robust formulation within a distributed sub-gradient framework, explicitly designed to handle these obstacles. Our approach addresses the problem in its original form, without resorting to iterative simplifications or approximations, resulting in enhanced computational efficiency and improved estimation accuracy. We demonstrate that our method converges to a stationary point, highlighting its effectiveness and reliability. Through numerical simulations, we confirm the superior performance of our approach, notably in outlier-rich environments, which surpasses existing state-of-the-art localization methods.
This paper proposes a proximal variant of the alternating direction method of multipliers (ADMM) for distributed optimization. Although the current versions of ADMM algorithm provide promising numerical results in pro...
详细信息
ISBN:
(纸本)9798350300673
This paper proposes a proximal variant of the alternating direction method of multipliers (ADMM) for distributed optimization. Although the current versions of ADMM algorithm provide promising numerical results in producing solutions that are close to optimal for many convex and non-convexoptimization problems, it remains unclear if they can converge to a stationary point for weakly convex and locally non-smooth functions. Through our analysis using the Moreau envelope function, we demonstrate that MADM can indeed converge to a stationary point under mild conditions. Our analysis also includes computing the bounds on the amount of change in the dual variable update step by relating the gradient of the Moreau envelope function to the proximal function. Furthermore, the results of our numerical experiments indicate that our method is faster and more robust than widely-used approaches.
This paper proposes an alternating direction method of multiplier (ADMM) based algorithm for solving the sparse robust phase retrieval with non-convex and non-smooth sparse penalties, such as minimax concave penalty (...
详细信息
ISBN:
(纸本)9781665459068
This paper proposes an alternating direction method of multiplier (ADMM) based algorithm for solving the sparse robust phase retrieval with non-convex and non-smooth sparse penalties, such as minimax concave penalty (MCP). The accuracy of the robust phase retrieval, which employs an l(1) based estimator to handle outliers, can be improved in a sparse situation by adding a non-convex and non-smooth penalty function, such as MCP, which can provide sparsity with a low bias effect. This problem can be effectively solved using a novel proximal ADMM algorithm, and under mild conditions, the algorithm is shown to converge to a stationary point. Several simulation results are presented to verify the accuracy and efficiency of the proposed approach compared to existing methods.
While many distributed optimization algorithms have been proposed for solving smooth or convex problems over the networks, few of them can handle non-convex and non-smooth problems. Based on a proximal primal-dual app...
详细信息
While many distributed optimization algorithms have been proposed for solving smooth or convex problems over the networks, few of them can handle non-convex and non-smooth problems. Based on a proximal primal-dual approach, this paper presents a new (stochastic) distributed algorithm with Nesterov momentum for accelerated optimization of non-convex and non-smooth problems. Theoretically, we show that the proposed algorithm can achieve an epsilon-stationary solution under a constant step size with O(1/epsilon(2)) computation complexity and O(1/epsilon) communication complexity when the epigraph of the non-smooth term is a polyhedral set. When compared to the existing gradient tracking based methods, the proposed algorithm has the same order of computation complexity but lower order of communication complexity. To the best of our knowledge, the presented result is the first stochastic algorithm with the O(1/epsilon) communication complexity for non-convex and non-smooth problems. Numerical experiments for a distributed non-convex regression problem and a deep neural network based classification problem are presented to illustrate the effectiveness of the proposed algorithms.
In this paper, we propose a novel approach to convolutional sparse representation with the aim of resolving the dictionary learning problem. The proposed method, referred to as the adaptive alternating direction metho...
详细信息
In this paper, we propose a novel approach to convolutional sparse representation with the aim of resolving the dictionary learning problem. The proposed method, referred to as the adaptive alternating direction method of multipliers (AADMM), employs constraints comprising non-convex, non-smooth terms, such as the l(0)-norm imposed on the coefficients and the unit-norm sphere imposed on the length of each dictionary element. The proposed scheme incorporates a novel parameter adaption scheme that enables ADMM to achieve convergence more quickly, as evidenced by numerical and theoretical analysis. In experiments involving image signal applications, the dictionaries learned using AADMM outperformed those learned using comparable dictionary learning methods.
暂无评论