We study a class of misspecified saddle point (SP) problems, where the optimization objective depends on an unknown parameter that must be learned concurrently from data. Unlike existing studies that assume parameters are fully known or pre-estimated, our framework integrates optimization and learning into a unified formulation, enabling a more flexible problem class. To address this setting, we propose two algorithms based on the accelerated primal-dual (APD) by Hamedani & Aybat 2021. In particular, we first analyze the naive extension of the APD method by directly substituting the evolving parameter estimates into the primal-dual updates; then, we design a new learning-aware variant of the APD method that explicitly accounts for parameter dynamics by adjusting the momentum updates. Both methods achieve a provable convergence rate of O(logK/K), while the learning-aware approach attains a tighter O(1) constant and further benefits from an adaptive step-size selection enabled by a backtracking strategy. Furthermore, we extend the framework to problems where the learning problem admits multiple optimal solutions, showing that our modified algorithm for a structured setting achieves an O(1/K) rate. To demonstrate practical impact, we evaluate our methods on a misspecified portfolio optimization problem and show superior empirical performance compared to state-of-the-art algorithms.
O(logK/K) ; conv. bound scales with domain diameters
Table 1: Comparison with related work on misspecified problems in terms of the primary problem (the optimization problem) and the secondary problem (the learning problem); the misspecified setting , i.e. which component carries the unknown parameter; the learning solution (Learn. Sol.), which is unique (U) or multiple (M); whether a backtracking line search (LS) is available; and the resulting convergence rate in the number of iterations K . Abbreviations: min., minimization; str., strongly; mon., monotone; s-mon., strongly monotone; VI, variational inequality; SVI, stochastic VI; SP, saddle point.
Figure 1: Comparison of our proposed Naive (blue) and Learning-aware (red) with IPALM (yellow) and VI (purple) across three datasets and three metrics over iteration k . From top to bottom: NASDAQ-100, Dow Jones, and Synthetic datasets. From left to right, the figures correspond to suboptimality, infeasibility, and learning solution metrics.
Figure 2: Separate effects of the parameter-aware momentum and the backtracking line search on the Dow Jones dataset, in terms of suboptimality (left) and infeasibility (right): Naive and Learning-aware approaches with fixed step-sizes, and the full Learning-aware approach with backtracking.
Figure 3: Sensitivity to the step-size on the Dow Jones dataset, in terms of suboptimality (left) and infeasibility (right). The primal–dual step-sizes are scaled by a common factor ν∈{100,10−1,10−2} for the Naive and fixed-step Learning-aware approaches; solid and dashed curves of the same color correspond to the two approaches at the same ν .
Primal-dual optimization jointly updates decision variables and constraint multipliers to solve constrained problems with feasibility and optimality guarantees.
The Alternating Direction Method of Multipliers (ADMM) is a widely used method for structured convex optimization, and its practical performance depends strongly on the choice of penalty and relaxation parameters. Motivated by settings such as Model Predictive Control (MPC), where one repeatedly solves related optimization problems with fixed structure and changing parameter values, we propose learning online updates of the relaxation parameter to improve average performance on problem classes of interest, while guaranteeing that asymptotic convergence is not compromised for the worst-case realization of such problems. This choice is computationally attractive in the Operator Splitting Quadratic Program (OSQP)-like architectures, since adapting relaxation does not trigger the matrix refactorizations associated with penalty updates. We establish convergence guarantees for ADMM with time-varying penalty and relaxation parameters under mild assumptions, and show on benchmark quadratic programs that the resulting learned policies improve both iteration count and wall-clock time on average over baseline OSQP.
Junan Lin, Paul J. Goulart, Luca Furieri
Department of Engineering Science, University of Oxford, OX1 3PJ Oxford, UK
In this paper, we study last-iterate convergence of learning algorithms in bilinear saddle-point problems, a preferable notion of convergence that captures the day-to-day behavior of learning dynamics. We focus on the challenging setting where players select actions from compact convex sets and receive only bandit feedback. Our main contribution is the design of an uncoupled learning algorithm that guarantees last-iterate convergence to the Nash equilibrium with high probability. We establish a convergence rate of O~(T−1/4) up to polynomial factors in problem parameters. Crucially, our proposed algorithm is computationally efficient, requiring only an efficient linear optimization oracle over the players' compact action sets. The algorithm is obtained by combining techniques from experimental design and the classic Follow-The-Regularized-Leader (FTRL) framework, with a carefully chosen regularizer function tailored to the geometry of the action set of each learner.
Arnab Maiti, Claire Jie Zhang, Kevin Jamieson +3
University of Washington · Amazon · University of California, Irvine
Solving massive-scale optimization problems requires scalable first-order methods with low per-iteration cost. This tutorial highlights a shift in optimization: using differentiable programming not only to execute algorithms but to learn how to design them. Modern frameworks such as PyTorch, TensorFlow, and JAX enable this paradigm through efficient automatic differentiation. Embedding first-order methods within these systems allows end-to-end training that improves convergence and solution quality. Guided by Fenchel-Rockafellar duality, the tutorial demonstrates how duality-informed iterative schemes such as the alternating direction method of multipliers, and the primal-dual hybrid gradient can be learned and adapted through representative case studies.