Brian Bullins

activity

20132026

most citedOnline Control with Adversarial Disturbances

54 citations · 225 across the 30 of their papers we have counts for

collaborators

36 papers

cs.LG2026

Ori: Drift-Aware Streaming $k$ -PCA for Very Low-Rank LLM Training

Xinyu Luo, Jincheng Zhou, Mengbo Wang +5

A prominent family of low-rank LLM optimizers, pioneered by GaLore, performs gradient-subspace projection: at each step, they project the gradient into a low-dimensional subspace a…

cs.LG2026

MuonIO: Principled Norm-Aware Descent for Embedding Tables and Language Model Heads

Linkai Ma, Xinyu Luo, Mengbo Wang +3

The Muon optimizer derives its update rule for hidden linear layers by solving a local linearization of the loss penalized by the spectral norm, motivated by an RMS-stability argum…

math.OC2026

Near-Optimal Acceleration for Smooth $ℓ_{p}$ / $ℓ_{q}$ Nondual Convex First-Order Oracle Optimization

David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1

We study the optimization of convex objectives with $(L, κ - 1)$ -Hölder-continuous gradients in $ℓ_{q}$ over $R B_{p}^{d}$ , $1 < κ \leq 2$ . (MG26) provides selectors with a movement bound fo…

math.OC2026

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1

We study first-order black-box convex optimization over an $ℓ_{p}$ -ball for objectives Lipschitz in the $ℓ_{q}$ -norm, solving in the affirmative the nonsmooth version of the COLT…

cs.LG2026

Spectral Saliency for Machine Unlearning

Cedar Site Bai, Amber Yijia Zheng, Raymond A. Yeh +1

Machine unlearning (MU) aims to remove the influence of specific training data while preserving model utility. As the name suggests, MU can be viewed as the inverse of learning, us…

math.OC2026

On the Limits of Biased Derivative Information for Nonconvex Stochastic Optimization

Anant Shyam, Brian Bullins

We consider the problem of finding $δ$ -stationary points for $δ > 0$ , i.e., $x \in R^{d}$ such that $∣∣\nabla F (x) ∣∣ \leq δ$ , for smooth, non-convex objectives, where the deri…

cs.LG2026

Can Entry-Wise Clipping Give Spectral Control of Stochastic Gradients?

Zitao Song, Cedar Site Bai, Zhe Zhang +2

Training instabilities such as loss spikes are frequently the result of stochastic gradient noise. Because of rare expressions in language training data, and multiple layer composi…

math.OC2026

Mirror-Free Proximal Methods

Abhijeet Vyas, Brian Bullins

We present a \emph{mirror-free} mirror prox (MFMP) algorithm, which extends the classic approach of Nemirovski (2004) to allow for proximal-like updates without the explicit need f…

math.OC2026

Beyond First-Order Methods for $ℓ_{p}$ -Structured Non-Monotone Variational Inequalities

Abhijeet Vyas, Brian Bullins

We propose novel high-order algorithms for a class of $ℓ_{p}$ -structured non-monotone variational inequalities. In particular, work by Diakonikolas et al. (2021), which introduced…

cs.LG2026

Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points

Abhijeet Vyas, Brian Bullins

We propose and study an online version of min-max optimization based on cumulative saddle points under a variety of performance measures beyond convex-concave settings. After first…

cs.LG2026

Decoupling Variance and Scale-Invariant Updates in Adaptive Gradient Descent for Unified Vector and Matrix Optimization

Zitao Song, Cedar Site Bai, Zhe Zhang +2

Adaptive methods like Adam have become the $de facto$ standard for large-scale vector and Euclidean optimization due to their coordinate-wise adaptation with a second-orde…

math.OC2025

Balancing Gradient and Hessian Queries in Non-Convex Optimization

Deeksha Adil, Brian Bullins, Aaron Sidford +1

We develop optimization methods which offer new trade-offs between the number of gradient and Hessian computations needed to compute the critical point of a non-convex function. We…

cs.LG2025

Stacey: Promoting Stochastic Steepest Descent via Accelerated $ℓ_{p}$ -Smooth Nonconvex Optimization

Xinyu Luo, Cedar Site Bai, Bolian Li +3

While popular optimization methods such as SGD, AdamW, and Lion depend on steepest descent updates in either $ℓ_{2}$ or $ℓ_{\infty}$ norms, there remains a critical gap in handli…

cs.LG2025

Model Immunization from a Condition Number Perspective

Amber Yijia Zheng, Cedar Site Bai, Brian Bullins +1

Model immunization aims to pre-train models that are difficult to fine-tune on harmful tasks while retaining their utility on other non-harmful tasks. Though prior work has shown e…

math.OC2024

Convex optimization with $p$ -norm oracles

Deeksha Adil, Brian Bullins, Arun Jambulapati +1

