We consider the convex-concave saddle point problem where is smooth and convex and is smooth and strongly convex. We prove that if the coupling matrix has full column rank, the vanilla primal-dual gradient method can achieve linear convergence even if is not stron…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,738 papers · 148 categories
Trend · papers per month
48 results for “primal-dual gradient”
Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometrymath.OC
Quantized Stochastic Primal-Dual Methods for Distributed Optimization
problem Distributed optimization with stochastic gradients and finite-bit communication
method q-PDGD, a quantized stochastic primal-dual method
result Linear contraction to an explicit neighborhood under RSI, O(1/k) convergence under PL inequality
New method accelerates convergence for entropy-regularized reinforcement learning problems.
problem Slow convergence of standard first-order methods for entropy-regularized Markov decision processes.
method Introduce a quadratically convexified primal-dual formulation and a new interpolating metric to accelerate convergence.
result Global convergence and exponential convergence rate for the new method.
We study a stochastic and distributed algorithm for nonconvex problems whose objective consists of a sum of nonconvex -smooth functions, plus a nonsmooth regularizer. The proposed NonconvEx primal-dual SpliTTing (NESTT) algorithm splits the problem into subproblems, and utilizes an augmented Lagrangian b…
In this paper, we consider a class of finite-sum convex optimization problems whose objective function is given by the summation of () smooth components together with some other relatively simple terms. We first introduce a deterministic primal-dual gradient (PDG) method that can achieve the optimal black-bo…
A new method for distributed optimization reduces communication rounds without minibatches.
problem Efficient training in distributed machine learning with different data distributions.
method A primal-dual method (GA-MSGD) applied to the Lagrangian of distributed optimization.
result Achieves linear convergence in communication rounds for strongly convex objectives.
Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximationcs.LG
Study efficient convergence of RL algorithm with function approximation.
problem Convergence of actor-critic algorithm with nonlinear function approximation.
method Stochastic gradient descent ascent with adaptive proximal term, Polyak-Łojasiewicz condition.
result First efficient convergence result with rate of O(sqrt{ln(N d G^2) / N}).
Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliersmath.OC
New methods solve saddle point problems without line search.
problem Solving saddle point problems efficiently and adaptively.
method Auto-conditioned primal-dual hybrid gradient (AC-PDHG) and auto-conditioned ADMM (AC-ADMM) methods.
result Methods achieve optimal complexity and convergence guarantees.
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 …
Two algorithms solve nonconvex minimax problems with linear constraints, achieving complexity guarantees.
problem Nonconvex minimax problems with coupled linear constraints.
method Zeroth-order primal-dual alternating projected gradient (ZO-PDAPG) and zeroth-order regularized momentum primal-dual projected gradient (ZO-RMPDPG) algorithms.
result Iteration complexity guarantees for solving nonconvex-(strongly) concave minimax problems with coupled linear constraints.
In this paper, we propose a new primal-dual algorithm for minimizing , where , , and are proper lower semi-continuous convex functions, is differentiable with a Lipschitz continuous gradient, and is a bounded linear operator. The proposed algorithm has some famous primal-dual algo…
This paper improves inverse problem solving with weakly convex regularisers and proves convergence.
problem Improving solution methods for inverse problems.
method Generalised formulation of convergent regularisation using weakly convex regularisers, and proof of convergence for primal-dual hybrid gradient method.
result Proves convergence of primal-dual hybrid gradient method for variational problems and shows improved performance with IWCNNs.
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…
Study iterative regularization for linear models with convex bias, improving robust sparse recovery.
problem Improving robust sparse recovery with iterative regularization for linear models.
method Primal-dual gradient approach, analyzing convergence in presence of noise, combining regularization and optimization.
result Theoretical results show state-of-the-art performances with computational speed-ups.
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 …
Proposes a fair meta-learning framework for few-shot classification.
problem Fairness in few-shot learning.
method Primal-Dual subgradient approach for fair initialization.
result Significant improvements over prior work in fairness.
Constrained Markov Decision Process (CMDP) is a natural framework for reinforcement learning tasks with safety constraints, where agents learn a policy that maximizes the long-term reward while satisfying the constraints on the long-term cost. A canonical approach for solving CMDPs is the primal-dual method which updat…
A new method uses deep learning for optimal stopping problems.
problem Solving optimal stopping problems in financial mathematics.
method Deep primal-dual BSDE framework with a novel loss function.
result The method provides a true upper bound for the optimal value.
New algorithm solves complex minimax problems efficiently.
problem Minimizing and maximizing bilinearly coupled smooth functions.
method Lifted Primal-Dual (LPD) method that optimally handles both smooth and bilinear terms.
result First optimal algorithm achieving the lower complexity bound for the problem.
Develops an online method for solving constrained optimization problems with debiasing techniques.
problem Online inference of solutions to constrained optimization problems with equality and inequality constraints.
method Stochastic Sequential Quadratic Programming (SSQP) with momentum debiasing.
result Achieves global almost-sure convergence and local asymptotic normality with optimal primal-dual limiting covariance.
Despite the success of single-agent reinforcement learning, multi-agent reinforcement learning (MARL) remains challenging due to complex interactions between agents. Motivated by decentralized applications such as sensor networks, swarm robotics, and power grids, we study policy evaluation in MARL, where agents with jo…
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…
This paper deals with supervised classification and feature selection in high dimensional space. A classical approach is to project data on a low dimensional space and classify by minimizing an appropriate quadratic cost. A strict control on sparsity is moreover obtained by adding an constraint, here on the ma…
A new algorithm reduces the complexity of solving optimal transport problems.
problem Optimal transport problem with linear constraints.
method Primal-dual accelerated stochastic gradient descent with variance reduction (PDASGD).
result Achieves the best-known computational complexity of for OT problems.
New algorithm solves minimax games with linear constraints.
problem Nonconvex minimax games with coupled linear constraints.
method Primal-dual alternating proximal gradient (PDAPG) algorithm.
result Achieves ε-stationary solution within O(ε^(-2)) iterations for strongly concave settings.
Sketching techniques have become popular for scaling up machine learning algorithms by reducing the sample size or dimensionality of massive data sets, while still maintaining the statistical power of big data. In this paper, we study sketching from an optimization point of view: we first show that the iterative Hessia…
A new algorithm tackles bilevel optimization with multiple inner minima.
problem Challenges in bilevel optimization with multiple inner minima.
method Reformulated as constrained optimization, solved via primal-dual bilevel optimization (PDBO) algorithm.
result First non-asymptotic convergence guarantee for bilevel optimization with multiple inner minima.
New algorithm for fast nonsmooth optimization with applications in image processing and machine learning.
problem Minimizing the sum of three convex functions with specific properties.
method PDDY algorithm, based on Davis-Yin splitting in a primal-dual product space.
result Sublinear and linear convergence rates in various scenarios, including strong convexity.
Given a convex optimization problem and its dual, there are many possible first-order algorithms. In this paper, we show the equivalence between mirror descent algorithms and algorithms generalizing the conditional gradient method. This is done through convex duality, and implies notably that for certain problems, such…
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 …
LEAD algorithm speeds up decentralized optimization with compression.
problem Slow convergence and stability issues in decentralized optimization with compression.
method Proposes the first linearly convergent decentralized algorithm with compression.
result First consensus error bound for coupled dynamics of primal and dual updates.
Stochastic Primal Dual Coordinate Method with Non-Uniform Sampling Based on Optimality Violationsstat.ML
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…
Unified framework for decentralized bilevel optimization with various heterogeneity-correction strategies.
problem Decentralized bilevel optimization with neighborhood communications and data heterogeneity.
method SPARKLE: Single-loop Primal-dual Algorithm for decentralized bilevel optimization, incorporating various heterogeneity-correction techniques.
result Unified convergence analysis for SPARKLE with state-of-the-art convergence rates compared to existing algorithms.
PDCA algorithm learns policies for RL with constraints using a primal-dual approach.
problem Offline constrained reinforcement learning with general function approximation.
method Primal-Dual-Critic Algorithm (PDCA) using a primal-dual approach.
result PDCA finds a near saddle point of the Lagrangian, nearly optimal for constrained RL.
Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learningcs.LG
Algorithm optimizes constrained reinforcement learning with dual variables.
problem Minimizing convex functional subject to convex constraint in large state spaces.
method VPDPO algorithm using Lagrangian and Fenchel duality.
result Achieves sublinear regret and constraint violation, globally optimal policy.
New algorithm speeds up large-scale statistical inference.
problem Efficiently solving large-scale mean-field variational inference problems.
method Developed a novel primal-dual algorithm (PD-VI) and a block-preconditioned extension (PD-VI) for mean-field variational inference.
result PD-VI and PD-VI achieve faster convergence and better solution quality compared to existing methods.
PURE-CD algorithm proves complexity bounds for convex-concave problems.
problem Solving convex-concave min-max problems with bilinear coupling.
method Primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD).
result Complexity bounds match or improve existing results for dense and sparse problems.
Novel analysis of EFP for finite-sum problems in neural networks.
problem Optimization of two-layer neural networks in the mean-field regime.
method Primal-dual analysis of entropic fictitious play (EFP) for finite-sum problems.
result Established global convergence guarantees for EFP dynamics.
Magnetic resonance imaging (MRI) is known to be a slow imaging modality and undersampling in k-space has been used to increase the imaging speed. However, image reconstruction from undersampled k-space data is an ill-posed inverse problem. Iterative algorithms based on compressed sensing have been used to address the i…
New algorithm achieves sublinear regret in CMDPs without error cancellations.
problem Safety constraints in reinforcement learning with error cancellations.
method Model-based primal-dual algorithm for CMDPs with multiple constraints.
result Achieves sublinear regret without error cancellations.
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 convergence rate in terms of the objective value and feasibility m…
Cross-learning improves multi-task learning performance.
problem Improving multi-task learning across different domains.
method Coupling parameters across tasks with a stochastic projected gradient algorithm and primal-dual approach.
result Cross-learned functions outperform task-specific and consensus approaches in image classification.
Accelerates machine learning algorithms for sparse data.
problem Efficiently solving composite convex minimization problems.
method Accelerated dual-averaging primal-dual method for composite convex minimization.
result Demonstrates advantages in handling sparse data both theoretically and empirically.
This work tackles resource allocation in asynchronous and stochastic systems.
problem Distributed resource allocation in asynchronous and stochastic settings.
method Approximate stochastic primal-dual approach with asynchronous updates.
result The Asynchronous stochastic Primal-Dual (Asyn-PD) algorithm converges to the saddle point solution at a rate of .
New algorithm reduces online learning iterations by a factor of T^2/3.
problem Efficiency in online learning with smooth cost functions.
method Follow-the-Perturbed-Leader method using online primal-dual framework.
result Guaranteed T^2/3 regret for general online convex optimization.
Primal-Dual Wasserstein GANstat.ML
We introduce Primal-Dual Wasserstein GAN, a new learning algorithm for building latent variable models of the data distribution based on the primal and the dual formulations of the optimal transport (OT) problem. We utilize the primal formulation to learn a flexible inference mechanism and to create an optimal approxim…
Paper analyzes complexity of PSGLA for sampling log-concave distributions.
problem Sampling from log-concave distributions with composite potentials.
method Uses primal-dual interpretation and duality gap to analyze PSGLA complexity.
result Complexity of PSGLA is for strongly convex potentials.
(Martingale) Optimal Transport And Anomaly Detection With Neural Networks: A Primal-dual Algorithmmath.OC
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 …