More Like this

1. Primal-Dual Extrapolation Methods for Monotone Inclusions Under Local Lipschitz Continuity

   https://doi.org/10.1287/moor.2024.0407  

   Lu, Zhaosong; Mei, Sanyou (October 2024, Mathematics of Operations Research)

   In this paper, we consider a class of monotone inclusion (MI) problems of finding a zero of the sum of two monotone operators, in which one operator is maximal monotone, whereas the other is locally Lipschitz continuous. We propose primal-dual (PD) extrapolation methods to solve them using a point and operator extrapolation technique, whose parameters are chosen by a backtracking line search scheme. The proposed methods enjoy an operation complexity of [Formula: see text] and [Formula: see text], measured by the number of fundamental operations consisting only of evaluations of one operator and resolvent of the other operator, for finding an ε-residual solution of strongly and nonstrongly MI problems, respectively. The latter complexity significantly improves the previously best operation complexity [Formula: see text]. As a byproduct, complexity results of the primal-dual extrapolation methods are also obtained for finding an ε-KKT or ε-residual solution of convex conic optimization, conic constrained saddle point, and variational inequality problems under local Lipschitz continuity. We provide preliminary numerical results to demonstrate the performance of the proposed methods. Funding: This work was partially supported by the National Science Foundation [Grant IIS-2211491], the Office of Naval Research [Grant N00014-24-1-2702], and the Air Force Office of Scientific Research [Grant FA9550-24-1-0343]. 

   more » « less
2. Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning

   https://doi.org/10.1287/moor.2024.0444  

   Srikant, R (October 2025, Mathematics of Operations Research)

   We prove a nonasymptotic central limit theorem (CLT) for vector-valued martingale differences using Stein’s method, and we use Poisson’s equation to extend the result to functions of Markov chains. We then show that these results can be applied to establish a nonasymptotic CLT for temporal difference learning with averaging. Funding: This work was supported by National Science Foundation [Grants CNS 23-12714, CCF 22-07547, and CNS 21-06801] and Air Force Office of Scientific Research [Grant FA9550-24-1-0002]. 

   more » « less
3. Stochastic Zeroth-Order Functional Constrained Optimization: Oracle Complexity and Applications

   https://doi.org/10.1287/ijoo.2022.0085  

   Nguyen, Anthony; Balasubramanian, Krishnakumar (November 2022, INFORMS Journal on Optimization)

   Functionally constrained stochastic optimization problems, where neither the objective function nor the constraint functions are analytically available, arise frequently in machine learning applications. In this work, assuming we only have access to the noisy evaluations of the objective and constraint functions, we propose and analyze stochastic zeroth-order algorithms for solving this class of stochastic optimization problem. When the domain of the functions is [Formula: see text], assuming there are m constraint functions, we establish oracle complexities of order [Formula: see text] and [Formula: see text] in the convex and nonconvex settings, respectively, where ϵ represents the accuracy of the solutions required in appropriately defined metrics. The established oracle complexities are, to our knowledge, the first such results in the literature for functionally constrained stochastic zeroth-order optimization problems. We demonstrate the applicability of our algorithms by illustrating their superior performance on the problem of hyperparameter tuning for sampling algorithms and neural network training. Funding: K. Balasubramanian was partially supported by a seed grant from the Center for Data Science and Artificial Intelligence Research, University of California–Davis, and the National Science Foundation [Grant DMS-2053918]. 

   more » « less
4. Analysis of a Class of Minimization Problems Lacking Lower Semicontinuity

   https://doi.org/10.1287/moor.2023.0295  

   Han, Shaoning; Cui, Ying; Pang, Jong-Shi (August 2024, Mathematics of Operations Research)

   The minimization of nonlower semicontinuous functions is a difficult topic that has been minimally studied. Among such functions is a Heaviside composite function that is the composition of a Heaviside function with a possibly nonsmooth multivariate function. Unifying a statistical estimation problem with hierarchical selection of variables and a sample average approximation of composite chance constrained stochastic programs, a Heaviside composite optimization problem is one whose objective and constraints are defined by sums of possibly nonlinear multiples of such composite functions. Via a pulled-out formulation, a pseudostationarity concept for a feasible point was introduced in an earlier work as a necessary condition for a local minimizer of a Heaviside composite optimization problem. The present paper extends this previous study in several directions: (a) showing that pseudostationarity is implied by (and thus, weaker than) a sharper subdifferential-based stationarity condition that we term epistationarity; (b) introducing a set-theoretic sufficient condition, which we term a local convexity-like property, under which an epistationary point of a possibly nonlower semicontinuous optimization problem is a local minimizer; (c) providing several classes of Heaviside composite functions satisfying this local convexity-like property; (d) extending the epigraphical formulation of a nonnegative multiple of a Heaviside composite function to a lifted formulation for arbitrarily signed multiples of the Heaviside composite function, based on which we show that an epistationary solution of the given Heaviside composite program with broad classes of B-differentiable component functions can in principle be approximately computed by surrogation methods. Funding: The work of Y. Cui was based on research supported by the National Science Foundation [Grants CCF-2153352, DMS-2309729, and CCF-2416172] and the National Institutes of Health [Grant 1R01CA287413-01]. The work of J.-S. Pang was based on research supported by the Air Force Office of Scientific Research [Grant FA9550-22-1-0045]. 

   more » « less
5. Variational Theory and Algorithms for a Class of Asymptotically Approachable Nonconvex Problems

   https://doi.org/10.1287/moor.2023.0202  

   Li, Hanyang; Cui, Ying (January 2025, Mathematics of Operations Research)

   We investigate a class of composite nonconvex functions, where the outer function is the sum of univariate extended-real-valued convex functions and the inner function is the limit of difference-of-convex functions. A notable feature of this class is that the inner function may fail to be locally Lipschitz continuous. It covers a range of important, yet challenging, applications, including inverse optimal value optimization and problems under value-at-risk constraints. We propose an asymptotic decomposition of the composite function that guarantees epi-convergence to the original function, leading to necessary optimality conditions for the corresponding minimization problem. The proposed decomposition also enables us to design a numerical algorithm such that any accumulation point of the generated sequence, if it exists, satisfies the newly introduced optimality conditions. These results expand on the study of so-called amenable functions introduced by Poliquin and Rockafellar in 1992, which are compositions of convex functions with smooth maps, and the prox-linear methods for their minimization. To demonstrate that our algorithmic framework is practically implementable, we further present verifiable termination criteria and preliminary numerical results. Funding: Financial support from the National Science Foundation Division of Computing and Communication Foundations [Grant CCF-2416172] and Division of Mathematical Sciences [Grant DMS-2416250] and the National Cancer Institute, National Institutes of Health [Grant 1R01CA287413-01] is gratefully acknowledged. 

   more » « less