Convex Optimization

Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent

Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , ,

Stochastic Gradient Descent (\(\textsf{SGD}\)) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet its practical implementation differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (\(\textsf{Shuffling SGD}\)). A particularly popular strategy in \(\textsf{Shuffling SGD}\) is Random Reshuffling (\(\textsf{RR}\)), which has achieved great empirical success. … Read more

BDRS Can Fail for Matrix Scaling and Optimal Transport

Categories Convex Optimization Tags , ,

We show that the Bregman Douglas–Rachford splitting method (BDRS) can fail for matrix scaling and unregularized optimal transport. For matrix scaling, we construct a strictly positive \(36\times6\) integer matrix, positive rational marginals of equal mass, and a positive auxiliary initialization for which the matrix iterates enter a nonconstant six-cycle after one iteration. The construction prescribes … Read more

Peppy: An AI-Assisted Workflow for Tight Convergence Analysis of Optimization Algorithms

Categories Convex Optimization Tags , , ,

This paper presents Peppy, an AI-assisted workflow for discovering tight, analytic convergence proofs for first-order optimization algorithms. Generic approaches to using LLMs to conduct mathematical research target an unspecified, broad spectrum of problems and sometimes use the Lean 4 proof assistant for formalization. On the other hand, Peppy leverages domain-specific knowledge more heavily and is … Read more

Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems

Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

We study nonsmooth convex-concave saddle-point problems over compact convex sets, assuming access to stochastic subgradients of the payoff function. We develop single-loop projection-free algorithms that use linear minimization oracles over the primal and dual domains. Unlike prior projection-free approaches that rely on smoothing, our methods are purely subgradient-based and handle nonsmoothness directly. This design makes … Read more

Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case

Categories Convex Optimization Tags ,

We study gradient descent with predetermined nonnegative stepsizes on smooth strongly convex functions. Let \(p_{\mathrm{sil}}=\log_2(1+\sqrt2)\) and \(\kappa\) be the condition number. We prove the iteration lower bound \(\Omega\left(\kappa^{\frac{1}{p_{\mathrm{sil}}}-o(1)}\log\frac1\delta\right)\)for both relative squared distance and relative function error, uniformly over \(0<\delta<1\) and sufficiently large \(\kappa\). This matches the polynomial exponent of \(\kappa\) for the Silver stepsize schedule … Read more

A sufficient convergence condition for generalized Benders decomposition with general dual functions

Categories (Mixed) Integer Linear Programming, Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , ,

We revisit the framework of generalized Benders decomposition over a compact but non-finite master domain. We show by counterexample that strong general dual functions alone may fail to guarantee convergence. We then define a condition of uniform local strongness and prove that strong general dual functions satisfying this condition guarantee finite \(\epsilon\)-termination. Finally, we show … Read more

The best approximation tuple: an extension of the Cheney-Goldstein algorithm and results to the multiple sets case

Categories Convex Optimization, Global Optimization, Nonlinear Optimization Tags , , , , , ,

We extend the algorithm and several results published in the celebrated 1959 paper of Cheney and Goldstein about the best approximation pair (BAP) problem in two separate directions. One is, for the first time, the ability to consider more than two sets, a task which has been in the mind of researchers for many years … Read more

An exact algorithm for the probabilistic TSP via a new tractable convex representation of recourse

Categories (Mixed) Integer Linear Programming, Convex Optimization, Stochastic Programming Tags , , , ,

We consider the probabilistic traveling salesman problem (PTSP) in which customer presences are Bernoulli random variables, and the objective is to determine an a priori tour minimizing the expected traveling cost of the a posteriori tour obtained by skipping absent customers after customer presence is revealed. The existing literature has established that, given an a … Read more

Symmetry-dependence in Rounding of a Convex Body

Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Polyhedra Tags , , , ,

The symmetry measure of a convex body \(S\subset\mathbb{R}^n\) is given by: \(\mathrm{sym}(S):=\max\{\alpha\ge0:\ \mathrm{there\ exists}\ x\in S\ \mathrm{such\ that}\ -\alpha(S-x)\subseteq S-x\}\), where such an \(x\) is called a Minkowski center. We prove that every convex body \(S\) admits a \(\sqrt{\frac{n}{\mathrm{sym}(S)}}\)-rounding of \(S\), namely, there exists an origin-centered ellipsoid \(E\) and a center \(c\) such that the … Read more

UGM: A Unified Framework and New Perspectives for Accelerated Gradient Methods in Smooth and Strongly Convex Optimization

Categories Convex Optimization Tags ,

In this paper, we propose a unified framework for accelerated gradient methods, dubbed UGM, which subsumes a wide range of accelerated and conventional gradient-type methods designed for minimizing $L$-smooth and $\mu$-strongly convex functions. We demonstrate that the iteration update of the proposed framework can be intrinsically interpreted as a hybrid combination of the heavy-ball method … Read more