# RECAPP: Crafting a More Efficient Catalyst for Convex Optimization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 51 references that are in the map.
- First posted on arXiv 17 Jun 2022.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [Complexity of Highly Parallel Non-Smooth Convex Optimization](https://mlsanity.com/paper/1906.10655/) (2019)
- [Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization](https://mlsanity.com/paper/1506.07512/) (2015)
- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization](https://mlsanity.com/paper/1309.2375/) (2013)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [Faster Eigenvector Computation via Shift-and-Invert Preconditioning](https://mlsanity.com/paper/1605.08754/) (2016)
- [A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization](https://mlsanity.com/paper/2003.04375/) (2020)
- [Adaptive Catalyst for Smooth Convex Optimization](https://mlsanity.com/paper/1911.11271/) (2019)
- [Unified Acceleration of High-Order Algorithms under H"older Continuity and Uniform Convexity](https://mlsanity.com/paper/1906.00582/) (2019)
- [Catalyst Acceleration for Gradient-Based Non-Convex Optimization](https://mlsanity.com/paper/1703.10993/) (2017)

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

- [Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2302.06763/) (2023)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Stabilized Proximal-Point Methods for Federated Optimization](https://mlsanity.com/paper/2407.07084/) (2024)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Smooth Quasar-Convex Optimization with Constraints](https://mlsanity.com/paper/2510.01943/) (2025)
- [An Optimal Algorithm for Strongly Convex Min-min Optimization](https://mlsanity.com/paper/2212.14439/) (2022)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)

## Abstract (arXiv)

The accelerated proximal point algorithm (APPA), also known as "Catalyst", is a well-established reduction from convex optimization to approximate proximal point computation (i.e., regularized minimization). This reduction is conceptually elegant and yields strong convergence rate guarantees. However, these rates feature an extraneous logarithmic term arising from the need to compute each proximal point to high accuracy. In this work, we propose a novel Relaxed Error Criterion for Accelerated Proximal Point (RECAPP) that eliminates the need for high accuracy subproblem solutions. We apply RECAPP to two canonical problems: finite-sum and max-structured minimization. For finite-sum problems, we match the best known complexity, previously obtained by carefully-designed problem-specific algorithms. For minimizing maxy f(x,y) where f is convex in x and strongly-concave in y, we improve on the best known (Catalyst-based) bound by a logarithmic factor.