Primal-Dual Optimization

Follow this topic Ask about this topic

Momentum

6 papers in the last four weeks, against 2 the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 36

Oct 7, 2026cs.LG

CERO: Where and When to Allocate Rollouts for RL Post-Training

Adaptive rollout methods for group-relative reinforcement learning typically allocate a fixed per-update budget across prompts. We instead study how to coordinate a finite rollout budget over the entire training horizon. We formulate this problem using a concave surrogate utility of cumulative prompt exposure and introduce CERO, an online primal dual scheduler for prompt admission and budget pacing. In our experiments, each admitted prompt receives a fixed-size response group. CERO instead adapts which prompts are selected, how often they are revisited across rounds, and how many groups are generated in each round. A compact Fenchel representation linearizes the dependence on cumulative exposure, while projected online gradient descent updates prompt-specific supporting slopes and a shared budget price using reward-variation feedback and budget deviations. We establish pathwise guarantees for the surrogate allocation objective against fixed-rate and same-path time-varying benchmarks, with explicit terms for proxy discrepancy and rate variation. Under matched training-response budgets, CERO attains the highest avg@16 macro-average on each of three backbones across five mathematical reasoning benchmarks. Mechanistic analyses link CERO's prompt choices to within-group reward contrast, while multi-seed ablations show gains from adaptive pacing over both uniform and preset spending schedules.

Yiming Zong, Yige Wang, Xing Hu +2

Department of Industrial Engineering & Decision Analytics, Hong Kong University of Science and Technology · Innovation and Information Management, The University of Hong Kong · Faculty of Engineering & Faculty of Business and Economics, The University of Hong Kong

Reinforcement Learning RL Post-Training RL for Language Model Reasoning Group Relative Policy Optimization Primal-Dual Optimization

Oct 5, 2026cs.LG

Neural Algorithmic Reasoning for Graph Saddle Point Problems

Neural algorithmic reasoning, or aligning a neural network with an algorithmic paradigm, has emerged as an approach to solving polynomial-time-solvable and computationally harder combinatorial optimization problems. We propose a new message-passing framework based on the Chambolle-Pock Primal--Dual Hybrid Gradient (PDHG) method called \textsc{GraphPDHG} for solving general graph saddle-point problems. Theoretically, we show that \textsc{GraphPDHG} can efficiently solve a family of graph saddle-point problems by simulating PDHG. We also show that our network can learn an accelerated PDHG algorithm. Experimentally, we support our results on accelerated PDHG by evaluating the performance of our model as a learned warm start for second-order optimization techniques (SSNAL). We also show that alignment with PDHG leads to stronger size generalization than non-aligned graph neural network (GNN) baselines. Overall, we propose a novel architecture for solving a general family of optimization problems on graphs.

Samantha Chen, Jesse He, Coleman Clougherty +2

Oberlin College · Department of Computer Science, Oberlin College · University of California, San Diego +2

Primal-Dual Optimization Graph Neural Networks Neural Algorithmic Reasoning Min-Max Optimization Algorithmic Reasoning Accelerated Gradient Methods

Oct 1, 2026math.OC

Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming

Primal-dual hybrid gradient (PDHG) methods solve large-scale linear programs (LPs) using GPU-friendly matrix-vector products and projections, but their practical performance depends on coordinating algorithm parameters, acceleration, and restarts. We introduce GALLOP, which uses reinforcement learning to jointly learn continuous algorithm parameters and discrete restart decisions without differentiating through the solver. Its generalized accelerated PDHG update combines separate primal and dual extrapolation, history corrections, and restart anchoring with independently adjustable coefficients. We train a dimension-agnostic feedback policy using a groupwise proximal policy optimization objective that clips likelihood ratios separately for different control groups and excludes inactive acceleration controls on restart transitions. We evaluate GALLOP on six LP families and a public item-placement benchmark. On the main evaluation settings across the six families, GALLOP reduces iteration counts by factors of

1.9

-

5.6

and achieves up to a

16.0\times

speedup in algorithm wall-clock time over MPAX. With one policy trained per family, the learned policies generalize without retraining to within-family LPs

3\times

-

400\times

larger than the largest training instances, including Transport LPs with

10.24

million variables.

Jinhwan Sul, Alex Oshin, Evangelos A. Theodorou

Georgia Institute of Technology, USA

Primal-Dual Optimization Reinforcement Learning Linear Programming Accelerated Gradient Methods

Sep 28, 2026math.OC

Learned Preconditioning for a Primal-Dual Interior-Point Method

Interior-point methods (IPMs) are among the most widely used algorithms for constrained optimization, yet their Newton-based search directions require costly second-order information and large linear-system solves. Learning to optimize offers cheaper updates learned from data, but the singular behavior of logarithmic barriers near constraint boundaries makes IPMs highly sensitive to perturbations, complicating both warm starting and learning reliable updates. We introduce pdLIP, an IPM for smooth nonlinear programs that integrates learned preconditioning with pdProj, an all-shifted primal-dual projected-search IPM. A shared coordinate-wise recurrent network predicts a positive diagonal preconditioner that scales the right-hand side of the reduced Newton system for the primal step, and the remaining slack and multiplier directions are recovered analytically. The learned iterations avoid Hessian evaluations and Newton-system solves, using only first-order and coordinate-wise operations amenable to GPU parallelization. Training is self-supervised, with a loss based on a penalty-barrier merit function and the residual of perturbed optimality conditions, requiring neither target directions nor precomputed solutions. Primal and dual shifts mitigate the barrier's sensitivity to perturbations near constraint boundaries, enabling effective warm starting. Across four classes of 200-dimensional convex and nonconvex constrained problems, pdLIP warm starts reduce pdProj refinement iterations by 63-67% compared with cold starts at the same KKT residual tolerance of

