8 papers
AI-Assisted Discovery of Convex Relaxations via Dual Agents
Sungyoon Kim, Mert Pilanci
Recent work shows that LLM agents can improve sharp-constant inequalities by searching for extremal constructions, which yield upper bounds. We address the complementary side: a lo…
Optimizer-Induced Mode Connectivity: From AdamW to Muon
Fangzhao Zhang, Sungyoon Kim, Erica Zhang +2
Mode connectivity has been widely studied, yet the role of the optimizer remains underexplored. We revisit it through optimizer-induced implicit regularization, asking how connecti…
Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition
Calvin Ang, Sungyoon Kim, Mert Pilanci
We study entrywise scalar quantization of two matrices prior to multiplication. Given and , we quantize entries of and independentl…
FlashSketch: Sketch-Kernel Co-Design for Fast Sparse Sketching on GPUs
Rajat Vadiraj Dwaraknath, Sungyoon Kim, Mert Pilanci
Sparse sketches such as the sparse Johnson-Lindenstrauss transform are a core primitive in randomized numerical linear algebra because they leverage random sparsity to reduce the a…
MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search
Sungyoon Kim, Rajat Vadiraj Dwaraknath, Longling geng +1
Iterative methods for computing matrix functions have been extensively studied and their convergence speed can be significantly improved with the right tuning of parameters and by…
Exploring the loss landscape of regularized neural networks via convex duality
Sungyoon Kim, Aaron Mishkin, Mert Pilanci
We discuss several aspects of the loss landscape of regularized neural networks: the structure of stationary points, connectivity of optimal solutions, path with nonincreasing loss…
Randomized Geometric Algebra Methods for Convex Neural Networks
Yifei Wang, Sungyoon Kim, Paul Chu +2
We introduce randomized algorithms to Clifford's Geometric Algebra, generalizing randomized linear algebra to hypercomplex vector spaces. This novel approach has many implications…
Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time
Sungyoon Kim, Mert Pilanci
In this paper, we study the optimality gap between two-layer ReLU networks regularized with weight decay and their convex relaxations. We show that when the training data is random…