Deeksha Adil

NeurIPS Conference 2025 Conference Paper

Balancing Gradient and Hessian Queries in Non-Convex Optimization

• Deeksha Adil
• Brian Bullins
• Aaron Sidford
• Chenyi Zhang

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 provide a method that for a twice-differentiable $f\colon \mathbb{R}^d \rightarrow \mathbb{R}$ with $L_2$-Lipschitz Hessian, and input initial point with $\Delta$-bounded sub-optimality and sufficiently small $\epsilon > 0$ outputs an $\epsilon$-critical point, i. e. , a point $x$ such that $\|\nabla f(x)\| \leq \epsilon$, using $\tilde{O}(\Delta L_2^{1/4} n_H^{-1/2}\epsilon^{-9/4})$ queries to a gradient oracle and $n_H$ queries to a Hessian oracle. As a consequence, we obtain an improved gradient query complexity of $\tilde{O}(d^{1/3}L_2^{1/2}\Delta\epsilon^{-3/2})$ in the case of bounded dimension and of $\tilde{O}(\Delta^{3/2} L_2^{3/4}\epsilon^{-9/4})$ in the case where we are allowed only a single Hessian query. We obtain these results through a more general algorithm which can handle approximate Hessian computations and recovers known prior state-of-the-art bounds of computing an $\epsilon$-critical point, under the additional assumption that $f$ has an $L_1$-Lipschitz gradient, with $O(\Delta L_2^{1/4}\epsilon^{-7/4})$-gradient queries.

NeurIPS Conference 2021 Conference Paper

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, $\ell_p$ regression, and logistic regression. Central to our approach is the notion of width reduction, a technique which has proven immensely useful in the context of maximum flow [Christiano et al. , STOC'11] and, more recently, $\ell_p$ regression [Adil et al. , SODA'19], in terms of improving the iteration complexity from $O(m^{1/2})$ to $\tilde{O}(m^{1/3})$, where $m$ is the number of rows of the design matrix, and where each iteration amounts to a linear system solve. However, a considerable drawback is that these methods require both problem-specific potentials and individually tailored analyses. As our main contribution, we initiate a new direction of study by presenting the first \emph{unified} approach to achieving $m^{1/3}$-type rates. Notably, our method goes beyond these previously considered problems to more broadly capture \emph{quasi-self-concordant} losses, a class which has recently generated much interest and includes the well-studied problem of logistic regression, among others. In order to do so, we develop a unified width reduction method for carefully handling these losses based on a more general set of potentials. Additionally, we directly achieve $m^{1/3}$-type rates in the constrained setting without the need for any explicit acceleration schemes, thus naturally complementing recent work based on a ball-oracle approach [Carmon et al. , NeurIPS'20].

SODA Conference 2020 Conference Paper

Faster p -norm minimizing flows, via smoothed q -norm problems

• Deeksha Adil
• Sushant Sachdeva

We present faster high-accuracy algorithms for computing ℓ p -norm minimizing flows. On a graph with m edges, our algorithm can compute a (1 + 1/poly( m ))-approximate unweighted ℓ p -norm minimizing flow with operations, for any p ≥ 2, giving the best bound for all p ≳ 5. 24. Combined with the algorithm from the work of Adil et al. (SODA '19), we can now compute such flows for any 2 ≤ p ≤ m o (1) in time at most O ( m 1. 24 ). In comparison, the previous best running time was Ω( m 1. 33 ) for large constant p. For p ∼ σ −1 log m, our algorithm computes a (1 + σ )-approximate maximum flow on undirected graphs using m 1+ o (1) σ −1 operations, matching the current best bound, albeit only for unit-capacity graphs. We also give an algorithm for solving general ℓ p -norm regression problems for large p. Our algorithm makes calls to a linear solver. This gives the first high-accuracy algorithm for computing weighted ℓ p -norm minimizing flows that runs in time o ( m 1. 5 ) for some p = m Ω(1). Our key technical contribution is to show that smoothed ℓ p -norm problems introduced by Adil et al. , are interreducible for different values of p. No such reduction is known for standard ℓ p -norm problems.

NeurIPS Conference 2019 Conference Paper

Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression

• Deeksha Adil
• Richard Peng
• Sushant Sachdeva

Linear regression in L p-norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processing. Generic convex optimization algorithms for solving L p-regression are slow in practice. Iteratively Reweighted Least Squares (IRLS) is an easy to implement family of algorithms for solving these problems that has been studied for over 50 years. However, these algorithms often diverge for p > 3, and since the work of Osborne (1985), it has been an open problem whether there is an IRLS algorithm that converges for p > 3. We propose p-IRLS, the first IRLS algorithm that provably converges geometrically for any p \in [2, \infty). Our algorithm is simple to implement and is guaranteed to find a high accuracy solution in a sub-linear number of iterations. Our experiments demonstrate that it performs even better than our theoretical bounds, beats the standard Matlab/CVX implementation for solving these problems by 10–50x, and is the fastest among available implementations in the high-accuracy regime.

SODA Conference 2019 Conference Paper

Iterative Refinement for ℓp-norm Regression

• Deeksha Adil
• Rasmus Kyng
• Richard Peng
• Sushant Sachdeva

TCS Journal 2018 Journal Article

Parameterized algorithms for stable matching with ties and incomplete lists

• Deeksha Adil
• Sushmita Gupta
• Sanjukta Roy
• Saket Saurabh
• Meirav Zehavi

We study the parameterized complexity of NP-hard optimization versions of Stable Matching and Stable Roommates in the presence of ties and incomplete lists. These problems model many real-life situations where solutions have to satisfy certain predefined criterion of suitability and compatibility. Specifically, our objective is to maximize/minimize the size of the stable matching. Our main theorems state that Stable Matching and Stable Roommates admit small kernels. Consequently, we also conclude that Stable Matching is fixed-parameter tractable (FPT) with respect to solution size, and that Stable Roommates is FPT with respect to a structural parameter. Finally, we analyze the special case where the input graph is planar.