10^{-8}

, with negligible warm-start generation cost relative to the subsequent pdProj solve. Improvements persist on box-constrained QPs with 1000 variables and extend to applications including portfolio optimization, support vector machines, and a nonlinear control example.

Abhinav Madabhushi, Jialin Liu, Minxin Zhang

Department of Mathematics, University of California, Los Angeles · School of Data, Mathematical, and Statistical Sciences, University of Central Florida

Primal-Dual Optimization Learning to Optimize Constrained Optimization

Sep 28, 2026cs.LG

Predictive Dual Smoothing for Column Generation

Solving large-scale linear programs efficiently is an important challenge in many optimization settings. A key technique is column generation, which alternates between solving the master problem over a restricted subset of the variables, and using a pricing subproblem to identify new variables to add. The pricing subproblem is guided by the dual solution of the current restricted master problem, but oscillations in these dual solutions can substantially slow convergence. Dual stabilization methods address this issue. Dual smoothing is a common stabilization method, which guides the pricing subproblem using a combination of the current dual solution and duals from previous iterations. However, while past dual solutions can stabilize the dual trajectory, they do not necessarily guide pricing towards useful new variables. We therefore introduce predictive dual smoothing, which instead combines the current dual solution with a learned prediction of future duals to steer pricing towards variables that are more useful in subsequent iterations. The predictor is trained offline using supervision extracted from standard column generation trajectories and is used only to modify the pricing subproblem's objective function, while exact reduced-cost checks and fallback pricing with the unsmoothed duals preserve correctness. Experiments on cutting stock and generalized assignment problems show that predictive dual smoothing substantially reduces generated columns and wall-clock time relative to standard column generation and existing classical and learned stabilization methods. These gains extend to out-of-distribution instance sizes, and predictive smoothing provides further improvements when combined with strong classical stabilization.

Senne Berden, Noah Schutte, Andrea Lodi +1

KU Leuven · TU Delft · Cornell Tech

Primal-Dual Optimization Linear Programming Learning-Augmented Algorithms

Sep 27, 2026math.OC

Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory

We characterize Bregman Douglas-Rachford splitting (BDRS) for unregularized discrete optimal transport and develop an anytime primal-dual certificate in linear memory. We first establish that BDRS coincides with warm-started Inexact Proximal point method for exact Optimal Transport (IPOT) using a single inner Sinkhorn iteration. By eliminating the primal transport plan from the updates, we derive an equivalent dual formulation that reveals BDRS as annealed Sinkhorn under an implicit inverse-linear temperature schedule, with an additional log-scaling momentum term and a cooler kernel. While this explains the role of the temperature parameter in BDRS as an initial temperature, it also reduces the solver's memory requirement from quadratic to linear. Utilizing this annealing perspective, we introduce overrelaxed BDRS, which combines annealing and overrelaxed scaling within a single recursion. We derive a primal-dual certificate for both methods that can be evaluated in linear memory without transport plan construction, thus providing a computable stopping rule. On the DOTmark benchmark, combining momentum with the cooler kernel produces substantially smaller optimality gaps than annealed Sinkhorn under the same schedule. For pixel-level color transfer between

1024\times1024

images, BDRS attains a lower repaired transport cost than MDOT-TNT with a 9

\times

speed up, reaching a relative duality gap of

1.59\%

in 24 minutes. We further demonstrate a color transfer with

4238\times2365

images, yielding 10 million pixels per image and approximately one hundred trillion implicit transport entries, reaching a best relative duality gap of

2.41\%

and

2.80\%

within 35 hours in each direction on a single NVIDIA L40S GPU.

Samuel J. K. Chin, Maximilian Schiffer

MIT · HEC Paris

Primal-Dual Optimization Optimal Transport

Sep 14, 2026cs.LG

Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions

Optimal transport (OT) compares distributions and aligns datasets in machine learning, yet unregularized discrete OT requires a linear program with quadratically many transport variables. We propose HELLO, a hierarchical solver that casts large-scale discrete OT as edge localization and uses dual potentials to guide both coarse-to-fine initialization and within-level refinement. Initialization propagates coarse dual potentials across a recursive subsampling hierarchy to assign candidate edges. Refinement then iteratively inserts the largest dual violators in each row and column until the relative KKT residual meets a prescribed tolerance, while budgeted pruning ensures linear memory complexity. For exact-arithmetic refinement, we prove finite termination at a global optimum under a symbolic lexicographic rule. At the million-point scale, HELLO attains lower transport objectives with order-of-magnitude runtime improvements over strong baselines across feature dimensions from single digits to thousands. It further scales to 1.28 million samples per marginal in 8192 dimensions on a single H100, using 41.6 GiB peak GPU memory while satisfying a full relative KKT residual below

10^{-6}

. Beyond standard discrete OT, the framework supports general pairwise costs and serves as a scalable balanced-OT oracle for semi-discrete OT, Gromov--Wasserstein, unbalanced OT, and OT-based Flow Matching.

Wenzhou Xia, Qiaoqiao Ding, Jingwei Liang +1

School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai 200240, China · Institute of Natural Sciences, Shanghai Jiao Tong University, Shanghai 200240, China

