Proximal algorithms for constrained composite optimization, with applications to solving low-rank SDPs

2019-03-01 · Yu Bai, John Duchi, Song Mei

We study a family of (potentially non-convex) constrained optimization problems with convex composite structure. Through a novel analysis of non-smooth geometry, we show that proximal-type algorithms applied to exact penalty formulations of such problems exhibit local linear convergence under a quadratic growth condition, which the compositional structure we consider ensures. The main application of our results is to low-rank semidefinite optimization with Burer-Monteiro factorizations. We precisely identify the conditions for quadratic growth in the factorized problem via structures in the semidefinite problem, which could be of independent interest for understanding matrix factorization.

📄 PDF Abstract BibTeX arXiv:1903.00184

Code (0)

등록된 구현이 없습니다.

Adaptive Smoothing Algorithms for Nonsmooth Composite Convex Minimization

2015-09-01 · Quoc Tran-Dinh

We propose an adaptive smoothing algorithm based on Nesterov's smoothing technique in \cite{Nesterov2005c} for solving "fully" nonsmooth composite convex optimization problems. Our method combines both Nesterov's acceler…

Proximal Oracles for Optimization and Sampling

2024-04-02 · Jiaming Liang, Yongxin Chen

We consider convex optimization with non-smooth objective function and log-concave sampling with non-smooth potential (negative log density). In particular, we study two specific settings where the convex objective/poten…

Constrained and Composite Optimization via Adaptive Sampling Methods

2020-12-31 · Yuchen Xie, Raghu Bollapragada, Richard Byrd, Jorge Nocedal

The motivation for this paper stems from the desire to develop an adaptive sampling method for solving constrained optimization problems in which the objective function is stochastic and the constraints are deterministic…

Decentralized Accelerated Proximal Gradient Descent

2020-12-01 · NeurIPS 2020 12 · Haishan Ye, Ziang Zhou, Luo Luo, Tong Zhang

Decentralized optimization has wide applications in machine learning, signal processing, and control. In this paper, we study the decentralized composite optimization problem with a non-smooth regularization term…

BIG-bench Machine Learning

Proximal Algorithms in Statistics and Machine Learning

2015-02-11 · Nicholas G. Polson, James G. Scott, Brandon T. Willard

In this paper we develop proximal methods for statistical learning. Proximal point algorithms are useful in statistics and machine learning for obtaining optimization solutions for composite functions. Our approach explo…

BIG-bench Machine Learning regression