# Optimistic Optimisation of Composite Objective with Exponentiated Update

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 45 references that are in the map.
- First posted on arXiv 8 Aug 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives](https://mlsanity.com/paper/1802.07623/) (2018)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examples](https://mlsanity.com/paper/1709.04114/) (2017)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization](https://mlsanity.com/paper/1910.06513/) (2019)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [A new regret analysis for Adam-type algorithms](https://mlsanity.com/paper/2003.09729/) (2020)
- [Online Learning for Time Series Prediction](https://mlsanity.com/paper/1302.6927/) (2013)
- [Exponentiated Gradient Meets Gradient Descent](https://mlsanity.com/paper/1902.01903/) (2019)
- [A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds](https://mlsanity.com/paper/1709.02726/) (2017)
- [A Generalized Online Mirror Descent with Applications to Classification and Regression](https://mlsanity.com/paper/1304.2994/) (2013)
- [Adaptive scale-invariant online algorithms for learning linear models](https://mlsanity.com/paper/1902.07528/) (2019)
- [Online Convex Optimization with Unconstrained Domains and Losses](https://mlsanity.com/paper/1703.02622/) (2017)
- [Smoothed Low Rank and Sparse Matrix Recovery by Iteratively Reweighted Least Squares Minimization](https://mlsanity.com/paper/1401.7413/) (2014)
- [NonSTOP: A NonSTationary Online Prediction Method for Time Series](https://mlsanity.com/paper/1611.02365/) (2016)

## Built on by (most cited first, 3 of 3)

- [Adaptive Stochastic Optimisation of Nonconvex Composite Objectives](https://mlsanity.com/paper/2211.11710/) (2022)
- [Joining Forces for Pathology Diagnostics with AI Assistance: The EMPAIA Initiative](https://mlsanity.com/paper/2401.09450/) (2023)
- [Structured Universal Adversarial Attacks on Object Detection for Video Sequences](https://mlsanity.com/paper/2510.14460/) (2025)

## Abstract (arXiv)

This paper proposes a new family of algorithms for the online optimisation of composite objectives. The algorithms can be interpreted as the combination of the exponentiated gradient and p-norm algorithm. Combined with algorithmic ideas of adaptivity and optimism, the proposed algorithms achieve a sequence-dependent regret upper bound, matching the best-known bounds for sparse target decision variables. Furthermore, the algorithms have efficient implementations for popular composite objectives and constraints and can be converted to stochastic optimisation algorithms with the optimal accelerated rate for smooth objectives.