Primal-Dual Optimization Optimal Transport

Sep 7, 2026math.OC

Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus

Generalized Nash Equilibrium Problems (GNEPs) often arise in multi-agent engineering applications that require distributed algorithms. Unlike traditional approaches that enforce consensus on multipliers, our method removes the need to share multipliers, reducing communication and improving privacy. As a result, different initializations can lead to different GNEs, including non-variational ones. We establish convergence under sufficient conditions using an input-to-state stability (ISS) framework.

Shao-An Yin

independent researcher

Primal-Dual Optimization Dynamical Systems Game Theory Decentralized Optimization Nash Equilibrium Computation

Aug 12, 2026cs.RO

ContactIPM: A Structure-Exploiting Interior-Point Solver for Contact-Implicit Trajectory Optimization

Contact-implicit trajectory optimization avoids prescribing contact sequences, but yields mathematical programs with complementarity constraints (MPCCs) whose degeneracy challenges conventional primal--dual solvers. Existing contact-specific methods improve robustness to this degeneracy but do not leverage a stagewise optimal-control factorization and primal--dual consistency, while structure-exploiting optimal-control solvers are not designed for complementarity constraints. We show that these capabilities can be combined in a single primal--dual method. ContactIPM identifies complementary inequality pairs, embeds them through a barrier-coupled elastic interior relaxation, eliminates slack and dual variables stagewise, and solves the reduced Newton system using a Riccati recursion. A fixed multi-phase MPCC recovery schedule provides four continuation and restart attempts from naive initializations, while termination is gated by the unrelaxed physical complementarity residual. We compare ContactIPM with two contact-specific MPCC solvers, CRISP and IMPACT, using matched benchmark conditions and common post-solve acceptance criteria. On four fixed CRISP benchmark cases, ContactIPM is

2.17

--

8.87\times

faster over 20 paired timing repetitions per case and achieves higher success on the Push Box and Push-T robustness suites. Against IMPACT, ContactIPM is

2.96\times

faster on Push T and

4.91\times

faster on Cart Transport, but

4.46\times

slower on Push Box. In 50 closed-loop Push Box rollouts spanning model mismatch, measurement noise, initial-pose errors, and state resets,

Yucheng Chen

Primal-Dual Optimization Trajectory Optimization Constrained Optimization

Aug 10, 2026cs.AI

DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning

Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs. Existing neural--operations-research (OR) hybrids predict guidance without requiring learned transitions to satisfy constraints discovered during search. DualCert introduces \emph{constraint-coupled learning}, in which current degree equations and dynamically separated subtour-elimination constraints (SECs) define each learned transition. At each refinement, the degree equations and selected, strictly satisfied SEC equations, with positive slacks, define an iterate-dependent primal-slack Karush--Kuhn--Tucker (KKT) manifold. Repaired dual variables and violated SEC rows define a local cost field. An exact constrained mirror-descent step maps each finite state to a positive state on the same manifold. Where selected rows and deterministic ties remain fixed, implicit differentiation maps parameter perturbations into the manifold tangent space and reuses the forward constraint operator for the local-cost-field derivative. The terminal edge state allocates computation across Held--Karp ascent, candidate-graph edge tests, and tour construction under a fixed budget. Deterministic verification recomputes original costs and accepts only verified candidate-graph lower bounds and edge decisions. On 1,000 held-out TSP1000 instances, DualCert attains a mean tour-cost gap of

0.0573\%

from Lin--Kernighan--Helsgaun version 3 (LKH-3) reference tours in

9.55

batch-amortized seconds per instance. It returns a verified candidate-graph lower bound for every instance and achieves

81.46\%

edge-decision coverage. The mean gap is

67.1\%

smaller than the reported NeuroLKH mean gap. Thus, optimization constraints govern learning, while deterministic verification preserves output validity.

Yancheng Song, Yongzhi Qi, Wei Qi +1

Department of Industrial Engineering, Tsinghua University, Beijing 100084, China · JD.com, Beijing, China · College of Engineering, UC Berkeley, Berkeley, CA 94720, USA; Faculty of Engineering, Faculty of Business and Economics, University of Hong Kong, Hong Kong, China

Traveling Salesperson Problem Primal-Dual Optimization Constrained Optimization Neural Combinatorial Optimization

Aug 9, 2026cs.LG

Constrained Learning with Universally Learnable Concept Classes

We study constrained statistical learning over infinite-dimensional hypothesis classes in the fully nonconvex setting, and establish universal PACC learnability of the solutions of dual algorithms: Probably Approximately Correct on Constraints, guaranteeing optimality and constraint satisfaction at once. This strengthens near-PACC results, whose feasibility residual no amount of data can remove. Optimality is caught between generalization, governed by Rademacher complexity and favoring small classes, and strong Lagrangian duality, which rests on Lyapunov convexity for vector measures and needs decomposability, a demand pulling the other way. We reconcile the two by posing the population problem over a universal RKHS

\mathcal{H}_K

, dense in a decomposable envelope, and learning over norm balls of growing radius. This yields the Tikhonov complexity

\mathfrak{T}^{\varepsilon}_{n}

, the least RKHS norm reaching an

\varepsilon

-optimal Lagrangian level set; we prove it finite, obtain exact learnability of the optimal value, and make the sample threshold explicit and polynomial in

1/\varepsilon

