# Complementary Composite Minimization, Small Gradients in General Norms, and Applications arXiv: https://arxiv.org/abs/2101.11041 · HTML: https://mlsanity.com/paper/2101.11041/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Builds on 24 of its 75 references that are in the map. - First posted on arXiv 26 Jan 2021. ## Builds on (most cited first, 24 of 24) - [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013) - [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017) - [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016) - [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018) - [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016) - [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016) - [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018) - [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016) - [On the Efficiency of Entropic Regularized Algorithms for Optimal Transport](https://mlsanity.com/paper/1906.01437/) (2019) - [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017) - [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013) - [An explicit analysis of the entropic penalty in linear programming](https://mlsanity.com/paper/1806.01879/) (2018) - [On Acceleration with Noise-Corrupted Gradients](https://mlsanity.com/paper/1805.12591/) (2018) - [Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration](https://mlsanity.com/paper/2011.06572/) (2020) - [Lower Bounds for Parallel and Randomized Convex Optimization](https://mlsanity.com/paper/1811.01903/) (2018) - [Optimal Complexity and Certification of Bregman First-Order Methods](https://mlsanity.com/paper/1911.08510/) (2019) - [Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions](https://mlsanity.com/paper/1803.06600/) (2018) - [Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression](https://mlsanity.com/paper/1907.07167/) (2019) - [Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method](https://mlsanity.com/paper/1706.04680/) (2017) - [Mirror Prox Algorithm for Multi-Term Composite Minimization and Semi-Separable Problems](https://mlsanity.com/paper/1311.1098/) (2013) - [Iterative Refinement for ℓp-norm Regression](https://mlsanity.com/paper/1901.06764/) (2019) - [Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria](https://mlsanity.com/paper/1610.03446/) (2016) - [An homotopy method for ℓp regression provably beyond self-concordance and in input-sparsity time](https://mlsanity.com/paper/1711.01328/) (2017) - [Faster p-norm minimizing flows, via smoothed q-norm problems](https://mlsanity.com/paper/1910.10571/) (2019) ## Built on by (most cited first, 9 of 9) - [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022) - [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022) - [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021) - [Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization](https://mlsanity.com/paper/2205.12751/) (2022) - [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023) - [Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp-Smooth Nonconvex Optimization](https://mlsanity.com/paper/2506.06606/) (2025) - [Optimal Algorithms for Stochastic Complementary Composite Minimization](https://mlsanity.com/paper/2211.01758/) (2022) - [Faster Acceleration for Steepest Descent](https://mlsanity.com/paper/2409.19200/) (2024) - [Oblivious Stochastic Composite Optimization](https://mlsanity.com/paper/2306.17470/) (2023) ## Abstract (arXiv) Composite minimization is a powerful framework in large-scale convex optimization, based on decoupling of the objective function into terms with structurally different properties and allowing for more flexible algorithmic design. We introduce a new algorithmic framework for complementary composite minimization, where the objective function decouples into a (weakly) smooth and a uniformly convex term. This particular form of decoupling is pervasive in statistics and machine learning, due to its link to regularization. The main contributions of our work are summarized as follows. First, we introduce the problem of complementary composite minimization in general normed spaces; second, we provide a unified accelerated algorithmic framework to address broad classes of complementary composite minimization problems; and third, we prove that the algorithms resulting from our framework are near-optimal in most of the standard optimization settings. Additionally, we show that our algorithmic framework can be used to address the problem of making the gradients small in general normed spaces. As a concrete example, we obtain a nearly-optimal method for the standard ℓ1 setup (small gradients in the ℓ∞ norm), essentially matching the bound of Nesterov (2012) that was previously known only for the Euclidean setup. Finally, we show that our composite methods are broadly applicable to a number of regression and other classes of optimization problems, where regularization plays a key role. Our methods lead to complexity bounds that are either new or match the best existing ones.