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

On the Convergence of Column-and-Constraint Generation Algorithms in Two-Stage Robust Optimization

Categories Robust Optimization Tags , , , , , , ,

We study the well-posedness and convergence of column-and-constraint generation algorithms for general two-stage robust optimization problems. The analysis is formulated in terms of regularity properties of the objective, the second-stage feasible region mapping, and the separation value function, without relying on a particular algebraic representation of the second-stage problem. We give sufficient conditions for the … Read more

Signed Budget Uncertainty for Robust Mixed-Integer Optimization

Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , ,

Classical budget uncertainty is widely used in robust optimization. It bounds the aggregate absolute deviation of uncertain parameters from nominal values and yields tractable robust counterparts. In many applications, however, information concerns aggregate signed deviations. We therefore study signed budget uncertainty, in which bounds are imposed on signed aggregates rather than absolute deviations. For robust … Read more

A One-Factorization Predictor–Corrector Long-Step Arc-Search Method and a Curvature-Amplified Variant for Semidefinite Programming with a Homogeneous Self-Dual Embedding

Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

In a predictor-corrector arc-search method, a point on the predictor arc is first selected and a corrector is then computed at that point. Since the Karush-Kuhn-Tucker (KKT) matrix changes with the selected point, this correction may require a second factorization in each iteration. We propose a one-factorization arc-search method (OFAS) for semidefinite programming (SDP) that … 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

Level-Set Geometry and the Theoretical Performance of PDHG for Conic Linear Optimization

Categories Cone Programming, Linear Programming Tags , , , ,

We consider solving (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG) — with heuristic enhancements and GPU implementation — has been very successful in solving huge-scale linear optimization problems (LPs). However, its application to more general conic convex optimization problems is … Read more

A tight 1/3–approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem

Categories Approximation Algorithms, Combinatorial Optimization, Dynamic Programming Tags , , ,

The \(\textit{Colored Knapsack Problem}\) (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an ordering in which consecutive items have different colors. The problem is weakly \(\mathcal{NP}\)-hard and admits two pseudo-polynomial dynamic programming (DP) algorithms proposed in the literature. These two DP algorithms have … Read more