In recent years, there have been significant advances in efficiently solving $ℓ_{s}$ -regression using linear system solvers and $ℓ_{2}$ -regression [Adil-Kyng-Peng-Sachdeva, J. AC…

math.OC2024

Faster Acceleration for Steepest Descent

Cedar Site Bai, Brian Bullins

Recent advances (Sherman, 2017; Sidford and Tian, 2018; Cohen et al., 2021) have overcome the fundamental barrier of dimension dependence in the iteration complexity of solving $\e…

math.OC2024

Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity

Cedar Site Bai, Brian Bullins

In this paper, we provide tight lower bounds for the oracle complexity of minimizing high-order Hölder smooth and uniformly convex functions. Specifically, for a function whose $p^…

cs.LG2023★ 2 cited

Federated Composite Saddle Point Optimization

Site Bai, Brian Bullins

Federated learning (FL) approaches for saddle point problems (SPP) have recently gained in popularity due to the critical role they play in machine learning (ML). Existing works mo…

math.OC2023

Beyond first-order methods for non-convex non-concave min-max optimization

Abhijeet Vyas, Brian Bullins

We propose a study of structured non-convex non-concave min-max problems which goes beyond standard first-order approaches. Inspired by the tight understanding established in recen…

cs.LG2023

Variance-Reduced Conservative Policy Iteration

Naman Agarwal, Brian Bullins, Karan Singh

We study the sample complexity of reducing reinforcement learning to a sequence of empirical risk minimization problems over the policy space. Such reductions-based algorithms exhi…

math.OC2022★ 1 cited

Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

Deeksha Adil, Brian Bullins, Arun Jambulapati +1

In this work, we present new simple and optimal algorithms for solving the variational inequality (VI) problem for $p^{t h}$ -order smooth, monotone operators -- a problem that gener…

math.OC2021★ 4 cited

A Stochastic Newton Algorithm for Distributed Convex Optimization

Brian Bullins, Kumar Kshitij Patel, Ohad Shamir +2

We propose and analyze a stochastic Newton algorithm for homogeneous distributed stochastic convex optimization, where each machine can calculate stochastic gradients of the same p…

math.OC2021★ 2 cited

Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization

Deeksha Adil, Brian Bullins, Sushant Sachdeva

We provide several algorithms for constrained optimization of a large class of convex problems, including softmax, $ℓ_{p}$ regression, and logistic regression. Central to our appr…

cs.DS2021

Almost-linear-time Weighted $ℓ_{p}$ -norm Solvers in Slightly Dense Graphs via Sparsification

Deeksha Adil, Brian Bullins, Rasmus Kyng +1

We give almost-linear-time algorithms for constructing sparsifiers with $n p o l y (lo g n)$ edges that approximately preserve weighted $(ℓ_{2}^{2} + ℓ_{p}^{p})$ flow or voltage obj…

Ori: Drift-Aware Streaming k-PCA for Very Low-Rank LLM Training

MuonIO: Principled Norm-Aware Descent for Embedding Tables and Language Model Heads

Near-Optimal Acceleration for Smooth ℓp​ / ℓq​ Nondual Convex First-Order Oracle Optimization

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

Spectral Saliency for Machine Unlearning

On the Limits of Biased Derivative Information for Nonconvex Stochastic Optimization

Can Entry-Wise Clipping Give Spectral Control of Stochastic Gradients?

Mirror-Free Proximal Methods

Beyond First-Order Methods for ℓp​-Structured Non-Monotone Variational Inequalities

Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points

Decoupling Variance and Scale-Invariant Updates in Adaptive Gradient Descent for Unified Vector and Matrix Optimization

Balancing Gradient and Hessian Queries in Non-Convex Optimization

Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp​-Smooth Nonconvex Optimization

Model Immunization from a Condition Number Perspective

Convex optimization with p-norm oracles

Faster Acceleration for Steepest Descent

Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity

Federated Composite Saddle Point Optimization

Beyond first-order methods for non-convex non-concave min-max optimization

Variance-Reduced Conservative Policy Iteration

Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

A Stochastic Newton Algorithm for Distributed Convex Optimization

Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization

Almost-linear-time Weighted ℓp​-norm Solvers in Slightly Dense Graphs via Sparsification

Ori: Drift-Aware Streaming $k$ -PCA for Very Low-Rank LLM Training

Near-Optimal Acceleration for Smooth $ℓ_{p}$ / $ℓ_{q}$ Nondual Convex First-Order Oracle Optimization

Beyond First-Order Methods for $ℓ_{p}$ -Structured Non-Monotone Variational Inequalities

Stacey: Promoting Stochastic Steepest Descent via Accelerated $ℓ_{p}$ -Smooth Nonconvex Optimization

Convex optimization with $p$ -norm oracles

Almost-linear-time Weighted $ℓ_{p}$ -norm Solvers in Slightly Dense Graphs via Sparsification