OS
Ohad Shamir
cs.LGstat.MLmath.OCcs.NEcs.AIcs.NAmath.NAcs.CCcs.GTmath.PR
On Valency
published · living versionsW_eyra28jp·v1 · currentpublished
Adaptively Learning the Crowd Kernel
with Omer Tamuz, Ce Liu, Serge Belongie, Adam Tauman Kalai
1 version
Preprints & journals
102 papers in the corpus · 2009–2026A Simple Complexity Lower Bound for Solving $Ax=b$2609.10874v1 · Ohad Shamir2026 · 0 citationsarXiv
Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory2607.24827v1 · Michael Menart, Aleksandar Nikolov, Ohad Shamir2026 · 0 citationsarXiv
A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate1409.2848v5 · Ohad Shamir2014 · 33 citationsarXiv
Dimension-Free Iteration Complexity of Finite Sum Optimization Problems1606.09333v1 · Yossi Arjevani, Ohad Shamir2016 · 2 citationsarXiv
When Models Don't Collapse: On the Consistency of Iterative MLE2505.19046v3 · Daniel Barzilai, Ohad Shamir2025 · 0 citationsarXiv
The Oracle Complexity of Simplex-based Matrix Games2412.06990v4 · Guy Kornowski, Ohad Shamir2024 · 0 citationsarXiv
Beyond Benign Overfitting in Nadaraya-Watson Interpolators2502.07480v3 · Daniel Barzilai, Guy Kornowski, Ohad Shamir2025 · 0 citationsarXiv
Simple Relative Deviation Bounds for Covariance and Gram Matrices2410.05754v3 · Daniel Barzilai, Ohad Shamir2024 · 0 citationsarXiv
Deterministic Nonsmooth Nonconvex Optimization2302.08300v2 · Michael I. Jordan, Guy Kornowski, Tianyi Lin et al.2023 · 4 citationsarXiv
On the Complexity of Finding Small Subgradients in Nonsmooth Optimization2209.10346v2 · Guy Kornowski, Ohad Shamir2022 · 1 citationarXiv
Logarithmic Width Suffices for Robust Memorization2502.11162v1 · Amitsour Egosi, Gilad Yehudai, Ohad Shamir2025 · 0 citationsarXiv
Hardness of Learning Fixed Parities with Neural Networks2501.00817v2 · Itamar Shoshani, Ohad Shamir2025 · 0 citationsarXiv
Implicit Regularization Towards Rank Minimization in ReLU Networks2201.12760v1 · Nadav Timor, Gal Vardi, Ohad Shamir2022 · 5 citationsProceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1429-1459, 2023
On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization2409.10323v1 · Guy Kornowski, Swati Padmanabhan, Ohad Shamir2024 · 0 citationsarXiv
Open Problem: Anytime Convergence Rate of Gradient Descent2406.13888v1 · Guy Kornowski, Ohad Shamir2024 · 0 citationsarXiv
An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization2307.04504v3 · Guy Kornowski, Ohad Shamir2023 · 2 citationsarXiv
Generalization in Kernel Regression Under Realistic Assumptions2312.15995v2 · Daniel Barzilai, Ohad Shamir2023 · 0 citationsarXiv
Depth Separation in Norm-Bounded Infinite-Width Neural Networks2402.08808v1 · Suzanna Parkinson, Greg Ongie, Rebecca Willett et al.2024 · 0 citationsarXiv
The Implicit Bias of Benign Overfitting2201.11489v5 · Ohad Shamir2022 · 4 citationsJMLR 24(113):1-40, 2023
Oracle Complexity in Nonsmooth Nonconvex Optimization2104.06763v3 · Guy Kornowski, Ohad Shamir2021 · 5 citationsarXiv
Width is Less Important than Depth in ReLU Neural Networks2202.03841v2 · Gal Vardi, Gilad Yehudai, Ohad Shamir2022 · 3 citationsarXiv
On the Power and Limitations of Random Features for Understanding Neural Networks1904.00687v4 · Gilad Yehudai, Ohad Shamir2019 · 48 citationsarXiv
Learning a Single Neuron with Gradient Methods2001.05205v3 · Gilad Yehudai, Ohad Shamir2020 · 9 citationsarXiv
Learning a Single Neuron with Bias Using Gradient Descent2106.01101v2 · Gal Vardi, Gilad Yehudai, Ohad Shamir2021 · 2 citationsarXiv
Convergence Results For Q-Learning With Experience Replay2112.04213v1 · Liran Szlak, Ohad Shamir2021 · 0 citationsarXiv
Replay For Safety2112.04229v1 · Liran Szlak, Ohad Shamir2021 · 0 citationsarXiv
Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems2106.06880v2 · Itay Safran, Ohad Shamir2021 · 3 citationsarXiv
The Sample Complexity of Learning Linear Predictors with the Squared Loss1406.5143v3 · Ohad Shamir2014 · 5 citationsarXiv
A Stochastic Newton Algorithm for Distributed Convex Optimization2110.02954v1 · Brian Bullins, Kumar Kshitij Patel, Ohad Shamir et al.2021 · 4 citationsarXiv
On the Optimal Memorization Power of ReLU Neural Networks2110.03187v1 · Gal Vardi, Gilad Yehudai, Ohad Shamir2021 · 3 citationsarXiv
The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication2102.01583v2 · Blake Woodworth, Brian Bullins, Ohad Shamir et al.2021 · 18 citationsarXiv
The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks2006.01005v2 · Itay Safran, Gilad Yehudai, Ohad Shamir2020 · 7 citationsarXiv
The Complexity of Finding Stationary Points with Stochastic Gradient Descent1910.01845v3 · Yoel Drori, Ohad Shamir2019 · 14 citationsarXiv
The Connection Between Approximation, Depth Separation and Learnability in Neural Networks2102.00434v2 · Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz et al.2021 · 4 citationsarXiv
Size and Depth Separation in Approximating Benign Functions with Neural Networks2102.00314v3 · Gal Vardi, Daniel Reichman, Toniann Pitassi et al.2021 · 4 citationsarXiv
Implicit Regularization in ReLU Networks with the Square Loss2012.05156v3 · Gal Vardi, Ohad Shamir2020 · 6 citationsarXiv
Depth Separations in Neural Networks: What is Actually Being Separated?1904.06984v3 · Itay Safran, Ronen Eldan, Ohad Shamir2019 · 13 citationsarXiv
How Good is SGD with Random Shuffling?1908.00045v4 · Itay Safran, Ohad Shamir2019 · 4 citationsarXiv
High-Order Oracle Complexity of Smooth and Strongly Convex Optimization2010.06642v2 · Guy Kornowski, Ohad Shamir2020 · 2 citationsarXiv
Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?2002.11962v3 · Ohad Shamir2020 · 7 citationsarXiv
Gradient Methods Never Overfit On Separable Data2007.00028v2 · Ohad Shamir2020 · 0 citationsarXiv
Is Local SGD Better than Minibatch SGD?2002.07839v2 · Blake Woodworth, Kumar Kshitij Patel, Sebastian U. Stich et al.2020 · 104 citationsarXiv
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks1610.09887v3 · Itay Safran, Ohad Shamir2016 · 107 citationsarXiv
Proving the Lottery Ticket Hypothesis: Pruning is All You Need2002.00585v1 · Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz et al.2020 · 87 citationsarXiv
Bandit Regret Scaling with the Effective Loss Range1705.05091v3 · Nicolo Cesa-Bianchi, Ohad Shamir2017 · 3 citationsarXiv
Global Non-convex Optimization with Discretized Diffusions1810.12361v2 · Murat A. Erdogdu, Lester Mackey, Ohad Shamir2018 · 8 citationsarXiv
Size-Independent Sample Complexity of Neural Networks1712.06541v5 · Noah Golowich, Alexander Rakhlin, Ohad Shamir2017 · 183 citationsarXiv
Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks1809.08587v4 · Ohad Shamir2018 · 30 citationsarXiv
Space lower bounds for linear prediction in the streaming model1902.03498v3 · Yuval Dagan, Gil Kur, Ohad Shamir2019 · 1 citationarXiv
The Complexity of Making the Gradient Small in Stochastic Convex Optimization1902.04686v2 · Dylan J. Foster, Ayush Sekhari, Ohad Shamir et al.2019 · 18 citationsarXiv
Career total: 168 works. 102 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.