Publication

Lower complexity bounds for minimizing regularized functions

2025

Abstract

In this paper, we establish lower bounds for the oracle complexity of the first-order methods minimizing regularized convex functions. We consider the composite representation of the objective. The smooth part has Hölder continuous gradient of degree and is accessible by a black-box local oracle. The composite part is a power of a norm. We prove that the best possible rate for the first-order methods in the large-scale setting for Euclidean norms is of the order for the functional residual, where k is the iteration counter and is the power of regularization. Our formulation covers several cases, including computation of the Cubically regularized Newton step by the first-order gradient methods, in which case the rate becomes. It can be achieved by the fast gradient method. Thus, our result proves the latter rate to be optimal. We also discover lower complexity bounds for non-Euclidean norms.

Official source

https://infoscience.epfl.ch/entities/publication/78e6a8a7-a59c-4c25-a717-cc7819b54391

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2025

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/78e6a8a7-a59c-4c25-a717-cc7819b54391

About this result

Related concepts (32)

Euclidean space

Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any positive integer dimension n, which are called Euclidean n-spaces when one wants to specify their dimension. For n equal to one or two, they are commonly called respectively Euclidean lines and Euclidean planes.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Euclidean distance

In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore occasionally being called the Pythagorean distance. These names come from the ancient Greek mathematicians Euclid and Pythagoras, although Euclid did not represent distances as numbers, and the connection from the Pythagorean theorem to distance calculation was not made until the 18th century.

Related publications (27)

Lower complexity bounds for minimizing regularized functions

Chat with Graph Search

Acceleration of Solvers for Plasma Simulation in the Tokamak Boundary

Efficient Krylov Methods for Linear Response in Plane-Wave Electronic Structure Calculations

Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices