arXiv research

We study primal-dual type stochastic optimization algorithms with non-uniform sampling. Our main theoretical contribution in this paper is to present a convergence analysis of Stochastic Primal Dual Coordinate (SPDC) Method with arbitrary sampling. Based on this theoretical framework, we propose Optimality Violation-ba…

We consider the convex-concave saddle point problem $\min_{x}\max_{y} f(x)+y^\top A x-g(y)$ where $f$ is smooth and convex and $g$ is smooth and strongly convex. We prove that if the coupling matrix $A$ has full column rank, the vanilla primal-dual gradient method can achieve linear convergence even if $f$ is not stron…

We provide theoretical complexity analysis for new algorithms to compute the optimal transport (OT) distance between two discrete probability distributions, and demonstrate their favorable practical performance over state-of-art primal-dual algorithms and their capability in solving other problems in large-scale, such …

Derives a primal-dual MLSVD formulation for multilinear data.

We present a primal-dual algorithmic framework to obtain approximate solutions to a prototypical constrained convex optimization problem, and rigorously characterize how common structural assumptions affect the numerical efficiency. Our main analysis technique provides a fresh perspective on Nesterov's excessive gap te…

In the present paper, the primal-dual problem consisting of the investment risk minimization problem and the expected return maximization problem in the mean-variance model is discussed using replica analysis. As a natural extension of the investment risk minimization problem under only a budget constraint that we anal…

Efficient algorithm solves best subset selection problem.

Study efficient convergence of RL algorithm with function approximation.

We develop a primal dual active set with continuation algorithm for solving the \ell^0-regularized least-squares problem that frequently arises in compressed sensing. The algorithm couples the the primal dual active set method with a continuation strategy on the regularization parameter. At each inner iteration, it fir…

Study iterative regularization for linear models with convex bias, improving robust sparse recovery.

We propose a new randomized coordinate descent method for a convex optimization template with broad applications. Our analysis relies on a novel combination of four ideas applied to the primal-dual gap function: smoothing, acceleration, homotopy, and coordinate descent with non-uniform sampling. As a result, our method…

New algorithm reduces regret and constraint violation in adversarial CMDP learning.

Paper analyzes and compares ELF algorithms for federated learning.

New methods solve MI problems with locally Lipschitz operators, improving solution efficiency.

We consider empirical risk minimization of linear predictors with convex loss functions. Such problems can be reformulated as convex-concave saddle point problems, and thus are well suitable for primal-dual first-order algorithms. However, primal-dual algorithms often require explicit strongly convex regularization in …

Novel analysis of EFP for finite-sum problems in neural networks.

We consider convex-concave saddle point problems with a separable structure and non-strongly convex functions. We propose an efficient stochastic block coordinate descent method using adaptive primal-dual updates, which enables flexible parallel optimization for large-scale problems. Our method shares the efficiency an…

Previous studies on stochastic primal-dual algorithms for solving min-max problems with faster convergence heavily rely on the bilinear structure of the problem, which restricts their applicability to a narrowed range of problems. The main contribution of this paper is the design and analysis of new stochastic primal-d…

PDCA algorithm learns policies for RL with constraints using a primal-dual approach.

FeDualEx tackles saddle point optimization in federated learning with composite objectives.

Optimizes subset selection in sparse learning problems.

Optimizes stochastic linear bandits with efficient, asymptotically optimal algorithm.

New algorithm speeds up large-scale statistical inference.

New method accelerates convergence for entropy-regularized reinforcement learning problems.

New iterative regularization method tackles non-smooth, non-strongly convex functionals.

In this paper, we propose a stochastic Primal-Dual Hybrid Gradient (PDHG) approach for solving a wide spectrum of regularized stochastic minimization problems, where the regularization term is composite with a linear function. It has been recognized that solving this kind of problem is challenging since the closed-form…

PURE-CD algorithm proves complexity bounds for convex-concave problems.

New algorithm achieves sublinear regret in CMDPs without error cancellations.

New algorithm for fast nonsmooth optimization with applications in image processing and machine learning.

Quantized Stochastic Primal-Dual Methods for Distributed Optimization

LEAD algorithm speeds up decentralized optimization with compression.

In this paper, we propose a new primal-dual algorithm for minimizing $f(x) + g(x) + h(Ax)$, where $f$, $g$, and $h$ are proper lower semi-continuous convex functions, $f$ is differentiable with a Lipschitz continuous gradient, and $A$ is a bounded linear operator. The proposed algorithm has some famous primal-dual algo…

We study a stochastic and distributed algorithm for nonconvex problems whose objective consists of a sum of $N$ nonconvex $L_i/N$-smooth functions, plus a nonsmooth regularizer. The proposed NonconvEx primal-dual SpliTTing (NESTT) algorithm splits the problem into $N$ subproblems, and utilizes an augmented Lagrangian b…

Improved resource allocation method reduces procurement costs.

Binarization of digital documents is the task of classifying each pixel in an image of the document as belonging to the background (parchment/paper) or foreground (text/ink). Historical documents are often subjected to degradations, that make the task challenging. In the current work a deep neural network architecture …

In this paper, we introduce a primal-dual algorithm for solving (martingale) optimal transportation problems, with cost functions satisfying the twist condition, close to the one that has been used recently for training generative adversarial networks. As some additional applications, we consider anomaly detection and …

New algorithm for federated learning with non-smooth regularizers.

New methods solve saddle point problems without line search.

PAPAL algorithm finds mixed Nash equilibria in continuous games.

Drago optimizes DRO problems with faster convergence.

In this paper we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its $O(1/t)$ convergence rate in terms of the objective value and feasibility m…

Unified framework for decentralized bilevel optimization with various heterogeneity-correction strategies.

In this paper we study nonconvex and nonsmooth multi-block optimization over Riemannian manifolds with coupled linear constraints. Such optimization problems naturally arise from machine learning, statistical learning, compressive sensing, image processing, and tensor PCA, among others. We develop an ADMM-like primal-d…

This work tackles resource allocation in asynchronous and stochastic systems.

Improved first-order algorithm for entropy regularized OT with faster convergence.

Unified algorithm solves convex optimization problems with optimal rates.

New algorithm solves minimax games with linear constraints.

Dual averaging-type methods are widely used in industrial machine learning applications due to their ability to promoting solution structure (e.g., sparsity) efficiently. In this paper, we propose a novel accelerated dual-averaging primal-dual algorithm for minimizing a composite convex function. We also derive a stoch…