TY - GEN

T1 - Zeroth-order randomized block methods for constrained minimization of expectation-valued Lipschitz continuous functions

AU - Shanbhag, Uday V.

AU - Yousefian, Farzad

N1 - Publisher Copyright:
© 2021 IEEE.

PY - 2021

Y1 - 2021

N2 - We consider the minimization of an L-{0}-Lipschitz continuous and expectation-valued function, denoted by f and defined as f(\mathrm{x})\ {\buildrel \triangle\over=}\\mathbb{E}[\tilde{f}(\mathrm{x}, \omega)], over a Cartesian product of closed and convex sets with a view towards obtaining both asymptotics as well as rate and complexity guarantees for computing an approximate stationary point (in a Clarke sense). We adopt a smoothing-based approach reliant on minimizing f-{\eta} where f(\mathrm{x})\ {\buildrel \triangle\over=}\\mathbb{E}-{u}[f(\mathrm{x}+\eta u)],u is a random variable defined on a unit sphere, and \eta > 0. In fact, it is observed that a stationary point of the \eta-smoothed problem is a 2\eta-stationary point for the original problem in the Clarke sense. In such a setting, we derive a suitable residual function that provides a metric for stationarity for the smoothed problem. By leveraging a zeroth-order framework reliant on utilizing sampled function evaluations implemented in a block-structured regime, we make two sets of contributions for the sequence generated by the proposed scheme. (i) The residual function of the smoothed problem tends to zero almost surely along the generated sequence; (ii) To compute an \mathrm{x} that ensures that the expected norm of the residual of the \eta-smoothed problem is within \epsilon requires no greater than \mathcal{O}(\frac{1}{\eta\epsilon^{2}}) projection steps and \mathcal{O}\left(\frac{1}{\eta^{2}\epsilon^{4}}\right) function evaluations. These statements appear to be novel with few related results available to contend with general nonsmooth, nonconvex, and stochastic regimes via zeroth-order approaches.

AB - We consider the minimization of an L-{0}-Lipschitz continuous and expectation-valued function, denoted by f and defined as f(\mathrm{x})\ {\buildrel \triangle\over=}\\mathbb{E}[\tilde{f}(\mathrm{x}, \omega)], over a Cartesian product of closed and convex sets with a view towards obtaining both asymptotics as well as rate and complexity guarantees for computing an approximate stationary point (in a Clarke sense). We adopt a smoothing-based approach reliant on minimizing f-{\eta} where f(\mathrm{x})\ {\buildrel \triangle\over=}\\mathbb{E}-{u}[f(\mathrm{x}+\eta u)],u is a random variable defined on a unit sphere, and \eta > 0. In fact, it is observed that a stationary point of the \eta-smoothed problem is a 2\eta-stationary point for the original problem in the Clarke sense. In such a setting, we derive a suitable residual function that provides a metric for stationarity for the smoothed problem. By leveraging a zeroth-order framework reliant on utilizing sampled function evaluations implemented in a block-structured regime, we make two sets of contributions for the sequence generated by the proposed scheme. (i) The residual function of the smoothed problem tends to zero almost surely along the generated sequence; (ii) To compute an \mathrm{x} that ensures that the expected norm of the residual of the \eta-smoothed problem is within \epsilon requires no greater than \mathcal{O}(\frac{1}{\eta\epsilon^{2}}) projection steps and \mathcal{O}\left(\frac{1}{\eta^{2}\epsilon^{4}}\right) function evaluations. These statements appear to be novel with few related results available to contend with general nonsmooth, nonconvex, and stochastic regimes via zeroth-order approaches.

UR - http://www.scopus.com/inward/record.url?scp=85126764354&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85126764354&partnerID=8YFLogxK

U2 - 10.1109/ICC54714.2021.9703135

DO - 10.1109/ICC54714.2021.9703135

M3 - Conference contribution

AN - SCOPUS:85126764354

T3 - 2021 7th Indian Control Conference, ICC 2021 - Proceedings

SP - 7

EP - 12

BT - 2021 7th Indian Control Conference, ICC 2021 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 7th Indian Control Conference, ICC 2021

Y2 - 20 December 2021 through 22 December 2021

ER -