convex optimization – Optimization Online

Robust Out-of-Distribution Stochastic Optimization Based on Wasserstein-Metric Meta-Distribution Support Learning

Published: 2026/10/05, Updated: 2026/10/08

Biao Han

Optimization in Data Science, Robust Optimization, Stochastic Programming bilevel optimization, convex optimization, data-driven stochastic programming, distributionally robust optimization, Machine learning and optimization, robust optimization

We study stochastic optimization with a completely unobserved target distribution and samples from related source distributions. Treating the sources and the target as independent draws from a common meta-distribution, we propose Wasserstein-metric meta-distribution support learning (MDSL). The model jointly learns the center and radius of a Wasserstein ball, with an exclusion parameter controlling the fraction … Read more

Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent

Published: 2026/09/30

Zijian Liu

Convex Optimization, Nonlinear Optimization, Stochastic Programming convex optimization, Random Reshuffling, stochastic gradient descent

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

Robust Out-of-Distribution Stochastic Optimization with Heterogeneous Inclusive and Exclusive Distribution Clusters

Published: 2026/09/10, Updated: 2026/09/18

Biao Han

Infinite Dimensional Optimization, Robust Optimization, Stochastic Programming Biconvex optimization, bilevel optimization, cognitive science, convex optimization, Data-Driven Robust Optimization, decision science, distributionally robust optimization (DRO), Machine learning and optimization, multiple kernel learning

Decision scenarios far from rare in practice often place data-driven decision-making in an awkward position, where the decision maker may have access to neither the target distribution itself nor any empirical samples drawn from it, especially when decisions must be made in novel or highly uncertain environments. In response, robust out-of-distribution stochastic optimization (RooDSO) has … Read more

Entropy-Smooth Convex Optimization Cannot Be Accelerated

Published: 2026/07/30

Convex and Nonsmooth Optimization, Convex Optimization, Optimization in Data Science complexity, convex optimization, nonlinear programming

We prove an $\Omega(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = \Omega(T^2)$. In particular, this shows that mirror descent is optimal up to a logarithmic factor in this … Read more

Disjunctive Sum of Squares

Published: 2026/05/30

Cone Programming, Convex Optimization, Semi-definite Programming Branch-and-Bound, conic optimization, convex optimization, copositive programming, polynomial optimization, semidefinite programming, sum of squares, sum of squares optimization

We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz … Read more

Function-free Optimization via Comparison Oracles

Published: 2026/05/18

Convex Optimization, Nonlinear Optimization Comparison Oracle, convex optimization, derivative-free optimization, oracle complexity

In this work, we study optimization specified only through a comparison oracle: given two points, it reports which one is preferred. We call it function-free optimization because we do not assume access to, nor the existence of, a canonical application-given objective function. Instead, our goal is to find a most-preferred feasible point, which we call … Read more

Data-Dependent Complexity of First-Order Methods for Binary Classification

Published: 2025/12/04

Convex Optimization, Optimization in Data Science accelerated first-order methods, binary classification, convergence complexity, convex optimization

Large-scale problems in data science are often modeled with optimization, and the optimization model is usually solved with first-order methods that may converge at a sublinear rate. Therefore, it is of interest to terminate the optimization algorithm as soon as the underlying data science task is accomplished. We consider FISTA for solving two binary classification … Read more

A Practical Adaptive Subgame Perfect Gradient Method

Published: 2025/10/30, Updated: 2026/02/11

Convex Optimization, Second-Order Cone Programming adaptive, auto-conditioning, convex optimization, linesearch-free, non-asymptotic complexity, preconditioning, subgame perfect

We present a performant gradient method for smooth convex optimization, drawing inspiration from several recent advances in the field. Our algorithm, the Adaptive Subgame Perfect Gradient Method (ASPGM) is based on the notion of subgame perfection, attaining a dynamic strengthening of minimax optimality. At each iteration, ASPGM makes a momentum-type update, optimized dynamically based on … Read more

A First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex

Published: 2025/08/18

Chee-Khian Sim

Convex and Nonsmooth Optimization, Nonlinear Optimization Asymptotic convergence rate, convex optimization, Fast iterative shrinkage thresholding algorithm (FISTA), iteration complexity, Nonconvex optimization problem

We propose a first order algorithm, a modified version of FISTA, to solve an optimization problem with an objective function that is the sum of a possibly nonconvex function, with Lipschitz continuous gradient, and a convex function which can be nonsmooth. The algorithm is shown to have an iteration complexity of $\mathcal{O}(\epsilon^{-2})$ to find an … Read more

On the Resolution of Ties in Fair Convex Allocation Problems

Published: 2025/07/29, Updated: 2026/03/11

Bismark Singh

Convex and Nonsmooth Optimization, Convex Optimization convex optimization, distinct solutions, fairness, perturbation, tie-breaking

We study the emergence of indistinguishable, but structurally distinct, allocation outcomes in convex resource allocation models. Such outcomes occur when different users receive proportionally identical allocations despite differences in initial conditions, eligibility sets, or priority weights. We formalize this behavior and analyze the structural conditions under which it arises, with a focus on fairness-oriented objectives. … Read more