In revision:
Nadav Hallak. "Randomized Oracle-Based Support Exploration for Constrained Sparse Optimization". 2026. [paper] [code]
Abstract: This paper studies smooth optimization over sparse simple-symmetric sets. We prove a local-to-global stationarity principle: at incomplete-support points, support stationarity on one gradient-ordered full extension implies stationarity for the original sparse problem, and hence global optimality when the objective is convex. We then develop an oracle-induced coordinate-wise framework that replaces exact restricted-support solves by closed descent oracles. These Algorithmic Oracles may encode first-order, regularized Newton-type, nested, inexact, or expert restricted-support procedures, so the resulting stationarity condition reflects the update actually implemented. Algorithmically, we propose randomized Algorithmic-Map Swapping (AMS), which combines oracle-based restricted updates with persistent support tests. At full-support accumulation points, recurrent randomized swaps yield full oracle-induced coordinate-wise stationarity almost surely, without exact local support optimization, deterministic gradient-ranked support selection, or per-iteration enumeration of the swap neighborhood. At incomplete-support accumulation points, recurrent compression-completion tests recover the limiting support and the gradient-ordered full extensions needed by the local-to-global principle. Numerical experiments illustrate the tradeoff between support exploration and restricted-support optimization.
-------------------------------------------------------------------
Old List: For the latest list please refer to my google scholar profile
Amir Beck and Nadav Hallak. "The Regularized Feasible Directions Method for Nonconvex Optimization." Operations Research Letters (2022).
[paper]
Eyal Cohen, Nadav Hallak, and Marc Teboulle. "A Dynamic Alternating Direction of Multipliers for Nonconvex Minimization with Nonlinear
Functional Equality Constraints." Journal of Optimization Theory and Applications. 2021 Sep 13:1-30.
[paper]
Nadav Hallak, Panayotis Mertikopoulos, and Volkan Cevher. "Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach." ICML '21. International Conference on Machine Learning. PMLR, 2021.
[paper]
Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher. "On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems ." In NeurIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[paper]
Fabian Latorre, Paul Rolland, Nadav Hallak, and Volkan Cevher. "Efficient proximal mapping of the 1-path-norm of shallow networks." In ICML '20: Proceedings of the 37th International Conference on Machine Learning, PMLR 119:5651-5661, 2020.
[paper]
Nadav Hallak, and Marc Teboulle. “Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach.” Journal of Optimization Theory and Applications (JOTA). 186, 480–503 (2020).
[submitted version] [paper]
Nadav Hallak, and Marc Teboulle. “A Non-Euclidean Gradient Descent Method with Sketching for Unconstrained Matrix Minimization .” Operations Research Letters 47, no. 5 (2019): 421-426.
[submitted version] [published version]
Beck Amir, and Nadav Hallak. “On the Convergence to Stationary Points of Deterministic and Randomized Feasible Descent Directions Methods .” SIAM Journal on Optimization. Accepted November 2019 (Submitted in 2018).
[submitted version] [published version]
Beck Amir, and Nadav Hallak. “Optimization Problems Involving Group Sparsity Terms .” Mathematical Programming (2017): 1-29.
[submitted version] [published version]
Beck, Amir, and Nadav Hallak. "Proximal Mapping for Symmetric Penalty and Sparsity." SIAM Journal on Optimization 28.1 (2018): 496-527.
[submitted version] [published version]
Beck Amir, and Nadav Hallak. “On the minimization over sparse symmetric sets: Projections, optimality conditions, and algorithms.” Mathematics of Operations Research 41.1 (2015): 196-223.
[submitted version] [published version]
Efficient Proximal Mapping of the 1-path-norm of Shallow Networks is presented in the Sparsity in Neural Networks: Advancing Understanding and Practice (SNN2021) workshop. [link]
ICML2021 slides on Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach: my slides here.