arXiv Machine Learning

Simultaneous Learning and Optimization via Misspecified Saddle Point Problems

The paper introduces a framework for misspecified saddle point problems where the objective depends on an unknown parameter that must be learned simultaneously from data. Two accelerated primal-dual algorithms are proposed: a naive extension that substitutes evolving parameter estimates, and a learning‑aware variant that adjusts momentum updates to account for parameter dynamics. Both achieve an ≥O(log K/K) convergence rate, with the learning‑aware method offering a tighter constant and adaptive step‑size, and an extended version handles multiple optimal solutions with an O(1/√K) rate, demonstrated on a portfolio optimization task.

arXiv Machine Learning
Sep 29

To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity

arXiv:2609. 30501v1 Announce Type: new Abstract: Although bilevel optimization (BLO) has emerged as a powerful framework for addressing many complex and nested machine learning problems in recent years, most existing studies are confined to the lower-level strongly convex (LLSC) or lower-level generally convex (LLGC) settings (i.

By Zhiyao Zhang, Menglu Yu, Alvaro Velasquez, Nathaniel D. Bastian, Jia Liu
arXiv Machine Learning
Sep 21

Decision-Focused Learning for Mean-Variance Portfolio Optimization via KKT-Based Reformulation

The paper introduces a decision‑focused learning framework for mean‑variance portfolio optimization that embeds the Karush‑Kuhn‑Tucker optimality conditions of the lower‑level optimization into a single‑level learning problem. This approach preserves budget and short‑sale constraints while remaining tractable for standard nonlinear solvers. Experiments on real‑world ETF data across two asset universes demonstrate superior performance on multiple investment metrics and highlight the benefits of the proposed regularization.

By Kensei Nosaka, Shunnosuke Ikeda, Yuichi Takano
arXiv Machine Learning
Aug 12

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

arXiv:2602. 21436v2 Announce Type: replace-cross Abstract: 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.

By Arnab Maiti, Claire Jie Zhang, Kevin Jamieson, Jamie Heather Morgenstern, Ioannis Panageas, Lillian J. Ratliff
arXiv Machine Learning
Oct 12

RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization

The paper introduces RanSOM, a second‑order momentum algorithm that eliminates the need for a Lipschitz Hessian or auxiliary forward/backward passes by randomizing the step length. By sampling the step from an exponential distribution and using a Stein‑type identity, the method obtains an unbiased estimate of the gradient change with a single Hessian‑vector product that also serves the next gradient computation. RanSOM-E achieves optimal oracle‑complexity exponents for heavy‑tailed noise without clipping, while RanSOM-B preserves feasibility for Frank‑Wolfe iterates, and experiments on CIFAR‑10 show comparable accuracy to existing methods with lower update time.

By El Mahdi Chayti, Mohamad Fakhouri