# Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 60 references that are in the map.
- First posted on arXiv 7 Aug 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015)
- [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014)
- [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014)
- [A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path](https://mlsanity.com/paper/2011.05365/) (2020)
- [Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization](https://mlsanity.com/paper/1506.07512/) (2015)
- [Chasing Nested Convex Bodies Nearly Optimally](https://mlsanity.com/paper/1811.00999/) (2018)
- [The entropic barrier: a simple and optimal universal self-concordant barrier](https://mlsanity.com/paper/1412.1587/) (2014)
- [A Lower Bound for the Optimization of Finite Sums](https://mlsanity.com/paper/1410.0723/) (2014)
- [Accelerated Mini-Batch Stochastic Dual Coordinate Ascent](https://mlsanity.com/paper/1305.2581/) (2013)
- [Universal Barrier is n-Self-Concordant](https://mlsanity.com/paper/1809.03011/) (2018)
- [The entropic barrier is n-self-concordant](https://mlsanity.com/paper/2112.10947/) (2021)
- [Structured learning of sum-of-submodular higher order energy functions](https://mlsanity.com/paper/1309.7512/) (2013)
- [Decomposable Submodular Function Minimization via Maximum Flow](https://mlsanity.com/paper/2103.03868/) (2021)
- [Short-step Methods Are Not Strongly Polynomial-Time](https://mlsanity.com/paper/2201.02768/) (2022)
- [Tutorial on the Robust Interior Point Method](https://mlsanity.com/paper/2108.04734/) (2021)

## Abstract (arXiv)

Many fundamental problems in machine learning can be formulated by the convex program [ minθ∈ Rd sumi=1nfi(θ), ] where each fi is a convex, Lipschitz function supported on a subset of di coordinates of θ. One common approach to this problem, exemplified by stochastic gradient descent, involves sampling one fi term at every iteration to make progress. This approach crucially relies on a notion of uniformity across the fi's, formally captured by their condition number. In this work, we give an algorithm that minimizes the above convex formulation to ε-accuracy in widetildeO(sumi=1n di log (1 /ε)) gradient computations, with no assumptions on the condition number. The previous best algorithm independent of the condition number is the standard cutting plane method, which requires O(nd log (1/ε)) gradient computations. As a corollary, we improve upon the evaluation oracle complexity for decomposable submodular minimization by Axiotis et al. (ICML 2021). Our main technical contribution is an adaptive procedure to select an fi term at every iteration via a novel combination of cutting-plane and interior-point methods.