under a source condition. Feasibility is harder: absent convexity the Lagrangian may not attain its infimum, and dual information pins down only an averaged constraint-risk vector, not the risks of any returned predictor. We introduce the closure-realization gap

\varepsilon^\star_\infty

, an index of how well

\mathcal{H}_K

retrieves feasible solutions from dualization; it is a property of the problem, not of a modeling choice. Learnability is exact when

\varepsilon^\star_\infty=0

, in particular under dual differentiability, and near-PACC with residual exactly

\varepsilon^\star_\infty

otherwise. Finally, no distribution-free threshold exists already in the unconstrained specialization, so universality is the canonical frame for dual algorithms over large hypothesis classes.

Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias

1Yale University · 2King’s College London

Primal-Dual Optimization Reproducing Kernel Hilbert Spaces PAC Learning Statistical Learning Theory

Jul 17, 2026math.NA

Non-Asymptotic Variational Learning for Monotone Nonlinear Multiscale Elliptic Equations: Scale-Robust Primal-Dual Bounds and Strong-Form Statistical Ill-Conditioning

We develop a non-asymptotic approximation, sampling, and finite-iteration optimization theory for variational physics-informed approximation of uniformly monotone nonlinear multiscale elliptic equations. For boundary-compatible neural feature classes, the population error splits into approximation, empirical quadrature, and projected-gradient terms, with all non-approximation constants uniform in the microscopic scale

\varepsilon

. Assuming a quantitative corrected

H^1

-estimate, a two-scale state class yields

\mathcal A_m^\varepsilon \le C\bigl(\varepsilon+Φ_{0,m_0}^2+Φ_{1,m_1}^2\bigr)

in arbitrary dimension. We further introduce a convex primal-dual physics loss whose population value is a computable upper certificate for the state error. With additional flux-corrector regularity, a divergence-compatible two-scale flux class gives a certified state-flux bound combining

O(\varepsilon)

approximation, state and flux feature errors, empirical sampling error, and an

O(K^{-1})

optimization term. In contrast, for general periodic nonlinear fluxes satisfying a natural nondegeneracy condition, the empirical Rademacher complexities of strong-residual and squared-residual classes are bounded below by constant multiples of

(\varepsilon\sqrt N)^{-1}

and

(\varepsilon^2\sqrt N)^{-1}

, respectively. These optimizer-independent lower bounds hold in every spatial dimension. Numerical experiments confirm the predicted

\varepsilon

- and

N

-scalings for nonlinear fluxes in

d=1,2,3

, validate every computed primal-dual certificate, and show that corrector-enriched classes substantially reduce energy and

H^1

errors as the microscopic scale is refined.

Ronald Katende

Department of Mathematics Kabale University Kikungiri Hill, Katuna Road, Kabale, Uganda

Primal-Dual Optimization Neural PDE Solvers Neural Network Approximation Theory Physics-Informed ML Statistical Learning Theory

Jul 15, 2026math.OC

Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation

Column generation (CG) is central to many large-scale optimization algorithms, including branch-price-and-cut methods for vehicle routing problems, but unstable dual solutions can substantially slow its convergence. Existing deep dual-optimal inequalities can reduce this instability by restricting the dual space. Their construction, however, typically relies on problem-specific exchange arguments that are difficult to establish for routing problems with capacity limits, time windows, and other resource constraints. We introduce learned pairwise deep dual-optimal inequalities (L-PDDOIs), a learning framework that predicts pairwise orderings between dual variables and incorporates their primal counterparts directly into the master problem. To construct training labels, the framework samples optimal dual solutions and selects pairwise order relations that hold simultaneously on a sufficiently large common subset of the samples. A classifier then assigns a score to each candidate relation. Because conflicts and redundancies among the predicted relations can impair performance, graph-based postprocessing filters and compresses the candidate set before deployment. We further introduce a recovery procedure that selectively relaxes learned inequalities and provides a certificate when the baseline CG bound has been restored. On the main test sets for the capacitated vehicle routing problem and the vehicle routing problem with time windows, direct deployment of L-PDDOIs reduces the geometric mean root CG time by 89.7% and 93.9%, respectively, while incurring mean bound losses of only 1.3% and 0.5%. The recovery procedure retains corresponding time reductions of 54.8% and 83.1%, respectively, while guaranteeing no loss in the CG bound.

Zhengzhong Ricky You, Bo Tang, Haoran Liu +1

Department of Civil Engineering, Tsinghua University, Beijing 100084, China · MIT Sloan School of Management, Massachusetts Institute of Technology, 100 Main Street, Cambridge, MA 02142, USA · Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA

Primal-Dual Optimization Combinatorial Optimization Vehicle Routing

Jul 9, 2026math.OC

Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity

We study nonasymptotic convergence of primal-dual methods for a class of nonconvex constrained optimization problems with a convex-composite structure. In this class, both the objective and the functional inequality constraints are given by convex Lipschitz outer functions composed with smooth nonlinear inner mappings. The analysis is complicated by constraint violation in a nonconvex functional inequality system and by the lack of an a priori bound on the multipliers. To address these issues, we restrict the dual variable to an auxiliary compact set and analyze a smoothed prox-linear augmented Lagrangian method through a nonsmooth nonconvex-concave minimax reformulation. The main contribution is a finite-time mechanism for converting stationarity of the truncated minimax problem into a KKT certificate for the original constrained problem. We show that, for a sufficiently large penalty parameter, all but a controlled number of iterates enter a near-feasible region. On this region, a local conic regularity condition uniformly bounds the associated prox-linear multipliers and thereby makes the artificial dual truncation inactive at the selected iterates. Building on this mechanism, we establish explicit convergence rates for the proposed method in terms of the KKT residual. With dual regularization, a global dual error bound together with a bias-balancing argument gives an

