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

Optimal Refinement in Dynamic Discretisation Discovery for Continuous-Time Service Network Design

Categories Combinatorial Optimization, Network Optimization, Transportation

Dynamic Discretisation Discovery (DDD) is a framework for solving a problem by iteratively solving and refining a relaxed version of the problem. DDD is the basis for state-of-the-art algorithms for various problems, including the continuous-time service network design problem (CTSNDP), which we study here. In the refinement step, such algorithms must identify conflicts in the … Read more

Brenier Meets Adversarial Training: Optimal Transport Geometry for Robust Learning

Categories Convex and Nonsmooth Optimization, Optimization in Data Science, Robust Optimization

Distributionally robust optimization (DRO) provides a principled framework for learning under distribution shift, but its practical use is hindered by the difficulty of evaluating worst-case risks for nonconvex loss functions. We study a penalized DRO formulation in which the adversary may choose any distribution but incurs a Wasserstein penalty for deviating from the empirical distribution. … Read more

Soft Separation for Adaptive Robust Optimization

Categories Robust Optimization, Stochastic Programming Tags , ,

We propose an algorithmic framework for solving adaptive robust optimization with provable guarantees on both tractability and solution accuracy. The framework introduces soft separation, a probabilistic mechanism for identifying worst-case uncertainty realizations via a time-inhomogeneous Markov chain. Rather than solving an exact separation problem in each iteration, which is intractable in general, the chain carries … Read more

Treewidth and the complexity of box-constrained quadratic programs

Categories Global Optimization Theory, Quadratic Programming Tags , , , ,

We consider the problem of minimizing a sparse quadratic function over the unit hypercube. In binary quadratic programming, treewidth of the interaction graph is a central parameter for tractability: bounded treewidth yields polynomial-time solvability. Motivated by this fact, we investigate whether treewidth plays a similar role when the binary domain is replaced by the unit … Read more

Transferability of Error Bounds and the Kurdyka-Lojasiewicz Property under $C^1$ Partial Smoothness

Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

This work studies how a generalized error bound (GEB) property in the ambient Euclidean space transfers to the active manifold under \(\mathcal{C}^1\) partial smoothness. The GEB generalizes the standard error bound, which upper bounds the distance to a subset of critical points using first-order stationarity residuals, by allowing the distance to be composed with a … Read more