More Like this

1. IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method

   Yossi Arjevani, Joan Bruna (January 2020, Proceedings of Machine Learning Research)

   null (Ed.)

   We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method, thereby providing a systematic way for deriving several well-known decentralized algorithms including EXTRA and SSDA. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds. We provide experimental results that demonstrate the effectiveness of the proposed algorithm on highly ill-conditioned problems. 

   more » « less
2. Linear Convergent Decentralized Optimization with Compression

   Liu, Xiaorui; Li, Yao; Wang, Rongrong; Tang, Jiliang; Yan, Ming (January 2021, ICLR 2021)

   Communication compression has become a key strategy to speed up distributed optimization. However, existing decentralized algorithms with compression mainly focus on compressing DGD-type algorithms. They are unsatisfactory in terms of convergence rate, stability, and the capability to handle heterogeneous data. Motivated by primal-dual algorithms, this paper proposes the first \underline{L}in\underline{EA}r convergent \underline{D}ecentralized algorithm with compression, LEAD. Our theory describes the coupled dynamics of the inexact primal and dual update as well as compression error, and we provide the first consensus error bound in such settings without assuming bounded gradients. Experiments on convex problems validate our theoretical analysis, and empirical study on deep neural nets shows that LEAD is applicable to non-convex problems. 

   more » « less
3. An Accelerated Asynchronous Distributed Method for Convex Constrained Optimization Problems

   https://doi.org/10.1109/CISS56502.2023.10089633  

   Abolfazli, Nazanin; Jalilzadeh, Afrooz; Hamedani, Erfan Yazdandoost (March 2023, 2023 57th Annual Conference on Information Sciences and Systems (CISS))

   We consider a class of multi-agent cooperative consensus optimization problems with local nonlinear convex constraints where only those agents connected by an edge can directly communicate, hence, the optimal consensus decision lies in the intersection of these private sets. We develop an asynchronous distributed accelerated primal-dual algorithm to solve the considered problem. The proposed scheme is the first asynchronous method with an optimal convergence guarantee for this class of problems, to the best of our knowledge. In particular, we provide an optimal convergence rate of $$\mathcal O(1/K)$$ for suboptimality, infeasibility, and consensus violation. 

   more » « less
4. A Smoother Way to Train Structured Prediction Models

   Pillutla, Venkata K; Roulet, Vincent; Kakade, Sham M; Harchaoui, Zaid (January 2018, Advances in Neural Information Processing Systems 31)

   We present a framework to train a structured prediction model by performing smoothing on the inference algorithm it builds upon. Smoothing overcomes the non-smoothness inherent to the maximum margin structured prediction objective, and paves the way for the use of fast primal gradient-based optimization algorithms. We illustrate the proposed framework by developing a novel primal incremental optimization algorithm for the structural support vector machine. The proposed algorithm blends an extrapolation scheme for acceleration and an adaptive smoothing scheme and builds upon the stochastic variance-reduced gradient algorithm. We establish its worst-case global complexity bound and study several practical variants. We present experimental results on two real-world problems, namely named entity recognition and visual object localization. The experimental results show that the proposed framework allows us to build upon efficient inference algorithms to develop large-scale optimization algorithms for structured prediction which can achieve competitive performance on the two real-world problems. 

   more » « less
5. A Primal-Dual Analysis of Global Optimality in Nonconvex Low-Rank Matrix Recovery

   Zhang, Xiao; Wang, Lingxiao; Yu, Yaodong; Gu, Quanquan (July 2018, International Conference on Machine Learning)

   We propose a primal-dual based framework for analyzing the global optimality of nonconvex low-rank matrix recovery. Our analysis are based on the restricted strongly convex and smooth conditions, which can be verified for a broad family of loss functions. In addition, our analytic framework can directly handle the widely-used incoherence constraints through the lens of duality. We illustrate the applicability of the proposed framework to matrix completion and one-bit matrix completion, and prove that all these problems have no spurious local minima. Our results not only improve the sample complexity required for characterizing the global optimality of matrix completion, but also resolve an open problem in Ge et al. (2017) regarding one-bit matrix completion. Numerical experiments show that primal-dual based algorithm can successfully recover the global optimum for various low-rank problems. 

   more » « less