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 …
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,695 papers · 148 categories
Trend · papers per month
48 results for “Primal-dual algorithm”
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 …
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.
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…
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.
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.
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…
Improved first-order algorithm for entropy regularized OT with faster convergence.
problem Solving entropy regularized optimal transport efficiently.
method Accelerated primal-dual stochastic mirror descent algorithm with variance reduction.
result Improved rate from to .
(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 …
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…
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.
A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Ratesmath.OC
Unified algorithm solves convex optimization problems with optimal rates.
problem Solving nonsmooth constrained convex optimization problems.
method Unified randomized block-coordinate primal-dual algorithm.
result Achieves optimal convergence rates of and .
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…
Efficient algorithm solves best subset selection problem.
problem Sparse learning problems, especially best subset selection.
method Primal-dual method based on dual forms of -regularized problems.
result Improves solutions of best subset selection with reduced redundant computation.
A Primal Dual Active Set with Continuation Algorithm for the \ell^0-Regularized Optimization Problemmath.OC
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…
A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learningcs.LG
Paper proposes a novel metric learning algorithm using Riemannian optimization.
problem Optimizing a smooth, convex function in Riemannian space with constraints.
method Developed a primal-dual algorithm with proximal operator for iterative optimization.
result Demonstrated the efficacy of the proposed metric learning algorithm on fund selection.
Improved RL algorithm with linear MDPs for offline learning with partial data coverage.
problem Efficient offline RL with linear MDPs under partial data coverage.
method Primal-dual algorithm with sample complexity.
result First computationally efficient algorithm with sample complexity for offline RL with linear MDPs under partial data coverage.
Paper analyzes and compares ELF algorithms for federated learning.
problem Improving efficiency and privacy in federated learning.
method Proposes P-ELF, D-ELF, and B-ELF algorithms with primal, dual, and bidirectional compression.
result Provides non-asymptotic convergence guarantees under Log-Sobolev inequality.
A new stochastic primal--dual algorithm for solving a composite optimization problem is proposed. It is assumed that all the functions/operators that enter the optimization problem are given as statistical expectations. These expectations are unknown but revealed across time through i.i.d. realizations. The proposed al…
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.
We propose a variant of the Frank-Wolfe algorithm for solving a class of sparse/low-rank optimization problems. Our formulation includes Elastic Net, regularized SVMs and phase retrieval as special cases. The proposed Primal-Dual Block Frank-Wolfe algorithm reduces the per-iteration cost while maintaining linear conver…
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.
A distributed algorithm for online multi-task learning reduces communication and runtime costs.
problem Heavy communication and high runtime complexity in online multi-task learning.
method Adaptive primal-dual algorithm that synchronizes data across geographically distributed tasks.
result The proposed algorithm achieves optimal regret and is effective on real-world datasets.
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…
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.
Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimizationstat.ML
Drago optimizes DRO problems with faster convergence.
problem Distributionally robust optimization with closed, convex uncertainty sets.
method Primal-dual coupled variance reduction algorithm with cyclic and randomized updates.
result Achieves state-of-the-art linear convergence rate on strongly convex-strongly concave problems.
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…
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…
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…
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 …
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}).
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.
In this work, we propose a deep neural network architecture motivated by primal-dual splitting methods from convex optimization. We show theoretically that there exists a close relation between the derived architecture and residual networks, and further investigate this connection in numerical experiments. Moreover, we…
Paper tackles offline RL with weak assumptions on both function classes and data coverage.
problem Achieve sample-efficient offline RL with weak assumptions on both factors.
method Simple algorithm based on primal-dual formulation of MDPs, with density-ratio function modeling dual variables.
result Polynomial sample complexity achieved under realizability and single-policy concentrability.
We propose a doubly stochastic primal-dual coordinate optimization algorithm for empirical risk minimization, which can be formulated as a bilinear saddle-point problem. In each iteration, our method randomly samples a block of coordinates of the primal and dual solutions to update. The linear convergence of our method…
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…
Asymptotically optimal algorithm for contextual linear bandits.
problem Contextual linear bandits with suboptimal algorithms.
method Decoupling context distribution and exploration policy, incremental primal-dual approach, confidence intervals.
result Asymptotic optimality and scalability of the algorithm.
Function Design for Improved Competitive Ratio in Online Resource Allocation with Procurement Costsmath.OC
Improved resource allocation method reduces procurement costs.
problem Online resource allocation with procurement costs.
method Primal-dual algorithm with surrogate function optimization.
result Enhanced competitive ratio through design methods.
Optimizes subset selection in sparse learning problems.
problem Sparse learning problems, particularly best subset selection.
method Developed an efficient primal-dual algorithm leveraging dual range estimation and incremental strategy.
result Improves solutions of best subset selection with reduced redundant computation.
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.
Improved algorithm reduces regret in NRM with unknown demand.
problem Optimizing prices for products with limited resources under unknown demand.
method Primal-dual optimization with demand balancing.
result Improved regret bound of .
Optimizes stochastic linear bandits with efficient, asymptotically optimal algorithm.
problem Optimizing stochastic linear bandits with multiple actions.
method Frequentist information-directed sampling (IDS) with a surrogate for information gain.
result Asymptotically optimal and nearly worst-case optimal in finite time.
We consider the problem of a firm seeking to use personalized pricing to sell an exogenously given stock of a product over a finite selling horizon to different consumer types. We assume that the type of an arriving consumer can be observed but the demand function associated with each type is initially unknown. The fir…
Paper tackles offline CMDP problems with near-optimal algorithm and sample complexity bound.
problem Offline CMDP problems with only offline data available.
method DPDL algorithm using single-policy concentrability coefficient and deviation control mechanism.
result DPDL algorithm matches sample complexity lower bound with factor.
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.
In this paper, we consider the problem of recovering a sparse signal based on penalized least squares formulations. We develop a novel algorithm of primal-dual active set type for a class of nonconvex sparsity-promoting penalties, including , bridge, smoothly clipped absolute deviation, capped and mini…
We study the problem of learning policy of an infinite-horizon, discounted cost, Markov decision process (MDP) with a large number of states. We compute the actions of a policy that is nearly as good as a policy chosen by a suitable oracle from a given mixture policy class characterized by the convex hull of a set of k…
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.