cs.LGOct 6, 2025

Simultaneous Learning and Optimization via Misspecified Saddle Point Problems

Authors: Mohammad Mahdi Ahmadi, Erfan Yazdandoost Hamedani

Organizations: Department of Systems and Industrial Engineering, The University of Arizona, Tucson, AZ, USA.

Abstract

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(log⁡K/K)\mathcal{O}(\log K / K), while the learning-aware approach attains a tighter O(1)\mathcal{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)\mathcal{O}(1/\sqrt{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.

Figures & tables

Explore similar work

Apr 29, 2026

Learning Over-Relaxation Policies for ADMM with Convergence 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.
Feb 24, 2026

Efficient Uncoupled Learning Dynamics with O~ ⁣(T−1/4)\tilde{O}\!\left(T^{-1/4}\right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback

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)\tilde{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.
Jan 23, 2026

Learning to Optimize by Differentiable Programming

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.