O(K^{-1/3})

rate. In the unregularized case, under additional local structural assumptions including piecewise linearity of the outer functions, a local dual error bound yields the sharper

O(K^{-1/2})

rate.

Linglingzhi Zhu, Jiajin Li

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · Sauder School of Business, University of British Columbia, Vancouver, BC, Canada.

Primal-Dual Optimization Nonconvex Optimization Augmented Lagrangian Method

Jul 1, 2026cs.LG

Neural Certificate Pricing for Combinatorial Optimization Problems

Combinatorial optimization (CO) problems are difficult because certifiable discrete structure induces exponential search. One needs to search over the set exponentially many candidates to certify optimality, however, the structural feasibility of a path, packing, or cover can be verified in polynomial time once supplied. In this study, we introduce Neural Certificate Pricing (NCP) that exploits this asymmetry under an unsupervised learning framework. A neural network is trained to predict certificate-level dual prices, while a structured recovery layer constructs the induced primal marginal. NCP can be viewed as amortized separation: instead of enumerating violated inequalities, it learns the residual prices through which their aggregate effect enters recovery. When the certificate-consistency condition holds, the recovered marginal is globally feasible, and a local theory shows that first-order errors in the predicted price induce only second-order loss in objective value. Across three classes of CO problems, NCP either outperforms state-of-the-art neural baselines by large margins or matches them at a fraction of the computation time, and shows stronger out-of-distribution generalization.

Jingyi Chen, Xinyuan Zhang, Xinwu Qian

Department of Civil and Environmental Engineering, Rice University, Houston, TX

Primal-Dual Optimization Unsupervised Learning Combinatorial Optimization Neural Combinatorial Optimization

Jun 30, 2026cs.LG

Constrained Online Convex Optimization without Slater's Condition

We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater's condition. For stochastic constraints and convex losses, our algorithm achieves

O(\sqrt{T})

expected regret and

O(\sqrt{T}\log T)

expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to

O(\log T)

with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.

Kihyun Yu, Junehee Lee, Dabeen Lee

1KAIST · 2Seoul National University

Primal-Dual Optimization Online Convex Optimization Constrained Optimization

Jun 30, 2026cs.AI

AI-Assisted Discovery of Convex Relaxations via Dual Agents

Recent work shows that LLM agents can improve sharp-constant inequalities by searching for extremal constructions, which yield upper bounds. We address the complementary side: a lower bound holds for every admissible function and follows from a convex relaxation of the nonconvex problem, with tighter relaxations giving stronger bounds. We instantiate the autoresearch paradigm to discover such relaxations: a coding agent proposes valid tightening constraints, a theory agent verifies each one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point checked in rigorous interval arithmetic. On two optimization constants studied by \citet{tao2025alphaevolve} - the first autocorrelation inequality (

C_{6.2}

) and the Erdős minimum-overlap constant (

C_{6.5}

) - we improve the certified lower bounds from

1.28

to

1.2937

and from

0.379005

to

0.37912

, respectively.

Sungyoon Kim, Mert Pilanci

Department of Electrical Engineering, Stanford University, CA, USA.

Primal-Dual Optimization AI Agents for Scientific Discovery Large Language Model-Guided Optimization

Jun 15, 2026cs.LG

Constrained Diffusion Models with Primal-Dual Inference

This paper develops constrained diffusion models with primal-dual inference (PDI) to sample from optimal distributions of entropy-regularized optimization problems with \emph{average} constraints. We formalize constrained sampling in the Lagrangian dual domain, where the optimal distribution takes the form of a Gibbs distribution indexed by the optimal dual variable. Rather than estimating this dual multiplier before sampling and freezing it throughout generation, PDI jointly infers the optimal primal distribution and its parametrizing dual variable. Each reverse diffusion step denoises using the score field associated with the current multiplier and then updates the multiplier through dual ascent using the estimated constraint violation of the denoised samples. To enable this conditional score field, we train a single dual-conditioned score network over the family of Gibbs distributions induced by the dual variables encountered during inference. We prove that the time average of the dual variables generated along the inference trajectory converges to a neighborhood of the dual optimum and bound the effect of residual dual mismatch on the terminal distribution through schedule-dependent stability factors. We evaluate PDI on constrained sampling from a mixture of Gaussians, wireless resource allocation, and portfolio management.

Samar Hadou, Yigit Berkay Uslu, Alejandro Ribeiro

Department of Electrical and Systems Engineering University of Pennsylvania

Primal-Dual Optimization Constrained Generative Modeling Diffusion Sampling Constrained Optimization Conditional Diffusion Models

Jun 15, 2026cs.RO

Elastic ODYN: Differentiable Optimization for Infeasible Control and Learning in Robotics

Robotic systems routinely encounter conflicting objectives, modeling errors, and degenerate contact conditions that render quadratic programs (QPs) infeasible. Yet most optimization solvers and differentiable QP layers assume feasibility, leading to numerical failures, unstable gradients, or solver breakdown when constraints cannot be simultaneously satisfied. We present Elastic ODYN, a primal-dual non-interior-point QP solver that handles infeasibility through smooth squared-

\ell_2

