Proxy support with Omaha (the Chromium updater) is questionable. We found what could be a work around for you when looking through an old Chrome forum, it might help you get Edge working from behind your proxy.
“For Microsoft EdgeUpdate to work via proxy, you must allow Windows (Internet Explorer) and Microsoft Edge to save (remember) your proxy credential (login and password). You must do it in both places: 1) in the checkbox "Remember password" in _Internet Explorer_ proxy authentication prompt window and 2) in Microsoft Edge during first proxy authentication (remember password in yellow top line of the window). If you already told Microsoft Edge NOT TO remember proxy password, you should go to Microsoft Edge settings - password settings and delete you proxy address from the list of sites, for which Microsoft Edge should not remember passwords. You should also disable getting automatic proxy settings in Internet Explorer network configuration window. After that you should close Internet Explorer, close Microsoft Edge window, and in windows task manager kill all Microsoft Edge processes all Microsoft EdgeUpdate. When you start Microsoft Edge again automatic update should work fine.”