IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i23p4858-d1293216.html
   My bibliography  Save this article

Efficient Automatic Subdifferentiation for Programs with Linear Branches

Author

Listed:
  • Sejun Park

    (Department of Artificial Intelligence, Korea University, Seoul 02841, Republic of Korea)

Abstract

Computing an element of the Clarke subdifferential of a function represented by a program is an important problem in modern non-smooth optimization. Existing algorithms either are computationally inefficient in the sense that the computational cost depends on the input dimension or can only cover simple programs such as polynomial functions with branches. In this work, we show that a generalization of the latter algorithm can efficiently compute an element of the Clarke subdifferential for programs consisting of analytic functions and linear branches, which can represent various non-smooth functions such as max, absolute values, and piecewise analytic functions with linear boundaries, as well as any program consisting of these functions such as neural networks with non-smooth activation functions. Our algorithm first finds a sequence of branches used for computing the function value at a random perturbation of the input; then, it returns an element of the Clarke subdifferential by running the backward pass of the reverse-mode automatic differentiation following those branches. The computational cost of our algorithm is at most that of the function evaluation multiplied by some constant independent of the input dimension n , if a program consists of piecewise analytic functions defined by linear branches, whose arities and maximum depths of branches are independent of n .

Suggested Citation

  • Sejun Park, 2023. "Efficient Automatic Subdifferentiation for Programs with Linear Branches," Mathematics, MDPI, vol. 11(23), pages 1-18, December.
  • Handle: RePEc:gam:jmathe:v:11:y:2023:i:23:p:4858-:d:1293216
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/23/4858/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/11/23/4858/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Boris Hanin, 2019. "Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations," Mathematics, MDPI, vol. 7(10), pages 1-9, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Rehan Zubair Khalid & Atta Ullah & Asifullah Khan & Afrasyab Khan & Mansoor Hameed Inayat, 2023. "Comparison of Standalone and Hybrid Machine Learning Models for Prediction of Critical Heat Flux in Vertical Tubes," Energies, MDPI, vol. 16(7), pages 1-22, March.
    2. Christoph Hertrich & Martin Skutella, 2023. "Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1079-1097, September.
    3. Jentzen, Arnulf & Welti, Timo, 2023. "Overall error analysis for the training of deep neural networks via stochastic gradient descent with random initialisation," Applied Mathematics and Computation, Elsevier, vol. 455(C).
    4. Timothy DeLise, 2023. "Deep Semi-Supervised Anomaly Detection for Finding Fraud in the Futures Market," Papers 2309.00088, arXiv.org.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:11:y:2023:i:23:p:4858-:d:1293216. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.