# Affine-invariant contracting-point methods for Convex Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2020.

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

- [Super-Universal Regularized Newton Method](https://mlsanity.com/paper/2208.05888/) (2022)
- [Second-order optimization with lazy Hessians](https://mlsanity.com/paper/2212.00781/) (2022)

## Abstract (arXiv)

In this paper, we develop new affine-invariant algorithms for solving composite convex minimization problems with bounded domain. We present a general framework of Contracting-Point methods, which solve at each iteration an auxiliary subproblem restricting the smooth part of the objective function onto contraction of the initial domain. This framework provides us with a systematic way for developing optimization methods of different order, endowed with the global complexity bounds. We show that using an appropriate affine-invariant smoothness condition, it is possible to implement one iteration of the Contracting-Point method by one step of the pure tensor method of degree p ≥ 1. The resulting global rate of convergence in functional residual is then cal O(1 / kp), where k is the iteration counter. It is important that all constants in our bounds are affine-invariant. For p = 1, our scheme recovers well-known Frank-Wolfe algorithm, providing it with a new interpretation by a general perspective of tensor methods. Finally, within our framework, we present efficient implementation and total complexity analysis of the inexact second-order scheme (p = 2), called Contracting Newton method. It can be seen as a proper implementation of the trust-region idea. Preliminary numerical results confirm its good practical performance both in the number of iterations, and in computational time.