5 papers
Finding Simple Proofs for First-Order Optimization
Daniel Berg Thomsen, Manu Upadhyaya, Baptiste Goujaud +2
Progress in mathematics often requires more than a certificate of truth: it requires proof structures that are transparent, checkable, and reusable. Automated systems can increasin…
A Tight Theory of Error Feedback Algorithms in Distributed Optimization
Daniel Berg Thomsen, Adrien Taylor, Aymeric Dieuleveut
Communication costs are a major bottleneck in distributed learning and first-order optimization. A common approach to alleviate this issue is to compress the gradient information e…
An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit
Manu Upadhyaya, Daniel Berg Thomsen, Aymeric Dieuleveut +1
We introduce Prox-ITEM, an optimal proximal gradient method for minimizing , where is smooth and strongly convex, and is convex, proper, and lower semicontinuous. In t…
Tight analyses of first-order methods with error feedback
Daniel Berg Thomsen, Adrien Taylor, Aymeric Dieuleveut
Communication between agents often constitutes a major computational bottleneck in distributed learning. One of the most common mitigation strategies is to compress the information…
Complexity of Minimizing Regularized Convex Quadratic Functions
Daniel Berg Thomsen, Nikita Doikov
In this work, we study the iteration complexity of gradient methods for minimizing convex quadratic functions regularized by powers of Euclidean norms. We show that, due to the uni…