elastic relaxations. The formulation remains well posed under ill-conditioning and degeneracy, supports warm starting, and converges to closest-to-feasible solutions, with lightweight refinement recovering physically meaningful dual variables. Building on this framework, we develop Elastic ODYNLayer, a differentiable QP layer with stable gradients under infeasibility, and Elastic OdynSQP, an SQP method that resolves inconsistent subproblems and intrinsically infeasible optimal control tasks through selective constraint elasticity. Across benchmark QPs, singular contact mechanics, differentiable parameter identification, and quadrupedal and humanoid trajectory optimization, Elastic ODYN outperforms state-of-the-art elastic QP solvers in robustness, warm-start performance, and convergence reliability, enabling optimization, simulation, control, and learning beyond standard feasibility assumptions.

Aristotelis Papatheodorou, Jose Rojas, Ioannis Havoutis +1

Department of Engineering Science, University of Oxford, Oxford, UK · Robot Motor Intelligence (RoMI) Lab, Heriot-Watt University, Edinburgh, UK

Robotic Control Primal-Dual Optimization Trajectory Optimization Constrained Optimization Quadratic Programming Differentiable Optimization

Jun 9, 2026math.OC

Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry

We study distributed optimization with stochastic gradients and finite-bit communication modeled by random (unbiased) quantization. We propose q-PDGD, a quantized stochastic primal-dual method, and analyze it under relaxed global geometry. Under restricted secant inequality (RSI), a constant step-size yields linear contraction to an explicit neighborhood determined by gradient noise, quantization distortion, and network connectivity, while a diminishing step-size achieves O(1/k) convergence without shared-minimizer assumptions. Under Polyak-Lojasiewicz (PL) inequality, we obtain linear-to-neighborhood convergence in the same stochastic quantized setting. Our results match the best-known centralized stochastic rates in oracle complexity, and are supported by experiments demonstrating the predicted tradeoffs between quantization level, step-size choice, and graph structure.

Susmit Sarkar, Abhinav Raghuvanshi, Kushal Chakrabarti +1

Indian Institute of Technology Bombay, Mumbai, Maharashtra, India · Tata Consultancy Services Research, Thane, Maharashtra, India

Stochastic Optimization Primal-Dual Optimization Optimization Convergence Analysis Distributed Optimization

Jun 8, 2026cs.GT

Duality for Optimal Multi-Item, Multi-Bidder Auction Design: Revenue Certificates through Deep Learning

Characterizing revenue-optimal auctions for multi-item, multi-bidder settings remains a fundamental open problem, with no known closed-form solution existing beyond restrictive binary-type instances. This has motivated interest in computational approaches to optimal auction design. In this paper, we introduce the first computational framework that directly tackles the dual problem for multi-item, multi-bidder auctions and dominant-strategy incentive compatibility (DSIC), generating certified revenue upper bounds. Our approach parametrizes Lagrange multipliers with a structurally guaranteed strict flow-conservation property using neural networks, enabling efficient optimization over feasible dual solutions via gradient descent. To bridge the gap between discrete computational methods and theoretical guarantees for continuous types, we develop a novel lifting technique that maps dual certificates from coarse discretizations to fine refinements. We prove that lifting gives valid revenue upper bounds for multi-item, multi-bidder auctions with continuous uniform valuations. Furthermore, we give a generalized lifting construction for arbitrary continuous distributions and demonstrate that these lifted duals converge to the revenue of the original continuous problem in the discrete limit. We validate this computational framework for the dual auction design problem by recovering known analytical mechanisms for canonical instances. For multi-item multi-bidder problems, our framework establishes a small gap between the optimal revenue and best-known DSIC mechanisms, providing computational certificates of near-optimality.

Yanchen Jiang, David C. Parkes, Tonghan Wang

Harvard University, USA · College of AI, Tsinghua University, China

Primal-Dual Optimization Game Theory Constrained Optimization

Jun 7, 2026math.OC

Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming

Recent research has developed practical, parallelizable first-order methods for large scale linear programming, but performance is highly dependent on hyperparameter selection. We derive generalization guarantees for hyperparameter tuning within (cu)PDLP, a state-of-the-art first-order LP solver designed for modern hardware. First, we pin down the behavior of PDHG, the primal-dual hybrid gradient algorithm that underlies PDLP, as a function of its step size and primal weight, leading to linear sample complexity guarantees for learning those parameters. We then conduct a structural analysis of PDLP, which augments PDHG with several specialized techniques like preconditioning, adaptive step sizes, averaging, adaptive restarts, and smoothed primal weight updates. Our analysis captures the behavior of the solution trajectory as a function of the hyperparameters and leverages recent advances in data-driven algorithm design to obtain polynomial sample complexity guarantees for learning those hyperparameters. Finally, we conduct proof-of-concept experiments that demonstrate the need for data-driven PDLP parameter tuning. Our results showcase the versatility of the data-driven algorithm design toolkit for principled hyperparameter tuning within solver-grade implementations of complex modern optimization algorithms.

Siddharth Prasad, Dravyansh Sharma

Toyota Technological Institute at Chicago

Primal-Dual Optimization Constrained Optimization Linear Programming Hyperparameter Optimization

Jun 5, 2026cs.LG

Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making

Stochastic constrained decision-making requires optimizing performance objectives while enforcing statistical requirements such as safety or fairness. However, standard primal--dual methods struggle to update multipliers robustly under stochastic mini-batch feedback, as the noise of mini-batch gradients and constraint estimates can be directly accumulated into the multiplier memory. To address this issue, we propose Residual-Controlled Multiplier Learning (RCML), which reformulates multiplier updating as projected-pressure feedback. The central idea is to decompose the projected multiplier into an effective pressure signal for primal descent and a pressure-memory residual for finite-gain multiplier tracking. To handle heterogeneous and noisy observations, we further augment this residual-integral backbone with modular stochastic stabilization components. For the convex-affine backbone, we establish finite-gain convergence, derive a stochastic residual bound under mini-batch feedback, and show that the residual feedback law admits a local KKT-residual interpretation near regular KKT points of nonconvex problems. Experiments across optimization, allocation, and fair-ranking tasks show that RCML improves feasibility control and multiplier stability while maintaining competitive objective performance. Code is released at https://anonymous.4open.science/r/RCML-3114/.

Kang Liu, Jianchen Hu, Ziyu Qu +3

School of Future Technology Xi’an Jiaotong University Xi’an, China, 710049 · School of Automation Science and Engineering Xi’an Jiaotong University Xi’an, China, 710049 · School of Mathematics and Physics China University of Geosciences Wuhan, China, 430074 +2

Stochastic Optimization Primal-Dual Optimization Constrained Optimization

May 29, 2026cs.LG

Unlearning in Diffusion Models: A Unified Framework with KL Divergence and Likelihood Constraints

Unlearning in diffusion models aims to remove undesirable data or concepts while preserving the utility of pretrained models -- two fundamentally conflicting objectives. We propose a principled constrained optimization framework that formulates unlearning as minimizing the deviation from a pretrained model, subject to explicit separation constraints from the unlearning distributions. Specifically, we formulate three constrained optimization problems based on reverse and forward KL divergences, and likelihood constraints. The first two generalize existing approaches for concept and data unlearning, while the third offers a novel and natural formulation for unlearning. Despite the nonconvexity of the KL constraints, we establish strong duality for all three problems, enabling us to explicitly characterize their optimal solutions as unlearning targets and develop primal-dual algorithms for each formulation. Experimental results demonstrate that our KL-constrained approach achieves superior retention-unlearning tradeoffs compared to weight-based baselines for concept and data unlearning, and that our likelihood-based approach matches unlearning effectiveness while better preserving retained concepts compared to baselines.

Shervin Khalafi, Alejandro Ribeiro, Dongsheng Ding

University of Pennsylvania · University of Tennessee, Knoxville

Primal-Dual Optimization Diffusion Model Unlearning Constrained Optimization Machine Unlearning Diffusion Models

May 15, 2026cs.LG

Avoiding Structural Failure Modes in Tabular Fair SSL: Online Primal-Dual Allocation under Confidence Gating

Semi-supervised learning (SSL) enables prediction with limited labels, but high-stakes tabular applications (medical, credit, recidivism) require statistical fairness guarantees. We identify a structural conflict in tabular fair SSL through a diagnostic stress test: under confidence-gated pseudo-labeling, moment-matching fairness regularizers can trigger two failure modes -- Masking Collapse (fairness erodes confidence, starving pseudo-labels) and Trivial Saturation (drift to constant predictors). We propose Online Primal-Dual Allocation (OPDA), an online controller that schedules fairness and entropy-based stability penalties using violation, risk, and pseudo-label health signals, avoiding per-dataset selection of a fixed fairness weight within this diagnostic regime. On the evaluated tabular benchmarks (Adult, ACSIncome, COMPAS), OPDA mitigates the degenerate regimes observed under static weighting and simple single-signal adaptive baselines. On Adult and COMPAS, it yields non-degenerate operating points competitive with the empirical static-

λ

frontier; on ACSIncome, it preserves utility with a wider fairness-utility spread. Relative to OPDA-lite, the full controller mainly shifts the operating point toward higher utility on ACSIncome, while Adult highlights the fairness-utility trade-off between the two variants. These results position OPDA as a calibration-free controller for non-degenerate operating points in tabular fair SSL without per-dataset tuning.

Hangchuan Liang, Changchun Li

College of Computer Science and Technology, Jilin University, China · Key Laboratory of Symbolic Computation and Knowledge Engineering of the Ministry of Education, Jilin University, China

Primal-Dual Optimization Group Fairness Adaptive Loss Weighting Semi-Supervised Learning Tabular Prediction

May 12, 2026cs.LG

Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses

Existing work on linear constrained Markov decision processes (CMDPs) has primarily focused on stochastic settings, where the losses and costs are either fixed or drawn from fixed distributions. However, such formulations are inherently vulnerable to adversarially changing environments. To overcome this limitation, we propose a primal-dual policy optimization algorithm for online finite-horizon {adversarial} linear CMDPs, where the losses are adversarially chosen under full-information feedback and the costs are stochastic under bandit feedback. Our algorithm is the \emph{first} to achieve sublinear regret and constraint violation bounds in this setting, both bounded by

\widetilde{\mathcal{O}}(K^{3/4})

, where

K

denotes the number of episodes. The algorithm introduces and runs with a new class of policies, which we call weighted LogSumExp softmax policies, designed to adapt to adversarially chosen loss functions. Our main result stems from the following key contributions: (i) a new covering number argument for the weighted LogSumExp softmax policies, and (ii) two novel algorithmic components -- periodic policy mixing and a regularized dual update -- which allow us to effectively control both the covering number and the dual variable. We also report numerical results that validate our theoretical findings on the performance of the algorithm.

