4 citations · 10 across the 12 of their papers we have counts for
16 papers
Awakening of the Buddha: Subspace Learning During Population-Loss Plateaus
Akash Kumar
Population loss can remain nearly constant while a neural network learns a substantially more predictive representation. We establish this separation for two-layer ReLU and leaky-R…
Can Representation Learning Decouple from Loss Minimization? Polar Updates Have an Answer
Akash Kumar
Does representation learning stop when the training loss stops improving? We study this question for matrix Muon, whose polar-normalised updates have a step length set by the gradi…
Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
Akash Kumar, Abhiruk Lahiri, C. Seshadhri
Consider a bounded-degree graph that belongs to a minor-closed family (such as planar graphs). Such a graph has a hyperfinite decomposition, wherein, for a sufficiently small $…
A Gap Between Decision Trees and Neural Networks
Akash Kumar
We study when geometric simplicity of decision boundaries, used here as a notion of interpretability, can conflict with accurate approximation of axis-aligned decision trees by sha…
Dictionary Learning: The Complexity of Learning Sparse Superposed Features with Feedback
Akash Kumar
The success of deep networks is crucially attributed to their ability to capture latent features within a representation space. In this work, we investigate whether the underlying…
Learning Smooth Distance Functions via Queries
Akash Kumar, Sanjoy Dasgupta
In this work, we investigate the problem of learning distance functions within the query-based learning framework, where a learner is able to pose triplet queries of the form: ``Is…
Robust Empirical Risk Minimization with Tolerance
Robi Bhattacharjee, Max Hopkins, Akash Kumar +2
Developing simple, sample-efficient learning algorithms for robust classification is a pressing issue in today's tech-dominated world, and current theoretical techniques requiring…
The complexity of testing all properties of planar graphs, and the role of isomorphism
Sabyasachi Basu, Akash Kumar, C. Seshadhri
Consider property testing on bounded degree graphs and let denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all prop…
Random walks and forbidden minors III: poly(d/ε)-time partition oracles for minor-free graph classes
Akash Kumar, C. Seshadhri, Andrew Stolman
Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs i…
The Teaching Dimension of Kernel Perceptron
Akash Kumar, Hanqi Zhang, Adish Singla +1
Algorithmic machine teaching has been studied under the linear setting where exact teaching is possible. However, little is known for teaching nonlinear learners. Here, we establis…
Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries
Akash Kumar, Adish Singla, Yisong Yue +1
We examine the task of locating a target region among those induced by intersections of halfspaces in . This generic task connects to fundamental machine learning…
Random walks and forbidden minors II: A -query tester for minor-closed properties of bounded-degree graphs
Akash Kumar, C. Seshadhri, Andrew Stolman
Let be a graph with vertices and maximum degree . Fix some minor-closed property (such as planarity). We say that is -far from $\mathcal{P…
Finding forbidden minors in sublinear time: a -query one-sided tester for minor closed properties on bounded degree graphs
Akash Kumar, C. Seshadhri, Andrew Stolman
Let be an undirected, bounded degree graph with vertices. Fix a finite graph , and suppose one must remove edges from to make it -minor free (for…
Flipping out with many flips: hardness of testing k-monotonicity
Elena Grigorescu, Akash Kumar, Karl Wimmer
A function f : {0, 1}^n -> {0, 1} is said to be k-monotone if it flips between 0 and 1 at most k times on every ascending chain. Such functions represent a natural generalization o…
Testing -Monotonicity
Clément L. Canonne, Elena Grigorescu, Siyao Guo +2
A Boolean -monotone function defined over a finite poset domain alternates between the values and at most times on any ascending chain in . Ther…
Approximation Algorithms for Digraph Width Parameters
Shiva Kintali, Nishad Kothari, Akash Kumar
Several problems that are NP-hard on general graphs are efficiently solvable on graphs with bounded treewidth. Efforts have been made to generalize treewidth and the related notion…