# Optimization with Access to Auxiliary Information

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 48 references that are in the map.
- First posted on arXiv 1 Jun 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [How transferable are features in deep neural networks?](https://mlsanity.com/paper/1411.1792/) (2014)
- [A Comprehensive Survey on Transfer Learning](https://mlsanity.com/paper/1911.02685/) (2019)
- [An Overview of Multi-Task Learning in Deep Neural Networks](https://mlsanity.com/paper/1706.05098/) (2017)
- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Universally Slimmable Networks and Improved Training Techniques](https://mlsanity.com/paper/1903.05134/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [SCAFFOLD: Stochastic Controlled Averaging for Federated Learning](https://mlsanity.com/paper/1910.06378/) (2019)
- [Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning](https://mlsanity.com/paper/2008.03606/) (2020)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Descending through a Crowded Valley - Benchmarking Deep Learning Optimizers](https://mlsanity.com/paper/2007.01547/) (2020)
- [On the Convergence of SGD with Biased Gradients](https://mlsanity.com/paper/2008.00051/) (2020)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks](https://mlsanity.com/paper/2106.12379/) (2021)
- [Auxiliary Learning by Implicit Differentiation](https://mlsanity.com/paper/2007.02693/) (2020)
- [meProp: Sparsified Back Propagation for Accelerated Deep Learning with Reduced Overfitting](https://mlsanity.com/paper/1706.06197/) (2017)
- [Auxiliary Task Reweighting for Minimum-data Learning](https://mlsanity.com/paper/2010.08244/) (2020)
- [Masked Training of Neural Networks with Partial Gradients](https://mlsanity.com/paper/2106.08895/) (2021)
- [Linear Speedup in Personalized Collaborative Learning](https://mlsanity.com/paper/2111.05968/) (2021)

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

- [TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels](https://mlsanity.com/paper/2207.06343/) (2022)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy](https://mlsanity.com/paper/2302.03542/) (2023)
- [Stabilized Proximal-Point Methods for Federated Optimization](https://mlsanity.com/paper/2407.07084/) (2024)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Balance is Essence: Accelerating Sparse Training via Adaptive Gradient Correction](https://mlsanity.com/paper/2301.03573/) (2023)
- [SPAM: Stochastic Proximal Point Method with Momentum Variance Reduction for Non-convex Cross-Device Federated Learning](https://mlsanity.com/paper/2405.20127/) (2024)
- [Stochastic Difference-of-Convex Optimization with Momentum](https://mlsanity.com/paper/2510.17503/) (2025)
- [Stochastic Optimization with Random Search](https://mlsanity.com/paper/2510.15610/) (2025)
- [Non-Convex Federated Optimization under Cost-Aware Client Selection](https://mlsanity.com/paper/2512.05327/) (2025)
- [Second-Order Optimization with Asynchronous Curvature](https://mlsanity.com/paper/2510.15714/) (2025)
- [Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking](https://mlsanity.com/paper/2610.13871/) (2026)

## Abstract (arXiv)

We investigate the fundamental optimization question of minimizing a target function f, whose gradients are expensive to compute or have limited availability, given access to some auxiliary side function h whose gradients are cheap or more available. This formulation captures many settings of practical relevance, such as i) re-using batches in SGD, ii) transfer learning, iii) federated learning, iv) training with compressed models/dropout, Et cetera. We propose two generic new algorithms that apply in all these settings; we also prove that we can benefit from this framework under the Hessian similarity assumption between the target and side information. A benefit is obtained when this similarity measure is small; we also show a potential benefit from stochasticity when the auxiliary noise is correlated with that of the target function.