Kihyun Yu, Seoungbin Bae, Dabeen Lee

Department of Industrial and Systems Engineering KAIST · Department of Mathematical Sciences Seoul National University · Research Institute of Mathematics, Seoul National University; Interdisciplinary Program in Artificial Intelligence, Seoul National University; Korea Institute for Advanced Study

Primal-Dual Optimization Markov Decision Processes Policy Optimization Constrained RL Constrained Optimization

May 10, 2026cs.AI

Primal-Dual Guided Decoding for Constrained Discrete Diffusion

Discrete diffusion models generate structured sequences by progressively unmasking tokens, but enforcing global property constraints during generation remains an open challenge. We propose primal-dual guided decoding, an inference-time method that formulates constrained generation as a KL-regularised optimisation problem and solves it online via adaptive Lagrangian multipliers. At each denoising step, the method modifies token logits through an additive, constraint-dependent bias, with multipliers updated by mirror descent based on constraint violation. The bias arises as the optimal KL-regularised projection of the constraint, so the constrained distribution remains as close as possible to the model's unconstrained distribution while still satisfying the constraint. The method requires no retraining and no additional model evaluations beyond standard sampling, supports multiple simultaneous constraints, and provides formal bounds on constraint violation. We evaluate our approach on topical text generation, molecular design, and music playlist generation, showing that a single algorithm instantiated via domain-specific scoring functions improves constraint satisfaction while preserving relevant domain-specific quality metrics.

Federico Tomasi, Dmitrii Moor, Alice Wang +1

Spotify

Primal-Dual Optimization Constrained Generative Modeling Constrained Decoding Diffusion Guidance Constrained Optimization Diffusion Models

May 10, 2026cs.LG

Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions

The transition to First-Price Auctions (FPA) in digital advertising has spurred significant research, yet existing work typically assumes access to a valuation oracle, ignoring the reality that values must be inferred from censored data. While Linear Treatment Effect (LTE) models address this by learning value uplift, they have not been adapted to realistic settings with hard Budget constraints or Return-on-Spend (RoS) targets requiring regret and violation control. In this work, we propose a unified primal-dual framework for constrained FPAs that jointly learns the latent LTE valuation parameters and the competitor's bid distribution. This simultaneous learning introduces a critical technical challenge: the estimation error is dynamically scaled by the Lagrangian multiplier, potentially leading to unbounded regret. We resolve this by leveraging a strong Slater condition and a novel adaptive burn-in procedure to stabilize the dual variables. Our approach achieves near-optimal regret guarantees, providing the first theoretically grounded solution for constrained bidding with latent valuations.

Zihao Hu, Yuxiao Wen, Yuan Yao +2

Department of Mathematics, The Hong Kong University of Science and Technology · Department of IEDA, The Hong Kong University of Science and Technology · Stern School of Business, New York University

Primal-Dual Optimization Constrained Optimization

May 9, 2026cs.RO

SHIELD: Scalable Optimal Control with Certification using Duality and Convexity

We present SHIELD, a hierarchical algorithm that reduces both the decision-variable dimension and the constraint set in

\ell_1

-regularized convex programs. From strong convexity and Lagrangian duality, we derive certificates that \emph{safely} discard constraints and decision variables while guaranteeing that all removed constraints remain satisfied and all removed variables are null. To further accelerate the proposed algorithm, we propose a transformer-based deep neural network to guide the dual certificate inference. We validate SHIELD on stochastic model predictive control (SMPC) in complex, multi-modal traffic scenarios, comparing against a full-dimensional SMPC policy. Numerical simulations demonstrate order-of-magnitude computational speedups while preserving feasibility and closed-loop safety, highlighting the practicality of certifiably safe, lightweight MPC in complex driving scenes.

Hansung Kim, Siddharth H. Nair, Francesco Borrelli

Model Predictive Control Laboratory, UC Berkeley · Nextracker Inc.

Primal-Dual Optimization Model Predictive Control Optimal Control

May 7, 2026cs.LG

Matrix-Valued Optimism is Matrix-Valued Augmentation: Additive Hybrid Designs for Constrained Optimization

Augmented Lagrangian and optimistic primal--dual methods stabilize equality-constrained optimization through seemingly different mechanisms: the former adds constraint-dependent primal curvature, while the latter adds dual memory. Recent work has shown that these mechanisms are equivalent for scalar parameters. We extend this equivalence to matrix-valued correction. We prove an additivity principle: for symmetric matrix parameters, the ideal primal trajectory depends only on the summed correction matrix, not on how it is split between augmented and optimistic channels. This exposes a design freedom: algebraically equivalent decompositions can have different finite-step feasibility because augmented correction affects primal curvature, whereas optimistic correction affects the scale of the dual memory correction. We formulate the resulting step-size-limited design problem and derive a closed-form hybrid rule that selects a matrix correction, splits it between the two channels, and chooses primal and dual steps using local spectral weights. Experiments on nonlinear equality-constrained problems with controlled constraint-Jacobian conditioning show that the hybrid design improves over pure augmented and pure optimistic endpoints, closely tracks a grid-search hybrid oracle, and is competitive with first-order primal--dual baselines under mild-to-moderate ill-conditioning. The experiments also identify the expected limitation: exact cancellation requires increasingly large matrix corrections as the constraint Jacobian becomes ill-conditioned.

Jiayi Zhao

University of Washington Seattle, WA, USA

Primal-Dual Optimization Augmented Lagrangian Method Constrained Optimization