# Online Optimization of Difference-of-Convex Compositions with Smooth Mappings

arXiv: https://arxiv.org/abs/2607.19553 · HTML: https://mlsanity.com/paper/2607.19553/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 45 references that are in the map.
- First posted on arXiv 21 Jul 2026.

## Builds on (most cited first, 11 of 11)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Non-Convex Learning: Following the Perturbed Leader is Optimal](https://mlsanity.com/paper/1903.08110/) (2019)
- [Efficient Regret Minimization in Non-Convex Games](https://mlsanity.com/paper/1708.00075/) (2017)
- [Dynamic Local Regret for Non-convex Online Forecasting](https://mlsanity.com/paper/1910.07927/) (2019)
- [Computing B-Stationary Points of Nonsmooth DC Programs](https://mlsanity.com/paper/1511.01796/) (2015)
- [Regret minimization in stochastic non-convex learning via a proximal-gradient approach](https://mlsanity.com/paper/2010.06250/) (2020)
- [DC approximation approaches for sparse optimization](https://mlsanity.com/paper/1407.0286/) (2014)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [A Local Regret in Nonconvex Online Learning](https://mlsanity.com/paper/1811.05095/) (2018)
- [Penalty and Augmented Lagrangian Methods for Constrained DC Programming](https://mlsanity.com/paper/2111.09263/) (2021)
- [Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity](https://mlsanity.com/paper/2607.08954/) (2026)

## Abstract (arXiv)

We study online optimization for a broad class of structured non-convex non-smooth problems where each loss is a composition of a difference-of-convex function with a smooth mapping, and the feasible region is defined by constraint functions of the same kind. We propose a time-smoothed proximal linear algorithm and a local-regret measure based on a proximal residual mapping. We show that this residual is a proper stationarity measure for the original problem: its fixed-point condition implies first-order stationarity. Our analysis relies on a tangent-cone characterization for a feasible region described by composite difference-of-convex constraints, which is of independent interest and allows each update to be computed via a convex optimization oracle, despite the non-convexity of the problem. We establish a local-regret bound and a bound on the total number of inner convex subproblems. We also derive an error bound connecting the proximal residual to the distance to stationarity, providing a quantitative certificate of approximate stationarity.