New algorithms exploit data's strong convexity for fast linear convergence without explicit regularization.
problem Empirical risk minimization with convex loss functions.
method Primal-dual first-order algorithms that exploit data's strong convexity.
result Adaptive primal-dual algorithms achieve linear convergence without explicit regularization.
New algorithm minimizes sum of three functions with linear operator.
problem Minimizing the sum of three convex functions with a linear operator.
method Proposes a new primal-dual algorithm for the problem.
result Proves convergence and provides convergence rates.
New algorithms improve computation of optimal transport and Wasserstein barycenter.
problem Computing optimal transport and Wasserstein barycenter for multiple probability distributions.
method Introduced APDRCD and APDGCD algorithms for efficient computation, demonstrating better performance than existing methods.
result New algorithms match or exceed the best known complexities for OT problems and improve practical performance.
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.
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.
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.
New method speeds up optimization with non-uniform sampling.
problem Optimizing complex stochastic problems efficiently.
method Stochastic Primal Dual Coordinate Method with Optimality Violation-based Sampling.
result The proposed method and variants outperform other methods in speed.
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.
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 O ~ ( n 2.5 / ε ) \widetilde{O}({n^{2.5}}/ε) O ( n 2.5 / ε ) to O ~ ( n 2 / ε ) \widetilde{O}({n^2}/ε) O ( n 2 / ε ) . NESTT tackles nonconvex optimization problems in a distributed and stochastic manner.
problem Nonconvex optimization problems with a sum of nonconvex functions and a nonsmooth regularizer.
method NESTT algorithm that splits the problem into N subproblems and uses an augmented Lagrangian based primal-dual scheme.
result NESTT achieves ε-stationary solution using O((\sum_{i=1}^N\sqrt{L_i/N})^2/ε) gradient evaluations, up to N times better than gradient descent methods.
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 (P 2 ^2 2 D-VI) for mean-field variational inference. result PD-VI and P 2 ^2 2 D-VI achieve faster convergence and better solution quality compared to existing methods. 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 O ( n / k ) \mathcal{O}(n/k) O ( n / k ) and O ( n 2 / k 2 ) \mathcal{O}(n^2/k^2) O ( n 2 / k 2 ) . Efficient algorithm solves best subset selection problem.
problem Sparse learning problems, especially best subset selection.
method Primal-dual method based on dual forms of ℓ 0 \ell_0 ℓ 0 -regularized problems. result Improves solutions of best subset selection with reduced redundant computation.
New algorithms solve convex-concave problems faster than previous methods.
problem Solving min-max problems without bilinear structure.
method Stochastic primal-dual algorithms with logarithmic dual updates.
result Faster convergence rates than O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) for certain problems. 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 new algorithm speeds up multi-agent reinforcement learning.
problem Complex interactions between agents in multi-agent reinforcement learning.
method Double averaging scheme for decentralized convex-concave saddle-point problems.
result The algorithm converges to the optimal solution at a global geometric rate.
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.
Paper solves optimal transport with neural nets, also detects anomalies.
problem Optimal transport problems with twist conditions.
method Primal-dual algorithm for neural networks.
result Solves financial data generation and anomaly detection.
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 O ( ε − 2 ) O(ε^{-2}) O ( ε − 2 ) sample complexity. result First computationally efficient algorithm with O ( ε − 2 ) O(ε^{-2}) O ( ε − 2 ) sample complexity for offline RL with linear MDPs under partial data coverage. Proposes neural network for optimization problems with hard constraints.
problem Optimization problems with hard constraints.
method Primal-dual splitting methods and residual networks.
result Our method outperforms classical splitting methods in speech dequantization.
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.
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.
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 O ~ ( n 2 / ε ) \widetilde{\mathcal{O}}(n^2/ε) O ( n 2 / ε ) 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.
A deep neural network improves document binarization accuracy.
problem Binarizing digital documents with historical degradations.
method Combines FCN with primal-dual network for end-to-end training.
result Achieves state-of-the-art binarization on four out of seven datasets.
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.
New algorithm beats traditional methods for seismic data interpolation.
problem Efficiently filling in missing seismic data volumes.
method Primal-dual alternating approach using matrix factors and block-coordinate algorithm.
result Successfully interpolated a large 5D seismic data volume from a 3D model.
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.
New algorithm solves composite optimization problems with unknown expectations.
problem Solving composite optimization problems with unknown statistical expectations.
method Proposes a new stochastic primal-dual algorithm for composite optimization problems with unknown statistical expectations.
result Converges to a saddle point of the Lagrangian function.
Improved Frank-Wolfe for sparse/low-rank problems.
problem Sparse/low-rank optimization problems.
method Primal-Dual Block Frank-Wolfe algorithm.
result Empirically outperforms state-of-the-art methods in classification tasks.
Paper tackles robust classification and feature selection with a novel primal-dual method.
problem Robust supervised classification and feature selection in high-dimensional data.
method Developed a novel constrained primal-dual method to jointly select features and classifiers.
result Demonstrated effectiveness on synthetic and biological datasets, comparing different costs.
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.
Accelerated method for solving convex optimization problems with linear constraints.
problem Solving large-scale convex optimization problems with linear constraints.
method Primal-dual proximal block coordinate updating method with accelerated convergence.
result Achieves O ( 1 / t 2 ) O(1/t^2) O ( 1/ t 2 ) convergence rate for strongly convex objectives and linear rate for independent blocks. 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.
New K-SVD framework speeds up image denoising with active set algorithm.
problem Efficiently denoise images with high noise levels.
method Proposes K-SVD P _P P using Primal-dual active set (PDAS) algorithm. result Demonstrates comparable performance to state-of-the-art methods.
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…
This paper proposes a communication-efficient distributed algorithm for high-dimensional data mining.
problem Reducing communication time and rounds in distributed data mining.
method Straggler-agnostic and bandwidth-efficient distributed primal-dual algorithm.
result Guaranteed linear convergence rate for convex problems.
A new GAN algorithm using primal-dual formulations of optimal transport.
problem Building latent variable models of data distributions.
method Primal formulation for inference and dual formulation for adversarial training.
result Improves mode coverage and avoids averaging properties of auto-encoding models.
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.
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.
New method improves convergence rates for convex optimization problems.
problem Convex optimization with nonsmooth objectives.
method Randomized coordinate descent with smoothing, acceleration, homotopy, and non-uniform sampling.
result First convergence rate guarantees for coordinate descent methods.
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 O ( N 3.25 T ) O(N^{3.25}\sqrt{T}) O ( N 3.25 T ) . 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.
New algorithm reduces big data processing time by sketching and random projection.
problem Efficiently processing large and high-dimensional data sets.
method Developed a new algorithm combining sketching and dual random projection, using preconditioned conjugate gradient.
result The algorithm can recover the optimum of the original problem up to arbitrary precision with a logarithmic number of small-scale solver calls.
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.