Source author record

Deeksha Adil

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.OC Machine Learning math.NA Numerical Analysis

Catalog footprint

Research overview

6works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Convex optimization with $p$ -norm oracles

In recent years, there have been significant advances in efficiently solving $\ell_s$ -regression using linear system solvers and $\ell_2$ -regression [Adil-Kyng-Peng-Sachdeva, J. ACM'24]. Would efficient smoothed $\ell_p$ -norm solvers lead to even faster rates for solving $\ell_s$ -regression when $2 \leq p < s$ ? In this paper, we give an affirmative answer to this question and show how to solve $\ell_s$ -regression using $\tilde{O}(n^{\fracν{1+ν}})$ iterations of solving smoothed $\ell_p$ regression problems, where $ν:= \frac{1}{p} - \frac{1}{s}$ . To obtain this result, we provide improved accelerated rates for convex optimization problems when given access to an $\ell_p^s(λ)$ -proximal oracle, which, for a point $c$ , returns the solution of the regularized problem $\min_{x} f(x) + λ||x-c||_p^s$ . Additionally, we show that these rates for the $\ell_p^s(λ)$ -proximal oracle are optimal for algorithms that query in the span of the outputs of the oracle, and we further apply our techniques to settings of high-order and quasi-self-concordant optimization.

preprint2026arXiv

On efficient robust regression with subquadratic samples

We revisit the problem of robust linear regression under Gaussian covariates with an unknown covariance matrix of condition number $κ$ . For this fundamental problem, significant gaps remain in our understanding of the trade-offs among sample complexity, condition number, runtime, and prediction error for efficient algorithms. Our first result is a near-linear-time algorithm that uses $\widetilde{O}(d/ε^4)$ samples, where $d$ is the dimension and $ε$ is the corruption rate, and achieves prediction error $O(\sqrt{εκ})$ under the condition $εκ\lesssim 1$ , improving over all prior works. We complement this result with a Statistical Query (SQ) lower bound showing that efficient SQ algorithms achieving error $o(\sqrt{εκ})$ when $εκ\lesssim 1$ require queries that take $Ω(d^2)$ samples to simulate. Finally, we prove a low-degree polynomial lower bound that gives fine-grained evidence that, without assumptions such as $εκ\lesssim 1$ , efficient algorithms may require $\tildeΩ\left(\min\{dε^{2}κ^{2},\ ε^{2}d^{2}\}\right)$ samples to significantly outperform the trivial estimator that always guesses $0$ .

preprint2022arXiv

Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

In this work, we present new simple and optimal algorithms for solving the variational inequality (VI) problem for $p^{th}$ -order smooth, monotone operators -- a problem that generalizes convex optimization and saddle-point problems. Recent works (Bullins and Lai (2020), Lin and Jordan (2021), Jiang and Mokhtari (2022)) present methods that achieve a rate of $\tilde{O}(ε^{-2/(p+1)})$ for $p\geq 1$ , extending results by (Nemirovski (2004)) and (Monteiro and Svaiter (2012)) for $p=1,2$ . A drawback to these approaches, however, is their reliance on a line search scheme. We provide the first $p^{\textrm{th}}$ -order method that achieves a rate of $O(ε^{-2/(p+1)}).$ Our method does not rely on a line search routine, thereby improving upon previous rates by a logarithmic factor. Building on the Mirror Prox method of Nemirovski (2004), our algorithm works even in the constrained, non-Euclidean setting. Furthermore, we prove the optimality of our algorithm by constructing matching lower bounds. These are the first lower bounds for smooth MVIs beyond convex optimization for $p > 1$ . This establishes a separation between solving smooth MVIs and smooth convex optimization, and settles the oracle complexity of solving $p^{\textrm{th}}$ -order smooth MVIs.

preprint2021arXiv

Almost-linear-time Weighted $\ell_p$ -norm Solvers in Slightly Dense Graphs via Sparsification

We give almost-linear-time algorithms for constructing sparsifiers with $n\ poly(\log n)$ edges that approximately preserve weighted $(\ell^{2}_2 + \ell^{p}_p)$ flow or voltage objectives on graphs. For flow objectives, this is the first sparsifier construction for such mixed objectives beyond unit $\ell_p$ weights, and is based on expander decompositions. For voltage objectives, we give the first sparsifier construction for these objectives, which we build using graph spanners and leverage score sampling. Together with the iterative refinement framework of [Adil et al, SODA 2019], and a new multiplicative-weights based constant-approximation algorithm for mixed-objective flows or voltages, we show how to find $(1+2^{-\text{poly}(\log n)})$ approximations for weighted $\ell_p$ -norm minimizing flows or voltages in $p(m^{1+o(1)} + n^{4/3 + o(1)})$ time for $p=ω(1),$ which is almost-linear for graphs that are slightly dense ( $m \ge n^{4/3 + o(1)}$ ).

preprint2020arXiv

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

Linear regression in $\ell_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 $\ell_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 is guaranteed to converge rapidly 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 $(1+\varepsilon)$ -approximate solution in $O(p^{3.5} m^{\frac{p-2}{2(p-1)}} \log \frac{m}{\varepsilon}) \le O_p(\sqrt{m} \log \frac{m}{\varepsilon} )$ 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.

preprint2020arXiv

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

We present faster high-accuracy algorithms for computing $\ell_p$ -norm minimizing flows. On a graph with $m$ edges, our algorithm can compute a $(1+1/\text{poly}(m))$ -approximate unweighted $\ell_p$ -norm minimizing flow with $pm^{1+\frac{1}{p-1}+o(1)}$ operations, for any $p \ge 2,$ giving the best bound for all $p\gtrsim 5.24.$ Combined with the algorithm from the work of Adil et al. (SODA '19), we can now compute such flows for any $2\le p\le 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\simδ^{-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 $\ell_{p}$ -norm regression problems for large $p.$ Our algorithm makes $pm^{\frac{1}{3}+o(1)}\log^2(1/\varepsilon)$ calls to a linear solver. This gives the first high-accuracy algorithm for computing weighted $\ell_{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 $\ell_p$ -norm problems introduced by Adil et al., are interreducible for different values of $p.$ No such reduction is known for standard $\ell_p$ -norm problems.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Deeksha Adil

Research overview

Is this your work?

6 publications

Convex optimization with $p$ -norm oracles

On efficient robust regression with subquadratic samples

Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

Almost-linear-time Weighted $\ell_p$ -norm Solvers in Slightly Dense Graphs via Sparsification

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

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

See the researcher in context

Building this map preview

Deeksha Adil

Research overview

Is this your work?

6 publications

Convex optimization with ppp-norm oracles

On efficient robust regression with subquadratic samples

Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

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

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

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

See the researcher in context

Building this map preview

Convex optimization with $p$ -norm oracles

Almost-linear-time Weighted $\ell_p$ -norm Solvers in Slightly Dense Graphs via Sparsification