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.
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.
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.
Network Lasso classifies partially labeled data with high-dimensional features.
problem Classifying data points with limited labeled data and high-dimensional features.
method Logistic Network Lasso using total variation regularization and primal-dual splitting.
result Accurate classification achieved from limited labeled data via network structure.
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.
A new model learns networked data with topology and features.
problem Learning from networked data with topology and features.
method Networked exponential families and network Lasso for efficient learning.
result Efficiently learns networked data with topology and features.
New algorithm solves saddle point problems in Banach spaces.
problem Solving saddle point problems in real reflexive Banach spaces.
method Stochastic Bregman Primal-Dual Splitting Algorithm with relative smoothness and strong convexity assumptions.
result Almost sure convergence to saddle points under various conditions.
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.
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.
Convex optimization is an essential tool for machine learning, as many of its problems can be formulated as minimization problems of specific objective functions. While there is a large variety of algorithms available to solve convex problems, we can argue that it becomes more and more important to focus on efficient, …
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 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. 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 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.
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.
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.
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.
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.
A new GAN training method using primal-dual subgradient methods.
problem Training GANs to avoid mode collapse and generate diverse samples.
method Relating GANs to convex optimization via Lagrangian perspective and primal-dual subgradient methods.
result The proposed method resolves mode collapse and generates diverse samples.
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
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.
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.
APDO optimizes CMDPs with off-policy dual updates for faster convergence.
problem Learning policies that maximize long-term reward while satisfying safety constraints.
method Accelerated Primal-Dual Optimization (APDO) incorporating off-policy dual updates.
result APDO achieves better sample efficiency and faster convergence than existing 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…
Unified view connects CoCoA and ADMM for distributed ERM.
problem Connection between CoCoA and ADMM for distributed ERM.
method Unified primal-dual perspective reformulation.
result Unified ADMM variants perform at least as good as CoCoA in ridge-regularized ERM.
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.
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.
Gradient method achieves linear convergence for saddle point problems without strong convexity.
problem Solving saddle point problems with non-strongly convex functions.
method Primal-dual gradient method with a novel analysis technique.
result Linear convergence achieved without strong convexity of f f f . 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.
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.
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 / ε ) . 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 ) . 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. This work reveals a primal-dual relationship between GANs and Autoencoders, improving their theoretical understanding.
problem Improving the theoretical understanding of GANs and Autoencoders.
method Study of f f f -GAN and WAE models, finding a primal-dual relationship and proving generalization bounds. result The f f f -GAN and WAE objectives are equivalent under certain assumptions, leading to improved theoretical understanding. 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.
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…
Efficient method solves large-scale saddle point problems with parallel updates.
problem Large-scale convex-concave saddle point problems with separable structure.
method Stochastic parallel block coordinate descent with adaptive primal-dual updates.
result Significantly better performance than state-of-the-art methods in various applications.
New methods solve MI problems with locally Lipschitz operators, improving solution efficiency.
problem Solving monotone inclusions with locally Lipschitz continuous operators.
method Primal-dual extrapolation methods using backtracking line search.
result Improved operation complexity for solving MI problems.
Derives a primal-dual MLSVD formulation for multilinear data.
problem Efficiently decompose multilinear data for signal analysis and deep learning.
method Kernelizable primal-dual formulation of MLSVD.
result Derives a new MLSVD formulation with computational advantages.
Develops a regression approach for solving MDPs with general state and action spaces.
problem Solving MDPs with large or infinite state and action spaces.
method Regression-based primal-dual martingale approach.
result Tight upper and lower approximations of value functions and optimal policies.
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. New SPD methods improve online policy estimation in MDPs with reduced storage and complexity.
problem Online estimation of optimal policies in Markov decision processes (MDPs).
method Stochastic Primal-Dual (SPD) methods that update few coordinates of value and policy estimates.
result SPD methods find absolute- ε ε ε -optimal policies with high probability using a specified number of iterations/samples. 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.
A new algorithm solves bilinear saddle-point problems efficiently.
problem Solving bilinear saddle-point problems in optimization.
method Doubly stochastic primal-dual coordinate method.
result The method converges linearly and has lower complexity than existing methods.
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. Replica analysis reveals dual structure in portfolio optimization.
problem Optimizing investment risk and return under constraints.
method Replica analysis in statistical mechanics.
result Optimal portfolios exhibit primal-dual structure.
Random extrapolation speeds up coordinate descent for sparse and dense data.
problem Efficiently solving primal-dual coordinate descent for sparse and dense data.
method Adapts to sparsity and uses large step sizes for dense data, proving linear convergence under metric subregularity.
result Linear convergence under metric subregularity and optimal sublinear convergence rates in general convex-concave problems.
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.