# Beyond Log-Concavity: Theory and Algorithm for Sum-Log-Concave Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 13 references that are in the map.
- First posted on arXiv 26 Sep 2023.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)
- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [Recent Theoretical Advances in Non-Convex Optimization](https://mlsanity.com/paper/2012.06188/) (2020)

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

- [A Bregman firmly nonexpansive proximal operator for baryconvex optimization](https://mlsanity.com/paper/2411.00928/) (2024)

## Abstract (arXiv)

This paper extends the classic theory of convex optimization to the minimization of functions that are equal to the negated logarithm of what we term as a sum-log-concave function, i.e., a sum of log-concave functions. In particular, we show that such functions are in general not convex but still satisfy generalized convexity inequalities. These inequalities unveil the key importance of a certain vector that we call the cross-gradient and that is, in general, distinct from the usual gradient. Thus, we propose the Cross Gradient Descent (XGD) algorithm moving in the opposite direction of the cross-gradient and derive a convergence analysis. As an application of our sum-log-concave framework, we introduce the so-called checkered regression method relying on a sum-log-concave function. This classifier extends (multiclass) logistic regression to non-linearly separable problems since it is capable of tessellating the feature space by using any given number of hyperplanes, creating a checkerboard-like pattern of decision regions.