# Learning-to-learn non-convex piecewise-Lipschitz functions

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 60 references that are in the map.
- First posted on arXiv 19 Aug 2021.

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

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Images](https://mlsanity.com/paper/1412.1897/) (2014)
- [How To Backdoor Federated Learning](https://mlsanity.com/paper/1807.00459/) (2018)
- [Rapid Learning or Feature Reuse? Towards Understanding the Effectiveness of MAML](https://mlsanity.com/paper/1909.09157/) (2019)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [Data Poisoning Attacks Against Federated Learning Systems](https://mlsanity.com/paper/2007.08432/) (2020)
- [One-Shot Imitation Learning](https://mlsanity.com/paper/1703.07326/) (2017)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [The Benefit of Multitask Representation Learning](https://mlsanity.com/paper/1505.06279/) (2015)
- [Adaptive Gradient-Based Meta-Learning Methods](https://mlsanity.com/paper/1906.02717/) (2019)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms](https://mlsanity.com/paper/1908.10400/) (2019)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Provable Guarantees for Gradient-Based Meta-Learning](https://mlsanity.com/paper/1902.10644/) (2019)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Federated Hyperparameter Tuning: Challenges, Baselines, and Connections to Weight-Sharing](https://mlsanity.com/paper/2106.04502/) (2021)
- [Learning-to-Learn Stochastic Gradient Descent with Biased Regularization](https://mlsanity.com/paper/1903.10399/) (2019)
- [Differentially Private Meta-Learning](https://mlsanity.com/paper/1909.05830/) (2019)
- [Robust Meta-learning for Mixed Linear Regression with Small Batches](https://mlsanity.com/paper/2006.09702/) (2020)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [Efficient Representations for Life-Long Learning and Autoencoding](https://mlsanity.com/paper/1411.1490/) (2014)
- [Regret Bounds for Lifelong Learning](https://mlsanity.com/paper/1610.08628/) (2016)
- [Data-Driven Clustering via Parameterized Lloyd's Families](https://mlsanity.com/paper/1809.06987/) (2018)
- [A Sample Complexity Separation between Non-Convex and Convex Meta-Learning](https://mlsanity.com/paper/2002.11172/) (2020)
- [Meta-Learning with Neural Tangent Kernels](https://mlsanity.com/paper/2102.03909/) (2021)
- [Semi-bandit Optimization in the Dispersed Setting](https://mlsanity.com/paper/1904.09014/) (2019)
- [Learning to Link](https://mlsanity.com/paper/1907.00533/) (2019)

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

- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Provably tuning the ElasticNet across instances](https://mlsanity.com/paper/2207.10199/) (2022)
- [A CMDP-within-online framework for Meta-Safe Reinforcement Learning](https://mlsanity.com/paper/2405.16601/) (2024)
- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Meta-Learning Adversarial Bandit Algorithms](https://mlsanity.com/paper/2307.02295/) (2023)
- [Meta-Learning Adversarial Bandits](https://mlsanity.com/paper/2205.14128/) (2022)
- [Learning-Augmented Private Algorithms for Multiple Quantile Release](https://mlsanity.com/paper/2210.11222/) (2022)
- [New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs](https://mlsanity.com/paper/2302.11700/) (2023)
- [Competitive strategies to use "warm start" algorithms with predictions](https://mlsanity.com/paper/2405.03661/) (2024)
- [Learning accurate and interpretable tree-based models](https://mlsanity.com/paper/2405.15911/) (2024)
- [How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension](https://mlsanity.com/paper/2506.16704/) (2025)
- [Learning in Structured Stackelberg Games](https://mlsanity.com/paper/2504.09006/) (2025)
- [Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning](https://mlsanity.com/paper/2506.05252/) (2025)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025)

## Abstract (arXiv)

We analyze the meta-learning of the initialization and step-size of learning algorithms for piecewise-Lipschitz functions, a non-convex setting with applications to both machine learning and algorithms. Starting from recent regret bounds for the exponential forecaster on losses with dispersed discontinuities, we generalize them to be initialization-dependent and then use this result to propose a practical meta-learning procedure that learns both the initialization and the step-size of the algorithm from multiple online learning tasks. Asymptotically, we guarantee that the average regret across tasks scales with a natural notion of task-similarity that measures the amount of overlap between near-optimal regions of different tasks. Finally, we instantiate the method and its guarantee in two important settings: robust meta-learning and multi-task data-driven algorithm design.